An arXiv preprint reports that its adaptive augmented Lagrangian method had the highest performance profile among the deterministic variants it tested and generally produced the smallest combined residual and constraint violation across the tested stochastic thresholds.
The central idea is to let the penalty parameter respond to how well the constraints are being reduced, while also using that parameter as the step size for updating multipliers.
A solver that changes course
At each outer iteration, the method keeps the penalty when the constraint norm has fallen enough. If the reduction is insufficient, it increases the penalty. The multiplier update is first formed with the current penalty and then projected onto a bounded region, limiting the size of the multiplier used at the next step.
For stochastic problems, the inner solver does not commit to one fixed number of passes through the data. It raises the epoch count geometrically after a failed check, and accepts a candidate only when it meets both a stationarity tolerance and a non-increasing augmented-Lagrangian-value test.
The paper's stopping target combines two requirements: the point should be close to stationary, meaning there is little first-order direction left after accounting for the nonsmooth part of the objective, and its constraint violation should be small. In the paper's definition, the sum of those two residuals must be no greater than the target tolerance.
The cost on paper
Under its stated assumptions, the deterministic proof reports a per-subproblem work order that grows like the inverse cube of the target accuracy, with an additional logarithmic factor. The paper says the outer loop adds only logarithmic overhead, so the overall order keeps that same leading dependence up to logarithms.
The authors describe this as matching best-known worst-case augmented Lagrangian complexity up to logarithmic factors, regardless of how the penalty parameter behaves. For the stochastic results, they say the guarantees hold with high probability and that the cost of adaptivity is only logarithmic in relevant factors.
With a stochastic proximal-gradient inner solver, the stated bounds hold with probability at least one minus the failure-probability parameter. Their stochastic-oracle order has an inverse-square dependence on that parameter and an inverse sixth-power dependence on target accuracy when only the objective is stochastic. When the constraints are stochastic too, the target-accuracy exponent becomes seven. The full-oracle count is reported with logarithmic dependence on inverse accuracy and failure-probability factors.
A separate PStorm analysis, under stronger mean-squared-smoothness and inner-solver conditions, reports lower target-accuracy exponents: four for a stochastic objective with deterministic constraints and five when both are stochastic. It retains the same logarithmic full-oracle order.
Tests on benchmark problems
For the deterministic check, the authors used a final set of 485 PyCUTEst problems after their stated exclusions. Inner solves used L-BFGS-B, and the comparison crossed two choices of penalty update, Always or Adaptive, with two multiplier step choices, Full or Short.
Adaptive-Full, the combination of adaptive penalty updates and full dual steps, had the highest performance profile across the displayed panels. The short-step variants solved fewer problems within the evaluation budget.
On instances where Always-Full failed and Adaptive-Full succeeded, Always-Full generally ended with much larger penalties and used more gradient evaluations. The authors suggest that aggressive penalty growth produced poorly conditioned inner subproblems, and present that as a likely explanation for the pattern.
The stochastic trial
The stochastic experiment used normalized Spambase in a Neyman-Pearson classification task. Observations were randomly split into 80% training and 20% test sets; results were averaged over 20 trials, using mini-batches of 128 sampled with replacement.
Across the tested constraint thresholds, Adaptive-Full generally produced the smallest combined residual and constraint violation. With adaptive inner epochs, Adaptive-Full showed the most consistent convergence, while the increasing-epoch strategy was more stable across thresholds and less sensitive to a single fixed epoch choice.
Why the result remains provisional
These are conditional findings. The paper's theory uses two assumptions throughout and adds three stochastic-specific assumptions, so the guarantees depend on the conditions stated for the relevant analysis.
The numerical evidence is tied to the selected 485-problem deterministic set and the normalized Spambase experiment averaged over 20 trials. The reported comparisons are therefore best read as evidence from those tested setups, rather than as a universal ranking for every nonconvex constrained problem.
The work is an arXiv version-one preprint, and the supplied text and metadata do not report a funding source.
Paper data and sources
Original title: An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
Authors: Tianzhu Liu, Michael J. O'Neill
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-27
DOI: Not available
Original paper · Full text