Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization

Andrzej Banburski; Qianli Liao; Tomaso Poggio

REVIEW 4 major objections 6 minor 64 references

Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Standard gradient descent on exponential-type losses implicitly constrains each layer's weight directions to the unit L2 sphere, and this hidden complexity control is why overparameterized deep ReLU networks generalize.

desk verdict A coherent review with a central generalization claim that is more suggestive than proven—worth discussing, not worth citing as a result. read the letter →

arxiv 1908.09375 v1 pith:JOGTPT3O submitted 2019-08-25 cs.LG stat.ML

Tomaso Poggio , Andrzej Banburski , Qianli Liao This is my paper · ORCID

classification cs.LGstat.ML MSC 68T0768Q32

keywords deeplearningtheoryimplicitregularizationgradientdescentgeneralizationmarginmaximizationReLUnetworksweightnormalizationapproximation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This review argues that overparameterized deep ReLU networks generalize despite having more weights than training points because ordinary gradient descent on exponential-type losses (exponential, logistic, cross-entropy) carries a hidden complexity control: it keeps the directions of each layer's weight matrices on the unit L2 sphere. Reparameterizing each weight matrix as $W_k = \rho_k V_k$ with $\|V_k\|_2=1$, the paper shows that the unconstrained gradient flow on the directions has the same critical points as weight normalization, the algorithm that imposes the constraint explicitly. Since classical uniform-convergence bounds control the generalization error of the normalized network class through its Rademacher complexity, the implicit constraint supplies exactly the regularization that the raw loss lacks. Under this constraint, minimizing the exponential-type loss is equivalent to maximizing the margin, connecting the argument to classical max-margin theory. The same manuscript also reviews why deep convolutional networks avoid the curse of dimensionality for compositional functions and why stochastic gradient descent favors the degenerate global minima of the exponential loss.

What carries the argument

The engine of the argument is the reparameterization $W_k = \rho_k V_k$ with $\|V_k\|_2 = 1$, combined with the one-homogeneity of ReLU networks, $f(\rho V;x) = \rho f(V;x)$. The flow for the directions is governed by the tangent-gradient projector $S = I - V_k V_k^\top$, which removes the radial component of the gradient; because $S^2 = S$, the constrained and unconstrained direction dynamics have identical critical points whenever $\rho_k(t)>0$. This projector is the same device used in the weight-normalization algorithm, and it is what converts an unconstrained loss minimization into a dynamics that respects a unit-norm constraint. The margin-maximization theorem then connects the constrained minimizer to the classical max-margin classifier.

What would settle it

Train a deep ReLU network on a separable dataset with the exponential loss until the training loss is nearly zero, compute $V_k = W_k/\|W_k\|_2$ at each layer, and check whether the normalized directions satisfy the constrained critical-point condition $S\,\nabla_{W_k} L = 0$, or equivalently whether they coincide with the directions produced by weight-normalized descent from the same initialization; a convergent run whose normalized directions are not a critical point of the constrained loss would refute the claimed equivalence.

Watch

Extended reading notes

Core claim

The central claim is that standard gradient descent applied to a deep ReLU network with an exponential-type loss and no explicit regularization implicitly enforces a unit L2 norm constraint on the directions $V_k$ of each layer's weight matrices, where $W_k = \rho_k V_k$ and $\|V_k\|_2 = 1$. The paper's Fact 1 states that if the dynamics converges, the $V_k$ are precisely the minimizers under the L2 unit norm constraint; equivalently, unconstrained gradient descent and the explicitly constrained weight-normalization dynamics share their critical points because the tangent projector $S = I - V_k V_k^\top$ is idempotent. Because the network is homogeneous, $f(W;x) = \rho f(V;x)$, and the generalization bound on the normalized class controls the Rademacher complexity, the implicit constraint acts as a hidden complexity control. A further theorem shows that minimizing the exponential loss under unit-norm constraints converges to the maximum-margin solution as $\rho \to \infty$. The paper presents this mechanism as the origin of generalization in overparameterized deep networks.

Load-bearing premise

The argument assumes that the gradient-flow dynamics on the weight directions converges to a critical point, so that the implicit unit-norm constraint governs the final solution; the paper proves this convergence explicitly only for the linear single-layer case and relies on cited results for deep nonlinear networks.

Editorial extensions

If this is right

