随机梯度法广泛应用于机器学习并取得显著成功，但许多随机方法主要针对无约束或简单约束的优化问题。对于带有正则项和大量凸约束的非凸随机优化问题，经典增广拉格朗日法是一种解法，但精确梯度信息的要求使其难以有效应对大量约束问题。为此，提出一种随机增广拉格朗日算法，该算法用随机一阶信息代替增广拉格朗日法的精确梯度，每步迭代仅使用一组抽样梯度和部分的约束梯度。对该算法，证明其可以在$\mathcal{O}\left(\epsilon^{-8}\right)$次方后找到$\epsilon$-KKT近似点。在多分类Neyman-Pearson问题上进行数值实验，实验结果验证了算法的有效性。
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.
[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.
