A stochastic augmented Lagrangian method for stochastic nonconvex nonsmooth programs with many convex constraint

doi:10.7523/j.ucas.2023.055

Abstract

Abstract: The stochastic gradient methods has been widely used in machine learning, but most existing works aim for unconstraint or simple constraint 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 problem, but the requirement of accurate gradient information makes it 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 stochastic gradient to approximate the accurate gradient, and it only sample stochastic gradients and batch constraint gradient per iteration. We establish the convergence theory of CSALM and show that the CSALM can find an ϵ-KKT point after O(ϵ-8) iterations. The numerical experiments on the multi-class Neyman-Pearson classification problem(mNPC) demonstrate the of efficiency CSALM.

Key words: stochastic gradient, augmented Lagrangian, nonlinear optimization, constraint optimization

CLC Number:

O224

ZHAO Wenshen, HAN Congying, JIN Lingzi. A stochastic augmented Lagrangian method for stochastic nonconvex nonsmooth programs with many convex constraint[J]. Journal of University of Chinese Academy of Sciences, DOI: 10.7523/j.ucas.2023.055.

References

[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: volume 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 - Volume 1. December 8 - 13, 2014, Montreal, Canada. New York. ACM, 2014: 1646-1654. DOI: 10.5555/2968826.2969010.