PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Damien Scieur

arXiv:2609.38741v1math.OCcs.NAmath.NA

TL;DR

Relatively smooth optimization can include objectives with non-Lipschitz gradients, while acceleration guarantees in Bregman geometry require additional structure. This paper introduces ABrA-GD, which adapts using a computable primal–dual certificate and only the relative strong convexity constant as a problem-dependent input. Under bounded local distortion, it obtains accelerated convex and relatively strongly convex rates, with reported performance varying across the stated experiments.

  • Problem

    Relative smoothness covers objectives with non-Lipschitz gradients, but Bregman gradient descent’s O(1/k) rate cannot be improved over the full class, making additional structure relevant to acceleration.

    Source: §1 · pp. 1–2

  • Method

    ABrA-GD combines a Bregman gradient step with a dual lower model and adapts through a computable primal–dual certificate, without evaluating the dual BLDF.

    Source: Contributions · p. 2, §7 · p. 9

  • Results

    Under bounded distortion, ABrA-GD achieves accelerated O(1/k^2) convex and accelerated linear relatively strongly convex rates; D-optimal results vary by convexity setting, and Poisson performance depends on the instance.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The algorithm adapts to smoothness and geometry while requiring only the relative strong convexity constant as a problem-dependent input.

    Source: Contributions · p. 2

    The accelerated analysis does not cover an additional nonsmooth term, and accelerated BLDF analysis for composite objectives remains open.

    Source: Contributions · p. 2

Abstract

from arXiv · show

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 $O(1/k^2)$ rate for convex objectives and an accelerated linear rate for relatively strongly convex objectives.

1 Setting and Introduction

The paper studies relatively smooth optimization with Bregman geometry, where standard acceleration guarantees can be limited. It introduces ABrA-GD and analyzes accelerated rates under bounded local distortion, while identifying a boundary in its composite-objective analysis.

1 Setting and Introduction

  • The feasible set is determined by the kernel domain, and the objective combines f with a Bregman regularizer centered at x0.The stated assumptions make f convex, differentiable, and relatively (L − µ)-smooth; the problem setting is equivalent to relative L-smoothness and µ-strong convexity of ϕ.Source: §1 · p. 1
  • Relative smoothness covers objectives with non-Lipschitz gradients, but Bregman gradient descent’s O(1/k) rate cannot be improved over the full class, so acceleration needs added structure.Existing acceleration guarantees depend on triangle-scaling gains or other conditions; some require problem-dependent constants as inputs, while one cited rate does not improve under relative strong convexity [24] [10].Source: §1 · pp. 1–2

Contributions

  • ABrA-GD certifies envelope descent through primal and dual bounds, adapts by backtracking on smoothness and acceleration parameters, and uses only µ as a problem-constant input.The dual Bregman Length Distortion Factor compares progress of gradient and dual-averaging steps; the algorithm adapts without evaluating it. Under bounded local distortion, the analysis gives O(1/k^2) convex and accelerated linear relatively strongly convex rates.Source: Contributions · p. 2
  • The accelerated analysis does not cover an additional nonsmooth term, although envelope descent extends to composite objectives; accelerated BLDF analysis for that setting remains open.The paper contrasts this boundary with ABPG analyses that do cover an additional nonsmooth term [24].Source: Contributions · p. 2

2 The Primal–Dual Envelope Framework

The framework uses a fixed-anchor Bregman–Moreau envelope to express progress as envelope descent, then certifies that condition through a dual lower bound. The conceptual scheme supplies an error bound but does not itself specify how to construct or verify each step.

2 The Primal–Dual Envelope Framework

  • The Bregman–Moreau envelope is anchored at x0 and approaches ϕ⋆ as η grows; envelope descent requires a candidate whose objective is no greater than the envelope minimum.The conceptual scheme does not require minimizing the regularized objective, but it does not specify how to compute the candidate or verify the requirement directly.Source: §2 · p. 2
  • The scheme keeps x0 fixed, unlike proximal subproblems centered at the current iterate, and its error bound makes the growth of η the central rate choice.Faster η growth improves the stated rate but lowers the envelope toward ϕ⋆, requiring more progress at each iteration.Source: §2 · pp. 2–3

