Pith. sign in

REVIEW 3 minor 63 references

Gradient descent jointly trains both layers of a one-hidden-layer ReLU network and converges globally to a linear target from moderately small random initialization.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-28 07:01 UTC pith:3OVNVQFE

load-bearing objection The paper delivers a three-phase trajectory analysis plus trajectory controls and uniform concentration that let joint GD reach linear convergence on linear targets in the realizable Gaussian case.

arxiv 2606.04476 v1 pith:3OVNVQFE submitted 2026-06-03 cs.LG math.OCmath.STstat.MLstat.TH

When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networks

Berk Tinaz , Changzhi Xie , Mahdi Soltanolkotabi This is my paper
classification cs.LG math.OCmath.STstat.MLstat.TH
keywords ReLU networkgradient descent dynamicsglobal convergencelinear targettraining phasessample complexityoptimization landscapetwo-layer network
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper studies gradient descent when both the hidden and output layers of a ReLU network are trained together to fit a linear function. In a realizable Gaussian-input setting with labels from a planted linear model, it establishes that the process reaches a global minimizer at linear rate while using an order-wise optimal number of samples. The argument proceeds by dividing the trajectory into an alignment phase, a growth phase, and a local refinement phase that together let the iterates escape non-strict saddle points. Novel uniform concentration bounds that hold along the entire path supply the sample-efficiency result. The framework is chosen because it captures key features of end-to-end training in inverse problems and certain auto-encoder models.

Core claim

Gradient descent from a moderately small random initialization, simultaneously training both layers, converges to a global minimizer at a linear rate with order-wise optimal sample complexity. The trajectory is tracked through three phases: an alignment phase in which hidden weights progressively align with the planted direction while output weights maintain the correct sign pattern; a growth phase in which the norms of both layers increase while preserving alignment; and a local refinement phase in which the aligned neurons rapidly converge to the planted direction, yielding fast local convergence. Trajectory-level control arguments and uniform concentration results along the path are used

What carries the argument

Three-phase trajectory (alignment phase, growth phase, local refinement phase) together with trajectory-level control and uniform concentration bounds that hold along the entire path.

Load-bearing premise

Inputs are drawn i.i.d. from a Gaussian distribution and labels are generated exactly by a planted linear model.

What would settle it

An experiment in which gradient descent from moderately small random initialization fails to reach the global minimizer (or converges slower than linear rate) when inputs remain i.i.d. Gaussian and labels remain exactly linear would falsify the claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Gradient descent reliably escapes the non-strict saddle points that exist in the loss landscape.
  • The algorithm achieves linear convergence once alignment is established.
  • The required number of samples is order-wise optimal for the problem.
  • The same three-phase structure explains reliable end-to-end training in inverse problems and certain auto-encoder models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The phase-based control technique may extend to deeper ReLU networks when the target remains linear.
  • Small random initialization appears to be a practical safeguard against bad stationary points when both layers are trained jointly.
  • New concentration tools would be needed to obtain comparable guarantees once the realizable Gaussian assumption is relaxed.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The paper studies gradient descent dynamics for jointly training both layers of a one-hidden-layer ReLU network to fit a linear target in a realizable setting with i.i.d. Gaussian inputs and planted linear labels. It proves that GD from moderately small random initialization converges to a global minimizer at linear rate with order-wise optimal sample complexity. The analysis proceeds via a three-phase trajectory (alignment, growth, local refinement), supported by trajectory-level control arguments that ensure escape from non-strict saddles and novel uniform concentration bounds that hold along the entire trajectory.

Significance. If the central claims hold, the work supplies a rigorous, end-to-end account of why simultaneous training of both layers succeeds in this stylized but representative inverse-problem setting. The three-phase decomposition together with the trajectory-control and uniform-concentration tools constitute a concrete technical advance that clarifies saddle avoidance and optimal sample complexity; these techniques may transfer to related architectures.