If the central claim is correct, overparameterized networks need no explicit weight decay or other regularizer for generalization on separable classification: the gradient dynamics themselves impose the needed norm control.
Weight normalization and, in the linear single-layer case, batch normalization are not merely optimization heuristics; they make explicit a constraint that plain gradient descent already obeys, which explains their regularizing effect.
The constrained-minimization view implies that training an overparameterized ReLU network with an exponential-type loss is asymptotically equivalent to margin maximization, tying generalization to the geometry of the separating solution.
Convergence rates differ: the direction error decays as $1/\log t$ under plain gradient descent and as $t^{-(1/2)\log t}$ under weight-normalized descent, so explicit normalization can reach the same margin solution faster.
Because kernel machines are one-homogeneous, the same implicit-norm-control analysis applies to them, extending the story from deep networks to classical large-margin classifiers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the implicit L2 constraint is the mechanism, then the optimizer matters as much as the loss for generalization: algorithms such as coordinate descent or sign-based updates, which have different geometries, should be expected to converge to different, possibly non-max-margin solutions on the same separable data.
Because convergence of the direction dynamics is only proved for the linear single-layer case, the theory as stated describes the limit point rather than early-stopped iterates; extending the argument to finite-time dynamics would be a natural test of whether it explains real training runs.
A direct empirical probe: track $V_k = W_k/\|W_k\|_2$ during ordinary training; if the account is right, the normalized directions should remain on the unit sphere and track the weight-normalization flow even when the training code performs no explicit normalization.
If homogeneity is broken, for example by adding biases or non-homogeneous activations, the implicit unit-norm constraint may disappear; the theory then predicts that explicit regularization becomes necessary, an effect that could be tested by ablating scale invariance in a small network.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this is a review/synthesis paper, not a new proof. Its main advertised result—that standard gradient descent implicitly enforces a unit L2 norm constraint on weight directions, and that this explains generalization in overparameterized ReLU networks—has a genuine logical gap. The stress-test note is right: the paper shows that unconstrained GD and weight-normalization have the same critical points in (rho, V) coordinates, but equality of critical point sets does not imply the flows share attractors. Even if the dynamics converges, it could converge to a saddle or a non-global critical point. So Fact 1's claim that "the V_k represent the minimizer under the L2 unit norm constraint" does not follow. The paper's own Conjectures 1 and 2 concede that the selection of global minima by SGD is unproved. This is a load-bearing gap, and the abstract oversells the result as "a solution" to the generalization puzzle.

What the paper does well: the three-part structure is clear, and the synthesis is honest. The approximation section is a useful review of the curse-of-dimensionality results, including the compositional-function advantage. The optimization section gives a coherent derivation (Equations 11–18) showing that weight normalization and standard GD coincide at critical points, and the margin-maximization claim is supported by independent work (Lyu & Li; Shpigel Nacson et al.), which the authors cite. They also explicitly flag their conjectures and call for a convergence analysis in the Discussion—so they're not hiding the gaps. But the companion-memo dependence (Theorem 3, Property 1) and the unproved convergence assumption are real soft spots.

If I were refereeing this for publication, I would treat it as a valuable position paper rather than a definitive solution. The authors should either include the missing proofs or carefully rescope the abstract and Fact 1 to say "if the dynamics converges to a global minimum, then…" and let the margin-maximization papers carry the convergence guarantee. As it stands, the paper is a good map of the area and a clear statement of a research program, but not a proof.

I would accept it for peer review—serious refereeing could push the authors to clarify the gap, and the synthesis is useful for the community. But I wouldn't cite it as evidence for implicit bias; I'd cite Soudry et al. and the margin-maximization papers directly. Bring it to reading group if you want a debate about what "implicit regularization" can and cannot mean.

Referee Report

4 major / 6 minor

Summary. This manuscript is a review article on three theoretical questions in deep learning: approximation power, optimization of the empirical risk, and generalization of overparameterized networks. For approximation, it summarizes results showing that deep hierarchical/convolutional networks can avoid the curse of dimensionality for compositional functions while shallow networks cannot. For optimization, it argues that under exponential-type losses the global minima are highly degenerate and that SGD, through a Langevin/Boltzmann analogy and the degeneracy structure, should select global minima with high probability. For generalization, the paper proposes that standard gradient descent on the weights implicitly enforces a unit L2 norm constraint on the weight directions V_k, so that the dynamics has the same critical points as weight-normalized constrained gradient descent; combined with Theorem 3, which connects the constrained minimization to margin maximization, this is offered as an explanation of hidden complexity control in deep ReLU networks. The central claim is that this implicit unit-norm constraint is the origin of generalization despite overparameterization.

Significance. If the hidden-norm-control thesis is correct, it would provide a unified explanation of generalization in overparameterized ReLU networks and would connect the classical Rademacher-complexity view with margin theory, implicit-bias results, and normalization techniques. The manuscript has real strengths: the explicit derivation of the critical-point equivalence between standard GD and constrained dynamics in Eqs. (17)-(18) is a useful observation; the paper engages seriously with independent work by Soudry et al., Lyu and Li, and Nacson et al.; and Figures 3 and 4 provide suggestive empirical support. However, the central inference from critical-point equivalence to convergence to the constrained global minimizer is not established in the manuscript, and the key Theorem 3 is deferred to a self-cited companion memo. The paper therefore reads as a plausible synthesis whose main theorem-level claims are not yet fully verifiable from the submitted text.

major comments (4)

