PaperlayerView exact revision on arXiv

Source-linked AI summary

Poly-time universality and limitations of deep learning

Emmanuel Abbe, Colin Sandon

arXiv:2001.02992v1cs.LGcs.CCcs.ITmath.ITstat.ML

TL;DR

The paper asks which function distributions deep learning can learn in polynomial time and develops positive results for SGD alongside limitations for GD. It shows SGD can efficiently learn any polynomial-time learnable distribution, whereas GD with sufficiently large batches is restricted by low cross-predictability.

  • Problem

    The paper studies whether neural networks can control optimization error in polynomial time, beyond their known polynomial approximation and estimation guarantees.

    Source: §1.1 · p. 3

  • Method

    It analyzes SGD and GD training through universality and cross-predictability, using polynomial-size networks, polynomial-time initialization, and noisy gradient-based updates.

    Source: §1.2 · p. 4, §1.3 · p. 6, §2.2 · p. 9

  • Results

    SGD learns any function distribution learnable in polynomial time, while GD with large batches cannot learn distributions with sufficiently low cross-predictability under the stated polynomial constraints.

    Source: §1.3 · pp. 6–7, §6 · p. 52

  • Takeaways & Limitations

    SGD is an efficiently universal learning paradigm in this framework, separating it from full GD and statistical query algorithms.

    Source: §1.3 · p. 7

    The negative results are illustrated by variants of community detection that deep learning is expected not to solve, although depth-first search can learn the basic function in polynomial time.

    Source: §4.2 · p. 22

Abstract

from arXiv · show

The goal of this paper is to characterize function distributions that deep learning can or cannot learn in poly-time. A universality result is proved for SGD-based deep learning and a non-universality result is proved for GD-based deep learning; this also gives a separation between SGD-based deep learning and statistical query algorithms: (1) {\it Deep learning with SGD is efficiently universal.} Any function distribution that can be learned from samples in poly-time can also be learned by a poly-size neural net trained with SGD on a poly-time initialization with poly-steps, poly-rate and possibly poly-noise. Therefore deep learning provides a universal learning paradigm: it was known that the approximation and estimation errors could be controlled with poly-size neural nets, using ERM that is NP-hard; this new result shows that the optimization error can also be controlled with SGD in poly-time. The picture changes for GD with large enough batches: (2) {\it Result (1) does not hold for GD:} Neural nets of poly-size trained with GD (full gradients or large enough batches) on any initialization with poly-steps, poly-range and at least poly-noise cannot learn any function distribution that has super-polynomial {\it cross-predictability,} where the cross-predictability gives a measure of ``average'' function correlation -- relations and distinctions to the statistical dimension are discussed. In particular, GD with these constraints can learn efficiently monomials of degree $k$ if and only if $k$ is constant. Thus (1) and (2) point to an interesting contrast: SGD is universal even with some poly-noise while full GD or SQ algorithms are not (e.g., parities).

1 Introduction

The paper asks whether neural networks trained by gradient methods form a universal efficient learning framework, and contrasts SGD's universality with GD's limitations through cross-predictability.

1.1 Context and this paper

  • SGD training of polynomial-size neural networks can emulate any polynomial-time learner using a polynomial-time, function-agnostic initialization and polynomially many steps.The result addresses neural-network optimization error, complementing known polynomial approximation and estimation guarantees.Source: §1.1 · p. 3
  • Polynomial gradient and weight noise still permits the SGD universality result, separating SGD from full GD and statistical-query algorithms.The paper specifically notes that SGD can learn parities under some polynomial noise while GD and SQ methods fail in such settings.Source: §1.1 · pp. 3–4
  • Full GD or sufficiently large batches cannot efficiently learn certain low-cross-predictability distributions from arbitrary initializations under polynomial-step and polynomial-noise constraints.The negative result depends on batch size: universality holds at batch size one but breaks down for polynomially large batches.Source: §1.1 · p. 3

