PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Power of Differentiable Learning versus PAC and SQ Learning

Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, Nathan Srebro

arXiv:2108.04190v2cs.LGstat.ML

TL;DR

The paper asks what learning problems mini-batch SGD and full-batch GD can solve, and whether their power depends on batch size, sample size, or gradient precision. It relates these methods to PAC and SQ learning through bSQ simulations and shows that fine precision enables PAC-level sample-based simulation, whereas sufficiently coarse precision limits SGD to SQ-level power.

  • Problem

    The paper investigates the learning power of differentiable gradient methods relative to PAC and SQ learning, beyond treating them simply as empirical-risk minimization.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces mini-batch statistical queries and constructs differentiable models whose gradients simulate query answers, relating bSGD and fbGD to PAC and SQ methods.

    Source: §3 · pp. 7–8

  • Results

    Fine precision lets bSGD and fbGD simulate sample-based learning, while bSGD always simulates SQ and becomes no more powerful than SQ when b = ω(log(n)/ρ^2).

    Source: §1 · p. 2

  • Takeaways & Limitations

    Differentiable learning can range from SQ-level to PAC-level power, with the boundary governed by gradient precision relative to batch or sample size.

    Source: §1 · p. 2, §7 · p. 15

    The power of bSGD remains unresolved in the intermediate regime between 1/ρ and log(n)/ρ^2, and the corresponding fbGD boundary is not as tight.

    Source: §7 · p. 15, §6 · p. 15

Abstract

from arXiv · show

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 $\rho$ 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 \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$. 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 $\rho$ is exponentially small), SGD and GD can both simulate PAC learning regardless of the mini-batch size. On the other hand, when $b \rho^2$ is large enough, the power of SGD is equivalent to that of SQ learning.

1 Introduction

The paper asks what differentiable learning can learn beyond empirical-risk-minimization intuitions, especially as batch size and gradient precision vary. It shows that bSGD and fbGD range from SQ-level power to PAC-level power depending on precision, while introducing bSQ as an intermediate simulation framework.

Motivation

  • Differentiable learning is treated as distinct from ERM because gradient descent need not find global minimizers, while implicit bias can select particular solutions among many empirical-risk minimizers.Even minimizing a neural network's empirical risk with two hidden units is NP-hard.Source: §1 · pp. 1–2

Main results

  • bSGD is always at least as powerful as SQ learning, but with b = ω(log(n)/ρ^2) it is no more powerful than SQ.With fine precision satisfying b < 1/(8ρ), bSGD can instead simulate any sample-based method and is as powerful as PAC learning.Source: §1 · p. 2
  • With fine enough precision, even full-batch GD can simulate any sample-based method based on m samples, including when ρ < 1/(8m).Thus full-batch gradients can match PAC-level sample-based learning despite having no stochasticity in updates.Source: §1 · p. 2

Precision dependence

  • With ρ = 2^-n, bSGD and fbGD can simulate arbitrary sample-based methods for any polynomial mini-batch size, and exact computation corresponds to ρ = 0.The required precision grows only logarithmically in the mini-batch or sample size when expressed as bits of precision.Source: §1 · pp. 2–3

Limitations

  • Low precision makes large batches restrictive: arbitrary sample-based simulation is impossible for fbGD and for bSGD with b = ω(log(n)/ρ^2).The paper precisely characterizes bSGD except for the intermediate regime between 1/ρ and log(n)/ρ^2.Source: §1 · p. 3

Computational scope

  • The analysis covers computationally bounded and unbounded settings by implementing polynomial-time PAC or SQ computations as circuits and then neural-network subnetworks.Arbitrary differentiable models handle unbounded methods, while poly-sized neural networks handle poly-time methods.Source: §1 · p. 3

Proof strategy

  • The paper introduces bSQ, which answers statistical queries from independently sampled mini-batches and enables sample extraction for relating bSGD to PAC and SQ learning.bSQ methods are simulated by constructing models whose parameter derivatives contain query answers.Source: §1 · p. 3

2 Learning Paradigms

