Dimension-free discretization inequalities with applications to low-degree learning

Add to your list(s) Download to your calendar using vCal

• Joseph Slote (Caltech)
• Tuesday 26 November 2024, 13:00-14:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

What global properties of a function can we infer from local information? Bernstein-type discretization inequalities offer one answer: they show the supremum norm of a polynomial can be controlled by its absolute maximum on a finite subset of the domain. While such inequalities enjoy widespread use in analysis and approximation theory, their multivariate versions are often limited by dependence on dimension or the need for very many test points. In this talk we show how to get a dimension-free discretization with few test points. Along the way we develop a probabilistic technique for iterating one-dimensional inequalities without paying a dimension-dependent price.

As a consequence, we obtain Bohnenblust—Hille inequalities for functions on Z_k^n (or the hypergrid). Following the recent breakthrough of Eskenazis and Ivanisvili (STOC ‘22), these imply learning algorithms for low-degree functions with only log(n) random queries.

Based on a line of work with Lars Becker, Ohad Klein, Alexander Volberg, and Haonan Zhang.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Quantum Computing Seminar
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.