2.1 Envelope Dual Problem and Lower Bound

  • The envelope’s dual problem gives a lower bound on the regularized minimum, and the framework seeks to certify candidate progress against that bound.The dual value is generally not tractable because it requires f∗; the associated primal point can be computed without evaluating f∗.Source: §2.1 · p. 3

3 Deriving ABrA-GD and Its Accepted-Parameter Rate

ABrA-GD constructs primal candidates and dual updates from a shared gradient, then uses a computable lower model to test envelope descent. Its a posteriori convergence guarantee is expressed through accepted acceleration parameters and assumes every iteration’s inner loop exits.

3 Deriving ABrA-GD and Its Accepted-Parameter Rate

  • A shared gradient at yk produces a primal candidate and dual update, while backtracking adjusts smoothness and acceleration parameters until the descent certificate holds.The primal step minimizes an upper model valid under relative smoothness; the dual step uses the same gradient, and the computable lower bound tests the invariant.Source: §3 · p. 3
  • The accepted Mk controls the rate through its relation to tk, which ABrA-GD selects by backtracking rather than fixing in advance.The parameter identities yield a quadratic relation analogous to Nesterov’s method.Source: §3 · p. 5
  • The computable lower model bounds the dual value from below, and its minimum at zk+1 supplies the comparison used to certify envelope descent.The lower model uses the current point information and one gradient evaluation; Figure 2 depicts the upper-model minimum lying below the lower-model minimum as the certificate.Source: Figure 2 · p. 4, §3 · p. 5

Convergence in terms of the accepted parameters

  • The a posteriori convergence theorem expresses the rate through accepted acceleration parameters Mk and assumes the inner loop exits at every iteration.The theorem does not itself bound the accepted parameters or establish that the inner loop terminates; bounded local distortion is treated in later analysis.Source: Convergence in terms of the accepted… · p. 5

4 Dual Bregman Length Distortion

The section compares the Bregman lengths generated by gradient and dual-averaging steps, then defines the dual BLDF to bound geometry-induced changes between them.

4.1 Comparing the gradient and dual-averaging steps (convex case)

  • In the convex case, the exit test is guaranteed when the gradient step’s upper model decreases at least as much as the lower bound.In dual coordinates, both decreases measure lengths along a common direction but from different anchors and at different scales.Source: §4.1 · p. 6
  • For µ > 0, the two dual segments are no longer parallel; the comparison instead pairs segments with the same anchor and direction but different scales.The paired comparisons run from ∇d(y_k) toward ∇d(x_{k+1}) and ∇d(q_{k+1}), and likewise from ∇d(z_k).Source: §4.1 · p. 6

4 Dual Bregman Length Distortion

  • The dual BLDF bounds changes in Bregman lengths when the steps differ in anchor, scale, or both.The analysis uses this factor to compare the gradient and dual-averaging steps.Source: §4 · p. 5, §4.2 · p. 6

4.2 The dual Bregman length distortion factor

  • At γ = 2, the dual BLDF removes quadratic scale effects and is bounded by variation in local dual norms; under smoothness and strong convexity, it is at most L_d*/µ_d*.For the Burg entropy, ρ_d*(∇d(X)) ≤ b/a when a ≤ x ≤ b throughout X.Source: §4.2 · p. 7

5 Accelerated Rates under Bounded Distortion

Under bounded local distortion, ABrA-GD’s accepted acceleration parameters are eventually bounded, yielding accelerated rates; the section compares the condition and required inputs with existing methods.

5.1 Convergence and iteration complexity

  • When local distortion is eventually bounded by ρ, backtracking eventually caps accepted M_k at 4ρ²L for µ = 0 or 4ρ⁴L for µ > 0, yielding accelerated rates.The theorem assumes the inner loop exits before the bounded-distortion regime begins; it then exits at every iteration.Source: §5.1 · p. 7, §5 · p. 7
  • When ρ = 1, the iteration-complexity bounds match Nesterov’s fast gradient method up to an absolute constant.Backtracking adds constant amortized oracle overhead per accepted iteration, with logarithmic terms for underestimated initial parameters.Source: §5.1 · pp. 7–8

