pith. sign in

arxiv: 2605.26260 · v1 · pith:7GVY3Z5Wnew · submitted 2026-05-25 · 🧮 math.OC

Prox-NAG-GS: A Semi-Implicit Proximal Method for Composite Optimization

Sikeh Gisele Wiykiynyuy , Kelvin Asu Ekuri , Valentin Leplat This is my paper

Pith reviewed 2026-06-29 20:18 UTC · model grok-4.3

classification 🧮 math.OC
keywords composite optimizationproximal methodsaccelerated gradient methodsLyapunov analysislinear convergenceconvex optimizationNAG-GS
0
0 comments X

The pith

Prox-NAG-GS controls sequence mismatch via an augmented Lyapunov function to obtain linear convergence for strongly convex composite problems when the proximal parameter meets or exceeds the smoothness constant.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops Prox-NAG-GS, a proximal extension of the NAG-GS method, for composite objectives of the form F = f + r where f is smooth and r is convex and proximable. The scheme maintains an x-sequence for gradient evaluation and a v-sequence from the proximal step, creating a mismatch that standard proximal-gradient analysis does not address. Under the condition that the proximal quadratic parameter is at least the smoothness constant of f, an augmented Lyapunov function bounds the mismatch between the two sequences. This structure produces linear convergence in the strongly convex case and O(1/k) rates for both the best iterate and the averaged iterate in the convex case. Numerical tests on deterministic Elastic Net and Group Lasso problems show the method reaching solutions in substantially fewer iterations than baselines, while stochastic sparse softmax-regression experiments compare favorably to Prox-SGD.

Core claim

Under the sufficient condition that the proximal quadratic parameter is at least as large as the smoothness constant of f, the augmented Lyapunov function controls the mismatch between the x-sequence and v-sequence, giving a linear convergence result in the strongly convex composite case and an O(1/k) rate for the best iterate and the averaged iterate in the convex case.

What carries the argument

The augmented Lyapunov function involving both the x-sequence and v-sequence, which bounds the mismatch created when the gradient of f is evaluated at x_{k+1} while the proximal update produces v_{k+1}.

If this is right

  • Linear convergence holds for strongly convex composite problems under the stated parameter condition.
  • O(1/k) rates are obtained for both the best iterate and the averaged iterate when the objective is convex.
  • The scheme applies directly to objectives where the nonsmooth term is proximable, including Elastic Net and Group Lasso.
  • In deterministic tests the method reaches target solutions with substantially fewer iterations than standard baselines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same Lyapunov construction could be tested on other semi-implicit inertial discretizations that produce coupled sequences.
  • Selecting the proximal parameter exactly equal to the smoothness constant may reduce unnecessary conservatism while preserving the guarantees.
  • The deterministic analysis supplies a template that variance-reduced stochastic variants could build upon.

Load-bearing premise

The proximal quadratic parameter must be at least as large as the smoothness constant of f.

What would settle it

A concrete counterexample in which the proximal quadratic parameter is set below the smoothness constant of f and the claimed linear or O(1/k) rates fail to hold.

Figures

Figures reproduced from arXiv: 2605.26260 by Kelvin Asu Ekuri, Sikeh Gisele Wiykiynyuy, Valentin Leplat.

