A new preprint reports that its two fixed-penalty variants, NR-LALM and NR-LALM+SOC, were each faster than L-AL on 14 of 15 deterministic data sets in the reported tests. The base method, NR-LALM, replaces the nonlinear primal subproblem with a regularized Gauss–Newton-type step while retaining the classical multiplier update based on the nonlinear constraint residual.
In the deterministic case, the paper says an ε-KKT pair—its stated accuracy target for constrained optimization—can be obtained in O(ε⁻²) iterations, first-order oracle evaluations, meaning counted calls for first-order information, and exact linear-system solves induced by the constraint Jacobian. The guarantee is conditional on the paper’s stated assumptions, making it a theoretical complexity order rather than a statistical estimate.
What the analysis establishes
For stochastic objectives, the paper gives two related complexity results. A projected stochastic estimator with safeguarded restarts has expected O(ε⁻³) stochastic-gradient evaluations and O(ε⁻²) constraint and Jacobian evaluations. A direct stochastic result reports O(ε⁻²) orders for iterations, deterministic constraint and Jacobian evaluations and exact solves, alongside O(ε⁻³) stochastic-gradient evaluations.
The analysis derives multiplier boundedness and localization of the algorithm’s trajectory rather than assuming them. Under compactness and a Kurdyka–Lojasiewicz condition, the deterministic primal-dual sequence is associated with finite-length convergence, meaning its total path length is finite.
The paper also analyzes an optional minimum-norm second-order correction, or SOC, with a constraint-linearization error that changes from second to fourth order while the complexity orders remain unchanged. In a numerical test using 12 step norms from 0.01 to 0.2, the fitted log-log slopes were 2.001 and 4.022, with R² greater than 0.9999 for every fit.
Results on selected benchmarks
The deterministic benchmark used 15 LIBSVM binary-classification data sets meeting the paper’s thresholds of n ≥ 2,561 and no more than 5 GiB in compressed size. The geometric-mean speedup over L-AL was 1.19 for NR-LALM and 1.71 for NR-LALM+SOC.
The stochastic comparison used multiclass logistic regression on the LIBSVM covtype and MNIST data sets. At all 16 post-initial checkpoints, both proposed methods had lower reported mean R2min(x), a residual surrogate based on the primal point, than both baselines. At the final checkpoint, the reported means were 1.95 × 10⁻⁴ for covtype and 1.27 × 10⁻³ for MNIST, compared with 9.22 × 10⁻⁴ and 4.66 × 10⁻³ for the best baseline—about 4.7-fold and 3.7-fold reductions, respectively.
How far the findings go
The reported complexity orders are conditional rather than universal: the analysis relies on the paper’s stated regularity, parameter, initialization, localization and stochastic assumptions. The direct stochastic result is likewise tied to its regularity conditions, while the projected estimator’s guarantee includes safeguarded restarts.
The stochastic benchmark does not measure a complete primal-dual outcome. It uses R2min(x) as a common comparison based on the primal point and does not assess the multiplier returned by a method. The timing and mean-value summaries are benchmark-specific and are reported without confidence intervals.
The manuscript identifies itself as arXiv:2608.19847v1, dated 20 August 2026, and is a preprint. It says all theoretical results were formally verified in Lean 4, with manual checks of their fidelity to the natural-language statements.
Paper data and sources
Original title: A Fixed-Penalty Linearized Augmented Lagrangian Method with Classical Multiplier Updates
Authors: Benqi Liu, Kangkang Deng, Zichen Wang, Zaiwen Wen
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text