Uniformly Optimal and Parameter-Free First-Order Methods for Convex and Function-Constrained Optimization

References

• Aravkin AY, Burke JV, Drusvyatskiy D, Friedlander MP, Roy S (2019) Level-set methods for convex optimization. Math. Programming 174:359–390.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2005) Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Programming 102:407–456.Crossref, Google Scholar
• Bolte J, Nguyen TP, Peypouquet J, Suter BW (2017) From error bounds to the complexity of first-order descent methods for convex functions. Math. Programming 165:471–507.Crossref, Google Scholar
• Boob D, Deng Q, Lan G (2023) Stochastic first-order methods for convex and nonconvex functional constrained optimization. Math. Programming 197:215–279.Crossref, Google Scholar
• Boob D, Deng Q, Lan G (2025) Level constrained first order methods for function constrained optimization. Math. Programming 209:1–61.Crossref, Google Scholar
• Boyd JPS (2014) Subgradient methods. Notes for EE364b, Stanford University, Spring 2013–14.Google Scholar
• Burke JV, Ferris MC (1993) Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31(5):1340–1359.Crossref, Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145.Crossref, Google Scholar
• Cheng Y, Lan G, Romeijn HE (2022) Functional constrained optimization for risk aversion and sparsity control. Preprint, submitted October 11, https://arxiv.org/abs/2210.05108.Google Scholar
• Cotter A, Jiang H, Gupta M, Wang S, Narayan T, You S, Sridharan K (2019) Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. J. Machine Learn. Res. 20(172):1–59.Google Scholar
• Davis D, Drusvyatskiy D, MacPhee KJ, Paquette C (2018) Subgradient methods for sharp weakly convex functions. J. Optim. Theory Appl. 179:962–982.Crossref, Google Scholar
• de Oliveira W, Sagastizábal C (2014) Level bundle methods for oracles with on-demand accuracy. Optim. Methods Software 29(6):1180–1209.Crossref, Google Scholar
• Deng Q, Lan G, Lin Z (2026) Uniformly optimal and parameter-free first-order methods for convex and function-constrained optimization. https://doi.org/10.1287/ijoc.2025.1177.cd, https://github.com/INFORMSJoC/2025.1177.Google Scholar
• Devanathan N, Boyd S (2024) Polyak minorant method for convex optimization. J. Optim. Theory Appl. 203:2263–2282.Crossref, Google Scholar
• Frangioni A (2020) Standard bundle methods: Untrusted models and duality. Bagirov AM, Gaudioso M, Karmitsa N, Mäkelä MM, Taheri S, eds. Numerical Nonsmooth Optimization (Springer, Berlin), 61–116.Crossref, Google Scholar
• Guyon I, Gunn S, Ben-Hur A, Gideon D (2008) Arcene (UCI Machine Learning Repository, Irvine, CA).Google Scholar
• Hamedani EY, Aybat NS (2021) A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM J. Optim. 31(2):1299–1329.Crossref, Google Scholar
• Hazan E, Kakade S (2019) Revisiting the Polyak step size. Preprint, submitted May 1, https://arxiv.org/abs/1905.00313.Google Scholar
• 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
• Kiwiel KC (1995) Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Math. Programming 69(1):89–109.Crossref, Google Scholar
• Koklu M, Özkan IA (2020) Multiclass classification of dry beans using computer vision and machine learning techniques. Comput. Electronics Agriculture 174:105507.Crossref, Google Scholar
• Lan G (2015) Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Math. Programming 149(1–2):1–45.Crossref, Google Scholar
• Lan G (2020) First-Order and Stochastic Optimization Methods for Machine Learning (Springer, Berlin).Crossref, Google Scholar
• Lan G, Monteiro RDC (2013) Iteration-complexity of first-order penalty methods for convex programming. Math. Programming 138:115–139.Google Scholar
• Lan G, Li T, Xu Y (2024) Projected gradient methods for nonconvex and stochastic optimization: New complexities and auto-conditioned stepsizes. Preprint, submitted December 18, https://arxiv.org/abs/2412.14291.Google Scholar
• Lemaréchal C, Nemirovski AS, Nesterov YE (1995) New variants of bundle methods. Math. Programming 69:111–148.Crossref, Google Scholar
• Li G (2013) Global error bounds for piecewise convex polynomials. Math. Programming 137(1):37–64.Crossref, Google Scholar
• Li T, Lan G (2023) A simple uniformly optimal method without line search for convex optimization. Preprint, submitted October 16, https://arxiv.org/abs/2310.10082.Google Scholar
• Lin Z, Deng Q (2024) Faster accelerated first-order methods for convex optimization with strongly convex function constraints. Adv. Neural Inform. Processing Systems 37:77409–77444.Google Scholar
• Lin Q, Nadarajah S, Soheili N (2018) A level-set method for convex optimization with a feasible solution path. SIAM J. Optim. 28(4):3290–3311.Crossref, Google Scholar
• Loizou N, Vaswani S, Laradji IH, Lacoste-Julien S (2021) Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 1306–1314.Google Scholar
• MOSEK ApS (2019) MOSEK optimization toolbox for MATLAB. User’s Guide and Reference Manual, Version 4(1).Google Scholar
• Necoara I, Nesterov Y, Glineur F (2019) Linear convergence of first order methods for non-strongly convex optimization. Math. Programming 175(1–2):69–107.Crossref, Google Scholar
• Nesterov Y (1983) A method for solving the convex programming problem with convergence rate o (1/k2). Dokl Akad Nauk SSSR 269:543.Google Scholar
• Nesterov Y (2015) Universal gradient methods for convex optimization problems. Math. Programming 152(1):381–404.Crossref, Google Scholar
• Nesterov Y (2018) Lectures on Convex Optimization, 2nd ed. (Springer, Berlin).Crossref, Google Scholar
• Polyak BT (1987) Introduction to Optimization (Optimization Software, New York).Google Scholar
• Rigollet P, Tong X (2011) Neyman-Pearson classification, convexity and stochastic constraints. J. Machine Learn. Res. 12(86):2831–2855.Google Scholar
• Rodomanov A, Kavis A, Wu Y, Antonakopoulos K, Cevher V (2024) Universal gradient methods for stochastic convex optimization. Forty-First Internat. Conf. Machine Learn., vol. 235 (PMLR, New York), 42620–42646.Google Scholar
• Tang C, Li Y, Jian J, Zheng H (2022) A new restricted memory level bundle method for constrained convex nonsmooth optimization. Optim. Lett. 16(8):2405–2434.Crossref, Google Scholar
• Tong X, Feng Y, Zhao A (2016) A survey on Neyman-Pearson classification and suggestions for future research. WIREs Comput. Statist. 8(2):64–81.Crossref, Google Scholar
• Tseng P (2008) On accelerated proximal gradient methods for convex-concave optimization. Technical report, Department of Mathematics, University of Washington, Seattle.Google Scholar
• van Ackooij W, de Oliveira W (2014) Level bundle methods for constrained convex optimization with various oracles. Comput. Optim. Appl. 57:555–597.Crossref, Google Scholar
• Xu Y (2021) Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming. Math. Programming 185:199–244.Crossref, Google Scholar
• Zhang Z, Lan G (2022) Solving convex smooth function constrained optimization is almost as easy as unconstrained optimization. Preprint, submitted October 11, https://arxiv.org/abs/2210.05807.Google Scholar