Seminar • Algorithms and Complexity • Estimating Euclidean Distance to Linearity

Please note: This seminar will take place in DC 1302 and online.

Andrej Bogdanov, Professor
School of Electrical Engineering and Computer Science, University of Ottawa

Learning a linear approximation of an unknown function is the basis of many algorithms. Is it possible to calculate the quality of the approximation before the effort is spent in learning it?  We study this question for real-valued functions f over the Boolean cube with respect to query complexity.

We show that, given oracle access to f, an ϵ-additive approximation of the squared Euclidean distance to its closest linear function can be computed with O(log^3(1/ϵ) · 1/ϵ^2) queries (assuming f has bounded 4-norm). This query complexity is independent of the dimension and optimal up to the polylogarithmic factor. In contrast, learning a linear approximation requires query complexity that is linear in the dimension. We also obtain tight bounds for the sample complexity of estimating the distance to linearity.

The talk is based on joint work with Lorenzo Taschin.

To attend this seminar in person, please go to DC 1302. You can also attend virtually using Zoom.