mlsanityData to 7 Oct 2026

Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution

arXiv 2207.07612 ↗First posted 15 Jul 2022cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

This work characterizes the effect of depth on the optimization landscape of linear regression, showing that, despite their nonconvexity, deeper models have more desirable optimization landscape. We consider a robust and over-parameterized setting, where a subset of measurements are grossly corrupted with noise and the true linear model is captured via an N-layer linear neural network. On the negative side, we show that this problem textitdoes not have a benign landscape: given any N≥ 1, with constant probability, there exists a solution corresponding to the ground truth that is neither local nor global minimum. However, on the positive side, we prove that, for any N-layer model with N≥ 2, a simple sub-gradient method becomes oblivious to such ``problematic'' solutions; instead, it converges to a balanced solution that is not only close to the ground truth but also enjoys a flat local landscape, thereby eschewing the need for "early stopping". Lastly, we empirically verify that the desirable optimization landscape of deeper models extends to other robust learning tasks, including deep matrix recovery and deep ReLU networks with ℓ1-loss.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 29 of its 43 references that are in the map. First posted on arXiv 15 Jul 2022.

Builds on

29 of 43 references.

References · 29

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2021On the Opportunities and Risks of Foundation Modelscited by 3,961
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  5. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  6. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  7. 2016Benefits of depth in neural networkscited by 248
  8. 2016Deep Learning without Poor Local Minimacited by 233
  9. 2018Sensitivity and Generalization in Neural Networks: an Empirical Studycited by 187
  10. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  11. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  12. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
17 more
  1. 2020Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Taskscited by 137
  2. 2015Best Subset Selection via a Modern Optimization Lenscited by 99
  3. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  4. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  5. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  6. 2019Implicit Regularization for Optimal Sparse Recoverycited by 78
  7. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  8. 2019Width Provably Matters in Optimization for Deep Linear Neural Networkscited by 52
  9. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  10. 2021Implicit Sparse Regularization: The Impact of Depth and Early Stoppingcited by 30
  11. 2021More is Less: Inducing Sparsity via Overparameterizationcited by 22
  12. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  13. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  14. 2017Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is lowcited by 17
  15. 2021Optimization-Based Separations for Neural Networkscited by 17
  16. 2018Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysiscited by 13
  17. 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 0; 2026: 1.

3 papers.

  1. 2023Mitigating Label Noise through Data Ambiguationcited by 10
  2. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4
  3. 2026Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Ratecited by 0