[Section 3E, Eqs. (17)-(18), Fact 1] The inference from equivalence of critical points to the conclusion of Fact 1 is not justified. Equations (17) and (18) show that the constrained and unconstrained dynamics differ by a factor ρ_k^2 in the V_k flow, so their zero sets coincide; Fact 1 then states that if the dynamics converges, the V_k represent the minimizer under the L2 unit norm constraint. For the nonconvex empirical loss of a deep ReLU network this is a non-sequitur: equality of critical-point sets does not imply equality of stable attractors, and a critical point of the V-flow need not be a global constrained minimizer. Indeed, Section 2's Conjecture 1 explicitly allows the existence of non-global critical points. Convergence to a meaningful limit is proved only in the linear single-layer case in Section 3F, and the Discussion lists multilayer convergence as an open point. Please either restate this as a conjecture or supply a convergence proof that rules out convergence to non-global critical points.
[Section 3C.1, Theorem 3] Theorem 3 is the bridge between the norm-constrained minimization and margin maximization, and hence between the paper's framework and the independent results of Lyu and Li and Nacson et al. Its proof is deferred to the self-cited CBMM Memo No. 090, and no proof or rigorous statement of conditions is given in the manuscript. Because this theorem is load-bearing for the central generalization claim, the manuscript needs a self-contained proof, or at minimum a precise statement of the assumptions and a citation to a publicly verifiable, peer-reviewed version of the result.
[Section 3C, Eqs. (4)-(5)] The route from the uniform-convergence bound to the constrained minimization problem is incomplete. The Rademacher bound in Eq. (4) contains the term c_1 R_N(F) = c_1 ρ R_N(\tilde F), so letting ρ tend to infinity as in Eq. (5) makes this term grow without bound; taking the limit does not preserve a nontrivial uniform-convergence guarantee. The intended control presumably comes from a margin-based bound after maximizing η(\tilde f) via Theorem 3, but no margin-based generalization bound is stated. Please make explicit which bound is being minimized when ρ→∞ and how the limiting classifier controls the expected classification error.
[Section 2, Property 1 and Conjecture 2] The abstract and Significance Statement assert that SGD 'will find with high probability the global minima,' but the body of the paper supports this only with a heuristic Langevin/Boltzmann analogy and explicitly labels the statement as Conjecture 2. Property 1 is also supported only by 'simple arguments (1)' and is not proved in the text. The optimization claims should be presented as conjectures unless the companion-memo proofs are included, and the abstract should be adjusted to match the conjectural status of this part of the argument.

minor comments (6)

[Section 3E, Fact 1] The text 'implicitly respectss a unit L2 norm constraint' contains a typo; it should read 'implicitly respects'.
[Section 1C] The sentence 'Let VN be the be set of all networks' contains a duplicated article; it should read 'the set of all networks'.
[Abstract and Significance Statement] The phrase 'a the class of compositional functions' contains a typo; it should read 'a class of compositional functions'.
[Section 3B] The sentence 'We sometime use the symbol W' should read 'We sometimes use the symbol W'.
[References] Reference [45] lists the arXiv identifier '180.3251', which appears malformed; please check the correct identifier.
[References] Reference [54] misspells the author name 'Kingma' as 'Kingm'.

Circularity Check

3 steps flagged · score 4.0 of 10

Fact 1 turns the definitional unit-norm reparametrization into a 'hidden constraint' and imports the convergence-to-minimizer premise; several supporting results are delegated to self-cited memos, though independent margin-maximization results keep the central claim from being forced.

self definitional [Section 3E, Eqs. 17–18 and Fact 1]
"Define w/||w||2 = w~; thus w = ||w||2 w~ with ||w~||2 = 1. Also define S = I − w~w~T ... The key point here is that the dynamics of ˙Vk includes a unit L2 norm constraint: using the tangent gradient transform will not change the equation because S2 = S. ... Fact 1 The standard dynamical system used in deep learning, defined by ˙Wk =−∂L/∂Wk, implicitly respectss a unit L2 norm constraint on Vk with ρkVk = Wk. Thus, under an exponential loss, if the dynamics converges, the Vk represent the minimizer under the L2 unit norm constraint."

Under the change of variables W_k = ρ_k V_k with ||V_k||_2 = 1, the statement that GD 'respects a unit L2 norm constraint on V_k' is a restatement of the normalization imposed in the definition; the projected operator S = I − VV^T is just the tangent map of the unit sphere. The nontrivial conclusion, that the limit is the constrained minimizer, is not derived: Eqs. 17 and 18 show only that the critical-point sets coincide because they differ by the nonzero factor ρ_k², and equality of critical-point sets does not imply the same attractor is selected. The paper's own Discussion lists convergence of the weights for multilayer networks as open, so the explanatory content of Fact 1 is definition plus an extra, unproved convergence assumption rather than a prediction.
self citation load bearing [Section 3C.1, Theorem 3]
"Then our margin maximization theorem (proved in (1)) takes the form ... Theorem 3 Consider the set of Vk,k = 1,···,K corresponding to min ||Vk||=1 L(f(ρk,Vk)) ... converges for ρ→∞ to the maximum margin of ˜f, that is to max||Vk||≤1 η(˜f)."

