Pith. sign in

REVIEW 1 major objections 5 minor 1 cited by

Optimized methods for composite optimization: a reduction perspective

T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that optimized first-order methods for smooth minimization extend to composite problems while preserving their accelerated rates.

desk verdict Genuinely useful reduction framework for composite optimization; the main thing to check before accepting is the unquantified state-of-the-art claim against [37]. read the letter →

arxiv 2506.23756 v1 pith:FCRZY2LC submitted 2025-06-30 math.OC cs.DS

Jinho Bok , Jason M. Altschuler This is my paper · ORCID
classification math.OCcs.DS MSC 90C2590C60
keywords compositeoptimizationfirst-ordermethodsperformanceestimationproblemstepsizeaccelerationproximalgradientmethodoptimizednormminimizationsilverstepsizes
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that optimized first-order methods designed for unconstrained smooth convex minimization can be automatically extended to the more general composite setting—minimizing a smooth function plus a nonsmooth one such as a regularization penalty—without losing their accelerated convergence rates. The extension is the natural one that replaces every gradient by the sum of the gradient and a subgradient of the nonsmooth term, generalizing how proximal gradient descent extends gradient descent. The proof relies on algebraic identities that reuse the unconstrained method's convergence certificate, provided that certificate has a special single-square structure. The framework yields three concrete results: proximal gradient descent with the silver stepsizes converges at rate $O(1/n^{\log_2(1+\sqrt{2})})$, the proximal optimized gradient method provably reaches $O(1/n^2)$ and beats FISTA, and a new proximal OGM-G gives the current best rate for reducing the gradient norm in composite problems.

What carries the argument

The key object is the rank-one sum-of-squares certificate: a proof that a convergence bound holds by writing the objective gap as a nonnegative combination of co-coercivity inequalities plus exactly one square term $\frac{1}{2}\|x_0 - x_* - \sum_i \gamma_i g_i\|^2$ (or no square term, for gradient-norm bounds). The paper's new identities (2.2) and (2.4) lift such a certificate to the composite setting, where the nonsmooth component contributes its own co-coercivities; the multipliers $\mu$ and the matrix $S$ are given in closed form in Definitions 3.3 and 3.4, with $S$ built so that, after a Schur complement, it is a rank-one perturbation of a Laplacian (or diagonally dominant) matrix. This structure is what makes the verification of positive semidefiniteness tractable, reducing it to comparisons of a few entries.

What would settle it

Construct an optimized first-order method whose performance-estimation certificate provably has rank at least two (a genuine sum of squares), form its composite extension by the paper's rule, and solve the composite performance estimation problem numerically with the same function class; if the resulting worst-case rate is worse than the unconstrained rate by more than the framework's overhead, or if the closed-form multipliers $\mu$ become negative, the single-square condition is necessary.

Watch

Extended reading notes

Core claim

The central claim, Theorem 2.6, is that if an unconstrained first-order method has a convergence certificate of the form $\sum_{i,j}\lambda_{ij}Q_{ij} + \frac{1}{2}\|x_0 - x_* - \sum_i \gamma_i g_i\|^2 = R_n(f_* - f_n) + \frac{1}{2}\|x_0-x_*\|^2$—one single square—then its composite extension satisfies a lifted identity with explicit multipliers $\mu$, $\sigma$ and a positive semidefinite matrix $S$ of Laplacian type, and therefore achieves $F_n - F_* \le \frac{1+\xi}{2R_n}\|x_0-x_*\|^2$. An analogous theorem, Theorem 2.8, holds when the performance metric is the gradient norm and the certificate has no square term. The paper verifies the required feasibility conditions (nonnegativity of $\mu$ and positive semidefiniteness of $S$) for three optimized methods, obtaining the stated rates.

Load-bearing premise

The load-bearing premise is that the unconstrained method's convergence proof takes the form of a certificate with a single square term (or no square term for gradient norms); if a future optimized method only admits a certificate with a sum of several squares, the closed-form lift of multipliers in this paper does not apply.

Editorial extensions

