Prediction, Generalization, Complexity: Revisiting the Classical View from Statistics Part 1 @SimonsInstituteTOC

Simons Institute | Prediction, Generalization, Complexity: Revisiting the Classical View from Statistics Part 1 @SimonsInstituteTOC | Uploaded 1 week ago | Updated 18 hours ago
Ryan Tibshirani (University of California, Berkeley)
https://simons.berkeley.edu/talks/ryan-tibshirani-university-california-berkeley-2024-08-28
Modern Paradigms in Generalization Boot Camp

Classical statistical decision theory treats the relationship between prediction error, generalization gap (which the statistics literature calls optimism), and model complexity from a point of view that treats the covariates X as fixed, nonrandom values. This fixed-X perspective delivers a number of insights, many of which are well-known to statisticians, but perhaps less well-known to researchers in machine learning. This talk reviews the classical statistics literature, and then emphasizes the ways in which this fixed-X theory is insufficient to the explain prediction error, generalization gap, and model complexity in a random-X setting---which is the predominant view in machine learning---especially as a predictive model becomes flexible enough to interpolate the training data. Finally, we show how to reinterpret some of the fixed-X classical statistics concepts in order to extend them to a random-X setting.

From Simulated Subjectivity to Collective Consciousness in Large Language Models

Re-thinking Transformers: Searching for Efficient Linear Layers over a Continuous Space of...

Specification-guided Reinforcement learning

$Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs Sepehr Assadi (University of Waterloo) https://simons.berkeley.edu/talks/sepehr-assadi-university-waterloo-2024-07-30 Sublinear Graph Simplification We follow the recent breakthrough of Behnezhad and Ghafari [FOCS24] in designing fully dynamic algorithms for the maximum matching problem whose runtimes is parameterized by the density of the so-called Ordered Ruzsa-Szemeredi (ORS) Graphs. These are graphs whose edges can be partitioned into an ordered set of linear-size matchings such that each matching is induced among the edges of the matchings that appear after it in this ordering. Behnezhad and Ghafari developed an algorithm for (1+eps)-approximation of matchings for any constant eps with update time roughly sqrt{n * ORS(n)}, where ORS(n) denotes the largest number of matchings possible in an n-vertex ORS graph. The parameter ORS(n) is still quite poorly understood and we effectively only know that it is between n^{o(1)} and o(n). Under the plausible scenario that the current lower bounds for ORS(n) are almost optimal, the BG algorithm will run in n^{1/2+o(1)} update time, which will be a major achievement in this area. In this talk, we will cover our recent improvements to the BG-algorithm that improve the update time to only n^{o(1)} * ORS(n). This means that under the plausible scenario above, this algorithm simply runs in n^{o(1)} update time. In its current stage also, this fully reduces the algorithmic problem of designing dynamic matching algorithms to a purely combinatorial problem of upper bounding ORS(n) with no algorithmic considerations.$

Error Embraced: Making Trustworthy Scientific Decisions with Imperfect Predictions

Stochastic Minimum Vertex Cover with Few Queries: a 3/2-approximation

Understanding the expressive power of transformers through the lens of formal language theory

Controller Synthesis Beyond the Worst Case

Social Behavior Prediction from Video Observations

$Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier Jane Lange (Massachusetts Institute of Technology) https://simons.berkeley.edu/talks/jane-lange-massachusetts-institute-technology-2024-08-02 Sublinear Graph Simplification We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given 2^Õ(sqrt(n)/ε) uniformly random examples of an unknown function f:{±1}^n→{±1}, our algorithm outputs a hypothesis g:{±1}^n→{±1} that is monotone and (opt+ε)-close to f, where opt is the distance from f to the closest monotone function. The running time of the algorithm (and consequently the size and evaluation time of the hypothesis) is also 2^Õ(sqrt(n)/ε), nearly matching the lower bound of Blais et al (RANDOM 15). We also give an algorithm for estimating up to additive error ε the distance of an unknown function f to monotone using a run-time of 2^Õ(sqrt(n)/ε). Previously, for both of these problems, sample-efficient algorithms were known, but these algorithms were not run-time efficient. Our work thus closes this gap in our knowledge between the run-time and sample complexity. This work builds upon the improper learning algorithm of Bshouty and Tamon (JACM 96) and the proper semiagnostic learning algorithm of Lange, Rubinfeld, and Vasilyan (FOCS 22), which obtains a non-monotone Boolean-valued hypothesis, then corrects it to monotone using query-efficient local computation algorithms on graphs. This black-box correction approach can achieve no error better than 2opt+ε information-theoretically; we bypass this barrier by a) augmenting the improper learner with a convex optimization step, and b) learning and correcting a real-valued function before rounding its values to Boolean. Our real-valued correction algorithm solves the poset sorting problem of [LRV22] for functions over general posets with non-Boolean labels.$