pith. sign in

arxiv: 2605.08593 · v2 · pith:CO7X4HHQnew · submitted 2026-05-09 · 🧮 math.OC

Optimal Acceleration for Proximal Minimization of the Sum of Convex and Strongly Convex Functions

Govind M. Chari , Uijeong Jang , Ernest K. Ryu , Beh\c{c}et A\c{c}{\i}kme\c{s}e This is my paper

Pith reviewed 2026-05-21 09:17 UTC · model grok-4.3

classification 🧮 math.OC
keywords Douglas-Rachford splittingaccelerated proximal methodsconvex optimizationstrongly convex functionsconvergence ratescomplexity lower boundsmonotone operators
0
0 comments X

The pith

Fast Douglas-Rachford Splitting improves constants and proves optimality of the O(1/N^2) rate for sums of convex and strongly convex functions.

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

This paper develops Fast Douglas-Rachford Splitting as an accelerated method for minimizing the sum of a convex function and a strongly convex function. It achieves a faster convergence in terms of constants compared to earlier accelerated proximal methods. The work also establishes a lower bound on the complexity that matches the achieved rate and constant, showing they are the best possible. A reader interested in optimization algorithms would care because this settles the question of how fast one can guarantee convergence in this important problem setting using proximal splitting techniques. If correct, it means algorithm designers now have both an improved method and proof that further improvements in rate are impossible.

Core claim

In the setting of minimizing the sum of a convex and a strongly convex function or finding zeros of monotone plus strongly monotone operators, the Fast Douglas-Rachford Splitting method attains an O(1/N^2) rate on the squared distance to the solution with better constants than those in Chambolle-Pock and Davis-Yin, and this rate together with its leading constant is optimal as shown by a matching lower bound.

What carries the argument

Fast Douglas-Rachford Splitting (FDR), an accelerated variant of the classical Douglas-Rachford iteration that adds an extrapolation step to shrink the distance to the fixed point at the optimal rate.

If this is right

  • The FDR method requires fewer iterations than prior accelerated schemes to reach a target accuracy on the squared distance to the solution.
  • No first-order proximal method can improve on the O(1/N^2) rate or the leading constant for this problem class.
  • The same optimal guarantees hold for both the minimization formulation and the equivalent monotone inclusion problem.
  • Tighter constants give more accurate a-priori estimates of the number of iterations needed in applications.

Where Pith is reading between the lines

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

  • The same acceleration pattern may be portable to other splitting schemes such as ADMM if they can be rewritten in an equivalent fixed-point form.
  • Strong monotonicity is the key ingredient that unlocks the quadratic-rate lower bound; relaxing it would require an entirely different analysis.
  • Numerical checks on quadratic test problems could verify whether the improved constants appear in practice as well as in theory.

Load-bearing premise

The objective is exactly the sum of one convex function and one strongly convex function, or a monotone operator plus a strongly monotone operator, with the proximal mappings well-defined and computable.

What would settle it

A concrete pair of convex and strongly convex functions on which the squared distance to the solution after N steps exceeds the leading constant times 1/N^2 by more than a fixed factor would disprove the claimed rate and optimality.

read the original abstract

When minimizing the sum of a convex and a strongly convex function, or when finding the zero of the sum of a monotone operator and a strongly monotone operator, Chambolle and Pock (2010) and Davis and Yin (2015) proposed accelerated mechanisms that achieve an $\mathcal{O}(1/N^2)$ convergence rate for the squared distance to the solution, but the optimality of this rate was not established. In this work, we present Fast Douglas--Rachford Splitting (FDR), an accelerated method that improves the constants established in the prior works, and provide a complexity lower bound establishing that both the $\mathcal{O}(1/N^2)$ convergence rate and the leading-order constant of FDR's rate are optimal.

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 manuscript introduces Fast Douglas-Rachford Splitting (FDR), an accelerated proximal method for minimizing the sum of a convex function and a strongly convex function (or finding zeros of a monotone plus strongly monotone operator). It claims improved leading constants relative to Chambolle-Pock (2010) and Davis-Yin (2015) while retaining the O(1/N^2) rate on squared distance to the solution, together with a matching complexity lower bound that establishes optimality of both the rate and the leading constant under standard proximal-access assumptions.

Significance. If the stated rates and constant comparisons hold, the work strengthens the theory of accelerated proximal splitting by supplying tighter explicit constants and a matching lower-bound construction. The explicit rate proofs, direct constant comparisons, and lower-bound argument constitute a clear advance for the analysis of convex-strongly-convex problems and monotone operator splitting.