minor comments (3)
  1. [Introduction] The introduction would benefit from an explicit statement of the network width and the precise scaling of the random initialization variance before the three-phase analysis begins.
  2. [Experiments] Figure captions for the experimental panels should include the precise values of n, d, and m used in each subplot to allow direct comparison with the stated sample-complexity bounds.
  3. A short remark clarifying whether the uniform concentration statements require the trajectory to remain inside a particular norm ball would help readers track the dependence on the initialization scale.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive recommendation to accept. We are pleased that the three-phase analysis, trajectory-control arguments, and uniform concentration bounds were viewed as a concrete technical advance.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives its central claims (linear-rate convergence to global minimizer with optimal sample complexity) directly from the realizable Gaussian-input planted-linear model via a three-phase trajectory analysis, trajectory-level saddle-escape control, and novel uniform concentration bounds. These steps are constructed from the stated assumptions and new analytic arguments rather than any reduction to fitted quantities, self-citation load-bearing premises, or ansatzes imported from prior author work. No load-bearing equation or claim reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the realizable Gaussian-linear setting and the moderate-small random initialization; these are standard domain assumptions rather than new free parameters or invented entities.

axioms (2)
  • domain assumption Inputs drawn i.i.d. from a Gaussian distribution
    Explicitly stated as the data model enabling the realizable linear-target analysis.
  • domain assumption Labels follow a planted linear model
    Defines the realizable setting used throughout the convergence proof.

pith-pipeline@v0.9.1-grok · 5822 in / 1346 out tokens · 24006 ms · 2026-06-28T07:01:04.739637+00:00 · methodology

0 comments
read the original abstract

In this paper, we study the gradient descent dynamics for jointly training both layers of a one-hidden-layer ReLU network to fit a linear target function. Concretely, we consider a realizable setting where inputs are drawn i.i.d. from a Gaussian distribution and labels follow a planted linear model. This stylized framework captures salient features of end-to-end training in inverse problems and certain auto-encoder models. Despite its apparent simplicity, the dynamics remain poorly understood, in part because the loss landscape contains multiple non-strict saddle points, making it unclear why gradient descent from random initialization reliably escapes bad stationary regions. We provide a detailed characterization of the optimization landscape and prove that gradient descent from a moderately small random initialization-simultaneously training both layers-converges to a global minimizer at a linear rate with order-wise optimal sample complexity. Our analysis tracks the trajectory through three phases: an alignment phase in which hidden weights progressively align with the planted direction while the output weights maintain the correct sign pattern; a growth phase in which the norms of both layers increase while preserving alignment; and a local refinement phase in which the aligned neurons rapidly converge to the planted direction, yielding fast local convergence. To rigorously show that GD avoids non-strict saddles, we develop trajectory-level control arguments for the end-to-end dynamics. In addition, we establish novel uniform concentration results that hold along the entire trajectory, and are essential for obtaining order-wise optimal sample complexity. We corroborate our theory with extensive experiments across a range of configurations.

Figures

Figures reproduced from arXiv: 2606.04476 by Berk Tinaz, Changzhi Xie, Mahdi Soltanolkotabi.

