Oracle Complexities of Augmented Lagrangian Methods for Nonsmooth Composite Optimization on a Compact Submanifold

References

• [1] Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [2] Aybat N, Iyengar G (2012) A first-order augmented Lagrangian method for compressed sensing. SIAM J. Optim. 22(2):429–459.Crossref, Google Scholar
• [3] Beck A, Rosset I (2023) A dynamic smoothing technique for a class of nonsmooth optimization problems on manifolds. SIAM J. Optim. 33(3):1473–1493.Crossref, Google Scholar
• [4] Bento GC, Ferreira OP, Melo JG (2017) Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds. J. Optim. Theory Appl. 173(2):548–562.Crossref, Google Scholar
• [5] Böhm A, Wright SJ (2021) Variable smoothing for weakly convex composite functions. J. Optim. Theory Appl. 188(3):628–649.Crossref, Google Scholar
• [6] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [7] Boumal N, Absil PA, Cartis C (2019) Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numer. Anal. (Oxford) 39(1):1–33.Crossref, Google Scholar
• [8] Burer S, Monteiro RD (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2):329–357.Crossref, Google Scholar
• [9] Carmon Y, Duchi JC, Hinder O, Sidford A (2018) Accelerated methods for nonconvex optimization. SIAM J. Optim. 28(2):1751–1772.Crossref, Google Scholar
• [10] Chen S, Ma S, Man-Cho So A, Zhang T (2020) Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM J. Optim. 30(1):210–239.Crossref, Google Scholar
• [11] Chen S, Ma S, Xue L, Zou H (2020) An alternating manifold proximal gradient method for sparse principal component analysis and sparse canonical correlation analysis. INFORMS J. Optim. 2(3):192–208.Link, Google Scholar
• [12] Cutkosky A, Mehta H (2021) High-probability bounds for non-convex stochastic optimization with heavy tails. Adv. Neural Inf. Process. Syst. 34:4883–4895.Google Scholar
• [13] Cutkosky A, Orabona F (2019) Momentum-based variance reduction in non-convex SGD. Adv. Neural Inf. Process. Syst. 32:15236–15245.Google Scholar
• [14] Deng K, Peng Z (2023) A manifold inexact augmented Lagrangian method for nonsmooth optimization on Riemannian submanifolds in Euclidean space. IMA J. Numer. Anal. (Oxford) 43(3):1653–1684.Crossref, Google Scholar
• [15] Deng K, Peng Z (2024) Trace LASSO regularization for adaptive sparse canonical correlation analysis via manifold optimization approach. J. Oper. Res. Soc. China 12(3):573–599.Crossref, Google Scholar
• [16] Deng Z, Deng K, Hu J, Wen Z (2025) An augmented Lagrangian primal-dual semismooth Newton method for multi-block composite optimization. J. Sci. Comput. 102(3):1–30.Crossref, Google Scholar
• [17] Ferreira O, Oliveira P (1998) Subgradient algorithm on Riemannian manifolds. J. Optim. Theory Appl. 97(1):93–104.Crossref, Google Scholar
• [18] Ferreira OP, Louzeiro MS, Prudente L (2019) Iteration-complexity of the subgradient method on Riemannian manifolds with lower bounded curvature. Optimization 68(4):713–729.Crossref, Google Scholar
• [19] Ghadimi S, Lan G (2016) Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program. 156(1–2):59–99.Crossref, Google Scholar
• [20] Grave E, Obozinski GR, Bach F (2011) Trace LASSO: A trace norm regularization for correlated designs. Adv. Neural Inf. Process. Syst. 24:2187–2195.Google Scholar
• [21] Han A, Gao J (2020) Riemannian stochastic recursive momentum method for non-convex optimization. Preprint, submitted August 11, https://arxiv.org/abs/2008.04555.Google Scholar
• [22] Hosseini S, Huang W, Yousefpour R (2018) Line search algorithms for locally Lipschitz functions on Riemannian manifolds. SIAM J. Optim. 28(1):596–619.Crossref, Google Scholar
• [23] Hosseini S, Uschmajew A (2017) A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim. 27(1):173–189.Crossref, Google Scholar
• [24] Hotelling H (1992) Relations between two sets of variates. Breakthroughs in Statistics: Methodology and Distribution (Springer, New York), 162–190.Crossref, Google Scholar
• [25] Hu J, Liu X, Wen ZW, Yuan YX (2020) A brief introduction to manifold optimization. J. Oper. Res. Soc. China 8(2):199–248.Crossref, Google Scholar
• [26] Huang W, Wei K (2022) Riemannian proximal gradient methods. Math. Program. 194(1):371–413.Crossref, Google Scholar
• [27] Huang W, Wei K (2023) An inexact Riemannian proximal gradient method. Comput. Optim. Appl. 85(1):1–32.Crossref, Google Scholar
• [28] Jiang B, Meng X, Wen Z, Chen X (2023) An exact penalty approach for optimization with nonnegative orthogonality constraints. Math. Program. 198(1):855–897.Crossref, Google Scholar
• [29] Jolliffe IT, Trendafilov NT, Uddin M (2003) A modified principal component technique based on the LASSO. J. Comput. Graph. Statist. 12(3):531–547.Crossref, Google Scholar
• [30] Kong W, Melo JG, Monteiro RD (2019) Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM J. Optim. 29(4):2566–2593.Crossref, Google Scholar
• [31] Laguel Y, Aybat NS, Gürbüzbalaban M (2024) High probability and risk-averse guarantees for a stochastic accelerated primal-dual method. J. Mach. Learn. Res. 25(421):1–56.Google Scholar
• [32] Lan G, Monteiro RD (2016) Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Math. Program. 155(1):511–547.Crossref, Google Scholar
• [33] LeCun Y (1998) The mnist database of handwritten digits. Accessed January 19, 2025, http://yann.lecun.com/exdb/mnist/.Google Scholar
• [34] Li J, Ma S, Srivastava T (2024) A Riemannian alternating direction method of multipliers. Math. Oper. Res., ePub ahead of print December 20, https://doi.org/10.1287/moor.2023.0068.Link, Google Scholar
• [35] Li X, Chen S, Deng Z, Qu Q, Zhu Z, Man-Cho So A (2021) Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM J. Optim. 31(3):1605–1634.Crossref, Google Scholar
• [36] Li X, Orabona F (2020) A high probability analysis of adaptive SGD with momentum. Preprint, submitted July 28, https://arxiv.org/abs/2007.14294.Google Scholar
• [37] Li X, Sun D, Toh KC (2018) A highly efficient semismooth Newton augmented Lagrangian method for solving LASSO problems. SIAM J. Optim. 28(1):433–458.Crossref, Google Scholar
• [38] Li Z, Chen PY, Liu S, Lu S, Xu Y (2021) Rate-improved inexact augmented Lagrangian method for constrained nonconvex optimization. Internat. Conf. Artificial Intelligence Statist. (PMLR), 2170–2178.Google Scholar
• [39] Li Z, Chen PY, Liu S, Lu S, Xu Y (2024) Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization. Comput. Optim. Appl. 87(1):117–147.Crossref, Google Scholar
• [40] Lin Q, Ma R, Xu Y (2019) Inexact proximal-point penalty methods for constrained non-convex optimization. Preprint, submitted August 30, https://arxiv.org/abs/1908.11518.Google Scholar
• [41] Lu Z, Zhou Z (2023) Iteration-complexity of first-order augmented Lagrangian methods for convex conic programming. SIAM J. Optim. 33(2):1159–1190.Crossref, Google Scholar
• [42] Nene SA, Nayar SK, Murase H (1996) Columbia object image library (coil-20). Technical report, Department of Computer Science, Columbia University, New York.Google Scholar
• [43] Peng Z, Wu W, Hu J, Deng K (2023) Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space. Appl. Math. Optim. 88(3):1–32.Crossref, Google Scholar
• [44] Sahin MF, Eftekhari A, Alacaoglu A, Latorre F, Cevher V (2019) An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints. Adv. Neural Inf. Process. Syst. 32:13966–13978.Google Scholar
• [45] Sato H (2021) Riemannian Optimization and Its Applications (Springer Cham, Cham, Switzerland).Crossref, Google Scholar
• [46] Wang B, Ma S, Xue L (2022) Riemannian stochastic proximal gradient methods for nonsmooth optimization over the Stiefel manifold. J. Mach. Learn. Res. 23(106):1–33.Google Scholar
• [47] Wang Y, Deng K, Liu H, Wen Z (2023) A decomposition augmented Lagrangian method for low-rank semidefinite programming. SIAM J. Optim. 33(3):1361–1390.Crossref, Google Scholar
• [48] Xu Y (2021) First-order methods for constrained convex programming based on linearized augmented Lagrangian function. INFORMS J. Optim. 3(1):89–117.Link, Google Scholar
• [49] Xu Y (2021) Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming. Math. Program. 185(2):199–244.Crossref, Google Scholar
• [50] Zass R, Shashua A (2006) Nonnegative sparse PCA. Adv. Neural Inf. Process. Syst. 19:1561–1568.Google Scholar
• [51] Zhang J, Lin H, Jegelka S, Sra S, Jadbabaie A (2020) Complexity of finding stationary points of nonconvex nonsmooth functions. Internat. Conf. Machine Learn. (PMLR, New York), 11173–11182.Google Scholar
• [52] Zhou Y, Bao C, Ding C, Zhu J (2023) A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds. Math. Program. 201(1):1–61.Crossref, Google Scholar