acceptodds
Under review as a conference paper at ICLR 2027

Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives

Abstract

We study Bregman proximal gradient (BPG) algorithms under relative smoothness for convex, relatively strongly convex, and nonconvex objectives. Existing accelerated BPG algorithms for convex objectives typically require additional assumptions on Bregman divergences, most notably triangle-scaling conditions, which can lead to slower convergence rates. We propose a family of geometry-accelerated BPG algorithms that exploit Bregman geometry in both proximal-gradient and mirror-space updates, without imposing additional geometric conditions such as triangle-scaling conditions. Our methods adapt the stepsizes and mirror-space updates through local backtracking and computable acceptance criteria, without a global relative-smoothness constant as input. We derive convergence bounds in terms of the parameters accepted during the iterations. These bounds yield an rate for convex objectives and a linear rate for relatively strongly convex objectives when the geometry-acceleration parameters remain uniformly bounded. For nonconvex objectives, we establish an rate for a stationarity measure without requiring a lower Bregman bound or a full-domain Bregman divergence. Numerical experiments on inverse problems, entropy-regularized least squares, D-optimal design, and nonnegative matrix factorization demonstrate faster practical convergence than established Bregman baselines.

Primary area:
optimization
Keywords:
convex optimization, nonconvex optimization, mirror decent, Bregman divergence, acceleration

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_AjcSOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a family of geometry-accelerated Bregman proximal gradient methods for convex, relatively strongly convex, and nonconvex composite optimization. The methods combine proximal updates with auxiliary mirror updates and computable backtracking or reset criteria. The analysis establishes parameter-dependent accelerated bounds for convex problems and a stationarity-residual bound for nonconvex problems, with additional parameter-boundedness guarantees for Burg geometry. Experiments evaluate the methods on several inverse and learning problems.

Critical strengths

The framework accommodates distinct proximal and auxiliary geometries, providing flexibility in constructing tractable updates. The analysis addresses domain feasibility, finite termination of the inner searches, and convergence guarantees across three optimization regimes. The Burg parameter-boundedness argument has technical value beyond merely assuming bounded parameters. The experiments include established Bregman baselines and report both iteration counts and wall-clock time, demonstrating improvements on the tested instances.

Critical weaknesses
  1. Limited novelty relative to ABPG-g. ABPG-g already combines adaptive gains with conditional accelerated guarantees. GA-BPG changes the proximal center, auxiliary updates, and acceptance tests, but the manuscript does not clearly establish a substantial conceptual advance or a distinct theoretical advantage. In particular, the Burg parameter-boundedness result requires a direct comparison with guarantees obtainable for ABPG-g under comparable assumptions.

  2. Insufficient experimental attribution and baseline transparency. Missing ablations prevent separating the effects of the update structure, auxiliary geometry, and parameter adaptation. Moreover, ABPG-g’s exponent, relative-smoothness constant, gain parameters, stopping thresholds, and tuning budget are not adequately specified. The reported speedups therefore cannot be confidently attributed to the proposed mechanism rather than parameter choices or favorable problem geometry.

Questions for authors
  1. What is the clearest theoretical advantage over ABPG-g under comparable assumptions?

  2. Can the authors provide the missing ablations and complete baseline configurations?

3 comments

Thank you for these constructive comments, which prompted us to strengthen the analysis and add additional experiments.

(W1), (Q1) Limited novelty relative to ABPG-g. What is the clearest theoretical advantage over ABPG-g under comparable assumptions?