Figure 1
Figure 1. Figure 1: GD trajectories and population loss landscape. We run gradient descent on the population loss for a one-hidden-layer ReLU network with two hidden units and fixed output weights v = [1, −1] T . Panels (a) and (b) use two different initializations of w (0) 1 and w (0) 2 . To visualize the dynamics in 2D, we plot each neuron in the plane spanned by a (black arrows indicate ±a) and a randomly chosen direction … view at source ↗
Figure 2
Figure 2. Figure 2: Trajectory of neurons for different values of k. We run gradient descent updates on the population loss. A randomly selected orthogonal direction to a is shown for the y-axis in order to visualize the neurons in 2D. Black arrows indicate ±a direction. We use colors red and blue to indicate whether vi corresponding to wi is positive or negative respectively. Points at the end of each trajectory denotes the … view at source ↗
Figure 3
Figure 3. Figure 3: Phases of GD Trajectory. We run gradient descent updates on the population loss with small initialization σ = 10−4 . We track the population loss L (blue), norms v1, ∥w1∥ (green and yellow), and the θ – i.e. angle between w1, w2 – (red). For visualization purposes θ uses the right vertical axis. v2 and ∥w2∥ behave similarly but omitted for clarity. aligned neurons then converge rapidly to the ground-truth … view at source ↗
Figure 4
Figure 4. Figure 4: ∥∇w1L∥2 + ∥∇w2L∥2 − αL is non-negative. We set α = 0.05 and draw 1 ∥w2∥ h˜ (w1, w2) for θ ∈ [0, π]. We show that 1 ∥w2∥ h˜ (w1, w2) is non-negative inside the shaded region (θ ≥ π 2 ). B.3 Bound on the Smoothness of the Population Loss (Lemma 9) We bound the population Hessian ∇2L(v,W) in the local refinement phase. That is, we assume c1 p ∥a∥ ≤ v1, v2, ∥w1∥ , ∥w2∥ ≤ c2 p ∥a∥. By the sub-additivity propert… view at source ↗
Figure 5
Figure 5. Figure 5: L(v,W) − α˜  ∥v1w1 − a∥ 2 + ∥v2w2 + a∥ 2  is non-negative. We set α˜ = 0.05 and draw 1 ∥w˜2∥ 2 h˜ (w˜1, w˜2) for θ ∈ [0, π]. We show that 1 ∥w˜2∥ 2 h˜ (w˜1, w˜2) is non-negative inside the shaded region (θ ≥ π 2 ). demonstrates that h˜ is non-negative for θ > π 2 . This finishes the proof of Lemma 13. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Pairing pattern in multi-dimensional setting. We train the network from small initialization when exactly parameterized (k = 6 and r = 3). On left (a), we depict the trajectories of individual weights in the outer layer (vi’s) across iterations. We observe that the weights at convergence can be grouped into three pairs such that one of the weights is approximately negative of the other. For instance, we ob… view at source ↗
Figure 7
Figure 7. Figure 7: Pairing pattern for r = 5. We train the network from small initialization when exactly parameterized (k = 10 and r = 5). On left (a), we depict the trajectories of individual weights in the outer layer (vi’s) across iterations. Each pair is indicated by the same color and the dashed line. A similar pairing is observed for the inner layer weights as well (b). While these vectors all lie in a higher dimensio… view at source ↗
Figure 8
Figure 8. Figure 8: Pairing pattern for r = 10. We train the network from small initialization when exactly parameterized (k = 20 and r = 10). On left (a), we depict the trajectories of individual weights in the outer layer (vi’s) across iterations. Each pair is indicated by the same color and the dashed line. A similar pairing is observed for the inner layer weights as well (b). While these vectors all lie in a higher dimens… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

