The stochastic gradient methods have been widely used in machine learning, but most existing works aim for unconstrained or simple constrained problems. In this paper, we consider the nonconvex stochastic programs with many functional convex constraints. The deterministic augmented Lagrangian method is a classic algorithm for such problems, but the requirement of accurate gradient information makes the method impractical for the case with large-scale constraints. To solve such problems, we propose a novel stochastic augmented Lagrangian method, which is called CSALM(composite stochastic augmented Lagrangian method). The CSALM uses a stochastic gradient to approximate the accurate gradient, and it only samples stochastic gradients and batches constraint gradient per iteration. We establish the convergence theory of CSALM and show that the CSALM can find an $\epsilon$-KKT point after $\mathcal{O}\left(\epsilon^{-8}\right)$ iterations. The numerical experiments on the multi-class Neyman-Pearson classification problem(mNPC) demonstrate the efficiency of CSALM.
ZHAO Wenshen
,
HAN Congying
,
JIN Lingzi
. Stochastic augmented Lagrangian method for stochastic nonconvex nonsmooth programs with many convex constraints[J]. Journal of University of Chinese Academy of Sciences, 2025
, 42(1)
: 26
-42
.
DOI: 10.7523/j.ucas.2023.055
[1] Li S Y, Sun Y N, Yen G G, et al. Automatic design of convolutional neural network architectures under resource constraints[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021:1-15. DOI: 10.1109/TNNLS.2021.3123105.
[2] Campi M C, Garatti S. A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality[J]. Journal of Optimization Theory and Applications, 2011, 148(2): 257-280. DOI: 10.1007/s10957-010-9754-6.
[3] Calafiore G, Campi M C. Uncertain convex programs: Randomized solutions and confidence levels[J]. Mathematical Programming, 2005, 102(1): 25-46. DOI: 10.1007/s10107-003-0499-y.
[4] Seri R, Choirat C. Scenario approximation of robust and chance-constrained programs[J]. Journal of Optimization Theory and Applications, 2013, 158(2): 590-614. DOI: 10.1007/s10957-012-0230-3.
[5] Wang M D, Bertsekas D P. Stochastic first-order methods with random constraint projection[J]. SIAM Journal on Optimization, 2016, 26(1): 681-717. DOI: 10.1137/130931278.
[6] Wang M D, Chen Y C, Liu J L, et al. Random multi-constraint projection: stochastic gradient methods for convex optimization with many constraints[EB/OL]. 2015: arXiv: 1511.03760. (2015-11-12)[2023-01-16]. https://arxiv.org/abs/1511.03760.
[7] Lan G H, Zhou Z Q. Algorithms for stochastic optimization with function or expectation constraints[J]. Computational Optimization and Applications, 2020, 76(2): 461-498. DOI: 10.1007/s10589-020-00179-x.
[8] Nocedal J, Wright S J. Numerical optimization: springer series in operations research and financial engineering[M]. New York, NY: Springer New York, 2006: 529-562.
[9] Lin Q H, Nadarajah S, Soheili N. A level-set method for convex optimization with a feasible solution path[J]. SIAM Journal on Optimization, 2018, 28(4): 3290-3311. DOI: 10.1137/17M1152334.
[10] Lin Q H, Ma R C, Yang T B. Level-set methods for finite-sum constrained convex optimization[C/OL]//Proceedings of the 35th International Conference on Machine Learning: Vol 80. PMLR, 2018: 3112-3121. https://proceedings.mlr.press/v80/lin18c.html.
[11] Aravkin A Y, Burke J V, Drusvyatskiy D, et al. Level-set methods for convex optimization[J]. Mathematical Programming, 2019, 174(1): 359-390. DOI: 10.1007/s10107-018-1351-8.
[12] Boob D, Deng Q, Lan G H. Stochastic first-order methods for convex and nonconvex functional constrained optimization[J]. Mathematical Programming, 2023, 197(1): 215-279. DOI: 10.1007/s10107-021-01742-y.
[13] Xu Y Y. Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming[J]. Mathematical Programming, 2021, 185(1): 199-244. DOI: 10.1007/s10107-019-01425-9.
[14] Xu Y Y. Primal-dual stochastic gradient method for convex programs with many functional constraints[J]. SIAM Journal on Optimization, 2020, 30(2): 1664-1692. DOI: 10.1137/18M1229869.
[15] Rockafellar R T. A dual approach to solving nonlinear programming problems by unconstrained optimization[J]. Mathematical Programming, 1973, 5(1): 354-373. DOI: 10.1007/BF01580138.
[16] Rockafellar R T. Augmented lagrangians and applications of the proximal point algorithm in convex programming[J]. Mathematics of Operations Research, 1976, 1(2): 97-116. DOI: 10.1287/moor.1.2.97.
[17] Kingma D, Ba J. Adam: a method for stochastic optimization[EB/OL]. (2014-12-22)[2023-01-16]. http://arxiv.org/abs/1412.6980.
[18] Defazio A, Bach F, Lacoste-Julien S. SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives[C]//Proceedings of the 27th International Conference on Neural Information Processing Systems, Vol 1. December 8-13, 2014, Montreal, Canada. New York. ACM, 2014: 1646-1654. DOI: 10.5555/2968826.2969010.