1.2 Problem formulations and learning objectives

  • The paper focuses on learning an unknown function distribution with a suitable initialization rather than learning one fixed function from a random initialization.For symmetric distributions such as parities, failure under the distribution also implies failure for a typical fixed function with random initialization.Source: §1.2 · p. 4
  • The learning objective is average-case prediction better than random guessing for a function drawn from a distribution, with failure of typical-weak learning implying failure of stronger requirements.The framework studies binary data and labels, sampled functions, descent-based training, and accuracy over both fresh data and the function distribution.Source: §1.2 · p. 5

1.3 Informal results: Cross-predictability, junk-flow and universality

  • Cross-predictability measures typical correlation among sampled functions, with batch size determining whether the data distribution or an empirical batch is used.Its value is maximal for a point-mass input distribution and equals 2^-n for purely random inputs and functions.Source: §1.3 · p. 6
  • The GD lower bound combines low cross-predictability with polynomial junk flow and inverse-noise factors, preventing useful progress when batches are sufficiently large.The mechanism is that descent updates correlations with perturbed network functions, which remain negligible for randomly drawn low-cross-predictability targets.Source: §1.3 · pp. 6–7
  • SGD remains universal because single-example updates avoid the averaging behavior that makes the GD bound effective, whereas sufficiently large batches restore the negative result.The paper also conjectures that rapidly decaying cross-predictability may obstruct learning from random initialization even without noise.Source: §1.3 · p. 7

2 Results

This section develops positive and negative results on the efficiency and limitations of neural-network learning with SGD, GD, and related constrained update schemes. It covers parity-specific separations, indistinguishability-based techniques, and an SGD emulation framework, emphasizing how sample-level information access shapes these outcomes.

2.1 Definitions and models

  • The paper models neural nets as weighted directed acyclic graphs and defines learning through accuracy over function and input distributions, distinguishing sample-based SGD from expected-gradient GD.GD updates use the exact expectation over inputs, whereas SGD updates sequentially from labeled samples; efficient learnability requires polynomial time and, for sample-based algorithms, polynomial samples and memory.Source: §2.1 · pp. 8–9

2.2 Positive results

  • SGD is efficiently universal: with polynomial-size networks, initialization, samples, steps, and learning rate, it can learn any efficiently learnable distribution having polynomial sample complexity.The construction can be made polynomial-time and distribution-agnostic for families learnable within an n^c sample and per-sample time bound, while tolerating possibly inverse-polynomial weight noise.Source: §2.2 · pp. 9–10
  • SGD can learn parities with accuracy 1 − o(1) using polynomially bounded training, even without random bits and with sufficiently small inverse-polynomial weight noise.The parity construction uses only samples labeled 1 in its deterministic form; the noisy extension uses perturbed SGD with polynomially many samples and a constant learning rate.Source: §2.2 · p. 10

2.3.1 GD with noise

  • For balanced, low-cross-predictability function distributions, noisy full GD cannot learn when polynomial constraints hold on network size, steps, learning rate, noise, and derivative range.The obstruction is that gradients cancel across inputs, so even exponentially small noise can overwhelm the remaining signal; random degree-k monomials are learnable by full GD if and only if k = O(1).Source: §2.3.1 · p. 11, §2.3.3 · p. 13
  • For sufficiently large n, gradient descent on polynomial-size neural nets fails to learn parities with accuracy 1/2 + 2−n/10 under fewer than 2n/10 steps, learning rate at most 2n/10, Gaussian noise variance at least 2−n/10, and overflow range at most 2n/10.Source: §2.3.1 · p. 12

2.3.2 SGD with memory constraint

  • Updating too few weights also prevents learning: bounded-memory SGD fails on low-cross-predictability functions, and block-coordinate descent with o(n/log(n)) updates per step fails on parities.For parities, the failure holds with at most 2^n/24 steps when weights use O(log(n)) bits and fewer than o(n/log(n)) edges are updated per step.Source: §2.3.2 · pp. 12–13