If this is right

  • Proximal gradient descent can be accelerated purely by choosing time-varying stepsizes, resolving the open question posed for composite/constrained settings; the silver stepsize schedule achieves $O(1/n^{1.2716})$ for both objective value and gradient norm.
  • The proximal optimized gradient method (POGM) provably converges at $O(1/n^2)$, faster than FISTA and within a small constant factor of the exactly optimal OptISTA.
  • A new proximal OGM-G achieves the state-of-the-art guaranteed rate for reducing the gradient norm in composite optimization, improving on the previous best bound by a factor of roughly 9.3.
  • For a method whose unconstrained certificate has the required single-square form, its composite extension automatically inherits the rate up to an explicit constant factor, so future optimized methods with such certificates can be extended without re-solving the composite performance estimation problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the observed rank-one certificate structure is universal for optimized methods, the framework would turn composite extension into a routine step for every new optimized method; this is an open question the paper itself raises.
  • The same 'rank-one plus Laplacian' decomposition of the witness matrix might be reusable in other PEP-based settings, such as strongly convex or stochastic variants, where similar certificates may exist but have not been exploited.
  • A fully black-box reduction could be obtained by replacing the manual verification of items (i) and (ii) with a small semidefinite check, since the multipliers are already in closed form.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. This paper develops a reduction framework for extending first-order methods from unconstrained smooth convex optimization to composite optimization (smooth f plus nonsmooth h). The central results, Theorems 2.6 and 2.8, show that if an unconstrained method admits a performance-estimation certificate of a special rank-1 form (for objective values) or rank-0 form (for gradient norms), then an explicitly constructed composite extension satisfies a lifted algebraic identity; after verifying two closed-form conditions --- nonnegativity of new multipliers and positive semidefiniteness of an explicit matrix S or S' --- the extension inherits a convergence rate. The framework is applied to three settings: stepsize-accelerated proximal gradient descent with rate O(1/n^{log_2(1+sqrt(2))}), the proximal optimized gradient method with rate (3+sqrt(5))/(4n^2), and a proximal OGM-G variant with gradient-norm rate 4(sqrt(5)-1)/n^2, claimed as state-of-the-art. The proofs are based on explicit algebraic coefficient matching in Appendices A-C.

Significance. If the claims hold, this is a genuinely useful unification: it exports unconstrained PEP certificates to composite settings without solving a new SDP, and it answers an open problem about stepsize-based acceleration for proximal gradient descent. The concrete applications are nontrivial, and the paper is honest about the scope: the reduction is not fully black-box (Section 6), and the hypotheses (2.1)/(2.3) are stated explicitly. The algebra is detailed enough to be checked, and the applications do verify the required μ >= 0 and S PSD conditions. The main advertised novelty -- contribution (3) -- currently rests on an unquantified comparison to [37], which needs to be resolved before the state-of-the-art claim can be accepted.

major comments (1)
  1. [Section 5.2, Theorem 5.5 and Section 1.1] The claim that the composite extension of OGM-G achieves the 'state-of-the-art convergence rate for minimizing gradient norm in the composite setting' is not substantiated. Theorem 5.5 establishes the constant 4(sqrt(5)-1)/n^2 ≈ 4.944/n^2, and the text reports an improvement over [34, Section D.4] by a factor of roughly 9.30. However, Section 1.3 also cites [37] as achieving O(1/n^2) in the composite setting, and no comparison with [37] is given anywhere in Section 5.2. If [37]'s composite gradient-norm bound has a constant no larger than 4(sqrt(5)-1), the state-of-the-art claim and the abstract contribution (3) are false; if [37] only treats the unconstrained setting, the citation in Section 1.3 should be corrected. Please provide the exact bound from [37] (or a precise statement of its setting) and adjust the claims accordingly.
