Timezone: »
Spotlight
On the Power of Differentiable Learning versus PAC and SQ Learning
Emmanuel Abbe · Pritish Kamath · Eran Malach · Colin Sandon · Nathan Srebro
@
We study the power of learning via mini-batch stochastic gradient descent (SGD) on the loss of a differentiable model or neural network, and ask what learning problems can be learnt using this paradigm. We show that SGD can always simulate learning with statistical queries (SQ), but its ability to go beyond that depends on the precision $\rho$ of the gradients and the minibatch size $b$. With fine enough precision relative to minibatch size, namely when $b \rho$ is small enough, SGD can go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for $b=1$. Moreover, with polynomially many bits of precision (i.e. when $\rho$ is exponentially small), SGD can simulate PAC learning regardless of the batch size. On the other hand, when $b \rho^2$ is large enough, the power of SGD is equivalent to that of SQ learning.
Author Information
Emmanuel Abbe (Swiss Federal Institute of Technology Lausanne)
Pritish Kamath (Toyota Technological Institute at Chicago)
Eran Malach (Hebrew University Jerusalem Israel)
Colin Sandon (MIT)
Nathan Srebro (University of Toronto)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: On the Power of Differentiable Learning versus PAC and SQ Learning »
Fri. Dec 10th 04:30 -- 06:00 PM Room
More from the Same Authors
-
2021 : Exponential Family Model-Based Reinforcement Learning via Score Matching »
Gene Li · Junbo Li · Nathan Srebro · Zhaoran Wang · Zhuoran Yang -
2023 Poster: Transformers learn through gradual rank increase »
Emmanuel Abbe · Samy Bengio · Enric Boix-Adsera · Etai Littwin · Joshua Susskind -
2023 Poster: Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs »
Emmanuel Abbe · Elisabetta Cornacchia · Aryo Lotfi -
2022 Poster: On the non-universality of deep learning: quantifying the cost of symmetry »
Emmanuel Abbe · Enric Boix-Adsera -
2022 Poster: Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures »
Emmanuel Abbe · Samy Bengio · Elisabetta Cornacchia · Jon Kleinberg · Aryo Lotfi · Maithra Raghu · Chiyuan Zhang -
2021 Oral: Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting »
Frederic Koehler · Lijia Zhou · Danica J. Sutherland · Nathan Srebro -
2021 Poster: Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting »
Frederic Koehler · Lijia Zhou · Danica J. Sutherland · Nathan Srebro -
2021 Poster: Representation Costs of Linear Neural Networks: Analysis and Design »
Zhen Dai · Mina Karzand · Nathan Srebro -
2021 Poster: An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning »
Blake Woodworth · Nathan Srebro -
2021 Poster: A Stochastic Newton Algorithm for Distributed Convex Optimization »
Brian Bullins · Kshitij Patel · Ohad Shamir · Nathan Srebro · Blake Woodworth -
2021 Poster: The staircase property: How hierarchical structure can guide deep learning »
Emmanuel Abbe · Enric Boix-Adsera · Matthew S Brennan · Guy Bresler · Dheeraj Nagaraj -
2020 Poster: On the universality of deep learning »
Emmanuel Abbe · Colin Sandon -
2018 Poster: Bayesian Inference of Temporal Task Specifications from Demonstrations »
Ankit Shah · Pritish Kamath · Julie A Shah · Shen Li -
2017 Poster: Decoupling "when to update" from "how to update" »
Eran Malach · Shai Shalev-Shwartz