Theorem 3 is the bridge from the norm-constrained minimization of Eq. 6 to the max-margin solution, and it is asserted without proof in this manuscript, with the proof deferred to the authors' own CBMM Memo No. 090 (ref. 1). Since that memo is not machine-checked or otherwise independently verified within the paper, the derivation chain at this point rests on self-citation. The margin conclusion has independent support in refs. (2)–(4), so this is partial rather than total circularity, but the paper's own proof obligation is discharged only by a same-author memo.

1 more flagged steps

self citation load bearing [Section 2B–2C, Property 1 and Conjecture 2]
"Simple arguments (1) suggest that the critical points which are not global minima cannot be completely degenerate. We thus have the following Property 1 Under the exponential loss, global minima are completely degenerate ... The other critical points ... less degenerate ... Together (43) and (1) suggest Conjecture 2 : ... SGD selects with high probability the global minimizers of the empirical loss, which are highly degenerate."

Property 1 and Conjecture 2 are the in-paper support for the optimization claim that SGD finds global minima with high probability. Both are explicitly sourced to the authors' own memos (refs. 1, 43, 44) and are labeled as suggested or conjectured rather than proved here. This is a self-citation chain, although it is not the main generalization derivation and the paper presents it as a conjecture rather than a theorem.

full rationale

The central generalization argument is not entirely circular: Srebro et al. (2), Lyu and Li (3), and Shpigel Nacson et al. (4) independently establish implicit-bias and margin-maximization results that support the paper's conclusion, and the uniform-convergence bound in Proposition 1 is standard. However, the paper presents its 'hidden unit-norm constraint' as a discovery when it is largely a consequence of defining V_k as the normalized direction W_k/||W_k||_2, and the step from critical-point coincidence to 'the V_k represent the minimizer' requires a convergence-to-global-minimizer premise that the paper itself lists as open for multilayer networks. Several supporting results (Theorem 3, Property 1, Conjecture 2) are delegated to the authors' own CBMM memos (1, 43, 44) rather than proved in the manuscript. Because external results supply much of the missing support, the paper is not forced by definition, but the self-citation chain and the definitional component justify a partial circularity score of 4.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper fits no numeric constants to data, so the free-parameter list is empty. The central claims rely on domain assumptions about compositional target functions, separable data, exponential-type loss, and the adequacy of continuous gradient flow as a model of SGD. Two conjectures from the authors' own memos carry the optimization argument without proof. No new entities are invented.

assumptions (4)

domain assumption Target functions belong to the class of hierarchically local compositional functions W^{n,2}_m with a fixed binary tree architecture matching the network.
Theorem 2's linear-in-n approximation guarantee applies only to this class; the paper concedes in the Discussion that it is unclear why practical tasks match this class.
domain assumption The data are separable and the loss is exponential-type (e.g., exponential, logistic, cross-entropy).
The global-minima-at-infinity analysis and the implicit-norm-constraint argument require separable data and exponential-type losses; see Sections 2B and 3D.
domain assumption Continuous-time gradient flow is an adequate model for discrete SGD, and the V_k dynamics converges to a critical point.
Fact 1 is stated for the dynamical system dW/dt = -grad L and includes the caveat 'if the dynamics converges'; convergence for deep nonlinear networks is delegated to refs (3,4).
ad hoc to paper Conjectures 1 and 2 about degeneracy of minima and SGD selecting degenerate global minima.
The optimization story (SGD finds global minima with high probability) rests on these unproved conjectures, supported only by simulations in the authors' memo (44).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization." pith.science (2026). https://pith.science/paper/JOGTPT3O

@misc{pith2026190809375,
  author       = {Pith},
  title        = {Pith review of: Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JOGTPT3O}},
  note         = {Machine review of arXiv:1908.09375}
}

read the original abstract

While deep learning is successful in a number of applications, it is not yet well understood theoretically. A satisfactory theoretical characterization of deep learning however, is beginning to emerge. It covers the following questions: 1) representation power of deep networks 2) optimization of the empirical risk 3) generalization properties of gradient descent techniques --- why the expected error does not suffer, despite the absence of explicit regularization, when the networks are overparametrized? In this review we discuss recent advances in the three areas. In approximation theory both shallow and deep networks have been shown to approximate any continuous functions on a bounded domain at the expense of an exponential number of parameters (exponential in the dimensionality of the function). However, for a subset of compositional functions, deep networks of the convolutional type can have a linear dependence on dimensionality, unlike shallow networks. In optimization we discuss the loss landscape for the exponential loss function and show that stochastic gradient descent will find with high probability the global minima. To address the question of generalization for classification tasks, we use classical uniform convergence results to justify minimizing a surrogate exponential-type loss function under a unit norm constraint on the weight matrix at each layer -- since the interesting variables for classification are the weight directions rather than the weights. Our approach, which is supported by several independent new results, offers a solution to the puzzle about generalization performance of deep overparametrized ReLU networks, uncovering the origin of the underlying hidden complexity control.

Figures

Figures reproduced from arXiv: 1908.09375 by the authors.