The paper formalizes differentiable models, approximate-gradient bSGD and fbGD, PAC and SQ methods, and a simulation-based notion of relative learning power. Its framework explicitly models clipping, rounding, randomness, batches, samples, and error guarantees.

Differentiable models

  • A differentiable model is a parameterized mapping f_w(x) with gradients existing for almost every parameter vector, and neural networks are a notable special case.Neural networks use edge weights as parameters and an activation function over a directed acyclic computation graph.Source: §2 · p. 3

Mini-batch SGD

  • bSGD independently samples batches of size b each iteration and updates parameters using ρ-approximately rounded, clipped empirical gradients.Gradient estimates lie on the ρ-grid and differ from the clipped batch gradient by at most 3ρ/4 in infinity norm.Source: §2 · p. 4

Precision and rounding

  • Precision is represented by rounding to multiples of ρ, with d = -log ρ bits of precision, while clipping prevents large gradients from bypassing the precision limit.The simulation constructions keep gradient coordinates within [-1,1], so clipping has no effect in those constructions.Source: §2 · p. 4

Full-batch GD

  • fbGD reuses one empirical sample set of size m at every iteration, whereas bSGD consumes fresh mini-batches and can use Tb samples overall.Both methods allow approximate gradients and evaluate final predictors by population loss under worst-case valid gradient estimates.Source: §2 · p. 5

PAC and SQ learning

  • A PAC method receives m samples and randomness, while an SQ method receives approximate expectations of adaptively chosen bounded queries within tolerance τ.The two paradigms are compared through their achieved population error on every source distribution.Source: §2 · p. 5

Comparing learning power

  • The relation C′ ⪯_δ C means that every method in C has a simulator in C′ whose error is at most δ larger, so C′ is at least as powerful as C.These simulation relations compose, adding their error tolerances.Source: §2 · p. 5

3 Main Results : bSGD versus PAC and SQ

The main results characterize when mini-batch SGD can match PAC learning and when its power is limited to SQ learning, based on the relationship between batch size and gradient precision. They establish tight PAC and SQ regimes, with an intermediate regime not fully characterized.

PAC versus bSGD

  • For all mini-batch sizes, bSGD can simulate PAC learning when ρ < 1/(8b), and the reduction preserves polynomial parameter relationships.Theorem 1a gives T′ = O(mn/δ), with model size and rounds polynomially related to the PAC method.Source: §3 · p. 6
  • PAC can simulate bSGD for arbitrary b, ρ, and polynomially bounded model and iteration parameters, making the fine-precision regime equivalent to PAC.This reverse simulation follows because bSGD is defined using samples.Source: §3 · p. 6

SQ versus bSGD

  • When bρ² exceeds a logarithmic threshold, bSGD cannot go beyond SQ for polynomial-size models and polynomially many iterations.Theorem 1c states the threshold as bρ² > C log(Tp/δ), while the asymptotic formulation is bρ² = ω(log n).Source: §3 · p. 6
  • Regardless of mini-batch size, bSGD can simulate every SQ method, so the high-precision boundary yields equivalence to SQ.The construction uses a differentiable model whose parameter derivatives encode statistical-query answers.Source: §3 · p. 6

Regime summary

  • The results are tight when b < 1/(8ρ) for the PAC side and when b > ω((log n)/ρ²) for the SQ side.The intermediate regime between these thresholds is not precisely resolved by the stated results.Source: §3 · p. 7

Scope and implementation

  • The reductions extend from arbitrary differentiable models to neural networks using a stage-wise ramp activation, while realizable-learning corollaries can also be generalized to agnostic and weak learning.The neural-network construction uses a piecewise-linear activation with a central flat region to reduce weight drift from rounding errors.Source: §3 · pp. 7–8

4 The Mini-Batch Statistical Query Model

The bSQ model answers statistical queries using empirical averages over mini-batches, separating sampling error from additional arbitrary precision error. Its power ranges from PAC-equivalent to SQ-equivalent depending on the relationship between batch size and tolerance.

