On the Power of Differentiable Learning versus PAC and SQ Learning

2021/08/09 by Emmanuel Abbé, Pritish Kamath, Abbe, Emmanuel +7 · 4 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2108.04190

openalex publication_date 2021/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the power of learning via mini-batch stochastic gradient descent (SGD) on the population loss, and batch Gradient Descent (GD) on the empirical loss, of a differentiable model or neural network, and ask what learning problems can be learnt using these paradigms. We show that SGD and GD can always simulate learning with statistical queries (SQ), but their ability to go beyond that depends on the precision ρ of the gradient calculations relative to the minibatch size b (for SGD) and sample size m (for GD). With fine enough precision relative to minibatch size, namely when b ρ 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. Similarly, with fine enough precision relative to the sample size m, GD can also simulate any sample-based learning algorithm based on m samples. In particular, with polynomially many bits of precision (i.e. when ρ is exponentially small), SGD and GD can both simulate PAC learning regardless of the mini-batch size. On the other hand, when b ρ² is large enough, the power of SGD is equivalent to that of SQ learning.

Citations

• Noise-tolerant learning, the parity problem, and the statistical query model
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a\n Fixed Learning Rate
• Computational Separation Between Convolutional and Fully-Connected Networks
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels

Cited by

• Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training
• To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models
• LLM-ERM: Sample-Efficient Program Learning via LLM-Guided Search
• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

Related

• On the Generalization Benefit of Noise in Stochastic Gradient Descent
• A Bayesian Perspective on Generalization and Stochastic Gradient Descent
• Three Factors Influencing Minima in SGD
• The Impact of the Mini-batch Size on the Variance of Gradients in Stochastic Gradient Descent
• Special Properties of Gradient Descent with Large Learning Rates