2.3.3 SGD with additional randomness

  • The additional-randomness analysis contrasts GD’s gradient cancellation with SGD’s preservation of single-sample information and introduces a weight-space τ-neighborhood for neural networks.The supplied passage defines the neighborhood by requiring every edge weight to differ by at most τ while preserving the graph’s edge set.Source: §2.3.3 · p. 13
  • Theorem 6 bounds noisy SGD’s parity-learning accuracy by 1/2 + 2p + O(Tm^4B^2γ^2/n^2) + O(T[e/4]^(n/4)).The bound applies to polynomial-size networks with Gaussian initialization and update noise, learning rate γ, T steps, and derivative threshold B.Source: §2.3.3 · p. 13
  • With T = c/γ and slowly decreasing γ, the theorem drives accuracy toward 1/2 + 2p, and toward 1/2 if B increases slowly so p approaches zero.The added noise scales as γ^3/2, becoming smaller than signal terms for sufficiently small γ.Source: §2.3.3 · p. 13
  • The positive result nevertheless shows that random parity can be learned by polynomial-size neural networks using polynomial-step SGD with inverse-polynomial noise and controlled weights and derivatives.It uses a constant learning rate, constant edge-weight bound, constant τ, and polynomial B; the result does not hold for all exponent choices.Source: §2.3.3 · p. 14

2.4 Proof techniques: undistinguishability, emulation and sequential learning algorithms

  • The negative-proof framework makes algorithm traces under parity and pure-noise models indistinguishable via total variation and information bounds, forcing failure when the null model cannot achieve the task.Chi-squared mutual information connects the analysis to cross-predictability, while the noisy-SGD argument repeatedly preserves indistinguishability after sample-dependent perturbations and added noise.Source: §2.4 · pp. 14–15
  • The framework formalizes sequential learning algorithms as trace-based procedures that query samples, update memory, and forget prior samples, encompassing SGD and mini-batch GD.The positive construction instead emulates polynomial-time learning algorithms with SGD-controlled neural-network subnets and randomization to handle correctly predicted samples.Source: §2.4 · pp. 15–16

3 Related literature

The related literature connects parity-learning barriers to circuit complexity, statistical-query limitations, memory–sample trade-offs, and gradient concentration, while distinguishing these results from the paper’s SGD findings.

3.1 Minsky and Papert

  • Parity-learning difficulty has longstanding connections to perceptrons, circuit complexity, and statistical query algorithms [MP87, Bot19, H˚as87, All96, Kea98].Source: §3.1 · p. 16

3.2 Statistical querry algorithms

  • Statistical-query results differ from this paper by studying worst-case function classes with adversarial noise, whereas this paper studies typical functions under statistical noise and weak learning.Source: §3.2 · p. 17
  • Cross-predictability and statistical dimension capture different distributional properties, so large statistical dimension does not necessarily prevent learning under low cross-predictability.Source: §3.2 · pp. 17–18
  • SGD can learn parities with better noise tolerance and complexity than SQ algorithms, because variance in random queries supplies noise-robustness unavailable to GD or SQ methods.Source: §3.2 · p. 18

3.3 Memory-sample trade-offs

  • The memory–sample trade-off differs from: bounded per-sample memory edits can require exponentially many samples even with unlimited total memory, whereas constrains total memory or samples.Source: §3.3 · p. 19

3.4 Gradient concentration

  • Prior gradient-concentration work showed neural-network gradients can be essentially independent of the target parity, but did not establish impossibility for SGD; this paper proves SGD learnability with suitable initialization and small batches.Source: §3.4 · pp. 19–20

4 Some challenging functions

This section examines parities, connectivity, arithmetic, and other low-cross-predictability functions as challenging cases for deep learning, while identifying conditions under which SGD can still succeed.