5.2 Comparison with existing methods

  • ABrA-GD takes only µ as a problem-dependent input, whereas Chen et al. [10] require the constant of their generalized Cauchy–Schwarz condition.The paper describes its accelerated linear rate as the first for relatively smooth, relatively strongly convex objectives obtained with these inputs.Source: §5.2 · p. 8
  • For standard non-Euclidean kernels, ABPG’s triangle-scaling guarantee gives no acceleration; when ABPG has a uniform gain, ABrA-GD also has an accelerated rate.The full relatively smooth class has an optimal O(1/k) rate, and ABrA-GD retains that rate when its accepted M_k grows without bound.Source: §5.2 · p. 8
  • The accelerated variants’ a posteriori rate depends on accepted gains, while ABrA-GD’s rate depends on bounded local distortion.For ABPG with γ = 2, the stated rate is O( Ḡ_k/k²), where Ḡ_k depends on accepted gains.Source: §5.1 · p. 7, §5.2 · p. 8

6 Numerical Experiments

Experiments compare ABrA-GD with Bregman and accelerated baselines on D-optimal design and Poisson inverse problems. Results vary by problem type and convexity setting.

6 Numerical Experiments

  • The evaluation covers D-optimal design and Poisson linear inverse problems, following Hanzely et al. for formulations, datasets, baselines, and initialization.Oracle-call counts include first-order oracle calls from trials rejected by backtracking.Source: §6 · p. 8
  • For D-optimal design, the ABPG comparisons use γ = 2; the γ = 1 comparison reproduces the slower-converging ABPG result reported by Hanzely et al..With γ = 1, ABPG has only an O(1/k) guarantee in this comparison.Source: §6 · p. 8
  • On Poisson problems, ABrA-GD improves on nonaccelerated baselines, while its performance relative to accelerated methods depends on the instance and variant.The reported instances are Poisson L1 with (m, n) = (200, 100) and Poisson L2 with (m, n) = (100, 1000).Source: §6 · p. 8
  • For housing D-optimal design, ABrA-GD performs similarly to the best ABPG variants when µ = 0 and reaches a lower residual with fewer oracle calls when µ = 10^-4.The other three D-optimal design datasets show the same pattern.Source: §6 · p. 8, Figure 4 · p. 9

7 Conclusion

The section summarizes ABrA-GD’s adaptive approach and accelerated rates under bounded distortion, alongside experiments across problem settings. It also characterizes the dual norm distortion factor for standard separable geometries, including when it is finite or divergent.

7 Conclusion

  • ABrA-GD combines a Bregman gradient step with a dual lower model to meet envelope descent, with convergence bounds depending on accepted acceleration parameters.The dual BLDF measures local geometric distortion between the steps, but the algorithm does not evaluate it; under bounded distortion, rates are O(1/k^2) for convex objectives and accelerated linear for relatively strongly convex objectives.Source: §7 · p. 9
  • In D-optimal design, ABrA-GD performs similarly to adaptive ABPG for convex problems and reaches lower residuals for relatively strongly convex problems; Poisson performance depends on the instance.Source: §7 · p. 9
  • Future directions include sharper local distortion bounds, accelerated analysis for composite objectives, and stochastic variants.Source: §7 · p. 9

A.1 The anchored decomposition

  • The anchored decomposition places all relative strong convexity of ϕ in the anchor term, which raises the relative smoothness constant from L − µ to L.Source: §A.1 · p. 14

A.2 Affine equality constraints

  • Affine equality constraints require no change to the analysis: coordinates on the affine subspace preserve the Bregman divergence and relative smoothness and strong convexity constants.Source: §A.2 · p. 14

B.1 Mirror Gradient Descent

  • Bregman gradient descent has O(1/k) convergence under relative smoothness and linear convergence under relative strong convexity; its envelope schedule translates these rates into algorithm 1.Source: §B.1 · p. 15

B.2 Saddle formulation of the envelope

  • The saddle formulation supports convergence-rate proofs for Dual Averaging and ABrA-GD.Source: §B.2 · p. 15

B.3 Dual Averaging

  • Dual Averaging uses damped best-response updates that avoid computing ∇f*(λ), which is usually intractable.Source: §B.3 · p. 16