Model definition

  • bSQ answers concurrent vector-valued queries using empirical averages over independently sampled mini-batches, with additional arbitrary error τ.This explicitly separates sampling error from precision error in statistical-query responses.Source: §4 · pp. 8–9

Relation to prior models

  • The model differs from Honest-SQ because bSQ permits arbitrary error and concurrent queries on one mini-batch, whereas Honest-SQ uses one independent single-bit query per batch.The paper attributes the different conclusions to these modeling differences.Source: §4 · p. 9

PAC equivalence

  • When τ < 1/(2b), bSQ can recover samples and simulate any sample-based method, including PAC learning.SAMPLE-EXTRACT recovers one sample in O(n) expected queries, so O(mn/δ) queries recover m samples with failure probability at most δ.Source: §4 · p. 9
  • Sample-based learning can simulate bSQ using kb samples, establishing equivalence between bSQ and PAC under the corresponding sample accounting.The computationally bounded version preserves polynomial runtime up to the stated transformation.Source: §4 · p. 10

SQ equivalence

  • When bτ^2 > C log(kp/δ), bSQ is no more powerful than standard SQ because sampling deviations are smaller than the tolerance.Population query answers become valid mini-batch responses uniformly across parallel queries and rounds.Source: §4 · pp. 10–11

SQ simulation

  • Regardless of batch size, bSQ can simulate SQ by averaging responses to the same query across multiple mini-batches.Repeated averaging reduces sampling error while retaining the arbitrary error tolerance.Source: §4 · p. 11

5 Simulating Mini-Batch Statistical Queries with Differentiable Learning

The paper simulates mini-batch statistical queries with differentiable models by encoding query responses in gradients. This yields differentiable and neural-network constructions that inherit the PAC and SQ simulation results of bSQ.

Simulation construction

  • A gradient computation can encode a bSQ response, allowing bSGD on a constructed differentiable model to simulate the query method.The construction can use arbitrary differentiable models and can be implemented with neural networks when the query mappings are computationally bounded.Source: §5 · pp. 11–12

Alternating Query Methods

  • Alternating bSQ methods restrict each round to a query involving only one label, enabling the differentiable simulation construction.Odd rounds use 1-queries and even rounds use 0-queries.Source: §5 · p. 11

PAC simulation

  • PAC learning is simulated by alternating bSQ when τ < 1/(2b), with polynomial overhead in dimension, sample size, runtime, and failure parameters.The alternating-query reduction uses k′ = 20m(n + 1)/δ and preserves computational boundedness with polynomial overhead.Source: §5 · p. 11

SQ simulation

  • SQ learning is likewise reduced to alternating bSQ with polynomial computational overhead, including the stated transformation for computationally bounded methods.The reduction applies the SQ-to-bSQ0/1 lemma and preserves the relevant transformed parameters.Source: §5 · pp. 11–12

Single-query mechanism

  • A single bSGD step stores a query answer in a parameter because the corresponding gradient equals the empirical query value up to precision ρ.The full construction reserves parameters for successive rounds and uses piecewise-linear dependencies to control which parameter is updated.Source: §5 · p. 12

Neural-network implementation

  • For computationally bounded methods, the differentiable construction can be realized as a neural network whose subnetworks compute the mapping from prior responses to new queries.An alternate construction keeps computation subnetworks effectively fixed while designated edges store query results.Source: §5 · pp. 12–13

Reverse direction

  • The reverse simulation implements bSGD directly with bSQ, completing the connection between differentiable learning and the statistical-query model.This direction is used with the bSQ-to-PAC and bSQ-to-SQ results to establish the main comparisons.Source: §5 · p. 13

6 Full-Batch Gradient Descent: fbGD versus PAC and SQ

Full-batch Gradient Descent can simulate PAC learning with sufficiently fine precision, while sufficiently large samples relative to precision place it within SQ learning; the exact boundary is less tight than for bSGD.