4.1 Parities

  • SGD can learn parities with a proper initialization, whereas GD with small noise, coordinate descent, or bounded-memory updates cannot learn them in polynomial time.The negative result applies despite noise smaller than that needed to make parities hard for standard learning methods.Source: §4.1 · p. 20
  • A three-hidden-layer ReLU perceptron trained on 13 × 13 parity images fits the training set but generalizes no better than random guessing.The experiment used 1,000 training and testing images, SGD with step size 0.1, and random rescaled-uniform initialization.Source: §4.1 · p. 21

4.2 Community detection and connectivity

  • Deep learning is conjectured to fail on distinguishing one pruned random graph from two randomly relabeled half-sized graphs, although depth-first search solves the task in polynomial time.The construction uses the AER graph distribution; the difficulty is attributed to the absence of informative small subgraphs.Source: §4.2 · p. 22

4.3 Arithmetic learning

  • Arithmetic tasks with unknown digit meanings can have low cross-predictability and be difficult for randomly initialized networks, although linear equations can recover the digit assignment from suitable samples.The techniques do not apply when the entire alleged sum is provided, because correctly labeled expressions would need to occur much more often.Source: §4.3 · pp. 22–23

4.4 Beyond low cross-predictability

  • For random degree-k monomials, GD fails under memory or noise constraints when k = ω(1), while deep learning succeeds robustly exactly when k = O(1).The positive construction inputs all monomials in the first layer and can use suitable nonlinearities or robust gate implementations.Source: §4.4 · p. 23
  • The authors expect small cross-predictability to be less typical for image and sound labels, which often combine correlated local features, unlike large-support parities.This compositional structure can give neural networks correlated intermediate functions from which learning can begin.Source: §4.4 · pp. 23–24
  • Polynomial cross-predictability permits at least polynomial accuracy, but it is insufficient for constant-advantage learning in general because rare constant functions can dominate the measure.The paper therefore suggests stronger projection-based conditions while noting they may not be necessary.Source: §4.4 · pp. 24–25

5.1 Proof of Theorem 3

The proofs analyze noisy sequential updates by comparing their behavior on true labels with behavior on random labels, then bound how distinguishable the resulting memories are.

5.1 Proof of Theorem 3

  • Theorem 3 applies to sequential algorithms whose memory updates are bounded noisy functions of the current state and queried data, including SGD-style mini-batch updates.The framework also relates statistical-query algorithms to the same update model by taking an infinite batch and matching the noise scale to query tolerance.Source: §5.1 · p. 25
  • The proof couples runs on true labels and random labels, using triangular, data-processing, Pinsker, Cauchy–Schwarz, and replicate arguments to control their distributional separation.The resulting bounds are expressed through gradient norms and cross-predictability terms.Source: §5.1 · pp. 25–27

5.1.1 Proof of Theorem 4

  • The parity-specific argument concludes that the relevant distributions remain difficult to distinguish under the stated polynomial-time noisy-update regime.The proof follows the general theorem but removes some unnecessary inequalities and improves the exponent factor for parities.Source: §5.1.1 · p. 29
  • For parities, the proof exploits their cross-predictability 2^-n and Fourier–Walsh identities to show that expectations under random parity inputs are close to expectations under truly random inputs.This yields the specialized scaling used in the parity lower bound.Source: §5.1.1 · pp. 28–29

5.2 Proof of Theorem 5

This section proves Theorem 5 by bounding the information revealed by sequential outputs and applying those bounds to distinguishing and SGD-style neural-network updates. It shows that sparse, bounded-memory procedures under the stated constraints cannot effectively distinguish structured samples from random ones or learn low-cross-predictability function distributions.

