acceptodds
Under review as a conference paper at ICLR 2027

ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization

Abstract

We propose ABrA-GD (Adaptive Bregman Accelerated Gradient Descent), an adaptive algorithm for relatively smooth convex optimization. The algorithm is derived from a computable primal–dual certificate that guarantees progress by comparing the objective value with a lower bound on the minimum of a regularized objective. This certificate enables adaptation to both smoothness and geometry, using only the relative strong convexity constant as a problem-dependent input. We introduce the dual Bregman Length Distortion Factor (BLDF), which measures how dual Bregman lengths change under an anchor shift or rescaling. Under bounded local dual BLDF, ABrA-GD achieves an accelerated rate for convex objectives and an accelerated linear rate for relatively strongly convex objectives.

Primary area:
optimization
Keywords:
convex optimization, accelerated gradient methods, Bregman divergence, relative smoothness, relative strong convexity, mirror descent, adaptive methods, backtracking line search, primal-dual

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_BJ91OpenReview ↗
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 O(1/k2)O(1/k^2) 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 O(1/k2)O(1/k^2) 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 d∗d^* is twice differentiable. This is stronger than the Legendre assumption in Assumption 1 and restricts the class of admissible Bregman kernels. For example, when d(x)=x4/4d(x)=x^4/4, 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 d(x)=−log⁡x,f(x)=−6log⁡(1+x),x>0d(x)=-\log x,\qquad f(x)=-6\log(1+x),\qquad x>0, with μ=1\mu=1, x0=1x_0=1, and initial parameters L0=M−1=1L_0=M_{-1}=1. This example satisfies Assumption 1 with L=7L=7 and μ=1\mu=1. Moreover, the objective ϕ(x)=f(x)+μDd(x,x0)\phi(x)=f(x)+\mu D_d(x,x_0) has a unique interior minimizer. However, at the first trial of Algorithm 2, we obtain M0=2M_0=2, t0=1t_0=1, η1−1=1\eta_1^{-1}=1, and λ1=∇f(1)=−3\lambda_1=\nabla f(1)=-3. 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 μ\mu, 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 O(log⁡k/k2)O(\log k/k^2) 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
  1. Theorem 3 assumes the eventual uniform boundedness of ρk\rho_k. 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?

  2. Why does Theorem 3 assume that the inner backtracking loops terminate for the first KK 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?

  3. The proposed algorithm requires the relative strong convexity parameter μ\mu as an input. How should this parameter be determined in practice? How sensitive are the theoretical guarantees and numerical performance to underestimating or overestimating μ\mu?

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

  5. 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
AuthorsOpenReview ↗

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.

"the paper does not establish the required uniform boundedness of the local distortion from readily verifiable assumptions"

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 GG, then ρ2≤G\rho^2\le 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\mu>0, an accelerated linear rate (App. E.1).

