Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks

References

• [1] Arora S, Cohen N, Golowich N, Hu W (2019) A convergence analysis of gradient descent for deep linear neural networks. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [2] Arora S, Cohen N, Hu W, Luo Y (2019) Implicit regularization in deep matrix factorization. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 7411–7422.Google Scholar
• [3] Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programming 116(1):5–16.Crossref, Google Scholar
• [4] Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel methods. Math. Programming 137(1):91–129.Crossref, Google Scholar
• [5] Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2):438–457.Link, Google Scholar
• [6] Bah B, Rauhut H, Terstiege U, Westdickenberg M (2022) Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. Inform. Inference 11(1):307–353.Crossref, Google Scholar
• [7] Bartlett P, Helmbold D, Long P (2018) Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 521–530.Google Scholar
• [8] Beck A (2017) First-Order Methods in Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [9] Behling R, Iusem A (2013) The effect of calmness on the solution set of systems of nonlinear equations. Math. Programming 137(1):155–165.Crossref, Google Scholar
• [10] Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146(1):459–494.Crossref, Google Scholar
• [11] Chen P, Jiang R, Wang P (2026) A complete loss landscape analysis of regularized deep matrix factorization. SIAM J. Optim. Forthcoming.Crossref, Google Scholar
• [12] Chitour Y, Liao Z, Couillet R (2023) A geometric approach of gradient descent algorithms in linear neural networks. Math. Control Related Fields 13(3):918–945.Crossref, Google Scholar
• [13] De Handschutter P, Gillis N, Siebert X (2021) A survey on deep matrix factorizations. Comput. Sci. Rev. 42:100423.Crossref, Google Scholar
• [14] Dominé CCJ, Anguita N, Proca AM, Braun L, Kunin D, Mediano PAM, Saxe AM (2025) From lazy to rich: Exact learning dynamics in deep linear networks. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [15] Drusvyatskiy D, Lewis AS (2018) Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3):919–948.Link, Google Scholar
• [16] Du S, Hu W (2019) Width provably matters in optimization for deep linear neural networks. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (PMLR, New York), 1655–1664.Google Scholar
• [17] Du SS, Zhai X, Poczos B, Singh A (2019) Gradient descent provably optimizes over-parameterized neural networks. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [18] Esteva A, Robicquet A, Ramsundar B, Kuleshov V, DePristo M, Chou K, Cui C, Corrado G, Thrun S, Dean J (2019) A guide to deep learning in healthcare. Nature Med. 25(1):24–29.Crossref, Google Scholar
• [19] Frei S, Gu Q (2021) Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems 34 (Curran Associates, Red Hook, NY), 7937–7949.Google Scholar
• [20] Han XY, Papyan V, Donoho DL (2022) Neural collapse under MSE loss: Proximity to and dynamics on the central path. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [21] Hanin B (2019) Universal function approximation by deep neural nets with bounded width and ReLU activations. Mathematics 7(10):992.Crossref, Google Scholar
• [22] He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. Proc. IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 770–778.Google Scholar
• [23] Horn R, Johnson C (2012) Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [24] Hu W, Xiao L, Pennington J (2020) Provable benefit of orthogonal initialization in optimizing deep linear networks. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [25] Hu EJ, Shen Y, Wallis P, Allen-Zhu Z, Li Y, Wang S, Wang L, Chen W (2022) LoRA: Low-rank adaptation of large language models. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [26] Jiang R, Li D (2019) Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29(2):1603–1633.Crossref, Google Scholar
• [27] Jiang R, Li X (2022) Hölderian error bounds and Kurdyka-Łojasiewicz inequality for the trust region subproblem. Math. Oper. Res. 47(4):3025–3050.Link, Google Scholar
• [28] Kingma DP, Ba J (2014) Adam: A method for stochastic optimization. Preprint, submitted December 22, https://arxiv.org/abs/1412.6980v1.Google Scholar
• [29] Krizhevsky A, Sutskever I, Hinton GE (2012) ImageNet classification with deep convolutional neural networks. Pereira F, Burges CJ, Bottou L, Weinberger K, eds. Adv. Neural Inform. Processing Systems, vol. 25 (Curran Associates, Red Hook, NY), 1106–1114.Google Scholar
• [30] Laurent T, von Brecht J (2018) Deep linear networks with arbitrary loss: All local minima are global. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 2902–2907.Google Scholar
• [31] Lee JD, Panageas I, Piliouras G, Simchowitz M, Jordan MI, Recht B (2019) First-order methods almost always avoid strict saddle points. Math. Programming 176(1–2):311–337.Crossref, Google Scholar
• [32] Li G, Pong TK (2018) Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods. Foundations Comput. Math. 18(5):1199–1232.Crossref, Google Scholar
• [33] Li G, Mordukhovich B, Zhu J (2024) Generalized metric subregularity with applications to high-order regularized Newton methods. Preprint, submitted June 19, https://arxiv.org/abs/2406.13207.Google Scholar
• [34] Liao FY, Ding L, Zheng Y (2024) Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. Abate A, Cannon M, Margellos K, Papachristodoulou A, eds. Proc. 6th Annual Learn. Dynam. Control Conf., Proceedings of Machine Learning Research, vol. 242 (PMLR, New York), 993–1005.Google Scholar
• [35] Liu H, So AMC, Wu W (2019) Quadratic optimization with orthogonality constraint: Explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods. Math. Programming 178(1):215–262.Crossref, Google Scholar
• [36] Luo ZQ, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: A general approach. Ann. Oper. Res. 46(1):157–178.Crossref, Google Scholar
• [37] Nguegnang GM, Rauhut H, Terstiege U (2024) Convergence of gradient descent for learning linear neural networks. Adv. Continuous Discrete Models 2024(1):23.Crossref, Google Scholar
• [38] Pang JS (1997) Error bounds in mathematical programming. Math. Programming 79(1):299–332.Crossref, Google Scholar
• [39] Polyak BT (1963) Gradient methods for the minimisation of functionals. USSR Comput. Math. Math. Phys. 3(4):864–878.Crossref, Google Scholar
• [40] Raghu M, Poole B, Kleinberg J, Ganguli S, Sohl-Dickstein J (2017) On the expressive power of deep neural networks. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (PMLR, New York), 2847–2854.Google Scholar
• [41] Rebjock Q, Boumal N (2024) Fast convergence to non-isolated minima: Four equivalent conditions for C2 functions. Math. Programming 213(1–2):151–199.Crossref, Google Scholar
• [42] Stewart GW, Sun JG (1990) Matrix Perturbation Theory (Academic Press, New York).Google Scholar
• [43] Tao T, Pan S, Bi S (2021) Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization. J. Global Optim. 81(4):991–1017.Crossref, Google Scholar
• [44] Trigeorgis G, Bousmalis K, Zafeiriou S, Schuller BW (2016) A deep matrix factorization method for learning attribute representations. IEEE Trans. Pattern Anal. Machine Intelligence 39(3):417–429.Crossref, Google Scholar
• [45] Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser L, Polosukhin I (2017) Attention is all you need. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates, Red Hook, NY), 5998–6008.Google Scholar
• [46] Wang P, Liu H, So AMC (2023) Linear convergence of a proximal alternating minimization method with extrapolation for ℓ1-norm principal component analysis. SIAM J. Optim. 33(2):684–712.Crossref, Google Scholar
• [47] Wang P, Liu H, Yaras C, Balzano L, Qu Q (2022) Linear convergence analysis of neural collapse with unconstrained features. OPT 2022 Optim. Machine Learn. (NeurIPS Workshop).Google Scholar
• [48] Wu L, Wang Q, Ma C (2019) Global convergence of gradient descent for deep linear residual networks. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 13368–13377.Google Scholar
• [49] Yaras C, Wang P, Balzano L, Qu Q (2024) Compressible dynamics in deep overparameterized low-rank learning and adaptation. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (PMLR, New York), 56946–56965.Google Scholar
• [50] Yu Y, Wang T, Samworth RJ (2015) A useful variant of the Davis–Kahan theorem for statisticians. Biometrika 102(2):315–323.Crossref, Google Scholar
• [51] Yue MC, Zhou Z, So AMC (2019) A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property. Math. Programming 174(1):327–358.Crossref, Google Scholar
• [52] Zhang C, Bengio S, Hardt M, Recht B, Vinyals O (2021) Understanding deep learning (still) requires rethinking generalization. Comm. ACM 64(3):107–115.Crossref, Google Scholar
• [53] Zhang Q, Chen C, Liu H, Zhou Z, So AMC (2025) On the linear convergence of the ADMM for regularized non-convex low-rank matrix recovery. Unpublished manuscript. The Chinese University of Hong Kong, Sha Tin, New Territories, Hong Kong.Google Scholar
• [54] Zhou Z, So AMC (2017) A unified approach to error bounds for structured convex optimization problems. Math. Programming 165(2):689–728.Crossref, Google Scholar
• [55] Zhou J, Li X, Ding T, You C, Qu Q, Zhu Z (2022) On the optimization landscape of neural collapse under MSE loss: Global optimality with unconstrained features. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (PMLR, New York), 27179–27202.Google Scholar