6 Full-Batch Gradient Descent: fbGD versus PAC and SQ

  • With ρ < 1/(8m), fbGD can simulate any PAC method using m samples, and therefore has PAC-level learning power.The construction uses T′ = O(mn) iterations and polynomial model size for general PAC simulation.Source: §6 · pp. 13–14
  • fbGD can simulate SQ learning, and when mρ^2 exceeds C(Tp log(1/ρ) + log(1/δ)), it cannot be more powerful than SQ under the stated conditions.The reduction accounts for the adaptive queries generated across T iterations and p parameters.Source: §6 · p. 14
  • The resulting polynomial-precision regime yields fbGD = PAC and fbGDNN = PACTM when parameters may depend polynomially on n.This establishes PAC equivalence for full-batch gradient descent and its neural-network variant in the paper’s parameterized setting.Source: §6 · p. 14
  • Unlike bSGD, fbGD precision depends on the total sample size m, so fixed precision can simulate only methods using at most 1/(8ρ) samples.bSGD instead relates the required precision to its mini-batch size, allowing more samples through repeated iterations.Source: §6 · pp. 14–15
  • The SQ boundary for fbGD is not tight because the sufficient SQ condition depends polynomially on model size and iteration count, leaving constant-precision simulation open.The paper explicitly leaves open whether fbGD with constant ρ and polynomial p,T can simulate every sample-based method.Source: §6 · p. 15
  • The same fixed training set can support random mini-batch gradient estimates, but analogous results for this hybrid setting are stated without details.This setting differs from population bSGD because each iteration samples with replacement from one fixed training set.Source: §6 · p. 15

7 Summary and Discussion

The paper nearly characterizes mini-batch SGD through SQ and PAC, and shows that sufficiently precise full-batch GD can also reach PAC power. It emphasizes that these constructions use unrealistic initialization and therefore do not directly explain practical deep learning.

7 Summary and Discussion

  • The paper gives an almost tight characterization of mini-batch SGD: it always reaches SQ power, reaches PAC power with fine precision, and leaves an intermediate gap.The unresolved region is between mini-batch sizes 1/ρ and log(n)/ρ^2.Source: §7 · p. 15
  • With sufficient polynomial precision, full-batch Gradient Descent on empirical loss can simulate PAC learning.This extends the PAC-simulation result beyond stochastic updates.Source: §7 · p. 15
  • The simulations require carefully constructed networks and extremely particular initialization, so they do not imply that a particular practical neural network can learn every PAC- or SQ-learnable function.Such unrestricted computational power would contradict known impossibility results under mild cryptographic assumptions.Source: §7 · p. 15
  • The authors identify restricted architectures or initializations as a direction for understanding which problems actual deep learning can learn.They point to evidence that restrictions such as near-zero initialization outputs or architectural regularity can reduce learning power.Source: §7 · pp. 15–16

A Reductions between bSQ, fbSQ and SQ, PAC

  • The reduction framework relates bSQ and fbSQ to SQ and PAC through sample extraction and batch-query simulations.The appendix section states that it proves analogous reductions for fixed-batch statistical queries.Source: A Reductions between bSQ, fbSQ and SQ,… · p. 19

A.1 bSQ versus PAC

The bSQ appendix establishes reductions between batch statistical queries and PAC learning, including a procedure that extracts samples from independent mini-batch responses.

A.1 bSQ versus PAC

  • A bSQ method can simulate PAC learning by extracting samples from batches when bτ < 1/2, using O(m(n+1)/δ) rounds.The construction uses SAMPLE-EXTRACT and returns the PAC algorithm’s output after extracting m samples, with error increase at most δ.Source: §A.1 · pp. 19–20
  • SAMPLE-EXTRACT samples the bits of z sequentially from conditional distributions, thereby producing a sample from D in at most 10(n+1) expected steps.Its correctness follows by induction over prefixes, while the runtime analysis tracks the probability of observing each prefix in a batch.Source: §A.1 · pp. 19–20
  • The extraction procedure’s expected runtime is controlled by prefix probability: rare prefixes require at most 5/(bps) expected remaining steps, while common prefixes require at most 10(n+1−|s|).The analysis separates prefixes with bps ≤ 1/5 from those with bps > 1/5.Source: §A.1 · pp. 19–20
  • PAC learning can simulate bSQ by computing each query’s empirical average from b fresh samples per round, so kb samples suffice for k rounds.The runtime remains polynomially related and the random-bit count is preserved.Source: §A.1 · p. 20
  • The same PAC-to-bSQ reduction can be restricted to Boolean-valued queries with a factor-two increase in rounds.After the first query fixes y, alternating rounds implement the remaining extraction queries.Source: §A.1 · p. 20