minor comments (5)
  1. [Section 1.1] The informal reduction statement 'if an algorithm A has convergence rate ... then there is a composite extension with rate O(tau_n)' omits the hypotheses of Theorems 2.6 and 2.8: the unconstrained certificate must have the special rank-1 or rank-0 form, and conditions (i) and (ii) must be verified. Please qualify the informal statement so that it does not suggest a fully black-box reduction.
  2. [Section 5.1 and Table 1] The gradient-norm result for stepsize-accelerated proximal GD uses the modified stepsize schedule w(k) from [25], not the silver schedule pi(k) from Section 4.1; this should be stated in the introduction bullet and in Table 1 to avoid implying the same schedule works for both performance metrics.
  3. [Section 1.2] There is a typo on page 5: 'nonnnegative' should be 'nonnegative'.
  4. [Section 5.2, proof of Theorem 5.5] The factorization H = U(theta_n,...,theta_1)^{-1} U(phi_n,...,phi_1) diag(2theta_{n-1},...,2theta_0) is stated as analogous to Lemma 4.8 without proof; since the proof of Theorem 5.5 relies on it, please include the derivation or make the analogy precise.
  5. [Remark 3.2] The shorthand e0 := -1_n and e* := -1_n is initially confusing; please clarify that these vectors are used to encode the column-sum behavior of mu and mu' in the one-to-one correspondence of Definition 3.1.

Circularity Check

0 steps flagged · score 0.0 of 10

Reduction is conditional on explicit external certificates; no fitted-input or self-citation circularity.

full rationale

The paper's derivation chain is conditional on unconstrained PEP certificates of the specific rank-1/rank-0 forms (2.1) and (2.3), all of which are imported from prior external works rather than derived from the composite results being claimed. Theorems 2.6 and 2.8 construct the composite certificate (2.2)/(2.4) by explicit closed-form formulae and coefficient matching, and the applications then verify the two hypotheses (nonnegativity of the new multipliers and positive semidefiniteness of S or S') by direct algebraic lemmas. No parameter is fitted to the composite target rate: the reused multipliers lambda and gamma come from the unconstrained certificates, and the target composite rate appears only after the identity is constructed, not as an input. The self-citation [9] reports a special case recovered by the framework and is transparent rather than load-bearing. The unquantified comparison to [37] in the claimed state-of-the-art gradient-norm rate is a correctness and scope concern, not circularity, because it does not enter the proof chain. The rank-1 certificate assumption is explicitly stated as a hypothesis, and the paper notes that it is not proved in general; this is an honest scope limitation rather than a hidden circular dependence. Overall, the reduction algebra is internally coherent and independently verifiable against the cited external certificates, so no significant circularity is present.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The framework is a reduction: it imports base-algorithm certificates from the literature and builds composite certificates. The internal numeric choices are the proof constants xi and xi', which are chosen to satisfy sufficient PSD conditions. No new physical or abstract entities are postulated.

free parameters (2)
  • xi (Theorem 2.6, objective-function reduction) = 1/sqrt(2) for silver proximal GD; (sqrt(5)-1)/4 for proximal OGM
    Chosen by hand inside the paper to satisfy the Schur complement condition L - (1/xi) v v^T being Laplacian, thereby making S positive semidefinite. It is not fitted to data; it affects only the constant factor in the rate, not the exponent.
  • xi' (Theorem 2.8, gradient-norm reduction) = 1 - (lambda'_{n-1,n}+lambda'_{n,n-1})/R'_n
    Selected so that S' is diagonally dominant. This is a proof-construction choice, analogous to a slack variable, and does not affect asymptotics.
assumptions (4)
  • domain assumption f is convex and 1-smooth (by scaling) and h is convex, possibly nonsmooth, with available prox operator.
    Defines the composite optimization setting in Section 2.1; all results are stated under this assumption.
  • domain assumption Co-coercivity inequalities are the complete set of valid inequalities for certifying convergence rates (PEP interpolation theorem).
    Invoked in Lemma 2.5 and as the framework for the certificates (2.1)-(2.4); the paper cites [48, Theorem 4] and does not re-prove completeness.
  • ad hoc to paper The unconstrained base method has a certificate of the exact rank-1 (objective) or rank-0 (gradient-norm) form (2.1)/(2.3).
    This is the structural hypothesis of Theorems 2.6 and 2.8. It is not proven for all optimized methods; the paper notes it as an observed phenomenon and verifies it for the specific certificates it imports from prior work.
  • domain assumption The imported multipliers and rates from published certificates are correct (silver stepsizes [2,51], OGM [31], OGM-G [33], w(k) stepsizes [25]).
    The reduction inherits these certificates as inputs. If any imported certificate were wrong, that particular application would be invalid; the paper does not re-derive them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimized methods for composite optimization: a reduction perspective." pith.science (2026). https://pith.science/paper/FCRZY2LC