5.2.1 Learning from a bit

  • For a recorded value W=g(X,Y), the analysis bounds information about F using conditional variance or chi-squared mutual information, cross-predictability, and g’s inherent bias.The chi-squared measure is stronger than classical mutual information, which is stronger than squared total variation; the bounds extend from bits to m-valued outputs.Source: §5.2.1 · pp. 29, 31
  • For uniform parity functions on uniform inputs, W provides no significant information about F unless its number of possible values m is exponentially large.The parity specialization also adds an L1 bound derived from Cauchy–Schwarz.Source: §5.2.1 · p. 32

5.2.2 Distinguishing with SLAs

  • Sequential learning algorithms with output space |W| sufficiently small relative to Pred(PX, PF) cannot effectively distinguish samples from a random function from true random samples.Theorem 8 formalizes this for m-traces generated from a mixture of the joint distribution and an independent reference distribution, under bounds on |W| and m.Source: §5.2.2 · pp. 32–33
  • Polynomial-memory data structures whose O(log n)-bit variables update only a sufficiently small number per step cannot distinguish the reference distribution with accuracy greater than 1/2 + O(√Pred(PX, PF)).The proof encodes each update as a small output and reconstructs the memory state, reducing the process to a sequential learning algorithm.Source: §5.2.2 · p. 36
  • After q/2 labeled pairs, such an algorithm cannot compute the hidden parity bit with accuracy 1/2 + ω(1/√q) with probability ω(1/q).Otherwise, prediction accuracy on later samples would distinguish the reference and function-generated distributions more accurately than the theorem permits.Source: §5.2.2 · p. 37

5.2.3 Application to SGD

  • The SGD application considers neural networks with polynomial size, O(log n)-bit edge weights, and update variants that adjust only a few weights per timestep when learning random parity functions.The supplied passage introduces Theorem 9 and specifies k = o(n/log(n)); its conclusion is not included here.Source: §5.2.3 · p. 37
  • More generally, after fewer than 2^(n/24) steps, an algorithm changing at most k weights per sample cannot identify whether PZ = ⋆ with accuracy above 1/2 + O(2^(-n/24)).The distribution PZ is either ⋆ or a randomly selected ρS, and the result follows immediately from Corollary 9.Source: §5.2.3 · p. 37
  • A related corollary implies that after training on 2^(n/24−1) pairs (x, pS(x)), the network computes pS(x) with accuracy no greater than 1/2 + ω(2^(-n/48)).This strengthens the indistinguishability statement by directly limiting prediction accuracy for the sampled function.Source: §5.2.3 · p. 37
  • For cross-predictability cp = o(1), polynomial-size neural networks trained by SGD for at most cp^(-1/24) steps fail to learn PF with accuracy 1/2 + ϵ.Each edge weight uses O(log(n)) bits, and fewer than o(|log(cp)|/log(n)) edge weights are updated per step.Source: §5.2.3 · p. 38
  • The proof encodes the network and a correctness bit in polynomial memory, then applies Corollary 9 to show the final state cannot distinguish random samples from samples of a random parity function.Because random samples make the correctness bit equally likely to be True or False, parity training yields correctness at most 1/2 + O(cp^(1/24)).Source: §5.2.3 · p. 38

5.3 Proof of Theorem 6

This section proves Theorem 6 by analyzing noisy SGD dynamics, including uniform-noise, Gaussian-blurring, distributional-indistinguishability, and locally stable perturbation arguments. It shows that under Gaussian initialization and noisy SGD, the network’s ability to compute the target parity is tightly bounded.

5.3 Proof of Theorem 6

  • The proof targets noisy SGD by comparing networks trained on random parity samples with networks trained on uniformly random values, despite potentially large per-sample gradients.Because expected-gradient differences are exponentially small but individual-sample gradients may not be, drowning out the signal requires substantially more noise.Source: §5.3 · p. 38

5.3.1 Uniform noise and SLAs

  • Uniform noise makes most small weight updates statistically uninformative, yielding failure to compute a random parity with nontrivial accuracy unless some pre-noise update exceeds D.Theorem 11 assumes t = 2^o(n), polynomial-size normal networks, uniform noise on [−D|E(G)|, D|E(G)|], and O(log(n))-bit edge weights, with probability 1 − o(1).Source: §5.3.1 · p. 39

