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

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

Pith reviewed 2026-05-12 01:40 UTC · model grok-4.3

classification 🧮 math.OC

keywords Douglas-Rachford splittingaccelerated proximal methodsconvex and strongly convex minimizationoperator splittingcomplexity lower boundsmonotone plus strongly monotone operatorsO(1/N²) convergence

0 comments

The pith

Fast Douglas-Rachford Splitting achieves optimal O(1/N²) convergence 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.

The paper introduces an accelerated algorithm called Fast Douglas-Rachford Splitting that solves the problem of minimizing the sum of one convex function and one strongly convex function. It improves the leading constants from earlier accelerated methods while preserving the O(1/N²) rate in squared distance to the solution. The authors also prove a matching lower bound that shows no algorithm can do better than this rate or this constant in the worst case over the general class of such problems. The same results apply when the task is recast as finding a zero of a monotone operator plus a strongly monotone operator. This establishes both the speed and the sharpness of the method for a broad family of proximal minimization tasks.

Core claim

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 O(1/N²) convergence rate and the leading-order constant of FDR's rate are optimal.

What carries the argument

Fast Douglas-Rachford Splitting (FDR), an accelerated variant of Douglas-Rachford splitting that incorporates momentum to reach the optimal rate for convex-plus-strongly-convex problems.

Load-bearing premise

The lower bound applies to the general class of convex-plus-strongly-convex problems without any extra structure or restrictions on the proximal operators.

What would settle it

A concrete algorithm that achieves faster than O(1/N²) convergence or a strictly better leading constant on some instance of a convex-plus-strongly-convex problem without using extra information beyond proximal evaluations would falsify the optimality claim.

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.

Desk Editor's Note private letter to a colleague

FDR improves the leading constants over prior accelerated splitting methods and supplies a matching lower bound that establishes optimality for both the rate and the constant on convex-plus-strongly-convex problems.

read the letter

The core takeaway is that this paper tightens the constants in accelerated Douglas-Rachford splitting and then proves you cannot improve the leading term further. FDR achieves a better O(1/N²) rate than Chambolle-Pock 2010 and Davis-Yin 2015, and the lower bound matches both the rate and FDR's specific constant for the sum of a convex and a strongly convex function (or monotone plus strongly monotone operator). That combination is what stands out: most prior work stopped at an upper bound without closing the optimality gap on the prefactor. The lower bound is framed as a direct complexity result on the problem class rather than something derived from the algorithm itself, which keeps it clean. The citations are focused and appropriate; they engage the two main references without unnecessary padding. The analysis appears formally grounded, with explicit rates rather than asymptotic statements. On the soft spots, the lower-bound construction needs checking in the full proof to confirm it applies without extra restrictions on the proximal oracles or hidden regularity. The abstract gives no numerical examples, so we do not yet see how much the constant improvement matters in practice, but that is secondary for a complexity-focused paper. The work is coherent on its own terms and shows clear engagement with the existing literature. It is aimed at researchers who analyze first-order methods and operator splitting. Anyone doing tight-rate work in nonsmooth convex optimization will find the matching bound useful. I would send this to peer review.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces Fast Douglas-Rachford Splitting (FDR), an accelerated proximal algorithm for minimizing the sum of a convex function and a strongly convex function (equivalently, finding zeros of a monotone plus strongly monotone operator). It claims an O(1/N²) convergence rate on the squared distance to the solution with improved leading constants over Chambolle-Pock (2010) and Davis-Yin (2015), together with a matching complexity lower bound establishing optimality of both the rate and the leading constant for the general problem class without extra structure.

Significance. If the upper-bound analysis and lower-bound construction hold, the work closes an open question on optimality for accelerated proximal splitting in the convex-plus-strongly-convex setting. The explicit constant improvement and the independent lower bound (which does not rely on self-referential fitting) are valuable contributions to the theory of first-order methods and provide guidance for practical parameter selection.

minor comments (2)

The abstract states that FDR improves the constants but does not display the explicit improved leading constant; adding the numerical value would help readers immediately compare with prior work.
In the complexity lower-bound section, the construction of the hard instance (the specific choice of the convex and strongly convex functions) should be cross-referenced to the exact parameter regime used in the upper-bound analysis to make the matching explicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, recognition of the contributions, and recommendation to accept the manuscript. We appreciate the acknowledgment that the work addresses an open question on optimality for accelerated proximal splitting in the convex-plus-strongly-convex setting.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivation consists of an explicit construction of the FDR algorithm with a direct convergence analysis yielding improved constants, plus a separate lower-bound argument constructed for the general convex-plus-strongly-convex (or monotone-plus-strongly-monotone) problem class without reference to FDR's parameters or iterates. No step equates a claimed prediction to a fitted quantity by construction, imports uniqueness via self-citation chains, or renames a known result as a new derivation. Prior citations (Chambolle-Pock, Davis-Yin) are external and the lower bound is stated to hold under the paper's weakest assumptions, rendering the optimality claim self-contained and falsifiable outside the algorithm itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard convex optimization assumptions without introducing new free parameters or invented entities.

axioms (1)

domain assumption The objective is the sum of a convex function and a strongly convex function (or the sum of a monotone operator and a strongly monotone operator).
This is the explicit problem class stated in the abstract and is the standard setup for proximal minimization.

pith-pipeline@v0.9.0 · 5444 in / 1181 out tokens · 61184 ms · 2026-05-12T01:40:31.915340+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[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]

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]

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
[4]

Journal of Mathematical Imaging and Vision40(1), 120–145 (2010)

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
[5]

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
[6]

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
[7]

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
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

Optimization letters15(2), 405–418 (2021)

Lieder, F.: On the convergence rate of the Halpern-iteration. Optimization letters15(2), 405–418 (2021)

work page 2021
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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
[21]

In: International Conference on Machine Learning, pp

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

work page 2022
[22]

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
[23]

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
[24]

Cambridge University Press (2022)

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

work page 2022