- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes an accelerated Bregman gradient method for optimization problems under relative smoothness. While classical accelerated Bregman proximal gradient methods rely on a triangle-scaling property and achieve convergence rates depending on its exponent, the proposed method does not require this property. Instead, the authors introduce the dual Bregman Length Distortion Factor (BLDF) and establish an accelerated convergence rate under a bounded local geometric distortion assumption. They further establish an accelerated linear convergence rate for relatively strongly convex objectives.
Critical strengths
-
The proposed method does not require the triangle-scaling property assumed in classical accelerated Bregman methods. The primal–dual approach provides an interesting framework for adaptive acceleration, using a certificate based on upper and lower models of the objective.
-
The paper introduces the dual BLDF and investigates its properties, providing a new way to characterize local geometric distortion in Bregman optimization.
-
The paper establishes an accelerated linear convergence rate for relatively strongly convex objectives. The method exploits the relative strong convexity parameter while adapting to the smoothness and geometric constants.
Critical weaknesses
1. Limited improvement over existing adaptive ABPG methods.
The accelerated convergence guarantees rely on the eventual uniform boundedness of the local dual geometric distortion. This condition is closely related to the bounded triangle-scaling gain used in existing ABPG analyses. In particular, the adaptive ABPG-g method of Hanzely et al. (2021) already avoids requiring a fixed global triangle-scaling exponent and provides convergence guarantees depending on the accepted gains.
Although the proposed geometric condition is formally different, it remains unclear to what extent it is weaker or more practically verifiable. Moreover, the paper does not establish the required uniform boundedness of the local distortion from readily verifiable assumptions for sufficiently broad problem classes. Without this condition, the rate is not guaranteed by the present analysis.
Consequently, the improvement over ABPG-g in the convex setting appears limited.
2. Additional regularity assumptions on the Bregman kernel.
Theorem 3 assumes that the conjugate kernel is twice differentiable. This is stronger than the Legendre assumption in Assumption 1 and restricts the class of admissible Bregman kernels. For example, when , its conjugate is not twice differentiable at the origin.
Although the authors acknowledge this limitation, it reduces the generality of the main accelerated convergence result.
3. Potential lack of well-definedness of the subproblems.
I am concerned that the subproblems in the proposed algorithm may not always admit minimizers under Assumption 1. Consider the one-dimensional example , with , , and initial parameters . This example satisfies Assumption 1 with and . Moreover, the objective has a unique interior minimizer. However, at the first trial of Algorithm 2, we obtain , , , and . Consequently, the subproblem in (5)–(6) becomes unbounded below. Thus, the subproblem has no minimizer, and the algorithm cannot proceed as currently specified. The first Bregman gradient subproblem in Algorithm 4 is also unbounded for these initial parameters.
This suggests that additional assumptions or safeguards may be required to ensure that the algorithm is well-defined. In particular, the existence of a minimizer of the original objective does not appear sufficient to guarantee the solvability of the subproblems.
4. Insufficient computational comparison.
The numerical experiments primarily report iteration counts and first-order oracle calls, without reporting wall-clock computation times. Although oracle calls are a meaningful measure and the paper accounts for rejected backtracking trials, the actual computational overhead of the nested backtracking procedure and Bregman subproblems remains unclear.
In particular, it is difficult to assess whether the proposed method offers a practical advantage over existing accelerated Bregman methods. Experiments on larger-scale problems, including computation times and backtracking statistics, would provide a more convincing evaluation.
Furthermore, in the relatively strongly convex experiments, ABrA-GD exploits the parameter , whereas the compared ABPG methods do not. This makes it difficult to separate the advantage of the proposed algorithm from the advantage of exploiting additional problem information.
5. Incomplete discussion of recent related work.
I also find the discussion of recent developments in accelerated Bregman optimization somewhat incomplete.
For example, Merchav et al. (2026) develop another accelerated Bregman proximal gradient framework and establish an rate for the Boltzmann–Shannon entropy kernel under additional assumptions. This is closely related to the present work and deserves discussion.
Aguirre and Ostrovskii (2026) establish a lower bound showing that acceleration is impossible in general for entropy-smooth convex optimization. Although the present paper cites earlier non-acceleration results, this more recent result is particularly relevant. It would be interesting to clarify how the bounded local distortion condition restricts the problem class so as to avoid such lower bounds.
De Marchi et al. (2026) also study mirror descent methods with logarithmic barriers, including cases where the solution lies on the boundary and the Bregman divergence to the solution may be infinite. The present convergence analysis relies on a finite initial Bregman divergence and does not address such settings.
A more detailed discussion of these results would help clarify the scope, limitations, and novelty of the proposed acceleration guarantees.
The relevant references are:
- Merchav, R., Sabach, S., Teboulle, M. (2026). The adaptive integrated mean: a novel perspective for acceleration and its extension to Bregman first-order methods. Mathematical Programming.
- Aguirre, J. M., Ostrovskii, D. M. (2026). Entropy-Smooth Convex Optimization Cannot Be Accelerated. arXiv:2607.27476.
- De Marchi, A., Malitsky, Y., Taylor, A. B. (2026). Mirror Descent Algorithms with Logarithmic Barriers. arXiv:2608.22834.
6. Overall assessment of the contribution.
I recognize that avoiding an explicit triangle-scaling assumption and establishing accelerated linear convergence under relative strong convexity are meaningful contributions compared with Hanzely et al. (2021).
However, the accelerated convergence guarantees still depend on additional geometric boundedness assumptions whose practical applicability is not sufficiently established. The theoretical improvement over existing adaptive ABPG methods, particularly in the convex setting, appears limited.
Questions for authors
-
Theorem 3 assumes the eventual uniform boundedness of . Can this assumption be verified from standard, practically checkable conditions for important problem classes? To what extent is this condition weaker than the assumptions underlying existing adaptive ABPG methods, such as ABPG-g? Also, could the accelerated convergence guarantees be established under a weaker condition formulated directly in terms of the dual BLDF?
-
Why does Theorem 3 assume that the inner backtracking loops terminate for the first iterations? Can finite termination be guaranteed independently of the bounded geometric distortion assumption? In particular, how does the algorithm handle cases where a trial Bregman subproblem has no minimizer, as illustrated by the example in Weakness 3?
-
The proposed algorithm requires the relative strong convexity parameter as an input. How should this parameter be determined in practice? How sensitive are the theoretical guarantees and numerical performance to underestimating or overestimating ?
-
Could the authors provide experiments on larger-scale problems and report wall-clock computation times, including the overhead of backtracking? This would help clarify the practical advantages of the proposed method over existing accelerated Bregman methods.
-
As acknowledged in Appendix F, the proposed accelerated convergence analysis does not cover an additional nonsmooth convex term, unlike Hanzely et al. (2021). Although Appendix F identifies difficulties in controlling the nonsmooth proximal residual, could the authors clarify whether this is an inherent limitation of the proposed acceleration framework or primarily a limitation of the current proof technique? Is there a plausible way to extend the accelerated guarantees to composite objectives?
7 comments
Rebuttal for Reviewer BJ91 (2/3)
3. Potential lack of well-definedness of the subproblems.
"the subproblem has no minimizer, and the algorithm cannot proceed as currently specified"
This case needs no additional assumption: a trial whose subproblem has no minimizer is rejected, and is doubled. Algorithms 3-4 are not explicit about this rule; we will state it in the paper.
On your instance (, ), doubling solves the problem:
| Iteration | Trial | Result |
|---|---|---|
| 0 | 2 | rejected: subproblem unbounded |
| 0 | 4 | accepted |
| 1 | 2 | rejected: subproblem unbounded |
| 1 | 4 | rejected: exit test fails |
| 1 | 8 | accepted |
In general, doubling always ends with a solvable subproblem. As grows, , , and tends to a Bregman gradient step from . Since is interior, the subproblem then has a minimizer. The inner backtracking (Algorithm 4) also always ends: it doubles , and it accepts at the latest once .
The safeguard is needed only to bound the number of inner iterations (next question).
"Why does Theorem 3 assume that the inner backtracking loops terminate for the first iterations? Can finite termination be guaranteed independently of the bounded geometric distortion assumption?"
Yes, with the safeguard (App. G.2), which uses the backtracked estimate of (general response 1/3, point 3). The safeguard rejects every trial with . Since decreases as grows, the search stops after finitely many trials and takes the fallback step, a backtracked Bregman gradient step. Without the safeguard, Theorem 3 bounds the number of trials only through . We will add this stopping rule to Algorithm 2 and state termination as a proposition.
4. Insufficient computational comparison.
"without reporting wall-clock computation times ... the actual computational overhead of the nested backtracking procedure ... remains unclear"
General response 3/3 now reports the time of every new experiment and the cost of one oracle call of each method.
- Counting oracle calls does not favor ABrA-GD: 3 of its 5 calls per iteration compute only, which is cheaper than . Average calls per iteration (rounded):
| Method | Calls with and | Calls with only (cheaper) | Oracle calls |
|---|---|---|---|
| ABrA-GD | 2 | 3 | 5 |
| ABPG-e | 1 | 1 | 2 |
| ABPG-g | 2 | 2 | 4 |
| ABPG | 1 ( only) | 0 | 1 |
| BPG | 1 | 0 | 1 |
| BPG-LS | 1 | 2 | 3 |
- On the larger D-optimal instances, ABrA-GD is competitive with ABPG, and it is the fastest in time for high accuracy targets.
- Rejected trials count as oracle calls (Sec. 6), so the overhead of backtracking is in the figures (measured in general response 3/3).
We will add these timings to the paper, with figures that plot the time on the x-axis.
"ABrA-GD exploits the parameter , whereas the compared ABPG methods do not"
Exploiting is the contribution: no ABPG variant can use with a guarantee. The triangle-scaling analyses give no accelerated linear rate under relative strong convexity (App. E.1). Running ABrA-GD with on the same objective isolates the effect: using makes it 3-3.5 times faster (general response 3/3).
Rebuttal for Reviewer BJ91 (3/3)
5. Incomplete discussion of recent related work.
"the discussion of recent developments ... somewhat incomplete"
We agree, and will add the three papers.
- Aguirre-Ostrovskii, on "how the bounded local distortion condition restricts the problem class so as to avoid such lower bounds": we agree: their bound rules out a uniform accelerated rate over the entropy-smooth class, for every first-order method, ABPG included. Their bound covers only the first iterations, and our burn-in can be longer. Our a priori result also needs a minimizer away from the boundary of the domain (automatic for Burg, general response 2/3). We will add this reference to the paper.
- Merchav-Sabach-Teboulle: a conditional rate for the entropy kernel.
- De Marchi-Malitsky-Taylor: we agree that our bounds need , i.e. interior minimizers. In our experiments the minimizers are on the boundary, so these experiments are outside the theory. The bounds of ABPG also contain , so the same holds for them. We will state this in Sec. 1 and 7.
6. Overall assessment of the contribution.
"the accelerated convergence guarantees still depend on additional geometric boundedness assumptions whose practical applicability is not sufficiently established. The theoretical improvement over existing adaptive ABPG methods, particularly in the convex setting, appears limited"
This concern applies equally to ABPG: ABPG-g is accelerated only if its accepted gains stay bounded, an a posteriori condition like ours (general response 1/3). So it is not a fair argument against ABrA-GD. For and the Burg, KL and power kernels, the new theorem now establishes our assumption a priori (point 1 and general response 2/3).
The improvement over ABPG-g is real. ABrA-GD needs no gain or exponent search. For , it reaches an accelerated linear rate, which ABPG-g does not give (App. E.1). For the Burg kernel, ABrA-GD is accelerated a priori, while the a priori rate of ABPG is at best (general response 2/3). We hope that these answers will lead the reviewer to revise their assessment.
Questions
- "Can this assumption be verified from standard, practically checkable conditions for important problem classes? To what extent is this condition weaker than the assumptions underlying existing adaptive ABPG methods, such as ABPG-g? Also, could the accelerated convergence guarantees be established under a weaker condition formulated directly in terms of the dual BLDF?"
Yes. See point 1 (R BJ91 (1/3)).
- "Can finite termination be guaranteed independently of the bounded geometric distortion assumption? In particular, how does the algorithm handle cases where a trial Bregman subproblem has no minimizer"
Yes. See point 3 (R BJ91 (2/3)).
- "How should this parameter be determined in practice? How sensitive are the theoretical guarantees and numerical performance to underestimating or overestimating ?"
is usually known by construction, as in the anchored form (Eq. (1)). If is relatively strongly convex with an unknown , ABrA-GD with and the same restart heuristic as ABPG is about as fast as with the true (general response 1/3, point 2, and 3/3). An underestimate keeps Assumption 1 valid and slows the rate; an overestimate voids the guarantee. is the extreme underestimate: 5566 against 1627 oracle calls on housing and 6764 against 2004 on abalone (general response 3/3).
- "Could the authors provide experiments on larger-scale problems and report wall-clock computation times, including the overhead of backtracking?"
See point 4 (R BJ91 (2/3)) and general response 3/3.
- "could the authors clarify whether this is an inherent limitation of the proposed acceleration framework or primarily a limitation of the current proof technique? Is there a plausible way to extend the accelerated guarantees to composite objectives?"
Of the proof technique, as far as we know: ABrA-GD is well defined for when a Bregman proximal step of is available. The envelope and the lower model extend to (App. F). The accelerated BLDF proof does not: its cancellation uses a single gradient-generated dual direction, and the composite model brings a set-valued subgradient residual. An extension would need additional control of this residual, which we do not have yet. In practice, ABrA-GD already handles such a term: in the Poisson L1 experiment (Fig. 8), the objective has an term, handled by the proximal step, and ABrA-GD matches the best ABPG variants.
Rebuttal for Reviewer BJ91 (1/3)
We thank the reviewer for the detailed review, the questions on the analysis, and the references.
1. Limited improvement over existing adaptive ABPG methods.
First, ABPG-g has the same limitation. ABPG-g, the adaptive accelerated ABPG variant, is accelerated only if its accepted gains stay bounded, an a posteriori condition like ours. Hanzely et al. bound it only under a box or a Hessian assumption (their Eq. (40) and Eq. (16)). Moreover, whenever ABPG-g has a uniform gain G, then ρ2≤G (App. E.2), so ABrA-GD is accelerated too. What ABrA-GD adds over ABPG-g is no gain or exponent search and, for μ>0, an accelerated linear rate (App. E.1).
Second, we identified a family of problems where the condition holds a priori: for μ>0, the Burg and KL kernels on the orthant or the simplex, and the power kernel on Rn, ABrA-GD is locally accelerated after an explicit iteration K (general response 2/3). For KL and power, the theorem also needs a minimizer away from the boundary of the domain. For Burg, this holds automatically.
Third, restricting the comparison to the convex setting leaves out one of the main contributions of the paper. ABrA-GD exploits relative strong convexity: for μ>0, it reaches an accelerated linear rate (App. E.1), which ABPG-g does not give. The improvement over ABPG-g is largest in this setting.
Yes. The proof of Theorem 3 uses ρk only through the bound cd∗(s,Ωk;2)≤ρk on the dual BLDF (App. C), so Theorem 3 holds when the dual BLDF stays bounded along the iterates. This condition is weaker: cd∗≤ρ whenever ρ is defined (Proposition 1), and it needs no twice differentiability of d∗ (point 2 below). We will state Theorem 3 this way.
2. Additional regularity assumptions on the Bregman kernel.
Twice differentiability is needed only to bound the distortion by ρ. The proof of Theorem 3 uses only the dual BLDF, which is defined for any Legendre kernel. Both steps of the proof that use ρk apply the bound cd∗(s,Ωk;2)≤ρk (App. C), and Proposition 1 needs d∗ twice differentiable only to give this bound. So ρk=∞ does not mean that the distortion is infinite. For a piecewise quadratic d∗, ρ is undefined at the kink, but the dual BLDF stays bounded. Theorem 3 then applies with the BLDF in place of ρk. We will state Theorem 3 with the dual BLDF (point 1 above). For d(x)=x4/4 the curvature of d∗ is unbounded at 0, so the dual BLDF itself is unbounded near 0, and no acceleration is claimed there.
ABPG-g has the same structure. Its gain is defined for any kernel, but Hanzely et al. bound it only through a Taylor expansion of d with a non-singular Hessian (their Sec. 2.2, Eq. (16)), which is the same assumption as d∗ twice differentiable. In their Sec. 2.2, Hanzely et al. also mention that for d(x)=x4/4 the gain can be unbounded.