**Figure 1.** The top graphs are associated to functions; each of the bottom diagrams depicts the ideal network approximating the function above. In a) a shallow universal network in 8 variables and N units approximates a generic function of 8 variables f(x1, · · · , x8). Inset b) shows a hierarchical network at the bottom in n = 8 variables, which approximates well functions of the form f(x1, · · · , x8) = h3(h21(h11(x1, x2), h… view at source ↗

**Figure 2.** Stochastic Gradient Descent and Langevin Stochastic Gradient Descent (SGDL) on the 2D potential function shown above leads to an asymptotic distribution with the histograms shown on the left. As expected from the form of the Boltzmann distribution, both dynamics prefer degenerate minima to non-degenerate minima of the same depth. From (1). degenerate, with at least one – and typically N – nonzero eigenvalues. For th… view at source ↗

**Figure 3.** The top left graph shows testing vs training cross-entropy loss for networks each trained on the same data sets (CIFAR10) but with a different initializations, yielding zero classification error on training set but different testing errors. The top right graph shows the same data, that is testing vs training loss for the same networks, now normalized by dividing each weight by the Frobenius norm of its layer. Notice… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Empirical and expected error in CIFAR 10 as a function of number of neurons in a 5-layer convolutional network. The expected classification error does not increase when increasing the number of parameters beyond the size of the training set in the range we tested. 4. D…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 48 canonical work pages

[1]

However, our theoretical understanding of deep learning, and thus the ability of developing principled improvements, has lagged behind

Introduction I n the last few years, deep learning has been tremendously successful in many important applications of machine learn- ing. However, our theoretical understanding of deep learning, and thus the ability of developing principled improvements, has lagged behind. A satisfactory theoretical characterization of deep learning is emerging. It covers...

work page
[2]

When Can Deep Networks Avoid the Curse of Dimension- ality?.We start with the ﬁrst set of questions, summarizing results in (5–7), and (8, 9)

approximation properties of deep networks 2)optimization of the empirical risk 3)generalization properties of gradient descent techniques – why the expected error does not suf- fer, despite the absence of explicit regularization, when the networks are overparametrized? A. When Can Deep Networks Avoid the Curse of Dimension- ality?.We start with the ﬁrst s...

work page
[3]

representation powerof deep networks 2) optimization of the empirical risk 3) generalization propertiesof gradient de- scent techniques – how can deep networks generalize despite being overparametrized – more weights than training data – in the absence of any explicit regularization? We review progress on all three areas showing that 1) for a the class of...

work page Pith review arXiv
[4]

solution

The Optimization Landscape of Deep Nets with Smooth Activation Function The main question in optimization of deep networks is to the landscape of the empirical loss in terms of its global minima and local critical points of the gradient. A. Related work. There are many recent papers studying opti- mization in deep learning. For optimization we mention wor...

work page 2019
[5]

implicit

Generalization Recent results by (2) illuminate the apparent absence of ”over- ﬁtting” (see Figure 4) in the special case of linear networks for binary classiﬁcation. They prove that minimization of loss functions such as the logistic, the cross-entropy and the expo- nential loss yields asymptotic convergence to the maximum margin solution for linearly se...
[6]

asymptotic minima

S2 =S The gradient descent dynamic system used in training deep networks for the exponential loss is given by Equation 7. Following the chain rulefor the time derivatives, the dynamics forWk is exactly (see (1)) equivalent to the following dynamics for||Wk||=ρk and Vk: ˙ρk = ∂||Wk|| ∂Wk ∂Wk ∂t =VT k ˙Wk [11] and ˙Vk = ∂Vk ∂Wk ∂Wk ∂t = Sk ρk ˙Wk [12] where...
[7]

CBMM memo 041

Poggio T, Anselmi F , Rosasco L (2015) I-theory on depth vs width: hierarchical function composition. CBMM memo 041

work page 2015
[8]

Discussion A main diﬀerence between shallow and deep networks is in terms of approximation power or, in equivalent words, of the ability to learn good representations from data based on the compositional structure of certain tasks. Unlike shallow networks, deep local networks – in particular convolutional networks – can avoid the curse of dimensionality i...

Show all 64 references

[9]

(2019) Theory of deep learning III: Dynamics and generalization in deep networks

Banburski A, et al. (2019) Theory of deep learning III: Dynamics and generalization in deep networks. CBMM Memo No. 090

2019
[10]

ArXiv e-prints

Soudry D, Hoffer E, Srebro N (2017) The Implicit Bias of Gradient Descent on Separable Data. ArXiv e-prints

2017
[11]

CoRR abs/1906.05890

Lyu K, Li J (2019) Gradient descent maximizes the margin of homogeneous neural networks. CoRR abs/1906.05890

2019 arXiv
[12]

arXiv e- prints p

Shpigel Nacson M, Gunasekar S, Lee JD, Srebro N, Soudry D (2019) Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models. arXiv e- prints p. arXiv:1905.07325

2019 arXiv
[13]

Center for Brains, Minds and Machines (CBMM) Memo No

Anselmi F , Rosasco L, Tan C, Poggio T (2015) Deep convolutional network are hierarchical kernel machines. Center for Brains, Minds and Machines (CBMM) Memo No. 35, also in arXiv

2015
[14]