minor comments (3)
  1. Abstract: the claim of improved constants would be clearer if the numerical values of the prior constants (from Chambolle-Pock and Davis-Yin) were stated explicitly alongside FDR's constant.
  2. Section 2 (notation and assumptions): the strong-convexity parameter and the proximal-operator step-size conventions could be aligned more explicitly with the notation in the cited prior works to facilitate direct comparison.
  3. The lower-bound construction in the complexity section would benefit from a short remark on whether the same constant optimality extends immediately to the operator setting or requires additional verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. We are pleased that the significance of the improved leading constants in FDR and the matching lower bound is recognized.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives an explicit convergence rate for the proposed FDR algorithm under standard convex + strongly convex assumptions and separately constructs an independent complexity lower bound that matches the O(1/N^2) rate and leading constant. The lower bound is presented as an external information-theoretic argument rather than a quantity obtained by fitting or reparameterizing the algorithm's own iterates or constants. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain; prior works cited for baseline constants are from disjoint author groups and serve only as comparison points. The full argument remains self-contained against external benchmarks with no reduction of the central claim to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of convexity, strong convexity, monotonicity, and proximal operators from convex analysis; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The objective is the sum of a convex function and a strongly convex function (or monotone plus strongly monotone operator).
    Invoked in the problem statement and used to derive the O(1/N^2) rate.