C.1 Convergence rate of gradient descent and dual averaging

  • Table 2 reports that the factor is finite when coordinate ratios over Ω are bounded, diverges near the domain boundary for KL and Burg geometries or the origin for power-type geometry, and equals 1 in Euclidean geometry.Source: Table 2 · p. 23

C.2 Technical results on BLDF

The section bounds dual Bregman length distortion under regularity assumptions and relates it to local dual-norm distortion. It also gives Euclidean and separable special cases.

C.2 Technical results on BLDF

  • Under smoothness and strong convexity of d*, Lemma 5 bounds the dual Bregman length distortion factor.Its assumptions apply on a convex subset of int(dom d*).Source: §C.2 · p. 23
  • For Euclidean d*(u) = 1/2∥u∥², the compared dual Bregman-length ratio is exactly 1.The two divergences scale quadratically with their respective segment lengths.Source: §C.2 · p. 23

Then the dual norm distortion factor satisfies

C.3 Technical results on Accelerated Method

The technical analysis derives one-step bounds and convergence guarantees for ABrA-GD using accepted acceleration parameters and local dual distortion. It also bounds the amortized cost of backtracking searches.

C.3 Technical results on Accelerated Method

  • The generic accelerated bound is derived from the exit condition and the lower-model and descent inequalities, with a separate convex specialization when τ_k = t_k.The convex specialization removes the terms multiplied by µ and the scalar-product term.Source: §C.3 · pp. 27–28

Then the accelerated step satisfies

  • The convex and strongly convex analyses establish one-step bounds under local dual norm distortion, using the relevant dual segments in each iteration.The strongly convex bound additionally requires the virtual point q_{k+1} to be well defined.Source: §C.3 · p. 28, Then the accelerated step satisfies · pp. 29–30
  • If local distortion is bounded by ρ after iteration K, the method eventually accepts M_k ≤ 4ρ²L for convex objectives and M_k ≤ 4ρ⁴L for relatively strongly convex objectives.The theorem also assumes that the inner loop exits before K; under these conditions it exits at every iteration.Source: Then the accelerated step satisfies · p. 32

C.4 Oracle complexity

  • Backtracking has constant amortized overhead, with logarithmic terms for underestimated initial values; its extra trials let the method use local estimates instead of a fixed worst-case constant.The trial count depends on the largest accepted value over the first K outer iterations.Source: §C.4 · p. 33

D Euclidean specialization and comparison with Nesterov

In Euclidean geometry, ABrA-GD recovers Nesterov’s estimate-sequence updates under sharp line-search constants, while its comparison with ABPG emphasizes a conditional accelerated linear guarantee for strong convexity.

D Euclidean specialization and comparison with Nesterov

  • With the sharp smoothness and acceleration constants, the Euclidean BLDF is 1, and ABrA-GD’s strongly convex updates match Nesterov’s estimate-sequence form.The classical accelerated linear contraction is recovered when M_k = L, up to constants and indexing.Source: D Euclidean specialization and… · pp. 34–35
  • ABrA-GD’s updates need not follow Nesterov’s ordinary trajectory: they use xbest instead of x_k, and form a monotone variant when the gradient step increases the objective.The trajectories coincide when the gradient step never increases the objective.Source: D Euclidean specialization and… · p. 34
  • The convex Euclidean specialization recovers the standard Nesterov/FISTA scalar recursion and the accelerated O(L∥x⋆−x₀∥²/k²) rate, up to indexing.The update coupling is the usual accelerated estimate-sequence coupling.Source: D Euclidean specialization and… · p. 34

E.1 Comparison with ABPG

  • For relatively strongly convex objectives, ABrA-GD gives a conditional accelerated linear rate; the cited TSP-based analyses do not establish such a guarantee.Its bounds are expressed in terms of quantities accepted during the run.Source: §E.1 · p. 36

E.2 Relation to the triangle-scaling property

The paper relates dual distortion to triangle-scaling gains, extends the envelope and lower-model mechanisms to composite objectives, and describes the experimental instances and parameter setup.

E.2 Relation to the triangle-scaling property

  • A uniform triangle-scaling gain at exponent 2 bounds dual norm distortion, but that implication requires a gain uniform over triples rather than a pointwise-limit exponent.The corresponding Hessian ratio controls local divergence comparisons, including those used for µ > 0.Source: §E.2 · p. 36
  • For the Burg kernel on X_{a,b}, local distortion is b/a, yielding an O(1/k²) convex rate and an accelerated linear rate when µ > 0.The guarantee is conditional on the iterate-defined dual segments remaining in the bounded-ratio region; the paper does not prove this bound a priori.Source: §E.2 · pp. 36–37