Poggio T, Rosasco L, Shashua A, Cohen N, Anselmi F (2015) Notes on hierarchical splines, dclns and i-theory, (MIT Computer Science and Artiﬁcial Intelligence Laboratory), Technical report

2015
[15]

Acta Numerica 8:143–195

Pinkus A (1999) Approximation theory of the mlp model in neural networks. Acta Numerica 8:143–195

1999
[16]

45, also in arXiv

Mhaskar H, Liao Q, Poggio T (2016) Learning real and boolean functions: When is deep better than shallow? Center for Brains, Minds and Machines (CBMM) Memo No. 45, also in arXiv

2016
[17]

Center for Brains, Minds and Machines (CBMM) Memo No

Mhaskar H, Poggio T (2016) Deep versus shallow networks: an approximation theory per- spective. Center for Brains, Minds and Machines (CBMM) Memo No. 54, also in arXiv

2016
[18]

Donoho DL (2000) High-dimensional data analysis: The curses and blessings of dimension- ality in AMS CONFERENCE ON MA TH CHALLENGES OF THE 21ST CENTURY

2000
[19]

Advances in Computational Mathematics pp

Mhaskar H (1993) Approximation properties of a multilayered feedforward artiﬁcial neural network. Advances in Computational Mathematics pp. 61–80

1993
[20]

Assuming ϵof the form ϵ∝1 logt we obtain−1 t log2t =−B 1 t log2t

We obtain (assuming normalized input||x||= 1) ˙ϵ= 1 ρe−ρvTx(x−(x+ϵ)(x+ϵ)Tx)≈1 ρe−ρvTx(x−x−xϵT−ϵxT ), [20] which has the form ˙ϵ=−1 t logt (2xϵT ). Assuming ϵof the form ϵ∝1 logt we obtain−1 t log2t =−B 1 t log2t. Thus the error indeed converges asϵ∝1 logt. A similar analysis f...

2019
[21]

Proceedings of the 1993 IEEE-SP Workshop

Mhaskar HN (1993) Neural networks for localized approximation of real functions in Neural Networks for Processing [1993] III. Proceedings of the 1993 IEEE-SP Workshop . (IEEE), pp. 190–196

1993
[22]

Mathematics of Computation 63(208):607–623

Chui C, Li X, Mhaskar H (1994) Neural networks for localized approximation. Mathematics of Computation 63(208):607–623

1994
[23]

Advances in Computational Mathematics 5(1):233–243

Chui CK, Li X, Mhaskar HN (1996) Limitations of the approximation capabilities of neural networks with one hidden layer. Advances in Computational Mathematics 5(1):233–243

1996
[24]

Notices of the American Mathematical Society (AMS) 50(5):537–544

Poggio T, Smale S (2003) The mathematics of learning: Dealing with data. Notices of the American Mathematical Society (AMS) 50(5):537–544

2003
[25]

F .and Pascanu R, Cho K, Bengio Y (2014) On the number of linear regions of deep neural networks

Montufar, G. F .and Pascanu R, Cho K, Bengio Y (2014) On the number of linear regions of deep neural networks. Advances in Neural Information Processing Systems 27:2924–2932

2014
[26]

CoRR abs/1304.7045

Livni R, Shalev-Shwartz S, Shamir O (2013) A provably efﬁcient algorithm for training deep networks. CoRR abs/1304.7045

2013 arXiv
[27]

(2014) Unsupervised learning of invariant representations with low sample complexity: the magic of sensory cortex or a new framework for machine learning?

Anselmi F , et al. (2014) Unsupervised learning of invariant representations with low sample complexity: the magic of sensory cortex or a new framework for machine learning?. Center for Brains, Minds and Machines (CBMM) Memo No. 1. arXiv:1311.4158v5

2014 arXiv
[28]

(2015) Unsupervised learning of invariant representations

Anselmi F , et al. (2015) Unsupervised learning of invariant representations. Theoretical Com- puter Science

2015
[29]

CBMM memo 037

Poggio T, Rosaco L, Shashua A, Cohen N, Anselmi F (2015) Notes on hierarchical splines, dclns and i-theory. CBMM memo 037

2015
[30]

Center for Brains, Minds and Machines (CBMM) Memo No

Liao Q, Poggio T (2016) Bridging the gap between residual learning, recurrent neural net- works and visual cortex. Center for Brains, Minds and Machines (CBMM) Memo No. 47, also in arXiv

2016
[31]

arXiv preprint arXiv:1509.08101v2 [cs.LG] 29 Sep 2015

Telgarsky M (2015) Representation beneﬁts of deep feedforward networks. arXiv preprint arXiv:1509.08101v2 [cs.LG] 29 Sep 2015

2015 arXiv
[32]

arXiv:1610.09887v1

Safran I, Shamir O (2016) Depth separation in relu networks for approximating smooth non- linear functions. arXiv:1610.09887v1

2016 arXiv
[33]

058, MIT Center for Brains, Minds and Machines), Technical report

Poggio T, Mhaskar H, Rosasco L, Miranda B, Liao Q (2016) Theory I: Why and when can deep - but not shallow - networks avoid the curse of dimensionality, (CBMM Memo No. 058, MIT Center for Brains, Minds and Machines), Technical report