@misc{pith2026250623756,
  author       = {Pith},
  title        = {Pith review of: Optimized methods for composite optimization: a reduction perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FCRZY2LC}},
  note         = {Machine review of arXiv:2506.23756}
}
read the original abstract

Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimized method is specially tailored for a particular problem setting, and it is a well-documented challenge to extend optimized methods to other settings due to their highly bespoke design and analysis. We provide a general framework that derives optimized methods for composite optimization directly from those for unconstrained smooth optimization. The derived methods naturally extend the original methods, generalizing how proximal gradient descent extends gradient descent. The key to our result is certain algebraic identities that provide a unified and straightforward way of extending convergence analyses from unconstrained to composite settings. As concrete examples, we apply our framework to establish (1) the phenomenon of stepsize acceleration for proximal gradient descent; (2) a convergence rate for the proximal optimized gradient method which is faster than FISTA; (3) a new method that improves the state-of-the-art rate for minimizing gradient norm in the composite setting.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the convergence rate of the Douglas-Rachford splitting algorithm

    math.OC 2025-09 conditional novelty 4.0 of 10

    The Douglas-Rachford splitting method has worst-case residual rate ((N-1)^(N-1))/N^N for relaxation 1, and a two-subspace feasibility example attains it.

Reference graph

Works this paper leans on

60 extracted references · 49 canonical work pages · cited by 1 Pith paper

  1. [37]

    A geometric structure of acceleration and its role in making gradients small fast

    Jongmin Lee, Chanwoo Park, and Ernest Ryu. A geometric structure of acceleration and its role in making gradients small fast. In Advances in Neural Information Processing Systems , volume 34, pages 11999–12012, 2021

    work page 2021

  2. [34]

    Jaeyeon Kim, Asuman Ozdaglar, Chanwoo Park, and Ernest K. Ryu. Time-reversed dissipation induces duality between minimizing gradient norm and function value. In Advances in Neural Information Processing Systems, volume 36, pages 23389–23440, 2023

    work page 2023

  3. [9]

    Accelerating Proximal Gradient Descent via Silver Stepsizes

    Jinho Bok and Jason M. Altschuler. Accelerating proximal gradient descent via silver stepsizes. arXiv preprint arXiv:2412.05497, to appear in Conference on Learning Theory , 2025

    work page Pith review arXiv 2025

  4. [1]

    Altschuler

    Jason M. Altschuler. Greed, hedging, and acceleration in convex optimization. Master’s thesis, Mas- sachusetts Institute of Technology, 2018

    work page 2018

  5. [2]

    Altschuler and Pablo A

    Jason M. Altschuler and Pablo A. Parrilo. Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization. Math. Program., 2024

    work page 2024

  6. [3]

    Altschuler and Pablo A

    Jason M. Altschuler and Pablo A. Parrilo. Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule. J. ACM, 72(2):1–38, 2025

    work page 2025

  7. [4]

    Gradient descent with non-convex constraints: local concavity determines convergence

    Rina Foygel Barber and Wooseok Ha. Gradient descent with non-convex constraints: local concavity determines convergence. Inf. Inference, 7(4):755–806, 2018

    work page 2018

  8. [5]

    Complexity guarantees for Polyak steps with momentum

    Mathieu Barr´ e, Adrien Taylor, and Alexandre d’Aspremont. Complexity guarantees for Polyak steps with momentum. In Conference on Learning Theory, volume 125, pages 452–478. PMLR, 2020

    work page 2020