A.2 fbSQ versus PAC

The fbSQ appendix shows that fixed-batch statistical queries and PAC learning simulate one another, with exact sample recovery possible when query tolerance is sufficiently small.

A.2 fbSQ versus PAC

  • When τ < 1/(2m), fbSQ can simulate PAC learning on m samples using m(n+1) queries.The fixed batch is recursively partitioned by prefixes until every sample is recovered.Source: §A.2 · p. 21
  • The recovery procedure uses one query to count samples extending each prefix with bit 1, then obtains the complementary count and recurses.Rounding empirical averages to multiples of 1/m recovers exact prefix counts.Source: §A.2 · p. 21
  • The fixed-batch reduction always extracts all m samples within m(n+1) queries, so it incurs no additional error.This contrasts with the independent-batch construction, whose bounded-round extraction uses a failure probability parameter.Source: §A.2 · p. 21
  • PAC can simulate fbSQ by answering every query with an empirical average over the same m samples, preserving the random-bit count.The resulting runtime remains polynomially related to the original method.Source: §A.2 · p. 21
  • A Boolean-query version of the PAC-to-fbSQ reduction uses k = 2m(n+1) rounds under τ < 1/(2m).The appendix obtains this by modifying the PAC-to-fbSQ construction analogously to the bSQ Boolean reduction.Source: §A.2 · p. 21

A.3 bSQ versus SQ

The section establishes equivalences between batch statistical-query learning and ordinary SQ learning under precision and sample-size conditions, for both mini-batch and full-batch settings.

A.3 bSQ versus SQ

  • When bτ^2 is sufficiently large, bSQ can be simulated by SQ with comparable error and polynomial runtime overhead.The sufficient condition is bτ^2 > C log(kp/δ).Source: §A.3 · p. 22
  • SQ can simulate bSQ by repeating each query and averaging responses, with polynomial overhead in the query count, precision, and runtime.The construction uses k′ = kq, τ′ = τ/2, and concentration across repeated mini-batches.Source: §A.3 · p. 22
  • SQ methods reduce to bSQ0/1 methods using paired 0- and 1-queries, with parameters (2k, τ/2, r) and polynomial runtime TIME′ = poly(TIME, k, 1/τ).Source: §A.3 · p. 23

A.4 fbSQ versus SQ

  • For full-batch queries, the sample requirement scales linearly with the number of adaptive queries because a naive union bound is insufficient.The section gives conditions of the form mτ^2 > C(k log(1/τ) + log(1/δ)) for SQ-to-fbSQ simulation.Source: §A.4 · pp. 23–24
  • fbSQ and SQ are reducible to one another under analogous precision and sample-size conditions, and fbSQ0/1 admits the corresponding simulation.The reductions account for adaptive transcripts by discretizing possible responses and union-bounding over the resulting query set.Source: §A.4 · pp. 23–24

B Simulating bSQ with bSGD : Proof of Lemma 3a

The construction simulates an alternating bSQ0/1 method through bSGD on a differentiable model, storing query responses and controlling updates with smooth, precision-tolerant mechanisms.