63 extracted references · 6 canonical work pages · 2 internal anchors

  1. [1]

    Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks

    Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In36th International Conference on Machine Learning, ICML 2019, pages 477–502. International Machine Learning Society (IMLS), 2019

    2019

  2. [2]

    High-dimensional asymptotics of feature learning: How one gradient step improves the representation.Advances in Neural Information Processing Systems, 35:37932–37946, 2022

    Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High-dimensional asymptotics of feature learning: How one gradient step improves the representation.Advances in Neural Information Processing Systems, 35:37932–37946, 2022

    2022

  3. [3]

    Neural networks and principal component analysis: Learning from examples without local minima.Neural Networks, 2(1):53–58, 1989

    Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima.Neural Networks, 2(1):53–58, 1989

    1989

  4. [4]

    Simplicity bias and optimization threshold in two-layer relu networks, 2025

    Etienne Boursier and Nicolas Flammarion. Simplicity bias and optimization threshold in two-layer relu networks, 2025

    2025

  5. [5]

    A Bennett concentration inequality and its application to suprema of empirical processes.C

    Olivier Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes.C. R. Acad. Sci. Paris, Ser. I, 334(6):495–500, 2002

    2002

  6. [6]

    Globally optimal gradient descent for a convnet with gaussian inputs, 2017

    Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs, 2017

    2017

  7. [7]

    Candès, Xiaodong Li, and Mahdi Soltanolkotabi

    Emmanuel J. Candès, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via Wirtinger flow: theory and algorithms.IEEE Trans. Inf. Theory, 61(4):1985–2007, 2015

    1985

  8. [8]

    Nonconvex rectangular matrix completion via gradient descent without ℓ2,∞regularization.IEEE Trans

    Ji Chen, Dekai Liu, and Xiaodong Li. Nonconvex rectangular matrix completion via gradient descent without ℓ2,∞regularization.IEEE Trans. Inf. Theory, 66(9):5806–5841, 2020

    2020

  9. [9]

    Yuxin Chen and Emmanuel J. Candès. Solving random quadratic systems of equations is nearly as easy as solving linear systems.Commun. Pure Appl. Math., 70(5):822–883, 2017

    2017

  10. [10]

    Learning a neuron by a shallow relu network: Dynamics and implicit bias for correlated inputs, 2023

    Dmitry Chistikov, Matthias Englert, and Ranko Lazic. Learning a neuron by a shallow relu network: Dynamics and implicit bias for correlated inputs, 2023

    2023

  11. [11]

    On lazy training in differentiable programming.Advances in Neural Information Processing Systems, 32:2937–2947, 2019

    Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming.Advances in Neural Information Processing Systems, 32:2937–2947, 2019

    2019

  12. [12]

    Neural networks can learn representations with gradient descent

    Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. InConference on Learning Theory, pages 5413–5452. PMLR, 2022

    2022

  13. [13]

    Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity.Advances in neural information processing systems, 29, 2016

    Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity.Advances in neural information processing systems, 29, 2016

    2016

  14. [14]

    Gradient descent finds global minima of deep neural networks

    Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. InInternational Conference on Machine Learning, pages 1675–1685. PMLR, 2019

    2019

  15. [15]

    Gradient Descent Provably Optimizes Over-parameterized Neural Networks

    Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks.arXiv preprint arXiv:1810.02054, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  16. [16]

    Humus-net: Hybrid unrolled multi-scale network architecture for accelerated mri reconstruction.Advances in Neural Information Processing Systems, 35:25306–25319, 2022

    Zalan Fabian, Berk Tinaz, and Mahdi Soltanolkotabi. Humus-net: Hybrid unrolled multi-scale network architecture for accelerated mri reconstruction.Advances in Neural Information Processing Systems, 35:25306–25319, 2022

    2022

  17. [17]

    Rong Ge, Furong Huang, Chi Jin, and Yang. Yuan. Escaping from saddle points: online stochastic gradient for tensor decomposition. InProceedings of The 28th Conference on Learning Theory, pages 797–842, 2015

    2015

  18. [18]

    Matrix completion has no spurious local minimum.Advances in Neural Information Processing Systems, 29:2973–2981, 2016

    Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum.Advances in Neural Information Processing Systems, 29:2973–2981, 2016

    2016

  19. [19]

    When do neural networks outperform kernel methods?arXiv preprint arXiv:2006.13409, 2020

    Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods?arXiv preprint arXiv:2006.13409, 2020

    work page arXiv 2006

  20. [20]

    Phase retrieval under a generative prior.Advances in Neural Information Processing Systems, 31, 2018

    Paul Hand, Oscar Leong, and Vlad V oroninski. Phase retrieval under a generative prior.Advances in Neural Information Processing Systems, 31, 2018

    2018

  21. [21]

    Neural tangent kernel: Convergence and generalization in neural networks

    Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. InAdvances in neural information processing systems, pages 8571–8580, 2018

    2018

  22. [22]

    Gradient descent aligns the layers of deep linear networks, 2019

    Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks, 2019

    2019

  23. [23]

    Kakade, and Michael I

    Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape saddle points efficiently. page 1724–1732, 2017

    2017

  24. [24]

    Deep convolutional neural network for inverse problems in imaging.IEEE transactions on image processing, 26(9):4509–4522, 2017

    Kyong Hwan Jin, Michael T McCann, Emmanuel Froustey, and Michael Unser. Deep convolutional neural network for inverse problems in imaging.IEEE transactions on image processing, 26(9):4509–4522, 2017. 13

    2017

  25. [25]

    Photo-realistic single image super-resolution using a generative adversarial network

    Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al. Photo-realistic single image super-resolution using a generative adversarial network. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 4681–4690, 2017

    2017

  26. [26]

    Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit.arXiv preprint arXiv:2406.01581, 2024

    Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit.arXiv preprint arXiv:2406.01581, 2024

    work page arXiv 2024

  27. [27]

    Feature averaging: An implicit bias of gradient descent leading to non-robustness in neural networks.arXiv preprint arXiv:2410.10322, 2024

    Binghui Li, Zhixuan Pan, Kaifeng Lyu, and Jian Li. Feature averaging: An implicit bias of gradient descent leading to non-robustness in neural networks.arXiv preprint arXiv:2410.10322, 2024

    work page arXiv 2024

  28. [28]

    Rapid, robust, and reliable blind deconvolution via nonconvex optimization.Appl

    Xiaodong Li, Shuyang Ling, Thomas Strohmer, and Ke Wei. Rapid, robust, and reliable blind deconvolution via nonconvex optimization.Appl. Comput. Harmon. Anal., 47(3):893–934, 2019

    2019

  29. [29]

    Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing.Inf

    Shuyang Ling and Thomas Strohmer. Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing.Inf. Inference, 8(1):1–49, 2019

    2019

  30. [30]

    Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.Found

    Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.Found. Comput. Math., 20(3):451–632, 2020

    2020

  31. [31]

    Yurii Nesterov and Boris T. Polyak. Cubic regularization of Newton method and its global performance.Math. Program., 108(1 (A)):177–205, 2006

    2006

  32. [32]

    Jorge Nocedal and Stephen J. Wright. Trust-region methods.Numerical Optimization, pages 66–100, 2006

    2006

  33. [33]

    A function space view of bounded norm infinite width relu nets: The multivariate case.arXiv preprint arXiv:1910.01635, 2019

    Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case.arXiv preprint arXiv:1910.01635, 2019

    work page arXiv 1910

  34. [34]

    Overparameterized nonlinear learning: Gradient descent takes the shortest path? InInternational Conference on Machine Learning, pages 4951–4960

    Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? InInternational Conference on Machine Learning, pages 4951–4960. PMLR, 2019

    2019

  35. [35]

    Towards moderate overparameterization: global convergence guarantees for training shallow neural networks.IEEE Journal on Selected Areas in Information Theory, 2020

    Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks.IEEE Journal on Selected Areas in Information Theory, 2020

    2020

  36. [36]

    Grokking: Generalization beyond overfitting on small algorithmic datasets, 2022

    Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets, 2022

    2022

  37. [37]

    Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis

    Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. pages 1674–1703, 2017

    2017

  38. [38]

    Yunwei Ren, Eshaan Nichani, Denny Wu, and Jason D. Lee. Emergence and scaling laws in sgd learning of shallow neural networks, 2025

    2025

  39. [39]

    Learning relus via gradient descent.Advances in neural information processing systems, 30, 2017

    Mahdi Soltanolkotabi. Learning relus via gradient descent.Advances in neural information processing systems, 30, 2017

    2017

  40. [40]

    Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.IEEE Transactions on Information Theory, 65(2):742–769, 2018

    Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.IEEE Transactions on Information Theory, 65(2):742–769, 2018

    2018

  41. [41]

    Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing

    Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie. Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing. InProceedings of Thirty Sixth Conference on Learning Theory, pages 5140–5142. PMLR, 2023

    2023

  42. [42]

    End-to-end variational networks for accelerated mri reconstruction

    Anuroop Sriram, Jure Zbontar, Tullie Murrell, Aaron Defazio, C Lawrence Zitnick, Nafissa Yakubova, Florian Knoll, and Patricia Johnson. End-to-end variational networks for accelerated mri reconstruction. InMedical Image Computing and Computer Assisted Intervention–MICCAI 2020: 23rd International Conference, Lima, Peru, October 4–8, 2020, Proceedings, Part...

    2020

  43. [43]

    Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction

    Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. InAdvances in Neural Information Processing Systems, pages 23831–23843. Curran Associates, Inc., 2021

    2021

  44. [44]

    When Are Nonconvex Problems Not Scary?

    Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary?arXiv preprint arXiv:1510.06096, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  45. [45]

    A geometric analysis of phase retrieval.Found

    Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval.Found. Comput. Math., 18(5): 1131–1198, 2018

    2018

  46. [46]

    Low-rank solutions of linear matrix equations via procrustes flow

    Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. InInternational Conference on Machine Learning, pages 964–973. PMLR, 2016. 14

    2016

  47. [47]

    Van der Vaart and Jon A

    Aad W. Van der Vaart and Jon A. Wellner.Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, New York, NY , 1996

    1996

  48. [48]

    Learning a single neuron with bias using gradient descent, 2022

    Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning a single neuron with bias using gradient descent, 2022

    2022

  49. [49]

    Wainwright.High-dimensional statistics

    Martin J. Wainwright.High-dimensional statistics. Cambridge University Press, Cambridge, 2019. A non- asymptotic viewpoint

    2019

  50. [50]

    Image inpainting via generative multi-column convolutional neural networks.Advances in neural information processing systems, 31, 2018

    Yi Wang, Xin Tao, Xiaojuan Qi, Xiaoyong Shen, and Jiaya Jia. Image inpainting via generative multi-column convolutional neural networks.Advances in neural information processing systems, 31, 2018

    2018

  51. [51]

    Large learning rate tames homogeneity: Convergence and balancing effect, 2022

    Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames homogeneity: Convergence and balancing effect, 2022

    2022

  52. [52]

    Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult, 2023

    Yuqing Wang, Zhenghao Xu, Tuo Zhao, and Molei Tao. Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult, 2023

    2023

  53. [53]

    Chenwei Wu, Jiajun Luo, and Jason D. Lee. No spurious local minima in a two hidden unit reLU network, 2018

    2018

  54. [54]

    Weihang Xu and Simon S. Du. Over-parameterization exponentially slows down gradient descent for learning a single neuron, 2023

    2023

  55. [55]

    Learning a single neuron with gradient methods, 2022

    Gilad Yehudai and Ohad Shamir. Learning a single neuron with gradient methods, 2022

    2022

  56. [56]

    Zhang, Somayeh Sojoudi, and Javad Lavaei

    Richard Y . Zhang, Somayeh Sojoudi, and Javad Lavaei. Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery.J. Mach. Learn. Res., 20(114):1–34, 2019

    2019

  57. [57]

    Learning one-hidden-layer relu networks via gradient descent, 2018

    Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer relu networks via gradient descent, 2018

    2018

  58. [58]

    A hitting time analysis of stochastic gradient langevin dynamics

    Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. InProceedings of the 2017 Conference on Learning Theory, pages 1980–2022. PMLR, 2017

    2017

  59. [59]

    Bartlett, and Inderjit S

    Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one- hidden-layer neural networks, 2017

    2017

  60. [60]

    How gradient descent balances features: A dynamical analysis for two-layer neural networks

    Zhenyu Zhu, Fanghui Liu, and V olkan Cevher. How gradient descent balances features: A dynamical analysis for two-layer neural networks. InThe Thirteenth International Conference on Learning Representations, 2025. 15 A Useful Calculations In this section we provide the derivation of several useful identities. A.1 Population Loss Leta,b∈R d be two arbitrar...

    2025

  61. [61]

    Here we use the fact that µv2 1 ≤c 0c2 2 ≤ 1

    Using Inequality (29), we have w(τ+1) 1 ≥ ∥w1∥ −µ v1∇v1 bL ∥w1∥ ≥ ∥w1∥ − µv2 1 2 ∥w1∥ ≥ ∥w1∥ − 1 4 ∥w1∥ =3 4 ∥w1∥. Here we use the fact that µv2 1 ≤c 0c2 2 ≤ 1

  62. [62]

    As a result, the sum v1 +∥w 1∥ will increase by a factor 1 + 1 8 µ∥a∥ as long as v1 ∥w1∥< 1 4 ∥a∥

    Thus, we have v(τ+1) 1 ∥w1∥(τ+1) ≥ 3 4 v1 · 3 4 ∥w1∥ ≥ 1 2 v1 ∥w1∥ ≥ 1 4 ∥a∥. As a result, the sum v1 +∥w 1∥ will increase by a factor 1 + 1 8 µ∥a∥ as long as v1 ∥w1∥< 1 4 ∥a∥. Once we have v1 ∥w1∥ ≥ 1 4 ∥a∥ at some iteration, it remains bounded below by 1 4 ∥a∥. By Lemma 6, v(T1) 1 + w(T1) 1 ≥ c3σ≥ 1 4 σ. Consequently, after T2 =⌈ c8 µ∥a∥ ln √ ∥a∥ σ ⌉ it...

  63. [63]

    v(τ) 1 v(τ) 2 #! W (τ) −W 2 F . 45 By further upper bounding the right-hand side using the fact that the ReLU activation is 1-Lipschitz, we have L θ(T) ≤ diag

    We have L θ(τ+1) ≤ 1−αc 2 min¯µ 3 4 −¯µL + 4¯µ 3 + ¯µ2L 80c2 maxδ2 L θ(τ) = 1− 3αc2 min 4 − 320c2 maxδ2 3 ¯µ+ αc2 min + 80c2 maxδ2 L¯µ2 L θ(τ) . We now choose δ and ¯µso that the quadratic factor above yields a strict contraction. First require that the linear coefficient is positive, i.e. δ2 ≤ 9αc2 min 1280c2max . Fix any suchδ(this is ensured by Lemma 1...