Show all 60 references
  1. [6]

    First-order methods in optimization , volume 25 of MOS-SIAM Series on Optimization

    Amir Beck. First-order methods in optimization , volume 25 of MOS-SIAM Series on Optimization . Society for Industrial and Applied Mathematics, 2017

    2017

  2. [7]

    Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems

    Amir Beck and Marc Teboulle. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process., 18(11):2419–2434, 2009

    2009

  3. [8]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems

    Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. , 2(1):183–202, 2009

    2009

  4. [10]

    Hendrickx, and Fran¸ cois Glineur

    Nizar Bousselmi, Julien M. Hendrickx, and Fran¸ cois Glineur. Interpolation conditions for linear opera- tors and applications to performance estimation problems. SIAM J. Optim. , 34(3):3033–3063, 2024. 23

    2024

  5. [11]

    Convex optimization

    Stephen Boyd and Lieven Vandenberghe. Convex optimization . Cambridge University Press, 2004

    2004

  6. [12]

    Convex until proven guilty

    Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. “Convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions. In International Conference on Machine Learning , volume 70, pages 654–663. PMLR, 2017

    2017

  7. [13]

    Performance estimation of the gradient method with fixed arbitrary step sizes

    Antoine Daccache. Performance estimation of the gradient method with fixed arbitrary step sizes. Master’s thesis, UCL - Ecole polytechnique de Louvain, 2019

    2019

  8. [14]

    An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

    Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm. Pure Appl. Math. , 57(11):1413–1457, 2004

    2004

  9. [15]

    The exact information-based complexity of smooth convex minimization

    Yoel Drori. The exact information-based complexity of smooth convex minimization. J. Complexity , 39:1–16, 2017

    2017

  10. [16]

    Performance of first-order methods for smooth convex minimization: a novel approach

    Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach. Math. Program., 145(1–2):451–482, 2014

    2014

  11. [17]

    An optimal variant of Kelley’s cutting-plane method

    Yoel Drori and Marc Teboulle. An optimal variant of Kelley’s cutting-plane method. Math. Program., 160(1-2):321–351, 2016

    2016

  12. [18]

    Acceleration methods

    Alexandre d’Aspremont, Damien Scieur, and Adrien Taylor. Acceleration methods. Foundations and Trends® in Optimization , 5(1-2):1–245, 2021

    2021

  13. [19]

    Worst-case functions for the gradient method with fixed variable step sizes

    Diego Eloi. Worst-case functions for the gradient method with fixed variable step sizes. Master’s thesis, UCL - Ecole polytechnique de Louvain, 2022

    2022

  14. [20]

    Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235 , 2023

    2023 arXiv

  15. [21]

    Accelerated gradient methods for nonconvex nonlinear and stochastic programming

    Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program., 156(1-2):59–99, 2016

    2016

  16. [22]

    Optimal first-order methods for convex functions with a quadratic upper bound

    Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Optimal first-order methods for convex functions with a quadratic upper bound. arXiv preprint arXiv:2205.15033 , 2022

    2022 arXiv

  17. [23]

    Provably faster gradient descent via long steps

    Benjamin Grimmer. Provably faster gradient descent via long steps. SIAM J. Optim. , 34(3):2588–2608, 2024

    2024

  18. [24]

    Benjamin Grimmer, Kevin Shu, and Alex L. Wang. Composing optimized stepsize schedules for gradient descent. arXiv preprint arXiv:2410.16249 , 2024

    2024

  19. [25]

    Benjamin Grimmer, Kevin Shu, and Alex L. Wang. Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS J. Optim. , 7(2):156–169, 2025

    2025

  20. [26]

    Tight convergence rate in subgradient norm of the proximal point algorithm

    Guoyong Gu and Junfeng Yang. Tight convergence rate in subgradient norm of the proximal point algorithm. arXiv preprint arXiv:2301.03175 , 2023

    2023 arXiv

  21. [27]

    Uijeong Jang, Shuvomoy Das Gupta, and Ernest K. Ryu. Computer-assisted design of accelerated composite optimization methods: OptISTA. arXiv preprint arXiv:2305.15704 , 2024

    2024

  22. [28]

    Linear convergence of gradient and proximal-gradient methods under the Polyak- Lojasiewicz condition

    Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the Polyak- Lojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases, pages 795–811. Springer, 2016

    2016

  23. [29]

    Wainwright

    Koulik Khamaru and Martin J. Wainwright. Convergence guarantees for a class of non-convex and non-smooth optimization problems. J. Mach. Learn. Res. , 20(154):1–52, 2019

    2019

  24. [30]

    Accelerated proximal point method for maximally monotone operators

    Donghwan Kim. Accelerated proximal point method for maximally monotone operators. Math. Pro- gram., 190(1-2):57–87, 2021. 24

    2021

  25. [31]

    Donghwan Kim and Jeffrey A. Fessler. Optimized first-order methods for smooth convex minimization. Math. Program., 159(1-2):81–107, 2016

    2016

  26. [32]

    Donghwan Kim and Jeffrey A. Fessler. Another look at the fast iterative shrinkage/thresholding algo- rithm (FISTA). SIAM J. Optim. , 28(1):223–250, 2018

    2018

  27. [33]

    Donghwan Kim and Jeffrey A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. J. Optim. Theory Appl. , 188(1):192–219, 2021

    2021

  28. [35]

    Jaeyeon Kim, Chanwoo Park, Asuman Ozdaglar, Jelena Diakonikolas, and Ernest K. Ryu. Mirror duality in convex optimization. arXiv preprint arXiv:2311.17296 , 2023

    2023 arXiv

  29. [36]

    A proof of the exact convergence rate of gradient descent

    Jungbin Kim. A proof of the exact convergence rate of gradient descent. arXiv preprint arXiv:2412.04427, 2025

    2025 arXiv

  30. [38]

    Yu. E. Nesterov. A method for solving the convex programming problem with convergence rate O(1/k2). Dokl. Akad. Nauk SSSR , 269(3):543–547, 1983

    1983

  31. [39]

    Lectures on convex optimization, volume 137 of Springer Optimization and Its Applica- tions

    Yurii Nesterov. Lectures on convex optimization, volume 137 of Springer Optimization and Its Applica- tions. Springer, 2018

    2018

  32. [40]

    Chanwoo Park, Jisun Park, and Ernest K. Ryu. Factor- √ 2 acceleration of accelerated gradient methods. Appl. Math. Optim. , 88(77):1–38, 2023

    2023

  33. [41]

    Jisun Park and Ernest K. Ryu. Exact optimal accelerated complexity for fixed-point iterations. In International Conference on Machine Learning , volume 162, pages 17420–17457. PMLR, 2022

    2022

  34. [42]

    Exact worst-case convergence rates of gradi- ent descent: a complete analysis for all constant stepsizes over nonconvex and convex functions

    Teodor Rotaru, Fran¸ cois Glineur, and Panagiotis Patrinos. Exact worst-case convergence rates of gradi- ent descent: a complete analysis for all constant stepsizes over nonconvex and convex functions. arXiv preprint arXiv:2406.17506, 2024

    2024

  35. [43]

    Ryu, Adrien B

    Ernest K. Ryu, Adrien B. Taylor, Carolina Bergeling, and Pontus Giselsson. Operator splitting per- formance estimation: tight contraction factors and optimal parameter selection. SIAM J. Optim. , 30(3):2251–2271, 2020

    2020

  36. [44]

    Cand` es

    Weijie Su, Stephen Boyd, and Emmanuel J. Cand` es. A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. J. Mach. Learn. Res. , 17(153):1–43, 2016

    2016

  37. [45]

    Towards principled and systematic approaches to the analysis and design of optimization algorithms

    Adrien Taylor. Towards principled and systematic approaches to the analysis and design of optimization algorithms. Habilitation ` a diriger des recherches, Universit´ e Paris Sciences & Lettres, 2024

    2024

  38. [46]

    An optimal gradient method for smooth strongly convex minimization

    Adrien Taylor and Yoel Drori. An optimal gradient method for smooth strongly convex minimization. Math. Program., 199(1-2):557–594, 2023

    2023

  39. [47]

    Taylor, Julien M

    Adrien B. Taylor, Julien M. Hendrickx, and Fran¸ cois Glineur. Exact worst-case performance of first- order methods for composite convex optimization. SIAM J. Optim. , 27(3):1283–1313, 2017

    2017

  40. [48]

    Taylor, Julien M

    Adrien B. Taylor, Julien M. Hendrickx, and Fran¸ cois Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Program., 161(1-2):307–345, 2017

    2017

  41. [49]

    Taylor, Julien M

    Adrien B. Taylor, Julien M. Hendrickx, and Fran¸ cois Glineur. Exact worst-case convergence rates of the proximal gradient method for composite convex minimization. J. Optim. Theory Appl. , 178(2):455–476, 2018. 25

    2018

  42. [50]

    An elementary approach to tight worst case complexity analysis of gradient based methods

    Marc Teboulle and Yakov Vaisbourd. An elementary approach to tight worst case complexity analysis of gradient based methods. Math. Program., 201(1-2):63–96, 2023

    2023

  43. [51]

    Relaxed proximal point algorithm: Tight complexity bounds and acceleration without momentum

    Bofan Wang, Shiqian Ma, Junfeng Yang, and Danqing Zhou. Relaxed proximal point algorithm: Tight complexity bounds and acceleration without momentum. arXiv preprint arXiv:2410.08890 , 2024

    2024 arXiv

  44. [52]

    Wilson, Ben Recht, and Michael I

    Ashia C. Wilson, Ben Recht, and Michael I. Jordan. A Lyapunov analysis of accelerated methods in optimization. J. Mach. Learn. Res. , 22(113):1–34, 2021

    2021

  45. [53]

    Taeho Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k2) rate on squared gradient norm. In International Conference on Machine Learning, volume 139, pages 12098–12109. PMLR, 2021

    2021

  46. [54]

    TaeHo Yoon and Ernest K. Ryu. Accelerated minimax algorithms flock together. SIAM J. Optim. , 35(1):180–209, 2025

    2025

  47. [55]

    On Richardson’s method for solving linear systems with positive definite matrices

    David Young. On Richardson’s method for solving linear systems with positive definite matrices. J. Math. Physics , 32(1-4):243–255, 1953

    1953

  48. [56]

    The exact worst-case convergence rate of the alternating direction method of multipliers

    Moslem Zamani, Hadi Abbaszadehpeivasti, and Etienne de Klerk. The exact worst-case convergence rate of the alternating direction method of multipliers. Math. Program., 208(1-2):243–276, 2024

    2024

  49. [57]

    Exact convergence rate of the last iterate in subgradient methods

    Moslem Zamani and Fran¸ cois Glineur. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint arXiv:2307.11134 , 2023

    2023 arXiv

  50. [58]

    Accelerated gradient descent by concatenation of stepsize schedules

    Zehao Zhang and Rujun Jiang. Accelerated gradient descent by concatenation of stepsize schedules. arXiv preprint arXiv:2410.12395 , 2024

    2024

  51. [59]

    Lee, Simon S

    Zihan Zhang, Jason D. Lee, Simon S. Du, and Yuxin Chen. Anytime acceleration of gradient descent. arXiv preprint arXiv:2411.17668 , 2024. 26 A Proof of Theorem 2.6 A.1 Implications of (2.1) In order to establish (2.2), we first parse out (2.1) by comparing the coefficients on ...

    2024 arXiv

  52. [60]

    + θ2 n−2 ⩾ − 5 16 θn(θn−1 − 1) + 2(θ2 n−1 − θn−1) − φn−1 − 1 φn−1 (2θ2 n−1 − θn−1 + x′ 3) + (θ2 n−1 − θn−1) ⩾ − 5 16 10 7 (θ2 n−1 − 1) + 2(θ2 n−1 − θn−1) − 1 4 (2θ2 n−1 − θn−1) − 1 4 x′ 3 + (θ2 n−1 − θn−1) ⩾ − 5 16 10 7 (θ2 n−1 − 1) + 2(θ2 n−1 − θn−1) − 1 4 (2θ2 n−1 − θn−1) − ...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.