2016
[34]

arXiv e-prints p

Daubechies I, DeVore R, Foucart S, Hanin B, Petrova G (2019) Nonlinear approximation and (deep) relu networks. arXiv e-prints p. arXiv:1905.02199

2019 arXiv
[35]

CoRR abs/1703.00887

Jin C, Ge R, Netrapalli P , Kakade SM, Jordan MI (2017) How to escape saddle points efﬁ- ciently. CoRR abs/1703.00887

2017 arXiv
[36]

CoRR abs/1503.02101

Ge R, Huang F , Jin C, Yuan Y (2015) Escaping from saddle points - online stochastic gradient for tensor decomposition. CoRR abs/1503.02101

2015 arXiv
[37]

Feldman V, Rakhlin A, Shamir O

Lee JD, Simchowitz M, Jordan MI, Recht B (2016) Gradient descent only converges to min- imizers in 29th Annual Conference on Learning Theory , Proceedings of Machine Learning Research, eds. Feldman V, Rakhlin A, Shamir O. (PMLR, Columbia University, New Y ork, New Y ork, USA),...

2016
[38]

Du SS, Lee JD, Tian Y (2018) When is a convolutional ﬁlter easy to learn? in International Conference on Learning Representations

2018
[39]

(JMLR.org), pp

Tian Y (2017) An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis inProceedings of the 34th International Conference on Machine Learning - Volume 70 , ICML ’17. (JMLR.org), pp. 3404–3413

2017
[40]

IEEE T ransactions on Information Theory 65(2):742–769

Soltanolkotabi M, Javanmard A, Lee JD (2019) Theoretical insights into the optimization land- scape of over-parameterized shallow neural networks. IEEE T ransactions on Information Theory 65(2):742–769

2019
[41]

(Curran Associates Inc., USA), pp

Li Y , Yuan Y (2017) Convergence analysis of two-layer neural networks with relu activation in Proceedings of the 31st International Conference on Neural Information Processing Systems , NIPS’17. (Curran Associates Inc., USA), pp. 597–607

2017
[42]

Brutzkus A, Globerson A (2017) Globally optimal gradient descent for a convnet with gaussian inputs in Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney , NSW, Australia, 6-11 August 2017. pp. 605–614

2017
[43]

Dy J, Krause A

Du S, Lee J, Tian Y , Singh A, Poczos B (2018) Gradient descent learns one-hidden-layer CNN: Don’t be afraid of spurious local minima inProceedings of the 35th International Conference on Machine Learning , Proceedings of Machine Learning Research, eds. Dy J, Krause A. (PMLR, ...

2018
[44]

CoRR abs/1811.03804

Du SS, Lee JD, Li H, Wang L, Zhai X (2018) Gradient descent ﬁnds global minima of deep neural networks. CoRR abs/1811.03804

2018 arXiv
[45]

(JMLR.org), pp

Zhong K, Song Z, Jain P , Bartlett PL, Dhillon IS (2017) Recovery guarantees for one-hidden- layer neural networks inProceedings of the 34th International Conference on Machine Learn- ing - Volume 70 , ICML ’17. (JMLR.org), pp. 4140–4149

2017
[46]

CoRR abs/1711.03440

Zhong K, Song Z, Dhillon IS (2017) Learning non-overlapping convolutional neural networks with multiple kernels. CoRR abs/1711.03440

2017 arXiv
[47]

arXiv e-prints

Zhang X, Yu Y , Wang L, Gu Q (2018) Learning One-hidden-layer ReLU Networks via Gradient Descent. arXiv e-prints

2018
[48]

Bengio S, et al

Li Y , Liang Y (2018) Learning overparameterized neural networks via stochastic gradient descent on structured data in Advances in Neural Information Processing Systems 31 , eds. Bengio S, et al. (Curran Associates, Inc.), pp. 8157–8166

2018
[49]

Du SS, Zhai X, Poczos B, Singh A (2019) Gradient descent provably optimizes over- parameterized neural networks in International Conference on Learning Representations

2019
[50]

CoRR abs/1811.08888

Zou D, Cao Y , Zhou D, Gu Q (2018) Stochastic gradient descent optimizes over- parameterized deep relu networks. CoRR abs/1811.08888

2018 arXiv
[51]

arXiv:1703.09833, CBMM Memo No

Poggio T, Liao Q (2017) Theory II: Landscape of the empirical risk in deep learning. arXiv:1703.09833, CBMM Memo No. 066

2017 arXiv
[52]

(2017) Theory of deep learning IIb: Optimization properties of SGD

Zhang C, et al. (2017) Theory of deep learning IIb: Optimization properties of SGD. CBMM Memo 072

2017
[53]

arXiv:180.3251 [cs, math]

Raginsky M, Rakhlin A, Telgarsky M (2017) Non-convex learning via stochastic gradient langevin dynamics: A nonasymptotic analysis. arXiv:180.3251 [cs, math]

2017
[54]

Guyon I, et al

Daniely A (2017) Sgd learns the conjugate kernel class of the network in Advances in Neural Information Processing Systems 30 , eds. Guyon I, et al. (Curran Associates, Inc.), pp. 2422– 2430

2017
[55]

CoRR abs/1811.04918

Allen-Zhu Z, Li Y , Liang Y (2018) Learning and generalization in overparameterized neural networks, going beyond two layers. CoRR abs/1811.04918

2018 arXiv
[56]

CoRR abs/1901.08584

Arora S, Du SS, Hu W, yuan Li Z, Wang R (2019) Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. CoRR abs/1901.08584

2019 arXiv
[57]

CoRR abs/1810.05369

Wei C, Lee JD, Liu Q, Ma T (2018) On the margin theory of feedforward neural networks. CoRR abs/1810.05369

2018 arXiv
[58]

CoRR abs/1711.01530

Liang T, Poggio T, Rakhlin A, Stokes J (2017) Fisher-rao metric, geometry, and complexity of neural networks. CoRR abs/1711.01530

2017 arXiv
[59]

Bousquet O, Boucheron S, Lugosi G (2003) Introduction to statistical learning theory. pp. 169–207

2003
[60]

Rosset S, Zhu J, Hastie T (2003) Margin maximizing loss functions in Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada] . pp. 1237–1244