We have clarified the methodological distinction in Section 2 and the theoretical contributions in Section 3. The theoretical advantage over ABPG-g is that we establish explicit conditions guaranteeing convergence for a broader class of problems, as detailed below.

  1. Broader scope. The framework also covers relatively strongly convex and nonconvex objectives, which ABPG-g does not cover; see Algorithm 1 in Section 2 and Sections 3.2–3.3 for relatively strongly objectives and nonconvex objectives, respectively.
  2. Separate auxiliary geometry. ABPG-g's convergence guarantee involves Dψ(u,y0)D_\psi(u,y_0), while our convex bound involves Dϕ(u,y0)D_\phi(u,y_0) (Theorem 3.5). For Burg–KL, the KL term remains finite as uu approaches a finite boundary point, whereas the Burg term in ABPG-g's guarantee diverges.
  3. Explicit sufficient conditions. We derive uniform boundedness of the accepted parameters from explicit assumptions on the objective, the BPG and auxiliary geometries, and the initial point; see Theorems 3.6 and 3.10. In comparison, the KL/Burg discussion in Section 4.1 of Hanzely et al. (2021) does not provide a complete bounded-gain proof from such assumptions. Our revision extends the previous version of the Burg-specific guarantees to a broader collection of geometry pairs, summarized in Table 2 in Appendix C.4 for the convex setting examples and Remark D.3 and D.4 in Appendix D.4 for the relatively strong setting examples.

(W2), (Q2) Insufficient experimental attribution and baseline transparency. Can the authors provide the missing ablations and complete baseline configurations?

We added experiments varying the auxiliary geometry and the stepsize rule; see Figure 4 in Appendix F.1. Their relationship to the new sufficient conditions is discussed in Appendix F.2. On NYTimes, KL auxiliary geometry performs best under both stepsize rules. With this geometry, stepsize adaptation yields approximately a twofold reduction in time to a normalized gap of 10−410^{-4} compared with fixed λ=1/L\lambda=1/L.

We also clarified the ABPG-g implementation and parameter-setting policy in the opening paragraph of Section 4. This paragraph describes the use of the authors' accbpg implementation and its linesearch settings, problem-specific relative-smoothness constants, and the initial-gain choice to match the first trial proximal stepsize of the corresponding GA-BPG method.

Thank you for the reply. I raised my score.

Thank you for taking the time to review our responses. We appreciate your thoughtful feedback and constructive discussion.

Reviewer_uenROpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper Bregman proximal gradient algorithms under relative smoothness for convex, relatively strongly convex, and nonconvex objectives. The methods. adapt the stepsizes and mirror-space updates through local backtracking and computable acceptance criteria. Convergence bounds are derived in terms of the parameters accepted during the iterations. These bounds yield an O(k−2)\mathcal O(k^{−2}) rate for convex objectives and a linear rate for relatively strongly convex objectives when the geometry-acceleration parameters remain uniformly bounded. For nonconvex objectives, we establish an O(k−1)\mathcal O(k^{−1}) rate for a stationarity measure.

Critical strengths
  • The convex, relatively strongly convex, and nonconvex objectives are treated uniformly by the framework and the convergence rate of the algorithms are well-established. When reducing to Euclidean geometry, the convergence rates are optimal. For Burg geometry, the assumptions to achieve the corresponding convergence rates are verified.

  • The criteria to determine whether to accept updates and to adjust parameters in the BPG algorithm are computable and proved to be terminated in finite trails or at a stationary point.

Critical weaknesses

The accelerated convergence rates for convex and relative strongly convex cases rely on the assumption that λk/κk\lambda_k/\kappa_k is uniformly bounded and the assumption is only verified for Burg geometry. The acceleration result is therefore limited to this specific mirror function.

Questions for authors

For other geometries other than Burg geometry which are also frequently used in Bregman proximal gradient methods, how to estimate the ratio λk/κk\lambda_k/\kappa_k?

Since the relative smoothness alone is proved not to have acceleration, what is the additional assumptions that the ratio put on the objective functions or the mirror geometry?

Discussions on more mirror geometry, in particular those tested in the numerical experiments would strengthen the acceleration claims.

2 comments

We thank the reviewer for the constructive suggestions, which prompted us to generalize the parameter-boundedness analysis.