pith-pipeline@v0.9.0 · 5675 in / 1155 out tokens · 42802 ms · 2026-05-21T09:17:01.962807+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Springer New York (2011)

    Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer New York (2011). DOI 10.1007/978-1-4419-9467-7. URL http://dx.doi.org/10.1007/978-1-4419-9467-7

    work page doi:10.1007/978-1-4419-9467-7 2011

  2. [2]

    SIAM journal on imaging sciences2(1), 183–202 (2009)

    Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences2(1), 183–202 (2009)

    work page 2009

  3. [3]

    arXiv preprint arXiv:2601.12190 (2026)

    Brice˜ no-Arias, L., Rold´ an, F.: Optimal leveraging of smoothness and strong convexity for peaceman–rachford splitting. arXiv preprint arXiv:2601.12190 (2026)

    work page arXiv 2026

  4. [4]

    arXiv preprint arXiv:2506.11785 (2025)

    Brice˜ no-Arias, L.M.: Lyapunov analysis for fista under strong convexity. arXiv preprint arXiv:2506.11785 (2025)

    work page arXiv 2025

  5. [5]

    Bruck, R.E.: On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in hilbert space. J. Math. Anal. Appl61(1), 159–164 (1977)

    work page 1977

  6. [6]

    Mathematical Pro- gramming184(1), 71–120 (2020)

    Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points i. Mathematical Pro- gramming184(1), 71–120 (2020)

    work page 2020

  7. [7]

    A first-order primal-dual algorithm for convex prob- lems with applications to imaging.J

    Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imag- ing. Journal of Mathematical Imaging and Vision40(1), 120–145 (2010). DOI 10.1007/s10851-010-0251-1. URL http://dx.doi.org/10.1007/s10851-010-0251-1

    work page doi:10.1007/s10851-010-0251-1 2010

  8. [8]

    Mathematical Programming204(1), 567–639 (2024)

    Das Gupta, S., Van Parys, B.P., Ryu, E.K.: Branch-and-bound performance estimation programming: A unified methodology for constructing optimal optimization methods. Mathematical Programming204(1), 567–639 (2024)

    work page 2024

  9. [9]

    Mathematics of Operations Research42(3), 783–805 (2017)

    Davis, D., Yin, W.: Faster convergence rates of relaxed peaceman-rachford and ADMM under regularity assumptions. Mathematics of Operations Research42(3), 783–805 (2017)

    work page 2017

  10. [10]

    Set-valued and variational analysis25, 829–858 (2017)

    Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. Set-valued and variational analysis25, 829–858 (2017)

    work page 2017

  11. [11]

    Journal of Scientific Computing66(3), 889–916 (2016)

    Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. Journal of Scientific Computing66(3), 889–916 (2016)

    work page 2016

  12. [12]

    Transactions of the American mathematical Society82(2), 421–439 (1956)

    Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American mathematical Society82(2), 421–439 (1956)

    work page 1956

  13. [13]

    Journal of Complexity39, 1–16 (2017)

    Drori, Y.: The exact information-based complexity of smooth convex minimization. Journal of Complexity39, 1–16 (2017)

    work page 2017

  14. [14]

    Journal of Complexity68, 101590 (2022)

    Drori, Y., Taylor, A.: On the oracle complexity of smooth strongly convex minimization. Journal of Complexity68, 101590 (2022)

    work page 2022

  15. [15]

    Math- ematical Programming145(1), 451–482 (2014)

    Drori, Y., Teboulle, M.: Performance of first-order methods for smooth convex minimization: a novel approach. Math- ematical Programming145(1), 451–482 (2014)

    work page 2014

  16. [16]

    Mathematical programming55(1), 293–318 (1992)

    Eckstein, J., Bertsekas, D.P.: On the douglas—rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical programming55(1), 293–318 (1992)

    work page 1992

  17. [17]

    IEEE International Symposium on Information Theory (2016)

    Fran¸ ca, G., Bento, J.: An explicit rate bound for over-relaxed ADMM. IEEE International Symposium on Information Theory (2016)

    work page 2016

  18. [18]

    Journal of Fixed Point Theory and Applications19(4), 2241–2270 (2017)

    Giselsson, P.: Tight global linear convergence rate bounds for douglas–rachford splitting. Journal of Fixed Point Theory and Applications19(4), 2241–2270 (2017)

    work page 2017

  19. [19]

    IEEE Transactions on Automatic Control62(2), 532–544 (2016)

    Giselsson, P., Boyd, S.: Linear convergence and metric selection for douglas-rachford splitting and ADMM. IEEE Transactions on Automatic Control62(2), 532–544 (2016)

    work page 2016

  20. [20]

    Bulletin of the American Mathematical Society73(6), 957–961 (1967)

    Halpern, B.: Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society73(6), 957–961 (1967). DOI 10.1090/s0002-9904-1967-11864-0. URL http://dx.doi.org/10.1090/S0002-9904-1967-11864-0

    work page doi:10.1090/s0002-9904-1967-11864-0 1967

  21. [21]

    Mathematical Programming pp

    Jang, U., Gupta, S.D., Ryu, E.K.: Computer-assisted design of accelerated composite optimization methods: Optista. Mathematical Programming pp. 1–109 (2025)

    work page 2025

  22. [22]

    Mathematical Programming190(1), 57–87 (2021)

    Kim, D.: Accelerated proximal point method for maximally monotone operators. Mathematical Programming190(1), 57–87 (2021)

    work page 2021

  23. [23]

    Mathematical programming 159(1), 81–107 (2016)

    Kim, D., Fessler, J.A.: Optimized first-order methods for smooth convex minimization. Mathematical programming 159(1), 81–107 (2016)

    work page 2016

  24. [24]

    Optimization letters15(2), 405–418 (2021) 34 Chari, Jang, Ryu, and A¸ cıkme¸ se

    Lieder, F.: On the convergence rate of the Halpern-iteration. Optimization letters15(2), 405–418 (2021) 34 Chari, Jang, Ryu, and A¸ cıkme¸ se

    work page 2021

  25. [25]

    SIAM Journal on Numerical Analysis16(6), 964–979 (1979)

    Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis16(6), 964–979 (1979)

    work page 1979

  26. [26]

    Journal of Complexity 7(2), 121–130 (1991)

    Nemirovsky, A.S.: On optimality of krylov’s information when solving linear operator equations. Journal of Complexity 7(2), 121–130 (1991)

    work page 1991

  27. [27]

    In: Dokl akad nauk Sssr, vol

    Nesterov, Y.: A method for solving the convex programming problem with convergence rateO(1/k 2). In: Dokl akad nauk Sssr, vol. 269, pp. 543–547 (1983)

    work page 1983

  28. [28]

    Mathematical Programming185(1), 1–35 (2021)

    Ouyang, Y., Xu, Y.: Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming185(1), 1–35 (2021)

    work page 2021

  29. [29]

    Applied Mathematics & Optimization88(3), 77 (2023)

    Park, C., Park, J., Ryu, E.K.: Factor- √ 2 acceleration of accelerated gradient methods. Applied Mathematics & Optimization88(3), 77 (2023)

    work page 2023

  30. [30]

    International Conference on Machine Learning (2022)

    Park, J., Ryu, E.K.: Exact optimal accelerated complexity for fixed-point iterations. International Conference on Machine Learning (2022)

    work page 2022

  31. [31]

    Journal of Mathematical Analysis and Applications72(2), 383–390 (1979)

    Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in hilbert space. Journal of Mathematical Analysis and Applications72(2), 383–390 (1979)

    work page 1979

  32. [32]

    IEEE Conference on Decision and Control (2014)

    Patrinos, P., Stella, L., Bemporad, A.: Douglas-rachford splitting: Complexity estimates and accelerated variants. IEEE Conference on Decision and Control (2014)

    work page 2014

  33. [33]

    Journal of the Society for Industrial and Applied Mathematics3(1), 28–41 (1955)

    Peaceman, D.W., Rachford Jr., H.H.: The numerical solution of parabolic and elliptic differential equations. Journal of the Society for Industrial and Applied Mathematics3(1), 28–41 (1955). DOI 10.1137/0103003

    work page doi:10.1137/0103003 1955

  34. [34]

    Princeton University Press (1970)

    Rockafellar, R.T.: Convex Analysis. Princeton University Press (1970). DOI 10.1515/9781400873173. URL http://dx.doi.org/10.1515/9781400873173

    work page doi:10.1515/9781400873173 1970

  35. [35]

    SIAM Journal on Optimization30(3), 2251–2271 (2020)

    Ryu, E.K., Taylor, A.B., Bergeling, C., Giselsson, P.: Operator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization30(3), 2251–2271 (2020)

    work page 2020

  36. [36]

    Cambridge University Press (2022)

    Ryu, E.K., Yin, W.: Large-Scale Convex Optimization via Monotone Operators. Cambridge University Press (2022)

    work page 2022

  37. [37]

    Mathematical Programming161(1), 307–345 (2017)

    Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming161(1), 307–345 (2017)

    work page 2017