# An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians

arXiv: https://arxiv.org/abs/2102.05320 · HTML: https://mlsanity.com/paper/2102.05320/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 61 of its 229 references that are in the map.
- First posted on arXiv 10 Feb 2021.

## Builds on (most cited first, 30 of 61)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On the Variance of the Adaptive Learning Rate and Beyond](https://mlsanity.com/paper/1908.03265/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Equilibrated adaptive learning rates for non-convex optimization](https://mlsanity.com/paper/1502.04390/) (2015)
- [Efficient Distributed Learning with Sparsity](https://mlsanity.com/paper/1605.07991/) (2016)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach](https://mlsanity.com/paper/2007.01290/) (2020)
- [Adaptive Sampling Strategies for Stochastic Optimization](https://mlsanity.com/paper/1710.11258/) (2017)
- [Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2007.10525/) (2020)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [Coauthorship and Citation Networks for Statisticians](https://mlsanity.com/paper/1410.2840/) (2014)
- [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017)
- [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging](https://mlsanity.com/paper/1702.04837/) (2017)
- [Distributed Multitask Learning](https://mlsanity.com/paper/1510.00633/) (2015)
- [Convergence of trust-region methods based on probabilistic models](https://mlsanity.com/paper/1304.2808/) (2013)
- [A Stochastic Trust Region Algorithm Based on Careful Step Normalization](https://mlsanity.com/paper/1712.10277/) (2017)

## Built on by (most cited first, 25 of 25)

- [A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians](https://mlsanity.com/paper/2106.13015/) (2021)
- [Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems](https://mlsanity.com/paper/2211.15943/) (2022)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022)
- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems](https://mlsanity.com/paper/2304.14907/) (2023)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization](https://mlsanity.com/paper/2308.03687/) (2023)
- [Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models](https://mlsanity.com/paper/2409.15734/) (2024)
- [Physics-Informed Neural Networks with Trust-Region Sequential Quadratic Programming](https://mlsanity.com/paper/2409.10777/) (2024)
- [High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise](https://mlsanity.com/paper/2503.19091/) (2025)
- [A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method](https://mlsanity.com/paper/2603.10230/) (2026)
- [Single-Loop Deterministic and Stochastic Interior-Point Algorithms for Nonlinearly Constrained Optimization](https://mlsanity.com/paper/2408.16186/) (2024)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [humancompatible.train: Implementing Optimization Algorithms for Stochastically-Constrained Stochastic Optimization Problems](https://mlsanity.com/paper/2509.21254/) (2025)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling](https://mlsanity.com/paper/2505.18327/) (2025)
- [Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks](https://mlsanity.com/paper/2507.04033/) (2025)
- [TRSVR: An Adaptive Stochastic Trust-Region Method with Variance Reduction](https://mlsanity.com/paper/2601.14647/) (2026)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)
- [TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.30732/) (2026)

## Abstract (arXiv)

We consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit and simplify an old SQP method citepLucidi1990Recursive developed for solving deterministic problems, which serves as the skeleton of our stochastic algorithm. Based on the simplified deterministic algorithm, we then propose a non-adaptive SQP for dealing with stochastic objective, where the gradient and Hessian are replaced by stochastic estimates but the stepsizes are deterministic and prespecified. Finally, we incorporate a recent stochastic line search procedure citepPaquette2020Stochastic into the non-adaptive stochastic SQP to adaptively select the random stepsizes, which leads to an adaptive stochastic SQP. The global "almost sure" convergence for both non-adaptive and adaptive SQP methods is established. Numerical experiments on nonlinear problems in CUTEst test set demonstrate the superiority of the adaptive algorithm.