(W1), (Q2) The acceleration result is limited to specific mirror function. What is the additional assumptions that the ratio put on the objective functions or the mirror geometry?

Beyond the Euclidean case, the previous parameter-boundedness analysis was limited to Burg geometry. We now add general sufficient conditions in Theorems 3.6 and 3.10. Table 2 in Appendix C.4 organizes representative geometries, including KL, log-determinant, and polynomial generators, according to whether they satisfy these conditions and what additional assumptions are needed. For relatively strongly convex objectives, Remarks D.3 and D.4 in Appendix D.4 give concrete applications of Theorem 3.10 to Euclidean/KL and Burg geometries, respectively.

(Q1) For other geometries other than Burg geometry, how to estimate the ratio λk/κk\lambda_k / \kappa_k?

To estimate λk/κk\lambda_k / \kappa_k, we provide an upper bound on κ\kappa and a lower bound on λ\lambda. Theorem 3.6 is key to estimate κ\kappa. In particular, assumption (v) in Theorem 3.6 provides a concrete estimate on κ\kappa. Combining this upper bound with the stepsize lower bound from Proposition B.7 gives the explicit lower bound on λk/κk\lambda_k/\kappa_k stated in Inequality (33).

(Q3) Discussions on more mirror geometry, in particular those tested in the numerical experiments would strengthen the acceleration claims.

Corollary C.4 applies to the NYTimes Burg–KL experiment, and Section 4 explicitly applies Theorem 3.10 to the KL experiment on the simplex. Appendix F.2 discusses the auxiliary-geometry comparison and D-optimal design in light of the sufficient conditions.

Thank the authors for the response. I maintain my score.

Reviewer_K8rZOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces an accelerated Bregman proximal gradient algorithm for relatively smooth functions, that does not require assumptions such as the triangle-scaling conditions. Accelerated convergence rates are obtained in the convex setting, assuming that some designed algorithmic parameters remain uniformly bounded. The proposed method seems to outperform the rest of the methods in numerical experiments in a large variety of problems tailored to Bregman methods.

Critical strengths

The paper studies an important problem in optimization, the acceleration of Bregman proximal gradient methods, and presents an analysis that is not based on the standard triangle scaling condition. Moreover, the method is adaptive and does not require knowledge of the problem parameters.

Critical weaknesses

There are no critical weaknesses. The main limitation is that most of the acceleration results in the paper are not universal (even for specific Bregman divergences) and rather depend on the algorithmic parameters staying uniformly bounded. I think that since universal acceleration of Bregman methods is provably impossible, even conditional or partial results are interesting. Nevertheless, some of the claims in the paper are overstated and need to be rewritten.

Questions for authors

No questions that could affect my assessment.

2 comments

We thank the reviewer for the thoughtful assessment. We agree that the scope of the acceleration guarantees should be stated more precisely and have revised the manuscript accordingly.

  • Clarified wording: In the Abstract (lines 15–22), we have narrowed “without imposing additional geometric conditions” to the absence of a triangle-scaling condition, while retaining the bounded-parameter qualification.

  • Broader sufficient conditions: Beyond the Euclidean case, the previous analysis was limited to Burg geometry. We add Theorems 3.6 and 3.10 that provide general sufficient conditions for bounded κk\kappa_k. In comparison, the KL/Burg discussion for ABPG-g in Section 4.1 of Hanzely et al. (2021) does not provide a complete bounded-gain proof from explicit assumptions on the problem and geometry. Table 2 in Appendix C.4 organizes representative geometries, including KL, log-determinant, and polynomial generators, according to whether they satisfy our conditions and what additional assumptions are needed. For relatively strongly convex objectives, Remarks D.3 and D.4 in Appendix D.4 give concrete applications of Theorem 3.10 to Euclidean/KL and Burg geometries, respectively.

We would welcome further suggestions regarding any wording that may still overstate our results and would be happy to revise it.

Dear authors, thank you for your answers. I have no further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.