2003
[61]

IEEE T ransactions on Signal Processing 48(6):1843–1847

Douglas SC, Amari S, Kung SY (2000) On gradient adaptation with unit-norm constraints. IEEE T ransactions on Signal Processing 48(6):1843–1847

2000
[62]

Advances in Neural Information Processing Systems

Salimans T, Kingm DP (2016) Weight normalization: A simple reparameterization to acceler- ate training of deep neural networks. Advances in Neural Information Processing Systems

2016
[63]

CoRR abs/1807.09659

Liao Q, Miranda B, Banburski A, Hidary J, Poggio TA (2018) A surprising linear relationship predicts test performance in deep networks. CoRR abs/1807.09659

2018 arXiv
[64]

Signal Processing 55:137–139

Ferreira PJSG (1996) The existence and uniqueness of the minimum norm solution to certain linear and nonlinear problems. Signal Processing 55:137–139. Poggio et al. PNAS | August 27, 2019 | vol. XXX | no. XX | 9

1996

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

However, our theoretical understanding of deep learning, and thus the ability of developing principled improvements, has lagged behind

Introduction I n the last few years, deep learning has been tremendously successful in many important applications of machine learn- ing. However, our theoretical understanding of deep learning, and thus the ability of developing principled improvements, has lagged behind. A satisfactory theoretical characterization of deep learning is emerging. It covers...

work page

[2] [2]

When Can Deep Networks Avoid the Curse of Dimension- ality?.We start with the ﬁrst set of questions, summarizing results in (5–7), and (8, 9)

approximation properties of deep networks 2)optimization of the empirical risk 3)generalization properties of gradient descent techniques – why the expected error does not suf- fer, despite the absence of explicit regularization, when the networks are overparametrized? A. When Can Deep Networks Avoid the Curse of Dimension- ality?.We start with the ﬁrst s...

work page

[3] [3]

representation powerof deep networks 2) optimization of the empirical risk 3) generalization propertiesof gradient de- scent techniques – how can deep networks generalize despite being overparametrized – more weights than training data – in the absence of any explicit regularization? We review progress on all three areas showing that 1) for a the class of...

work page Pith review arXiv

[4] [4]

solution

The Optimization Landscape of Deep Nets with Smooth Activation Function The main question in optimization of deep networks is to the landscape of the empirical loss in terms of its global minima and local critical points of the gradient. A. Related work. There are many recent papers studying opti- mization in deep learning. For optimization we mention wor...

work page 2019

[5] [5]

implicit

Generalization Recent results by (2) illuminate the apparent absence of ”over- ﬁtting” (see Figure 4) in the special case of linear networks for binary classiﬁcation. They prove that minimization of loss functions such as the logistic, the cross-entropy and the expo- nential loss yields asymptotic convergence to the maximum margin solution for linearly se...

[6] [6]

asymptotic minima

S2 =S The gradient descent dynamic system used in training deep networks for the exponential loss is given by Equation 7. Following the chain rulefor the time derivatives, the dynamics forWk is exactly (see (1)) equivalent to the following dynamics for||Wk||=ρk and Vk: ˙ρk = ∂||Wk|| ∂Wk ∂Wk ∂t =VT k ˙Wk [11] and ˙Vk = ∂Vk ∂Wk ∂Wk ∂t = Sk ρk ˙Wk [12] where...

[7] [7]

CBMM memo 041

Poggio T, Anselmi F , Rosasco L (2015) I-theory on depth vs width: hierarchical function composition. CBMM memo 041

work page 2015

[8] [8]

Discussion A main diﬀerence between shallow and deep networks is in terms of approximation power or, in equivalent words, of the ability to learn good representations from data based on the compositional structure of certain tasks. Unlike shallow networks, deep local networks – in particular convolutional networks – can avoid the curse of dimensionality i...