B Simulating bSQ with bSGD : Proof of Lemma 3a

  • Any bSQ0/1 method can be simulated by bSGD on a constructed differentiable model using the same mini-batches and valid query responses.The model is initialized so that T bSGD steps produce a predictor returned by the original method.Source: B Simulating bSQ with bSGD : Proof of… · pp. 24, 26
  • A single bSGD step can implement either a 0-query or a 1-query, with update error controlled by gradient precision ρ.The construction yields κ(1) ≥ ε − ρ in both cases.Source: B Simulating bSQ with bSGD : Proof of… · p. 25
  • Smooth approximations round previous query responses while preserving the original query values near the relevant discretized points.Lemma 9 supplies differentiable replacements that agree with rounded queries within the required neighborhood.Source: B Simulating bSQ with bSGD : Proof of… · p. 26
  • The model uses stored response parameters and clock parameters so each SGD iteration updates only the intended query state.The induction maintains zero future states, preserved past states, and clock values separated by at least ρ.Source: B Simulating bSQ with bSGD : Proof of… · p. 27

B.1 From Arbitrary Differentiable Models to Neural Networks.

  • For computationally bounded methods, the differentiable construction can be implemented as a neural network using circuit simulation and robust clock mechanisms.The section notes that large weights with small steps or gradient clipping can make the clock mechanism robust, while referring to a later direct construction for full details.Source: §B.1 · p. 28

NN : Proof of Lemma 3b

The neural-network construction directly emulates bounded bSQ0/1 methods by combining noise-tolerant circuit computation with trainable query and memory subgraphs.

NN : Proof of Lemma 3b

  • A direct neural-network construction simulates a bounded-runtime bSQ0/1 method through gradient descent updates.The construction uses specialized query subgraphs and a computation component to reproduce the method’s queries and outputs.Source: NN : Proof of Lemma 3b · p. 29
  • Noise-tolerant circuit emulation computes Boolean functions while keeping derivatives through the added computation vertices at zero.Flat activation regions prevent unwanted updates to the computation circuitry and its incoming edges.Source: NN : Proof of Lemma 3b · p. 30
  • The network encodes binary query information in trainable edge weights and reads those values through auxiliary vertices.The query subgraph is designed so selected gradients change an edge according to the current batch query while binary outputs expose its stored value.Source: NN : Proof of Lemma 3b · pp. 29–30

1. An edge of weight 1/12 from v0 to v1

The query-memory subgraph uses flat activation regions to remain unchanged except when deliberately activated, allowing gradient updates to encode batch-query statistics in edge weights.

1. An edge of weight 1/12 from v0 to v1

  • The query subgraph is inactive when its control vertex outputs 2 and becomes trainable when that vertex outputs 0.This switches the subgraph between preserving its weights and updating an encoded query value.Source: §1 · p. 31
  • Under the stated assumptions, only the timestep containing an activated query changes the subgraph’s weights.All later steps return the relevant vertices to flat activation regions, forcing subsequent gradients to zero.Source: §1 · pp. 31–32
  • The encoded edge weight tracks the fraction of activated samples on which the network output disagrees with the sample output, up to a precision-dependent error.The binary readout is within 3/2 of the corresponding count after normalization by bτ, plus the activated-sample fraction term.Source: §1 · p. 32
  • Binary auxiliary vertices recover the stored query value from the updated edge weight using a logarithmic number of bits.The construction uses k = ⌈log2(1/τ)⌉ binary digits to represent the encoded value.Source: §1 · p. 32
  • Multiple query subgraphs, computation circuitry, and output-control vertices together emulate the full bounded bSQ0/1 algorithm across training steps.The computation component selects queries and controls activations, while secondary controls cancel query-subgraph effects on the output.Source: §1 · p. 33

D bSGD versus PAC and SQ : Proofs of Theorems 1a to 1d

The proofs establish simulation relationships for mini-batch SGD, including simulation by PAC learning and reduction of rounded gradients to statistical queries. They combine lemmas controlling precision, batch size, iterations, and representation parameters to prove Theorems 1a–1d.

E fbGD versus PAC and SQ : Proofs of Theorems 3a to 3d

The proofs establish analogous relationships for full-batch gradient descent, including PAC simulation and reductions between gradient descent and statistical-query procedures. The results follow by combining lemmas under precision, sample-size, and runtime conditions.

Loading 2108.04190v2…