F Composite objectives and the subgradient envelope

  • The envelope descent requirement and lower-model mechanisms extend to a smooth relatively smooth f plus a proper closed convex r with an available Bregman proximal step.The accelerated BLDF proof does not follow automatically because the composite model introduces a set-valued subgradient or nonsmooth proximal residual.Source: F Composite objectives and the… · p. 37

G.1 Experimental protocol

  • The experiments include Burg-entropy simplex regression on abalone, bodyfat, mpg, and housing datasets, with relatively strongly convex instances formed using µ = 10⁻⁴.Those regression datasets are identified with their sample counts and feature counts in the protocol.Source: §G.1 · p. 38
  • The protocol also describes orthant Burg-entropy Poisson instances and starts ABrA-GD with L₀ = 1 and M₋₁ = L₀.The Poisson data use a column-normalized random matrix and a sparse nonnegative signal; baselines receive constants through their own interfaces.Source: §G.1 · p. 38

G.2 Safeguards and ablations

Across the tested problems, ABrA-GD improves on nonaccelerated Bregman methods; its comparison with accelerated methods is strongest on D-optimal design and more instance-dependent on Poisson problems. The experiments also find no consistent benefit from explicit restarts.

G.3.5–G.3.7 Restart comparisons

  • The tested restart heuristics are outside the convergence analysis and do not consistently improve performance; they can increase Mk variability or reduce oracle-call efficiency.In convex D-optimal design, the plain method is usually comparable or better; in strongly convex D-optimal design it typically reaches the lowest final residual. On both Poisson instances, restarts are neutral or worse, and both restarted variants stall on Poisson L2.Source: §G.2 · p. 38, Figure 10 · p. 44, Figure 11 · p. 45

G.2 Safeguards and ablations

  • The safeguard guarantees at least Bregman gradient descent’s convergence rate while retaining accelerated steps when they make better certificate progress.It was never triggered in the reported experiments, because every accepted step already matched or exceeded the nonaccelerated update’s certificate progress.Source: §G.2 · p. 39

G.3 Additional numerical experiments

  • Across convex D-optimal design instances, ABrA-GD improves on nonaccelerated Bregman methods and matches the best ABPG variants; it also reaches lower residuals than competitors in the strongly convex setting.On Poisson problems it improves on nonaccelerated baselines, but the lowest-residual method depends more strongly on the instance and variant.Source: §G.3 · p. 39

G.3.1 D-optimal design, convex, γ = 1 for ABPG

  • At γ = 1, ABPG has an O(k^-1) guarantee and was slower than BPG in the reported housing comparison; the authors use γ = 2 in their other ABPG comparisons.Source: Figure 5 · p. 40

G.3.2 D-optimal design, convex

  • On four convex D-optimal design datasets, ABrA-GD improves over BPG and BPG-LS and matches the best accelerated ABPG variants over the plotted range.The experiments plot residual against iterations and oracle calls, alongside ABrA-GD’s locally adapted Mk values.Source: Figure 6 · p. 41

G.3.3 D-optimal design, strongly convex

  • With µ = 10^-4, ABrA-GD’s log-residual decreases approximately linearly and reaches a lower residual than BPG, BPG-LS, and the ABPG variants over the plotted range.Accepted Mk values can fluctuate, while ϕbest_k is non-increasing by construction.Source: Figure 7 · p. 42

G.3.4 Poisson problem

  • On Poisson L1 (m = 200, n = 100), ABrA-GD improves on nonaccelerated Bregman methods and matches the best ABPG variants in iterations and oracle calls.Source: Figure 8 · p. 43
  • On Poisson L2 (m = 100, n = 1000), accelerated methods reach lower residuals than BPG and BPG-LS, while ABrA-GD tracks the best accelerated baseline.Which method reaches the lowest final residual is more sensitive to the instance and adaptive strategy than in D-optimal design.Source: Figure 9 · p. 43
Loading 2609.38741v1…