5.3.2 Gaussian noise, noise accumulation, and blurring

  • Gaussian noise is accumulated across steps so that edge-weight distributions become approximate Gaussian convolutions, blurring information from each input and supporting parity-versus-random indistinguishability.The approach uses noisy initial weights, smaller per-step Gaussian noise, blurring lemmas, and stability conditions to control nonlinear transformations; repeated-step errors motivate revisions to an idealized (σ, 0) blurring.Source: §5.3.2 · pp. 41, 44

5.3.3 Means, SLAs, and Gaussian distributions

  • The final construction revises edge weights after each step and seeks to show revisions do not change them while parity-generated and random samples induce nearly identical weight distributions.This would make the final edge-weight distribution nearly independent of the sampling distribution; the argument uses indistinguishability results for unknown parity functions and Gaussian-mixture weight distributions.Source: §5.3.3 · p. 45
  • The proof replaces locally controlled functions by globally bounded smooth approximations that preserve their values within the relevant radius.The approximation preserves f(x) for ||x − µ||_1 < r and bounds every derivative by 2B1 + 2rB2.Source: §5.3.3 · p. 47
  • Corollary 11 extends the Gaussian perturbation argument to functions stable only near likely evaluation regions, provided m < 1/(2B1 + 2rB2).The construction starts from W0 drawn from N(µ, σI) and compares distributions induced by random z and parity-labeled inputs.Source: §5.3.3 · p. 47
  • Theorem 15 couples noisy SGD to an auxiliary process whose distribution is independent of the input-distribution choice, except with probability bounded by p + T(ε + ε′/4 + ε′′).This yields an L1 distance bound ||Q−Q′||_1 ≤ 4p + T(4ε + ε′ + 4ε′′) between final-weight distributions.Source: §5.3.3 · pp. 47, 49
  • At most 1/2 + 2p + T(360m^4B^2γ^2/πn + 7[e/4]^(n/4)) is the probability that the resulting network computes p_S(X) correctly.This holds under the noisy stochastic-gradient procedure and the stated bound on γ, with p denoting the probability of a nearby perturbation having an excessively large first, second, or third derivative.Source: §5.3.3 · pp. 49, 51

6 Proofs of positive results: universality of deep learning

This section establishes the universality of SGD-trained, polynomial-size neural networks by emulating polynomial-time learning algorithms through embedded computation and memory components. It develops noise-tolerant constructions that preserve encoded samples, implement the required computations, and produce the desired outputs under bounded SGD noise.

6 Proofs of positive results: universality of deep learning

  • SGD-trained polynomial-size neural networks can learn any polynomial-time learnable function distribution with accuracy at least 1/2 + ϵ using polynomial samples, despite possibly polynomial noise.The networks can be constructed in polynomial time and trained with SGD.Source: §6 · p. 52

