Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization

DOI10.1007/S10589-023-00521-ZMaRDI QIDQ6179875zbMATH OpenOpenAlexFDO

Authors Zichong Li, Pin-Yu Chen, Sijia Liu, Songtao Lu, Yangyang Xu

Publication date 18 January 2024

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.09513

zbMATH Keywords

augmented Lagrangianexpectation constraintfirst-order methodsmomentum accelerationnonconvex optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Nonconvex programming, global optimization (90C26)

Abstract: Many real-world problems not only have complicated nonconvex functional constraints but also use a large number of data points. This motivates the design of efficient stochastic methods on finite-sum or expectation constrained problems. In this paper, we design and analyze stochastic inexact augmented Lagrangian methods (Stoc-iALM) to solve problems involving a nonconvex composite (i.e. smooth+nonsmooth) objective and nonconvex smooth functional constraints. We adopt the standard iALM framework and design a subroutine by using the momentum-based variance-reduced proximal stochastic gradient method (PStorm) and a postprocessing step. Under certain regularity conditions (assumed also in existing works), to reach an $varepsilon$-KKT point in expectation, we establish an oracle complexity result of $O(varepsilo{n}^{-5})$, which is better than the best-known $O(varepsilo{n}^{-6})$ result. Numerical experiments on the fairness constrained problem and the Neyman-Pearson classification problem with real data demonstrate that our proposed method outperforms an existing method with the previously best-known complexity result.

Recommendations

• Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
• Stochastic first-order methods for convex and nonconvex functional constrained optimization
• Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
• A stochastic primal-dual method for a class of nonconvex constrained optimization
• Stochastic nested primal-dual method for nonconvex constrained composition optimization

Cites work

• A dual approach to solving nonlinear programming problems by unconstrained optimization
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• A hybrid stochastic optimization framework for composite nonconvex optimization
• A stochastic primal-dual method for a class of nonconvex constrained optimization
• Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
• Algorithms for stochastic optimization with function or expectation constraints
• An accelerated linearized alternating direction method of multipliers
• An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
• Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization
• Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
• scientific article; zbMATH DE number 7625189 (Why is no real title available?)
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
• Iteration-complexity of first-order augmented Lagrangian methods for convex programming
• IX. On the problem of the most efficient tests of statistical hypotheses
• Lower bounds for non-convex stochastic optimization
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Multiplier and gradient methods
• Neyman-Pearson classification, convexity and stochastic constraints
• On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
• Penalty methods with stochastic approximation for stochastic nonlinear programming
• Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
• Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
• Stochastic first-order methods for convex and nonconvex functional constrained optimization

Cited in

(9)

• Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
• Stochastic nested primal-dual method for nonconvex constrained composition optimization
• Correction to: ``Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization
• Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees
• A two-phase stochastic momentum-based algorithm for nonconvex expectation-constrained optimization
• A SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization
• Stochastic interior-point methods for smooth conic optimization with applications
• The augmented Lagrangian methods: overview and recent advances
• Survey on first-order algorithms for solving functional constrained optimization problems

This page was built for publication: Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6179875)