Pith. sign in

REVIEW 5 cited by

Relaxed Proximal Point Algorithm: Tight Complexity Bounds and Acceleration without Momentum

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.08890 v1 pith:O57XKA5J submitted 2024-10-11 math.OC

Bofan Wang , Shiqian Ma , Junfeng Yang , Danqing Zhou This is my paper · ORCID
classification math.OC
keywords schedulesilverstepsizeschedulestypeconvergenceratethree
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

In this paper, we focus on the relaxed proximal point algorithm (RPPA) for solving convex (possibly nonsmooth) optimization problems. We conduct a comprehensive study on three types of relaxation schedules: (i) constant schedule with relaxation parameter $\alpha_k\equiv \alpha \in (0, \sqrt{2}]$, (ii) the dynamic schedule put forward by Teboulle and Vaisbourd [TV23], and (iii) the silver stepsize schedule proposed by Altschuler and Parrilo [AP23b]. The latter two schedules were initially investigated for the gradient descent (GD) method and are extended to the RPPA in this paper. For type (i), we establish tight non-ergodic $O(1/N)$ convergence rate results measured by function value residual and subgradient norm, where $N$ denotes the iteration counter. For type (ii), we establish a convergence rate that is tight and approximately $\sqrt{2}$ times better than the constant schedule of type (i). For type (iii), aside from the original silver stepsize schedule put forward by Altschuler and Parrilo, we propose two new modified silver stepsize schedules, and for all the three silver stepsize schedules, $O(1/N^{1.2716})$ accelerated convergence rate results with respect to three different performance metrics are established. Furthermore, our research affirms the conjecture in [LG24][Conjecture 3.2] on GD method with the original silver stepsize schedule.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

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

  1. Optimized methods for composite optimization: a reduction perspective

    math.OC 2025-06 conditional novelty 8.0 of 10

    A reduction framework converts unconstrained optimized first-order methods into composite-setting methods with analogous rates, yielding new proximal OGM and proximal OGM-G guarantees.

  2. Accelerating Proximal Gradient Descent via Silver Stepsizes

    math.OC 2024-12 conditional novelty 8.0 of 10

    Proximal and projected gradient descent using the silver stepsize schedule achieve the silver convergence rate O(ε^{-log_ρ 2}) for composite convex optimization, matching the rate known only for unconstrained smooth g...

  3. Finite Horizon Optimization: Framework and Applications

    math.OC 2024-12 reject novelty 6.0 of 10

    A finite-horizon stepsize rule for the primal-dual method on LP, found via a 4x4 SDP, is claimed to accelerate convergence at the T-th iteration and to give about 3.9x speedup on Netlib instances.

  4. 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.

  5. Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule

    math.OC 2024-12 accept novelty 4.0 of 10

    For m-strongly convex, M-smooth separable objectives, GD with i.i.d. inverse stepsizes from the Arcsine(m,M) distribution converges almost surely at rate (√κ−1)/(√κ+1), the optimal accelerated rate.

Pith tools