Figure 1
Figure 1. Figure 1: Deterministic Elastic Net. Optimality gap F(xk)−F ⋆ versus iterations. Left: easy instance. Right: hard instance [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Deterministic Elastic Net. Optimality gap F(xk) − F ⋆ versus wall-clock time. Left: easy instance. Right: hard instance. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Deterministic Group Lasso. Optimality gap F(xk) − F ⋆ versus iterations. Left: easy instance. Right: hard instance. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Deterministic Group Lasso. Optimality gap F(xk)−F ⋆ versus wall-clock time. Left: easy instance. Right: hard instance. This benchmark gives the clearest deterministic evidence in favor of Prox-NAG-GS. All methods reach the same objective value and recover the same number of active groups. However, Prox-NAG-GS reaches the 10−6 gap threshold in significantly fewer iterations. In contrast with the Elastic Net… view at source ↗
Figure 5
Figure 5. Figure 5: Numerical check of the theoretical regime on the deterministic Elastic Net benchmark with µb = L. Left: objective gaps at xk and vk. Right: augmented Lyapunov quantity Lk compared with the theoretical envelope L0θ k. Curves are averaged over five seeds, and shaded regions show one standard deviation. 4.4. Stochastic ℓ1 softmax regression The stochastic ℓ1 benchmark uses softmax regression on MNIST: min W∈R… view at source ↗
Figure 6
Figure 6. Figure 6: Stochastic ℓ1 softmax regression. Accuracy-sparsity trade-off across different values of λ1 [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Stochastic ℓ1 softmax regression. Training data-fit term versus epochs and wall-clock time [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Stochastic ℓ1 softmax regression. Sparsity versus epochs and wall-clock time. The stochastic ℓ1 experiment complements the deterministic tests. Prox-NAG-GS obtains a slightly lower full objective and a lower data-fit term for the base value of λ1, with essentially the same test accuracy. However, Prox-SGD gives a smaller 25 [PITH_FULL_IMAGE:figures/full_fig_p025_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Stochastic Group Lasso. Training data-fit term versus epochs and wall-clock time. 26 [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Stochastic Group Lasso. Group sparsity versus epochs and wall-clock time. The stochastic Group Lasso experiment is consistent with the stochastic ℓ1 test. Group Prox-NAG-GS gives the lowest data-fit term, while Group Prox-SGD gives the lowest full regularized objective. The reason is again the regularization term: Prox￾SGD produces stronger group sparsity, whereas Prox-NAG-GS keeps denser weights. The tes… view at source ↗
read the original abstract

Composite optimization problems, where a smooth loss is combined with a nonsmooth regularizer, are common in machine learning and inverse problems. In this work, we study a proximal extension of NAG-GS, a semi-implicit accelerated method obtained from a Gauss-Seidel discretization of an inertial dynamics. The proposed method, called Prox-NAG-GS, keeps the coupled structure of NAG-GS for the smooth part and replaces the second update by a proximal step. It therefore applies to objectives of the form $F=f+r$, where $f$ is smooth and $r$ is convex and proximable. We derive deterministic convergence guarantees for this method. The analysis has to account for a specific feature of the scheme. Prox-NAG-GS keeps two coupled sequences: an $x$-sequence, on which the gradient of the smooth term is evaluated, and a $v$-sequence, produced by the proximal update. The gradient is evaluated at $x_{k+1}$, whereas the proximal step returns $v_{k+1}$, which creates a mismatch absent from the standard proximal-gradient analysis. Under the sufficient condition that the proximal quadratic parameter is at least as large as the smoothness constant of $f$, we control this mismatch through an augmented Lyapunov function involving both sequences. This gives a linear convergence result in the strongly convex composite case. In the convex case, the same Lyapunov structure yields an $O(1/k)$ rate for the best iterate and for the averaged iterate. We test the method on deterministic Elastic Net and Group Lasso problems, and on stochastic sparse softmax-regression benchmarks. In the deterministic tests, Prox-NAG-GS reaches the same solutions as the baselines with substantially fewer iterations; for Group Lasso this also gives the best wall-clock time. In the stochastic tests, Prox-NAG-GS compares favorably with Prox-SGD in terms of data-fit reduction and gives similar test accuracies.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proposes Prox-NAG-GS, a proximal extension of the semi-implicit NAG-GS method for composite problems min f(x) + r(x) with f smooth and r convex proximable. The scheme maintains coupled x- and v-sequences, with the gradient of f evaluated at x_{k+1} and the proximal step producing v_{k+1}. Under the explicit sufficient condition that the proximal quadratic parameter is at least the smoothness constant L of f, an augmented Lyapunov function controls the resulting mismatch and yields linear convergence in the strongly convex case together with O(1/k) rates on both the best iterate and the averaged iterate in the convex case. Deterministic convergence guarantees are stated; numerical tests on Elastic Net, Group Lasso, and stochastic sparse softmax regression are reported.

Significance. If the stated rates hold, the work supplies a new accelerated proximal scheme whose analysis directly addresses the x/v-sequence mismatch via an augmented Lyapunov construction. The explicit sufficient condition on the proximal parameter is a clarity strength. The deterministic rates and the reported iteration reductions on deterministic ML problems constitute the main technical and practical contributions.

minor comments (3)
  1. [§3] §3 (analysis): the construction of the augmented Lyapunov function is described only at a high level in the abstract; the main text should explicitly display the two-sequence Lyapunov and the algebraic steps that absorb the mismatch term under the stated parameter condition.
  2. [Numerical section] Table 1 and Figure 2: the iteration counts and wall-clock times for Group Lasso would benefit from an additional column reporting the proximal parameter value used relative to the estimated L, to make the sufficient-condition compliance transparent.
  3. [Theorem on convex case] The O(1/k) claim for the averaged iterate in the convex case should be accompanied by the precise averaging weights (uniform or weighted) and the corresponding theorem number.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work on Prox-NAG-GS and for recommending minor revision. No specific major comments were provided in the report, so we have no point-by-point responses to offer. We remain available to address any additional feedback from the editor.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives convergence rates for Prox-NAG-GS via an augmented Lyapunov function that explicitly incorporates the x/v-sequence mismatch under the stated sufficient condition (proximal quadratic parameter >= smoothness constant of f). This is a standard first-principles analysis technique in optimization; the rates are not obtained by fitting parameters to data subsets, renaming known results, or reducing via self-citation chains to unverified premises. The condition is presented as necessary for the proof rather than smuggled in, and the derivation remains self-contained against external benchmarks without load-bearing self-references or definitional equivalence.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard domain assumptions of smoothness and convexity of the composite objective; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • domain assumption f is L-smooth and r is convex and proximable
    Invoked to define the composite objective F = f + r and to guarantee existence of the proximal step.
  • domain assumption The proximal quadratic parameter is at least the smoothness constant of f
    Stated as the sufficient condition required for the augmented Lyapunov argument to control the sequence mismatch.

pith-pipeline@v0.9.1-grok · 5896 in / 1543 out tokens · 21469 ms · 2026-06-29T20:18:11.974346+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 1 canonical work pages

  1. [1]

    Akiba, S

    T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama,Optuna: A Next-generation Hyperparameter Optimization Framework, inProceedings of the 25th ACM SIGKDD In- ternational Conference on Knowledge Discovery & Data Mining. 2019, pp. 2623–2631

    2019

  2. [2]

    Alvarez and H

    F. Alvarez and H. Attouch,An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Analysis 9 (2001), pp. 3–11. 28

    2001

  3. [3]

    Attouch, Z

    H. Attouch, Z. Chbani, and H. Riahi,Fast proximal methods via time scaling of damped inertial dynamics, SIAM Journal on Optimization 29 (2019), pp. 2227–2256

    2019

  4. [4]

    Bauschke and P.L

    H.H. Bauschke and P.L. Combettes,Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, 2017

    2017

  5. [5]

    Beck and M

    A. Beck and M. Teboulle,A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences 2 (2009), pp. 183–202

    2009

  6. [6]

    Bottou, F.E

    L. Bottou, F.E. Curtis, and J. Nocedal,Optimization methods for large-scale machine learning, SIAM Review 60 (2018), pp. 223–311

    2018

  7. [7]

    Chambolle and T

    A. Chambolle and T. Pock,A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision 40 (2011), pp. 120– 145

    2011

  8. [8]

    Combettes and J.C

    P.L. Combettes and J.C. Pesquet,Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, 2011, pp. 185–212

    2011

  9. [9]

    Combettes and V.R

    P.L. Combettes and V.R. Wajs,Signal recovery by proximal forward-backward splitting, Multiscale Modeling & Simulation 4 (2005), pp. 1168–1200

    2005

  10. [10]

    L. Condat,A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms, Journal of Optimization Theory and Applications 158 (2013), pp. 460–479

    2013

  11. [11]

    Daubechies, M

    I. Daubechies, M. Defrise, and C. De Mol,An iterative thresholding algorithm for lin- ear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics 57 (2004), pp. 1413–1457

    2004

  12. [12]

    Defazio, F

    A. Defazio, F. Bach, and S. Lacoste-Julien,SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives, inAdvances in Neural Infor- mation Processing Systems, Vol. 27. 2014, pp. 1646–1654

    2014

  13. [13]

    Duchi and Y

    J. Duchi and Y. Singer,Efficient online and batch learning using forward backward split- ting, Journal of Machine Learning Research 10 (2009), pp. 2899–2934

    2009

  14. [14]

    Ghadimi and G

    S. Ghadimi and G. Lan,Stochastic first- and zeroth-order methods for nonconvex stochas- tic programming, SIAM Journal on Optimization 23 (2013), pp. 2341–2368

    2013

  15. [15]

    Ghadimi, G

    S. Ghadimi, G. Lan, and H. Zhang,Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization, Mathematical Programming 155 (2016), pp. 267–305

    2016

  16. [16]

    Johnson and T

    R. Johnson and T. Zhang,Accelerating stochastic gradient descent using predictive vari- ance reduction, inAdvances in Neural Information Processing Systems, Vol. 26. 2013, pp. 315–323

    2013

  17. [17]

    Lan,An optimal method for stochastic composite optimization, Mathematical Pro- gramming 133 (2012), pp

    G. Lan,An optimal method for stochastic composite optimization, Mathematical Pro- gramming 133 (2012), pp. 365–397

    2012

  18. [18]

    Leplat, D

    V. Leplat, D. Merkulov, A. Katrutsa, D. Bershatsky, O. Tsymboi, and I. Oseledets, NAG-GS: Semi-implicit, accelerated and robust stochastic optimizer, arXiv preprint arXiv:2209.14937 (2022)

    work page arXiv 2022

  19. [19]

    Moudafi and M

    A. Moudafi and M. Oliny,Convergence of a splitting inertial proximal method for mono- tone operators, Journal of Computational and Applied Mathematics 155 (2003), pp. 447– 454

    2003

  20. [20]

    Nesterov,A method for solving the convex programming problem with convergence rate O(1/k2), inSoviet Mathematics Doklady, Vol

    Y. Nesterov,A method for solving the convex programming problem with convergence rate O(1/k2), inSoviet Mathematics Doklady, Vol. 27. 1983, pp. 372–376

    1983

  21. [21]

    Nesterov,Gradient methods for minimizing composite functions, Mathematical Pro- gramming 140 (2013), pp

    Y. Nesterov,Gradient methods for minimizing composite functions, Mathematical Pro- gramming 140 (2013), pp. 125–161

    2013

  22. [22]

    Nesterov,Lectures on Convex Optimization, Springer, 2018

    Y. Nesterov,Lectures on Convex Optimization, Springer, 2018

    2018

  23. [23]

    P. Ochs, Y. Chen, T. Brox, and T. Pock,iPiano: Inertial proximal algorithm for nonconvex optimization, SIAM Journal on Imaging Sciences 7 (2014), pp. 1388–1419

    2014

  24. [24]

    Parikh and S

    N. Parikh and S. Boyd,Proximal algorithms, Foundations and Trends in Optimization 1 (2014), pp. 127–239

    2014

  25. [25]

    Polyak,Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics 4 (1964), pp

    B.T. Polyak,Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics 4 (1964), pp. 1–17. 29

    1964

  26. [26]

    Schmidt, N

    M. Schmidt, N. Le Roux, and F. Bach,Minimizing finite sums with the stochastic average gradient, Mathematical Programming 162 (2017), pp. 83–112

    2017

  27. [27]

    W. Su, S. Boyd, and E.J. Cand` es,A differential equation for modeling Nesterov’s accel- erated gradient method: Theory and insights, Journal of Machine Learning Research 17 (2016), pp. 1–43

    2016

  28. [28]

    Tseng,On accelerated proximal gradient methods for convex-concave optimization, Manuscript (2008)

    P. Tseng,On accelerated proximal gradient methods for convex-concave optimization, Manuscript (2008). May 2008

    2008

  29. [29]

    Vu,A splitting algorithm for dual monotone inclusions involving cocoercive operators, Advances in Computational Mathematics 38 (2013), pp

    B.C. Vu,A splitting algorithm for dual monotone inclusions involving cocoercive operators, Advances in Computational Mathematics 38 (2013), pp. 667–681

    2013

  30. [30]

    Wilson, B

    A.C. Wilson, B. Recht, and M.I. Jordan,A lyapunov analysis of accelerated methods in optimization, Journal of Machine Learning Research 22 (2021), pp. 1–34

    2021

  31. [31]

    Xiao,Dual averaging methods for regularized stochastic learning and online optimiza- tion, Journal of Machine Learning Research 11 (2010), pp

    L. Xiao,Dual averaging methods for regularized stochastic learning and online optimiza- tion, Journal of Machine Learning Research 11 (2010), pp. 2543–2596

    2010

  32. [32]

    Xiao and T

    L. Xiao and T. Zhang,A proximal stochastic gradient method with progressive variance reduction, SIAM Journal on Optimization 24 (2014), pp. 2057–2075. 30

    2014