6.1 Emulation of arbitrary algorithms

  • An efficient learning algorithm can be represented by polynomial-size circuits that update memory from samples and compute predictions from memory and inputs.The construction translates these circuits into neural-network components while preserving their intended computations.Source: §6.1 · pp. 52, 56
  • Random output guesses solve the zero-gradient problem on correct predictions, allowing the network to learn from an unbiased sample distribution with about (2 + o(1)) times the original algorithm’s samples.After learning enough, the network switches from exploratory guessing to computing the learned function on each new input.Source: §6.1 · p. 53
  • For parity learning, the network stores samples until they span the input space, then returns correct outputs for all subsequent inputs after about 2n samples.The memory stores sample-label pairs and a counter, while computation tests linear dependence and reconstructs outputs from memorized samples.Source: §6.1 · p. 55
  • A flat-derivative activation function keeps computation circuits unchanged under SGD while enabling selected edge weights to encode and update the algorithm’s memory.The activation derivative is 0 outside [−3/2, 3/2], preventing backpropagation from altering protected components.Source: §6.1 · pp. 55–56
  • The basic memory construction only updates when the network predicts incorrectly, requiring random-output training to ensure samples are learned from with probability 1/2.Its implementation can be impractically large because the memory paths repeatedly cube small activations, although a different activation could reduce the required replication scale.Source: §6.1 · pp. 58–59
  • Polynomial-size networks trained with SGD can emulate any function distribution learnable from polynomially many samples and polynomial time, achieving accuracy α − o(1) after polynomially many steps.The construction emulates the learner’s memory and updates it through SGD, with random bits supporting both randomized learning and a randomized training phase.Source: §6.1 · pp. 59–60
  • A polynomial-size SGD-trained metanetwork can learn any efficiently learnable distribution given suitable polynomial bounds on the learner’s sample and time complexity.The metaalgorithm enumerates short candidate algorithms, evaluates them on held-out samples, and can also handle unknown sample requirements through progressively larger training budgets.Source: §6.1 · pp. 61–62

6.2 Noisy emulation of arbitrary algorithms

  • Noisy emulation replaces exact zero-input gating with an activation that is zero near zero, while redesigning memory so each stored value is updated once and has three possible states.The computation component tolerates sufficiently small perturbations because its inputs remain separated from zero, whereas memory requires protection against amplified weight errors and imperfect outputs.Source: §6.2 · p. 62
  • Inductive distortion bounds keep memory states separated and computation inactive between updates, so bounded noise does not alter stored bits or create unintended gradient effects.After the pivotal sample, secondary distortions remain at most 10800ϵ + 6ϵ′, while later memory outputs retain their encoded values.Source: §6.2 · pp. 64–66
  • The circuit-emulation lemma adds at most b new vertices, with y(0) < y(1), and makes derivatives with respect to edges leading to them zero, while paths through them do not contribute.The new vertices compute h correctly, with −2 and 2 encoding 0 and 1, respectively.Source: §6.2 · pp. 66–67
  • The network stores each training sample in indexed memory copies, allowing the computation component to recover the timestep, prior inputs, labels, and final prediction query.At each timestep it sets memory corresponding to the received input; after t_n samples, it reconstructs the history and evaluates h.Source: §6.2 · pp. 67–68
  • Lemma 13 gives a polynomial-size network whose perturbed-SGD output is within 1/2 of the polynomial-time computable function h on the observed samples.The construction uses squared loss, a specified learning rate, and noise bounded by 1/n^2t_n per edge and timestep.Source: §6.2 · pp. 67–68
  • The emulation works by encoding samples and random bits in network components that preserve computation and memory states despite noisy SGD updates.Inductive control of activations and edge weights makes the computation component reproduce the algorithm’s outputs, while the output vertex eventually produces the desired prediction.Source: §6.2 · pp. 69–70
  • Noisy SGD on a polynomial-size neural network learns any function distribution learnable from polynomially many samples by an efficient algorithm, with accuracy α − o(1).The construction uses perturbed SGD with polynomially bounded noise, a polynomial learning rate, and squared loss to emulate the algorithm’s computation.Source: §6.2 · p. 70

6.3 Additional comments on the emulation

  • The initial construction uses an impractical activation function, atypical connectivity, and a deliberately high learning rate, making direct emulation less efficient than running the algorithm itself.These choices are described as unlikely to arise in normal neural-network use.Source: §6.3 · pp. 70–71
  • More reasonable emulation can use selective edge initialization, sequential circuit updates, slowly stabilizing memory values, idle stabilization steps, and gradually increasing output influence.These mechanisms target lower learning rates, controlled weight changes, and memory updates that cannot occur in a single step.Source: §6.3 · p. 71
Loading 2001.02992v1…