Second, we identified a family of problems where the condition holds a priori: for μ>0\mu>0, the Burg and KL kernels on the orthant or the simplex, and the power kernel on Rn\mathbb R^n, ABrA-GD is locally accelerated after an explicit iteration KK (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\mu>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.

"could the accelerated convergence guarantees be established under a weaker condition formulated directly in terms of the dual BLDF?"

Yes. The proof of Theorem 3 uses ρk\rho_k only through the bound cd∗(s,Ωk;2)≤ρkc_{d^{\ast}}(s,\Omega_k;2)\le\rho_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∗≤ρc_{d^{\ast}}\le\rho whenever ρ\rho is defined (Proposition 1), and it needs no twice differentiability of d∗d^{\ast} (point 2 below). We will state Theorem 3 this way.

2. Additional regularity assumptions on the Bregman kernel.

"Theorem 3 assumes that the conjugate kernel d∗d^{\ast} is twice differentiable ... d(x)=x4/4d(x) = x^4/4"

Twice differentiability is needed only to bound the distortion by ρ\rho. 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\rho_k apply the bound cd∗(s,Ωk;2)≤ρkc_{d^{\ast}}(s,\Omega_k;2)\le\rho_k (App. C), and Proposition 1 needs d∗d^{\ast} twice differentiable only to give this bound. So ρk=∞\rho_k=\infty does not mean that the distortion is infinite. For a piecewise quadratic d∗d^{\ast}, ρ\rho is undefined at the kink, but the dual BLDF stays bounded. Theorem 3 then applies with the BLDF in place of ρk\rho_k. We will state Theorem 3 with the dual BLDF (point 1 above). For d(x)=x4/4d(x)=x^4/4 the curvature of d∗d^{\ast} 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 dd with a non-singular Hessian (their Sec. 2.2, Eq. (16)), which is the same assumption as d∗d^{\ast} twice differentiable. In their Sec. 2.2, Hanzely et al. also mention that for d(x)=x4/4d(x)=x^4/4 the gain can be unbounded.

AuthorsOpenReview ↗

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 MkM_k is doubled. Algorithms 3-4 are not explicit about this rule; we will state it in the paper.

On your instance (L0=1L_0=1, M−1=1M_{-1}=1), doubling MkM_k solves the problem:

IterationTrial MMResult
02rejected: subproblem unbounded
04accepted
12rejected: subproblem unbounded
14rejected: exit test fails
18accepted

In general, doubling MkM_k always ends with a solvable subproblem. As MkM_k grows, zk+1→zkz_{k+1}\to z_k, yk→xkbesty_k\to x_k^{best}, and xk+1x_{k+1} tends to a Bregman gradient step from xkbestx_k^{best}. Since zkz_k is interior, the subproblem then has a minimizer. The inner backtracking (Algorithm 4) also always ends: it doubles LnewL_{new}, and it accepts at the latest once Lnew≥LL_{new}\ge L.

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 KK 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 LL (general response 1/3, point 3). The safeguard rejects every trial with tk<tkgdt_k<t_k^{gd}. Since tkt_k decreases as MkM_k 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 ρk\rho_k. 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 ff only, which is cheaper than ∇f\nabla f. Average calls per iteration (rounded):
MethodCalls with ff and ∇f\nabla fCalls with ff only (cheaper)Oracle calls
ABrA-GD235
ABPG-e112
ABPG-g224
ABPG1 (∇f\nabla f only)01
BPG101
BPG-LS123
  • 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 μ\mu, whereas the compared ABPG methods do not"

Exploiting μ\mu is the contribution: no ABPG variant can use μ\mu with a guarantee. The triangle-scaling analyses give no accelerated linear rate under relative strong convexity (App. E.1). Running ABrA-GD with μ=0\mu=0 on the same objective isolates the effect: using μ\mu makes it 3-3.5 times faster (general response 3/3).

AuthorsOpenReview ↗

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 T≲d/8T\lesssim\sqrt{d/8} iterations, and our burn-in KK 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 O(log⁡k/k2)O(\log k/k^2) rate for the entropy kernel.
  • De Marchi-Malitsky-Taylor: we agree that our bounds need Dd(x⋆,x0)<∞D_d(x_\star,x_0)<\infty, i.e. interior minimizers. In our μ=0\mu=0 experiments the minimizers are on the boundary, so these experiments are outside the theory. The bounds of ABPG also contain Dd(x⋆,x0)D_d(x_\star,x_0), 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 μ>0\mu>0 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 μ>0\mu>0, 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 O(k−1/2)O(k^{-1/2}) (general response 2/3). We hope that these answers will lead the reviewer to revise their assessment.

Questions

  1. "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)).

  1. "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)).

  1. "How should this parameter be determined in practice? How sensitive are the theoretical guarantees and numerical performance to underestimating or overestimating μ\mu?"

μ\mu is usually known by construction, as in the anchored form ϕ=f+μDd(⋅,x0)\phi=f+\mu D_d(\cdot,x_0) (Eq. (1)). If ff is relatively strongly convex with an unknown μ\mu, ABrA-GD with μ=0\mu=0 and the same restart heuristic as ABPG is about as fast as with the true μ\mu (general response 1/3, point 2, and 3/3). An underestimate keeps Assumption 1 valid and slows the rate; an overestimate voids the guarantee. μ=0\mu=0 is the extreme underestimate: 5566 against 1627 oracle calls on housing and 6764 against 2004 on abalone (general response 3/3).

  1. "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.

  1. "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 f+rf+r when a Bregman proximal step of rr is available. The envelope and the lower model extend to f+rf+r (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 ℓ1\ell_1 term, handled by the proximal step, and ABrA-GD matches the best ABPG variants.

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

This paper proposes ABrA-GD, an adaptive accelerated method for relatively smooth and relatively (strongly) convex functions. The method works by guaranteeing a verifiable primal-dual gap, which in turn implies convergence by means of the Bregman-Moreau envelope of the objective, similar in spirit to the approximate duality gap technique by Diakonikolas–Orecchia. The gap is constructed using a lower bound on the dual value of the Bregman-Moreau envelope, and an upper bound on the objective, both of which can be computed explicitly without manipulating conjugates. By backtracking the acceleration hyperparameter M_k and a smoothness estimate L_cur, if necessary, at least as much progress on the upper bound as on the lower bound is achieved by an appropriate choice of M_k, L_cur and other hyperparameters, in the spirit of Nesterov's estimate sequences. This provides an exit test that certifies the optimality gap, with convergence rate O((\sum_k M_k^{-1/2})^{-2}) in the convex case and O(\prod_i(1-\sqrt{\mu/M_i}) )in the strongly convex case. The paper introduces the concept of Bregman Length Distortion Factor (BLDF), which provides an implicit sufficient lower bound on M_k that need not be explicitly checked. In particular, for problems with bounded local BLDF along the optimization path, after finitely many iterations the accepted M_k remain bounded, and acceleration is achieved both in convex and strongly convex problems, when the strong convexity parameter is provided as input. Numerical experiments show competitive performance with prior related methods.

Critical strengths
  1. Clean primal-dual formulation to derive the first accelerated method with linear rate for relatively smooth and strongly convex objectives with only the strong convexity parameter as input (and not the generalized CS constant). It's consequential because it closes a gap and provides a blueprint for developing new methods.
  2. Introducing the BLDF concept: a meaningful local geometric quantity that gives a sufficient condition for when relatively smooth (and relatively strongly convex) problems can be accelerated along a path. It's consequential because it could lead to a better understanding of this class of problems, and indeed already shows as a fundamental quantity in other methods.
Critical weaknesses
  1. Convergence guarantees built on the dual norm distortion factor. It seems that locally bounded BLDF is automatic for solutions inside the domain, but it's unclear whether the constants that depend on rho^2 and rho^4 can be much larger than the constants in other methods, say C in GCS.
  2. Not a reason for rejection, but the empirical performance seems to be a weakness. The only case in which ABrA-GD clearly outperforms prior art in the provided experiments is for the relatively strongly convex case when competing methods do not use restart, which could be seen as unfair, even if that's not part of the actual method.
Questions for authors
  1. It seems that the only way to guarantee that ABrA-GD always performs as well as BPG is through the safeguard, which depends on the true value of L. Can it be replaced by some estimate, e.g. using backtracking, or is the true value crucial?
  2. How does the generalized CS constant C compare with \rho^2 (and rho^4 for \mu>0)? Does GCS carry a transient term comparable to \bar{K}?
  3. Why is GCS not in the numerical experiments?

Clarification requests:

  1. Do you have an intuition for why ABPG seems to couple better with restart than ABrA-GD?
2 comments
AuthorsOpenReview ↗

Rebuttal for Reviewer dsim

We thank the reviewer for the review and the precise questions on the constants and the experiments.

We answer the two main concerns (the constants against GCS; the comparison with ABPG without restart) and the questions on the safeguard, GCS and restart below. We would be glad to clarify any point that remains open in the discussion.

"whether the constants that depend on rho^2 and rho^4 can be much larger than the constants in other methods, say C in GCS"

Not comparable in general: CC is a bilinear inequality on f−μdf-\mu d and dd; ρ\rho is a Hessian ratio of d∗d^{\ast} along the iterates. For μ=0\mu=0, Mk≤4ρ2LM_k\le4\rho^2L eventually, and at ρ=1\rho=1 the rate matches Nesterov up to constants. On the transient, Kˉ\bar K is KK plus a logarithmic term (App. C.3), and for the Burg, KL and power kernels with μ>0\mu>0, KK is now explicit (general response 2/3). Along the runs, the local ρk\rho_k has median 1.05 to 20, against global values of 2400 to 56000 (table in the answer to R BAQu). We will state this in the paper.

"the only case in which ABrA-GD clearly outperforms ... is ... when competing methods do not use restart, which could be seen as unfair"

We agree that the comparison should include restart. General response 3/3 now compares with the adaptive ABPG variants with restart. With function restart, ABrA-GD with μ=0\mu=0 needs fewer oracle calls than every adaptive ABPG variant (ABPG-e, ABPG-g) with restart on both problems (1392 against 2056 on housing, 2174 against 2674 on abalone). The contribution we claim is the proved accelerated linear rate from μ\mu, without tuning.

"Can [the safeguard's LL] be replaced by some estimate?"

Yes. The safeguard step is a Bregman gradient step from zkz_k, and the certificate holds for it with any constant LgdL_{gd} that passes the usual descent test at zkz_k (Lemma 3 does not use LL). So LgdL_{gd} can be backtracked like LcurL_{cur}, at the cost of one extra gradient when the safeguard triggers, and the O(1/k)O(1/k) rate is kept. The test that triggers the fallback can use the current LcurL_{cur}. We will write this version and its proof in the paper. In the experiments of the paper, the safeguard was never triggered (App. G.2).

"Why is GCS not in the numerical experiments?"

GCS needs the constant CC as an input, and CC is unknown for these problems. This is precisely the case for an adaptive method. ABrA-GD needs only μ\mu and adapts to the smoothness and the local geometry during the run.

"why ABPG seems to couple better with restart"

We have no explanation specific to ABPG. Restarting accelerated methods is well studied. It is a common way to improve their rate in practice, in particular under strong convexity or quadratic growth (O'Donoghue and Candes, 2015; Fercoq and Qu, 2019).

AuthorsOpenReview ↗

Follow-up: new results since our answer

We thank the reviewer again for the positive assessment. As the discussion period comes to an end, we summarize how the rebuttal answers the two weaknesses reported in the review.


"It seems that locally bounded BLDF is automatic for solutions inside the domain, but it's unclear whether the constants that depend on rho^2 and rho^4 can be much larger than the constants in other methods, say C in GCS."

We present new theorems that bound these constants a priori:

  • For μ>0\mu>0, the Burg, KL and power kernels and an interior minimizer, the constant tends to 4L4L after an explicit iteration (Thm. 5, App. H).
  • For μ=0\mu=0, ABrA-GD now also has an a priori O(1/k2)O(1/k^2) rate for the KL and Burg kernels with an interior minimizer (Thm. 6, App. H).
  • Compared with GCS: CC and ρ\rho are not comparable in general, but GCS needs CC as an input, while ABrA-GD needs no ρ\rho, and for μ>0\mu>0 its constant now tends to 4L4L a priori.

"Not a reason for rejection, but the empirical performance seems to be a weakness. The only case in which ABrA-GD clearly outperforms prior art in the provided experiments is for the relatively strongly convex case when competing methods do not use restart, which could be seen as unfair, even if that's not part of the actual method."

Numerical performance. We compare ABrA-GD against a bundle of methods (ABPG, ABPG-e and ABPG-g) that require the exact knowledge of LL. Without LL, ABrA-GD is faster than the best of them, or within 10%, in 41 of 47 cases, including the convex case (μ=0\mu=0). If the roles were reversed, i.e., a comparison of a bundle of variants that require an extra parameter against a single method, this would be considered unfair.

Moreover, with function restart, ABrA-GD needs fewer oracle calls than every ABPG variant with restart (1392 against 2056 on housing, 2174 against 2674 on abalone). For further details, we invite the reviewer to read our discussion with Reviewer BJ91 (follow-up 2/3, point 3) and general response 3/3.


We believe that this rebuttal solves the critical weakness of the review, the convergence guarantees, and addresses the second one. We would be grateful if the reviewer could take this into account in the final assessment.

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

This paper introduces the Adaptive Bregman Accelerated Gradient Descent (ABrA-GD) for solving Bregman-relatively smooth convex minimization. It uses lower and upper models on the objective function, and uses an argument resembling Nesterov's estimate sequence technique to derive an accelerated O(1/k2)O(1/k^2) objective value convergence for Legendre functions dd with bounded dual Bregman Length Distortion Factor (BLDF), as well as accelerated linear convergence with additional strong convexity.

Critical strengths

The paper develops a solid intuition on what generally hinders acceleration for relatively smooth convex minimization with arbitrary Bregman divergence. This is distilled into the concept of BLDF and is eventually bounded by dual norm distortion factor, capturing an important quantity that affects the global convergence rate for the minimization problem relatively smooth with respect to dd. As a reader who is not particularly familiar with optimization under Bregman geometry, the paper's approach is informative. The results seem technically sound.

Critical weaknesses

Despite the contributions section, it is not clear what main novelty is being claimed. I understand that Sections 2-3 do provide some expository value on relatively smooth minimization and proposes the paper's new ABrA-GD algorithm, which is proved to have an accelerated rate in Section 5 under certain conditions. Section 4 introduces dual BLDF governing the convergence theory, and relates it to dual norm distortion factor.

Now, this is not the first accelerated rate because, as the paper acknowledges, a prior work ABPG achieves an acceleration, despite under a different characterization of dd called Triangle Scaling Property and the associated exponent γ\gamma, as the authors acknowledge. Therefore, I expected that this paper's new acceleration result would have a strictly larger scope and achieve a faster rate even for problems with γ=1\gamma=1 in order to have a strong, original contribution. However, my understanding of Section 4 is that the paper essentially focuses on problems with dd having the quadratic term with bounded variation on the regions Ωk\Omega_k, the convex set where all iterates stay in (which does not seem to be much stronger than a global assumption). Lines 178-179 explain that even for the Burg entropy they have distortion factor bounded by b/ab/a but this is under the box constraint a≤x≤ba \le x \le b. On the other hand, the non-acceleration in the Burg entropy case from the prior work was when the domain is the general unbounded positive orthant, and given that distinction, it is not clear if the characterization of this paper is fundamentally tighter than that in the ABPG paper. Even if I am incorrect here, it would be the authors' responsibility to clarify the strict benefit of their new characterization.

The paper also claims that they achieve the first accelerated linear rate that requires only the knowledge of μ\mu, but this is based on simple backtracking. I am not sure if it is the case that prior works seriously tried adapting to smoothness constant but failed, so this paper's result is genuinely attributed to their new insight, or if it is something that could have been achieved easily by combining preexisting techniques with backtracking but just was never formally recorded. In any case, it is still not fully satisfying that the knowledge of μ\mu is required for acceleration so that the proposed algorithm is not entirely parameter-free.

Questions for authors

Please refer to the weaknesses section, where I have essentially raised all points that would significantly affect my assessment.

2 comments
AuthorsOpenReview ↗

Rebuttal for Reviewer BAQu

We thank the reviewer for the review. The review raises three concerns: (1) the main novelty is unclear; (2) the benefit over ABPG is not strict, since the bounded-distortion condition seems close to a global box assumption; (3) the method relies on simple backtracking and needs μ\mu.

We add a significant new result that may affect the reviewer's assessment of (1) and (2): for μ>0\mu>0, ABrA-GD is proved to be locally accelerated a priori for the Burg, KL and power kernels (general response 2/3). Moreover, whenever ABPG-g has a gain GG uniform over triples, ABrA-GD is accelerated too (ρ2≤G\rho^2\le G, App. E.2). We answer (3) in Concern 3.

Concern 1: the main novelty

"it is not clear what main novelty is being claimed"

The core novelty is the computable primal-dual certificate (Theorem 2): a single test on it gives the adaptivity and the accelerated linear rate.

  • A new, constructive way to design adaptive accelerated methods from this certificate.
  • An accelerated linear rate for μ>0\mu>0 under bounded distortion (Theorem 3), which no triangle-scaling analysis of ABPG gives (App. E.1).
  • A characterization of when acceleration holds: an explicit formula for the distortion (App. C), and a new theorem showing that, for μ>0\mu>0, it is bounded a priori after an explicit iteration KK (general response 2/3).

We will state these three items as the main contributions in the introduction. General response 1/3 compares them with ABPG point by point.

Concern 2: the scope relative to ABPG

"I expected ... a strictly larger scope and ... a faster rate even for problems with γ=1\gamma=1"

"it is not clear if the characterization of this paper is fundamentally tighter"

General response 2/3 gives a family of problems where ABrA-GD is proved accelerated (for μ>0\mu>0, after an explicit iteration KK) and ABPG has no a priori accelerated guarantee. For example, on the Burg kernel on the unbounded orthant, the guarantee of ABPG is at best O(k−1/2)O(k^{-1/2}).

"the regions Ωk\Omega_k, the convex set where all iterates stay in (which does not seem to be much stronger than a global assumption)"

Ωk\Omega_k is local to iteration kk. It is built from the trials of iteration kk only, so it moves with the iterates. In the new theorem, Ωk\Omega_k lies in a small ball around ∇d(x⋆)\nabla d(x^\star) after iteration KK, so no box a≤x≤ba\le x\le b on the whole orthant is assumed. Theorem 3 needs ρk≤ρ\rho_k\le\rho only from some kk on. The local ρk\rho_k stays far below the global ρ\rho of one region that holds all these iterates:

Poisson, μ=0\mu=0housing, μ=0\mu=0housing, μ=10−4\mu=10^{-4}abalone, μ=0\mu=0abalone, μ=10−4\mu=10^{-4}
ρk\rho_k, median (min-max, rounded)2.9 (1-4)3.9 (1-14)1.05 (1-70)20 (1-110)1.05 (1-230)
global ρ\rho24007900160005600021000

Concern 3: backtracking and the knowledge of μ\mu

"based on simple backtracking ... could have been achieved easily"

Backtracking on LL alone is standard. Backtracking on the geometry and on LL together is not, and our primal-dual analysis is what makes it possible. In the triangle-scaling analysis of ABPG, LL also enters the momentum parameter, which couples it with the geometry. Hanzely et al. (2021) adapt the geometry (the exponent or the gain), but they take LL as input. The main contribution of Savchuk et al. (2024) is to make accelerated Bregman methods adaptive, but their method adapts to LL only: the exponent γ\gamma is fixed and given as input (App. E). To our knowledge, neither backtracks both.

Our analysis instead builds a computable primal-dual gap, so a single test on this gap (Theorem 2) checks the geometry and LL at once. Making this possible was far from trivial and is a main contribution of the paper.

"it is still not fully satisfying that the knowledge of μ\mu is required for acceleration"

μ\mu is optional: without it, ABrA-GD takes no problem constant and keeps the O(1/k2)O(1/k^2) rate. Only the linear rate needs μ\mu. We agree that this is a limitation for the linear rate.

  • ABPG, ABPG-e and ABPG-g take LL as input, so with μ=0\mu=0 ABrA-GD needs one constant fewer.
  • Strong convexity often comes from a regularization term, such as μDd(⋅,x0)\mu D_d(\cdot,x_0) in the anchored form (Eq. (1)); μ\mu is then known by construction.
  • In the Euclidean case, restarts adapt to an unknown μ\mu (O'Donoghue and Candes, 2015; Fercoq and Qu, 2019). A proved extension to the relatively strongly convex setting is a result large enough to need a paper of its own. In practice, ABrA-GD with μ=0\mu=0 and the same restart heuristic as ABPG is about as fast as with the true μ\mu (general response 1/3, point 2). As for ABPG, this heuristic has no proof.
AuthorsOpenReview ↗

Follow-up: new a priori acceleration results and summary of our answers

As the discussion period comes to an end and we have not heard back from the reviewer, we take this opportunity to summarize how the rebuttal answers the concerns of the review.

The review says that the weaknesses section holds all the points that would significantly affect the assessment; we answer each one below, and we add a new theorem on the scope question.

New results: a priori acceleration for μ=0\mu=0 and μ>0\mu>0

"Therefore, I expected that this paper's new acceleration result would have a strictly larger scope and achieve a faster rate even for problems with γ=1\gamma = 1 in order to have a strong, original contribution."

The rebuttal now provides this, in both the convex and the strongly convex settings, which by the reviewer's own criterion makes the contribution strong and original.

  • μ=0\mu=0: a priori accelerated. With the KL or Burg kernel on the unbounded positive orthant, with no assumed box, ABrA-GD has an a priori O(1/k2)O(1/k^2) rate when a minimizer is interior (for Burg, with a bounded set of minimizers; Thm. 6 and Cor. 3-4, App. H; follow-up to Reviewer BJ91, 1/3, point 2). For the same kernels, ABPG has at best O(1/k)O(1/k) (KL, γ=1\gamma=1) and O(k−1/2)O(k^{-1/2}) (Burg) a priori (App. E). This covers Poisson linear inverse problems and KL nonnegative regression (Cor. 5, App. H).
  • μ>0\mu>0: a linear rate, while ABPG stays polynomial.
    • Linear rate. With the safeguard (Alg. 5, App. H), the rate of ABrA-GD is always linear (Thm. 5, App. H). The guarantees of ABPG, ABPG-e and ABPG-g stay polynomial, O(k−γ)O(k^{-\gamma}) (Hanzely et al., 2021; Sec. 5.2; general response 1/3, point 1).
    • Acceleration. For the Burg, KL and power kernels, this linear rate is accelerated a priori after an explicit iteration KK (Thm. 5, App. H; general response 2/3). No triangle-scaling analysis gives an accelerated linear rate (App. E.1).

Both theorems, with full proofs, are in App. H of the revised PDF, in blue. Whenever ABPG-g has a gain uniform over triples, ABrA-GD is accelerated too (App. E.2).

Concerns of the review and our answers

Each concern of the review, our answer, and where to check it:

Concern of the reviewOur answerWhere
(1) The main novelty is unclearThe computable primal-dual certificate (Thm. 2). One test on it adapts to LL and to the geometry together, and gives the accelerated linear rate for μ>0\mu>0 (Thm. 3)Rebuttal, Concern 1
(2) No strictly larger scope than ABPG; the Burg bound needs a box a≤x≤ba\le x\le bA priori acceleration for Burg on the unbounded orthant (μ>0\mu>0, and now μ=0\mu=0), where ABPG has at best O(k−1/2)O(k^{-1/2})General response 2/3; App. H
(2) Ωk\Omega_k seems close to a global assumptionΩk\Omega_k is built from the trials of iteration kk only. In the experiments, the local ρk\rho_k has median 1.05 to 20, against global values of 2400 to 56000Rebuttal, Concern 2
(3) Simple backtrackingBacktracking on the geometry and on LL together is non-trivial: in the triangle-scaling analysis, LL enters the momentum parameter and is coupled with the geometry, so the ABPG variants take LL as input. Our certificate checks both in one test (Thm. 2)Rebuttal, Concern 3
(3) Acceleration needs μ\muWith μ=0\mu=0, ABrA-GD takes no problem constant, and it now has an a priori O(1/k2)O(1/k^2) rate on the problems aboveApp. H

This also answers the remark that the method is not parameter-free: with μ=0\mu=0, ABrA-GD needs neither LL nor μ\mu, and its accelerated rate now holds a priori for the KL and Burg kernels with an interior minimizer.

We would be grateful if the reviewer could reconsider the rating in this light. We will state the three contributions of Concern 1 in the introduction, and add App. H and the comparison with ABPG on the Burg and KL kernels to the paper.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General Response to Common Concerns

General response (1/3): General concern about the comparison between ABrA-GD and ABPG

We compare each concern with what holds for ABPG.

Acceleration is conditional

The accelerated convergence guarantees rely on the eventual uniform boundedness of the local dual geometric distortion (R BJ91)

the paper does not establish the required uniform boundedness of the local distortion from readily verifiable assumptions ... Without this condition, the O(1/k2)O(1/k^2) rate is not guaranteed by the present analysis (R BJ91)

the regions Ωk\Omega_k, the convex set where all iterates stay in (which does not seem to be much stronger than a global assumption) (R BAQu)

acceleration is impossible in general for entropy-smooth convex optimization (R BJ91)

These concerns apply equally to ABPG. The lower bound holds for every first-order method, ABPG included. For the standard kernels, the theoretical result of ABPG gives no acceleration (γ≤1\gamma\le1, and γ≤1/2\gamma\le1/2 for Burg). ABPG-g accelerates only if its accepted gains stay bounded by a constant GG, an a posteriori condition like ours (Hanzely et al., 2021, Sec. 4.1). See point 1 and its table below.

This rebuttal goes further: it gives a family of problems where our condition holds a priori. For μ>0\mu>0 and the Burg and KL kernels on the orthant or the simplex, and the power kernel on Rn\mathbb R^n, ABrA-GD is locally accelerated after an explicit iteration KK (general response 2/3).

The assumptions

this is under the box constraint a≤x≤ba\le x\le b (R BAQu)

Theorem 3 assumes that the conjugate kernel d∗d^{\ast} is twice differentiable (R BJ91)

ABPG-g needs the same box and the same Hessian assumption (their Eq. (40) and Eq. (16)). For μ>0\mu>0, the box holds a priori after an explicit iteration KK (general response 2/3). Theorem 3 needs only a bounded dual BLDF, which needs no twice differentiability (answer to R BJ91, point 2).

We show below that ABrA-GD matches ABPG on these points and goes further. It adapts to LL and to the geometry with no gain or exponent to search. It has an accelerated linear rate for μ>0\mu>0.

1. What is new relative to ABPG-g

ABrA-GD searches no gain or exponent and takes no LL, and for μ>0\mu>0 it has an accelerated linear rate, which no triangle-scaling analysis gives (App. E.1). The table compares the guarantees (Sec. 5.2).

Guarantees:

MethodRateConstants input
ABPGO(1/kγ)O(1/k^{\gamma}); γ≤1\gamma\le1 for standard kernels, ≤1/2\le1/2 for BurgLL, γ\gamma
ABPG-eO(1/kγk)O(1/k^{\gamma_k}), γk\gamma_k the accepted exponentsLL
ABPG-gO(1/k2)O(1/k^2) if Gk≤GG_k\le GLL
ABrA-GD (μ=0\mu=0)O(1/k2)O(1/k^2) if ρk≤ρ\rho_k\le\rho (Thm. 3)none
ABrA-GD (μ>0\mu>0)Strongly convex: linear accelerated if ρk≤ρ\rho_k\le\rho (Thm. 3)μ\mu

App. E.2 shows that whenever ABPG-g has a uniform gain GG, ρ\rho is uniformly bounded too (ρ2≤G\rho^2\le G), so ABrA-GD is accelerated.

2. Knowing μ\mu only adds flexibility

  • With μ=0\mu=0, ABrA-GD takes no constant at all and is accelerated under the same condition as ABPG-g.
  • When μ\mu is known, passing it gives a proved accelerated linear rate, which no ABPG analysis establishes (App. E.1). ABPG takes no μ\mu, so a known μ\mu cannot speed it up.
  • When μ\mu is unknown, ABrA-GD can use the same restart heuristic as ABPG, and it then converges linearly in practice. On both datasets it is as fast as ABrA-GD given the true μ\mu (1392 and 2174 oracle calls, against 1627 and 2004). It is also faster than ABPG-e and ABPG-g with restart (general response 3/3).

3. Inputs

Besides μ\mu, the parameters of ABrA-GD are initial estimates that backtracking corrects (Sec. 5.2, "Inputs"). As written in the paper, the optional safeguard (App. G.2) needs the true LL. We adapted it so that it uses an estimate of LL found by backtracking instead, with the same O(1/k)O(1/k) guarantee (answer to R dsim). We will write this version in the paper.

4. A significant new result: the assumption holds a priori for the Burg, KL and power kernels

Hanzely et al. (2021, Sec. 4.1) write:

an a priori theoretical guarantee of the O(k−2)O(k^{-2}) rate seems to be out of reach in general

For the Burg and KL kernels on the orthant or the simplex, and the power kernel on Rn\mathbb R^n, with μ>0\mu>0, we prove that ABrA-GD is locally accelerated a priori, with an explicit KK in Theorem 3 (general response 2/3). The only assumptions are μ>0\mu>0 and a minimizer away from the boundary of the domain (automatic for Burg). For Burg, the a priori rate of ABPG is at best O(k−1/2)O(k^{-1/2}) (App. E). This new result was prompted by R BAQu and R BJ91; we will add it to the paper and thank the reviewers in the acknowledgments.

AuthorsOpenReview ↗

General response (2/3): New Result, A Priori Acceleration for the Burg, KL and Power Kernels

As requested by R BAQu and R BJ91, we give a family of problems where ABrA-GD is proved to be accelerated a priori, while the a priori rate of ABPG is at best O(k−1/2)O(k^{-1/2}) for the Burg kernel (App. E). This result is new to this rebuttal; we will add it to the paper. We hope that it will lead the reviewers to reconsider their score.

We prove that, in the strongly convex case (μ>0\mu>0), ABrA-GD is locally accelerated a priori, after an explicit iteration KK, for the Burg and KL kernels on the orthant or the simplex, and for the power kernel on Rn\mathbb R^n. For any ρˉ>1\bar\rho>1, after K=O(Lμlog⁡LD0ρˉμr)K=O\big(\tfrac{L}{\mu}\log\tfrac{LD_0\bar\rho}{\mu r}\big) iterations, the hypothesis of Theorem 3 holds with ρk≤ρˉ\rho_k\le\bar\rho. ABrA-GD then converges at the accelerated linear rate O(ρˉ2L/μlog⁡(1/ε))O\big(\bar\rho^2\sqrt{L/\mu}\log(1/\varepsilon)\big). The radius r=r(ρˉ)r=r(\bar\rho) depends on the distance from x⋆x^\star to the boundary of the domain (table below). For the Burg kernel, rr is a constant, independent of x⋆x^\star.

Hanzely et al. (2021, Sec. 4.1, Eq. (40)) bound their gain for the KL and Burg kernels only if the iterates converge, which they leave open "without additional assumptions (such as relative strong convexity)". Under relative strong convexity, we prove the corresponding result for ABrA-GD.

Setting

ϕ=f+μDd(⋅,x0)\phi=f+\mu D_d(\cdot,x_0) with μ>0\mu>0 (Eq. (1)), ff convex and LL-smooth relative to dd, minimizer x⋆x^\star, and D0=Dd(x⋆,x0)D_0=D_d(x^\star,x_0). ABrA-GD runs with its safeguard (App. G.2, with the backtracked estimate of LL, general response 1/3, point 3). On the simplex we use the coordinates of App. A.2. In the table, a>0a>0 is a lower bound on the coordinates of x⋆x^\star (on their absolute values for the power kernel). It measures the distance from x⋆x^\star to the boundary of the domain (to 0 for the power kernel).

KernelDomainHypothesis on x⋆x^\starRadius r(ρˉ)r(\bar\rho)
Burg, −∑ilog⁡xi-\sum_i\log x_iorthant or simplexnone (interior for μ>0\mu>0)1−ρˉ−1/21-\bar\rho^{-1/2}
KL, ∑ixilog⁡xi−xi\sum_ix_i\log x_i-x_iorthantxi⋆≥a>0x^\star_i\ge a>0aln⁡ρˉ\sqrt{a}\ln\bar\rho
KLsimplexxi⋆≥a>0x^\star_i\ge a>023aln⁡ρˉ\tfrac23\sqrt{a}\ln\bar\rho
power, ∑i∣xi∣p/p\sum_i\lvert x_i\rvert^p/p, p>1p>1, p≠2p\neq2Rn\mathbb R^n∣xi⋆∣≥a>0\lvert x^\star_i\rvert\ge a>0(β−1)ap/2(β+1)p−1\frac{(\beta-1)a^{p/2}}{(\beta+1)\sqrt{p-1}}

For the power kernel, β=ρˉ2(p−1)/∣2−p∣\beta=\bar\rho^{2(p-1)/\lvert 2-p\rvert}.

Theorem (local acceleration)

Fix ρˉ>1\bar\rho>1 and take r=r(ρˉ)r=r(\bar\rho) from the table. After K=O(Lμlog⁡LD0ρˉμr)K=O\big(\tfrac{L}{\mu}\log\tfrac{LD_0\bar\rho}{\mu r}\big) iterations, every point that ABrA-GD computes, rejected trials included, gives ρk≤ρˉ\rho_k\le\bar\rho. By Theorem 3, ABrA-GD then reaches ϕ(xkbest)−ϕ⋆≤ε\phi(x^{best}_k)-\phi^\star\le\varepsilon in O(ρˉ2L/μlog⁡(1/ε))O\big(\bar\rho^2\sqrt{L/\mu}\log(1/\varepsilon)\big) more iterations. A ρˉ\bar\rho close to 1 costs only a logarithm in KK. So, for μ>0\mu>0 and these kernels, the hypothesis of Theorem 3 is guaranteed to hold from iteration KK on, so the accelerated rate holds from KK on. KK is a worst-case bound, of the order of non-accelerated Bregman gradient descent. After KK, each further factor of accuracy costs O(ρˉ2L/μ)O(\bar\rho^2\sqrt{L/\mu}) iterations, against O(L/μ)O(L/\mu) for Bregman gradient descent. In the experiments, the local ρk\rho_k has median 1.05 to 20, against global values of 2400 to 56000 (table in the answer to R BAQu).

ABrA-GD needs none of these quantities: it takes no knowledge of KK, rr or ρˉ\bar\rho. The acceleration comes adaptively, from the certificate test of each step.

Proof sketch

Let BB be the ball of radius rr around ∇d(x⋆)\nabla d(x^\star) in the dual local norm at x⋆x^\star. On BB, ρ≤ρˉ\rho\le\bar\rho: by Table 2 for KL and power, and by self-concordance for Burg (Nesterov and Nemirovskii 1994, Thm. 2.4.1; Nesterov 2018, Thm. 5.1.7).

  1. With the safeguard, the certificate (Theorem 2) decreases at least like (1−μ/L)k(1-\mu/L)^k. It bounds ϕ(xkbest)−ϕ⋆\phi(x^{best}_k)-\phi^\star and Dd(x⋆,zk)D_d(x^\star,z_k).
  2. By relative strong convexity, xkbestx^{best}_k, zkz_k and yky_k are then in BB (in dual coordinates). The descent lemma puts the point qq of Lemma 9 in BB too, once the certificate is below μ3r2/(8ρˉ4L2)\mu^3r^2/(8\bar\rho^4L^2); this takes KK iterations.
  3. Every trial point is a dual convex combination of these points, so Ωk⊂B\Omega_k\subset B and ρk≤ρˉ\rho_k\le\bar\rho.

Comparison with ABPG

The triangle-scaling analysis has no certificate that bounds the distance of its iterates to x⋆x^\star.

AuthorsOpenReview ↗

General response (3/3): New experiments: Large Scale problem, Restart and Cost per Oracle call

All methods were re-implemented in one code base (same Bregman solvers and counters, one thread). An oracle call is one evaluation of ff and/or ∇f\nabla f; a value-only call counts as a full call, and rejected trials count.

Larger instances (random D-optimal, m=100m=100, n=2000n=2000, two random instances)

Oracle calls to reach F−F⋆≤εF-F^\star\le\varepsilon, with time = calls x ms/call measured in one job on one node (ABPG 7.62, ABPG-e 4.79, ABPG-g 4.74, ABrA-GD 4.24 ms at μ=0\mu=0). "-" means not reached within 10510^5 iterations (2.5⋅1052.5\cdot10^5 for ABPG).

Instance 1

μ=0\mu=0ε=10−4\varepsilon=10^{-4}10−510^{-5}10−610^{-6}
ABrA-GD18288 (77.5 s)55613 (235.5 s)171607 (726.8 s)
ABPG-e14772 (70.7 s)127446 (609.9 s)-
ABPG-g26684 (126.6 s)67578 (320.6 s)183938 (872.5 s)
ABPG13808 (105.3 s)119408 (910.3 s)-

Instance 2

μ=0\mu=0ε=10−4\varepsilon=10^{-4}10−510^{-5}10−610^{-6}
ABrA-GD18130 (76.8 s)55185 (233.7 s)170185 (720.8 s)
ABPG-e14668 (70.2 s)126576 (605.8 s)-
ABPG-g30562 (145.0 s)88184 (418.3 s)186338 (883.9 s)
ABPG13742 (104.8 s)118645 (904.5 s)-

BPG and BPG-LS reach none of these targets. At μ=10−4\mu=10^{-4} (ABPG-e 4.88, ABPG-g 4.92, ABrA-GD 4.00 ms), to 10−510^{-5}: ABrA-GD 931 calls (3.7 s), ABPG-e 897 (4.4 s), ABPG-g 3298 (16.2 s).

Adaptive ABPG variants with restart

(anchored objective, μ=10−4\mu=10^{-4}; oracle calls to reach 10−510^{-5}, with the time measured in one job on one node, mean of two runs):

MethodHousingAbalone
ABrA-GD with μ=10−4\mu=10^{-4}1627 (0.41 s)2004 (1.04 s)
ABrA-GD with μ=0\mu=05566 (1.39 s)6764 (3.43 s)
ABrA-GD with μ=0\mu=0 + function restart1392 (0.35 s)2174 (1.11 s)
ABrA-GD with μ=0\mu=0 + gradient restart2078 (0.51 s)2969 (1.49 s)
ABPG-e without restart3844 (0.79 s)not reached
ABPG-e + gradient restart2056 (0.43 s)not reached
ABPG-e + function restart3088 (0.49 s)not reached
ABPG-g without restart5048 (1.00 s)9114 (4.12 s)
ABPG-g + gradient restart2254 (0.46 s)2674 (1.22 s)
ABPG-g + function restart2824 (0.49 s)3343 (1.31 s)

We compare with the adaptive variants, which search the exponent (ABPG-e) or the gain (ABPG-g). Plain ABPG fixes the exponent to 2, which is outside its guarantee for the Burg kernel (exponent at most 1/2, Sec. 5.2).

Cost of one oracle call

The table gives the time of one call of each method divided by that of ABrA-GD (μ=0\mu=0; all methods in one job on one node). It counts the oracle and the bookkeeping, but not the Bregman steps, whose cost grows only linearly in the dimension. To read a figure in time, multiply the x-axis of each method by its factor.

MethodHousingAbaloneD-opt 100x2000
BPG1.351.621.68
BPG-LS0.780.790.80
ABPG1.591.801.80
ABPG-e1.001.051.13
ABPG-g0.991.041.12
ABrA-GD (ms per call)1 (0.089)1 (0.237)1 (4.24)

At μ=10−4\mu=10^{-4} the factors are within 0.24 of these. Against BPG, ABPG, ABPG-e and ABPG-g the factors are 0.99-1.80; against BPG-LS they are 0.78-0.80.

On Poisson the factors depend on the size (same job design, μ=0\mu=0):

MethodPoisson 200x100 (paper)2000x10004000x2000
BPG0.731.401.39
BPG-LS0.750.960.95
ABPG1.181.441.41
ABPG-e0.821.041.07
ABPG-g0.791.071.06
ABrA-GD (ms per call)1 (0.030)1 (0.78)1 (4.58)

At the size of the paper an oracle call is very cheap, and the fixed cost of the vector operations dominates. ABrA-GD does more of them per call. On the larger instances the oracle dominates.

Overhead of backtracking

Each iteration restarts the search from Mk−1/4M_{k-1}/4 and Lcur/2L_{cur}/2. On Poisson, housing, abalone and D-opt 100x2000 (μ=0\mu=0 and 10−410^{-4}), ABrA-GD makes on average 2.0 trials of MkM_k per iteration, 1.5 Bregman gradient trials per trial, and 5.0 oracle calls per iteration. The largest number of trials of MkM_k in one iteration is 8 (D-opt, μ=0\mu=0).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.