Fast Frank–Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions
Authors: Shota Takahashi
Sebastian Pokutta
Akiko Takeda
Venue: ICLR 2026 Poster (2026)
Keywords: Optimization
First-order method
Convex optimization
Nonconvex optimization
Primary area: optimization

Abstract: We propose Frank–Wolfe (FW) algorithms with an adaptive Bregman step-size strategy for smooth adaptable (also called: relatively smooth) (weakly-) convex functions. This means that the gradient of the objective function is not necessarily Lipschitz continuous, and we only require the smooth adaptable property. Compared with existing FW algorithms, our assumptions are less restrictive. We establish convergence guarantees in various settings, including convergence rates ranging from sublinear to linear, depending on the assumptions for convex and nonconvex objective functions. Assuming that the objective function is weakly convex and satisfies the local quadratic growth condition, we provide both local sublinear and local linear convergence with respect to the primal gap. We also propose a variant of the away-step FW algorithm using Bregman distances over polytopes. We establish faster global convergence (up to a linear rate) for convex optimization under the Hölder error bound condition and local linear convergence for nonconvex optimization under the local quadratic growth condition. Numerical experiments demonstrate that our proposed FW algorithms outperform existing methods.

Published as a conference paper at ICLR 2026
FAST FRANK-WOLFE ALGORITHMS WITH ADAPTIVE BREGMAN STEP-SIZE FOR WEAKLY CONVEX FUNCTIONS
Shota Takahashi
Sebastian Pokutta
The University of Tokyo shota@mist.. www.ko...oo...ooooooooooo ac. jp
Zuse Institute Berlin & Technische Universität Berlin pokuttaß a0220ib 2ii.de
Akiko Takeda
The University of Tokyo & RIKEN AIP takeda@mist. i. u-tokyo. ac. jp
ABSTRACT
We propose Frank-Wolfe (FW) algorithms with an adaptive Bregman step-size strategy for smooth adaptable (also called: relatively smooth) (weakly-) convex functions. This means that the gradient of the objective function is not neces- sarily Lipschitz continuous, and we only require the smooth adaptable property. Compared with existing FW algorithms, establish convergence guarantees in various settings, including convergence rates ranging from sublinear linear, depending the assumptions for convex and nonconvex objective functions. Assuming that the objective function is weakly convex and satisfies the local quadratic growth condition, provide both lo- cal sublinear and local linear convergence with respect to the primal gap. We also propose variant of the away-step FW algorithm using Bregman distances over polytopes. We establish faster global convergence (up to a linear rate) for convex optimization under the Hölder error bound condition and local linear con- vergence for nonconvex optimization under the local quadratic growth condition. Numerical experiments demonstrate that our proposed FW algorithms outperform existing methods.
assumptions are less restrictive. We
INTRODUCTION
In this paper, we consider constrained optimization problems of the form
min
f(x),
(1.1)
xEP
where f R" + (-o0, +00] a continuously differentiable function and P C IR" is a compact convex We are interested in both convex and nonconvex and assume that we have first-order oracle access to f. i.e., given x E RR,, we can compute fz(). The Frank-Wolfe (FW) algorithm projection-free first-order method. Instead of requiring access to a projection oracle, the FW algorithm requires only access to a so-called linear minimization oracle (LMO), which for given linear function a IR" computes y arg min,,gp(a. (a, v). LMOs are often much cheaper than projection oracles, as shown in Combettes & Pokutta (2021) (see also (Braun et al., 2025, Table 1.1)). Consequently, in practice, FW algorithms are often faster than projected gradient methods when the projection operation is nontrivial. Additionally, FW algorithms tend be numerically quite robust and stable due to their intine-ivvrrince and can also be used, e.g., to provide theoretical guarantees for the approximate Carathéodory problem by Combettes & Pokutta (2023).
Overview of Existing FW Studies: The FW algorithm was originally proposed by Frank & Wolfe (1956) and was independently rediscovered and extended by Levitin & Polyak (1966) the con- ditional gradient method; we will use these terms interchangeably. Canon Cullum (1968) estab- lished initial lower bound for the rate of the FW algorithm. GuéLat & Marcotte (1986) improved

---

Published as a conference paper at ICLR 2026
this bound and also provided the first analysis of the atey-step FW algorithm by Wolfe (1970). Jaggi (2013) provided more detailed convergence analysis of the FW algorithm, establishing a new lower bound that demonstrated trade-off between sparsity and error. Concurrently, Lan (2013) examined the complexity of linear programming- based first-order methods, establishing a similar lower bound. For comprehensive review of FW algorithms, refer the interested reader to the survey by Braun et al. (2025) and the brief introduction by Pokutta (2024).
The classical FW algorithm (Algorithm 1) has been improved in two main directions enhance both performance and convergence. One focuses on refining the step-size rule. The short-step strategy computes Y/ using the Lipschitz constant L of f. Pedregosa al. (2020) introduced an adaptive step-size strategy that dynamically estimates L. They proved that this strategy is at least as effective as the short-step strategy. It was enhanced by Pokutta (2024) to improve numerical stability.
Another direction is to modify the classical FW algorithm to eliminate the zigzag behavior when approaching the optimal face containing the optimal solution x². This behavior inspired Wolfe (1970) to propose the away-step FW algorithm in 1970 that shortcuts the zigzagging by removing atoms that slow down the iterative sequence. Lacoste-Julien & Jaggi (2015) showed the linear convergence of the away-step FW algorithm. Their analysis introduced geometric constant, the pyramidal width, that measures the conditioning of the polytope P. representing the feasible region.
Our Research Idea: To derive the convergence rate of the above- mentioned FW algorithms, pre- vious studies have typically required L-smoothness, i.e., that / is Lipschitz continuous, and con- vexity for the objective function /, although exceptions exist.2 These assumptions often narrow the application of FW algorithms. Even if they do not satisfy T-ssmoothness, there many functions that satisfy the L-smooth adaptable property (L-smad) with kernel generating distances Φ (see Defi- nition 2.1) by choosing & well to match the function f. Since the L-smad property is consistent with L-smoothness when Φ = 111-112 the class of L-smad functions includes the L-smooth function class. Other first-order algorithms, such as the Bregman proximal gradient algorithm, are often analyzed under the L-smad property (see Appendix A and Bolte et al. (2018); Hanzely et al. (2021); Rebegoldi et al. (2018); Takahashi et al. (2022); Takahashi & Takeda (2025); Yang & Toh (2025)). L-smad functions appear in many applications, such nonnegative linear inverse problems (Bauschke & Borwein, 1997: Takahashi & Takeda, 2025), lg loss problems (Kyng et al., 2015; Maddison et al., 2021). phase retrieval (Bolte et al., 2018; Takahashi et al., 2022), nonnegative matrix factorization (NMF) (Mukkamala & Ochs, 2019; Takahashi et al., 2026), and blind deconvolution (Takahashi et al., 2023). Any C2 function is locally L-smooth over compact sets, but the resulting Lipschitz constant L can be overly conservative, hindering practical performance. Functions outside C2 may not satisfy L-smoothness all. Moreover, functions in the above- mentioned applications are weakly convex on compact sets. For nonconvex functions, although Lacoste- Julien (2016) established sub- linear convergence, little else has been done, and simply tracing existing research does not achieve convergence rates better than sublinear convergence. Then the following question naturally arises:
Is it possible to relax the L-smoothness and convexity assumptions often made in FW algorithm studies while still achieving the theoretical guarantee of linear convergence rates?
The answer to the above question yes. We develop FW algorithms for I--mad I and give theoretical guarantees of linear convergence under weaker assumptions (Hölder error bound (HEB) condition with parameter 9 2 for convex ff and the special case with q = 2 called quadratic growth for nonconvex f) than the strong convexity assumption that is often made when linear convergence is shown for FW algorithms. The convexity assumption on ff is also weakened to weakly convex, i.e., f + 2 - 2|a is convex with some p > 0 (see, e.g., (Davis et al., 2018, Examples 3.1 and 3.2) and Nurminskii (1975)). Any C2 function 1983; Wu, 2007) (see Proposition C.1); since p is only for the theoretical guarantee and not for the
Contribution:
a compact set is weakly convex (Vial,
'Similar analyses based on the pyramidal width have been developed for other advanced variants, such as the pairwise FW algorithm (Lacoste-Julien & Jaggi, 2015), Wolfe's algorithu (Lacoste-Juile & Jaggi, 2015), the blended conditional gradient method (Braun et al., 2019), and blended pairwise conditional gradient methods and similar variants (Comhettes & Pokutta, 2020; Tsuji et al., 2022). Even Nesterov-style acceleration is possible under weak assumptions (Diakonikolas et al., 2020) building upon this analysis.
Quite recently, Vyguzov& & Stonyakin (2025) proposed FW algorithm with the Bregman distance, similar ours, yet it restricted convex problems and provides only partial convergence guarantees.
2

---

Published as a conference paper at ICLR 2026
Table 1: Our converpence
generalizations of existing rates. Moreover, our convergence rate is better than O ()) some cases. For nonconvex functions, convergence is measured using the Frank- Wolfe gap (V](x)) ž₁ vs) I c, instead of the primal gap f(x)) - f" S Convergence rates for weakly convex optimization hold locally.
Assumptions
Convergence rate
f conv. f growth IP poly. L-smooth
L-smad (v > 0)
Alg. (any step-size)
conv.
x x
O(e=))
( (Thm.D.2)
X Olloge " 1(, Ologe ()nge="),o00 (E 1+2-2
Alg. (short & adapt.) conv.
HEB
/
(Thm.
Olloge 1),O(E Olloge 1) O(e 142-9
away-step FW
conv.
q- Q-HEB
x
(Thm. 4.4y
1 (any step-size)
weak
2-HEB
x
x
O(c
(/- (Thm. E.3)
Alg. (short & adapt.)
weak
2-HEB
/
X
Olloge
Ologe (), O(e "2=
(Thm. 5.3)
away-step FW
weak
2-HEB
x V Olloge
Olloge (). O(c -
(Thm. 5.4)*
A (any step-size)
x
x
x O
O (Thm. E.1)
algorithm, there is no need for its estimation, and considering weakly convex f greatly broadens applicability.
Table I summarizes our contributions for the various cases that we consider. Relaxing the assump- tion from L-smoothness the L-smad property extends the FW algorithm a broader range of problems, while making the construction of the FW algorithm and its theoretical guarantee much more difficult. This is because we use the Bregman distance Da. which is an extension of the Fu- clidean distance, for the 7-smad property. While Equation 2.1 shown later is simple with = when using the Euclidean distance, v > cannot be eliminated for the general Bregman distance; 1 + represents its scaling exponent. needs to be estimated during the algorithm since its exact value is unknown, and thus, the extension to an L-smad f is not straightforward.
We establish sublinear convergence for the case of convex L-smad functions. Assuming that f convex and satisfies the HEB condition, and that the minimizer x' E int we provide faster convergence (up linear rate). In this setting, our algorithm always converges linearly the exponent of the HEB condition q equals the scaling exponent of v, if t < to with some
the Bregman distance 1 + V/ i.e., q 1 + v.? For q to N. linear convergence holds; otherwise, (( which is faster than existing sublinear rates. A similar argument also applies to the nonconvex case (g = 2) and the away-step FW algorithm.
For nonconvex optimization, assuming that is weakly convex and satisfies the local quadratic growth condition, establish local linear convergence. To the best of our knowl- edge, this is the first FW algorithm with linear convergence guarantees for a certain class of nonconvex optimization problems, albeit for a rather restricted subclass. These results also new for the standard setting: L-smooth f. Without weak convexity, we prove global sublinear convergence stationary point of Equation 1.1 for nonconvex L-smad f.
We also propose a variant of the away-step FW algorithm with the Bregman distance and establish linear convergence under the HEB condition for convex optimization and under the local quadratic growth condition for weakly convex optimization.
'f conv. means the convexity of f. IP means x" E int P, and poly. means that P is a polytope. *Ollog g = or q * and S to with to N: otherwise (c(2--)//1) (Kerdreux et al., 2022).
*Ollog if the exponent of the HEB condition equals the scaling exponent of the Bregman distance
1 + ((v.g) (1,2) for the away-step FW algorithm). For q > + v, it holds if to with N; otherwise O (1(tt)))))))
(Oog c -1) holds if = 1. For v E (0, 1), it holds if S to with to E N: otherwise (M-1)222
As discussed in Sec. 2, linear convergence with the Fuclidean distance is shown in Garber & Hazan (2015)
under the quadratic growth over strongly convex sets. This corresponds to the q
with
3

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
Let C' be a nonempty open convex subset of IR.. Let dist(a, C) == inf yeC I| - yll and let C* be the class of k-times continuously differentiable functions for k 2
Definition 2.1 (Kernel Generating Distance (Bolte et al., 2018)). A function Φ : I + (-00, +o0 is called kernel generating distance associated with C' if it satisfies the following conditions: (i)
is proper, lower semicontinuous, and convex, with dom & C cl C and dom Oe = C: (ii) Φ is C' on int dom C. We denote the class of kernel generating distances associated with C by G(C).
Definition 2.2 (Bregman Distance (Bregman, 1967)). Given @ 9(C), Bregman distance Dø dom Ø int dom Φ - R associated with ø is defined by Do(2, v) = ((x))((0 p(y) - (Vá(y), x-
The Bregman distance (1 y) measures the proximity between x E dom & and y E int dom ø Since is convex, (2, y) 0 holds. Moreover, when ø is strictly convex, D2 y) 0 holds and only if x = y. However, the Bregman distance is not always symmetric and does not have to satisfy the triangle inequality. See Example B.1. We use Dy in Definition 2.2 for nonconvex instead of convex ø for brevity. In the remainder of the paper, we assume that, for a given strictly convex @ and C, there exists v > such that the following holds for all x, y E int dom & and E [0, 1] (see Lemma B.3): Da((1 - 7)x y8.2) S 2 DoV.D)
(2.1)
We recall the smooth adaptable property, which is generalization of L-smoothness and was intro- duced by Bauschke et al. (2017); Bolte et al. (2018) 8); Lu et al. (2018). Its characterizations can be found in Appendix B.2, Example B.5, Remark B.6, and (Bauschke et al., 2017, Proposition 1).
Definition 2.3 (L-smooth Adaptable Property). Let ø E G(C)) and let f R" + (-oc +oo] be proper and lower semicontinuous with dom @ c dom f. which is C on C = int dom Φ. The pair of functions (f, Φ) is said to be L-smooth adaptable (for short: L-smad) on C if there exists T. > 0 such that Lap f and LΦ + f are convex on C.
The L-smad property is equivalent to the extended descent lemma (Bolte et al., 2018, Lemma 2.1), which implies that the L-smad property for (f, 6) provides upper and lower approximations for f majorized by & with L > O. For example, - log x is not L-smooth on x 0 and 4 is not L- smooth on R. It is the Bregman distance, rather than the Euclidean distance, that allows us to bound the first-order approximation of these functions. See Example B.5 for further examples of L-smad pairs. When (f, Φ) is L-smad with strictly convex function & E G(C), we have Lemma B.7, i.e.,
f(x) f(x+) 2 (Vf(x), - u) 1, (v,
(2.2)
where x+ = (1 7)x + yo with I, v E int dom & and 7 E [0, IJ. Often v E P C int dom e in Lemma B.7 is chosen Frank- vertex, i..., arg (V x u). but other choices, e.g., those arising from away away-directions, are also possible, as we will see in Section 3.2.
In Garber & Hazan (2015) (see also Garber (2020)) the linear convergence of the FW algorithm for convex optimization under the quadratic growth condition, which a weaker assumption than assuming strong convexity, was established over strongly convex sets and later generalized to uni- formly convex sets in Kerdreux et al. (2021) as well as to conditions weaker than quadratic growth in Kerdreux al. (2019; 2022). Local variants of these notions, as necessary, e.g., for the non- convex case, have been studied in Kerdreux et al. (2026) in the context of FW algorithms. For oc, +oo], let [f < <= fa R fx) S {} be a ç-sublevel set of f for some Ç E R. Definition 2.4 (Hölder Error Bound (Braun et al., 2025; Roulet & d' Aspremont, 2017) and Quadratic Growth Conditions (Garber & Hazan, 2015; Garber, 2020; Liao et al., 2024)). Let f : R" + (-o0, +oo] be a proper lower semicontinuous function and P C R be a compact convex set. Let X # 0 be the set of optimal solutions, i.e., X := arg mingeP f(x), and let f minzer f(x) and Ç > O. The function f satisfics the HöHöle error bound (HEB) condition on P if there exist constants Z 1 and μ > 0 such that dist(x, X* < [(((z)) - f*) holds for any E P. it is called the p-quadratic growth condition. Moreover, the function ff is said to satisfy local μl y-quadratic growth (with () if there exists a constant μ > such that (i, )² < (f(x)) f²) holds for any [ < l + +MMP.
R"" + R:
In particular, when q
4

---

Published as a conference paper at ICLR 2026
For example, f(x) = log(1 + x²) is nonconvex but satisfies local quadratic growth. This function is used for image restoration (Boj et al., 2016; Stella et al., 2017). See, for more examples, Ex- amples E.4 and E.5. The HEB condition shows sharpness bounds the primal gap (see Bolte et al. (2017); Roulet & d' Aspremont (2017)), which has been extensively analyzed for FW al- gorithms (Kerdreux al., 2019; 2022). Convergence of (sub)gradient algorithms for nonconvex optimization under the quadratic growth or HEB condition was established in Davis et al. (2018; 2024); Davis & Jiang (2024). We assume the HEB condition for convex optimization and the local quadratic growth for nonconvex optimization.
3 PROPOSED BREGMAN FW ALGORITHMS
Throughout this paper, we make the following assumptions.
Assumption 3.1. (i) e E G(C) with cl C cl dom e is strictly convex C int dom & and has v > 0 satisfying Equation 2.1; (ii) f IR" + (-o0, +oo] is proper and lower semicontinuous with dom & C dom f. which is C C: (iii) The pair (f, Φ) is L-smad on P; (iv) P IR" a nonempty compact convex set with P C.
Assumption 3.1(i)-(ii) standard for Bregman-type algorithms (Bolte et al., 2018; Takahashi & Takeda, 2025). The strict convexity of ensures the existence of by Lemma B.3 and is satisfied by many kernel generating distances (see, e.g., Bauschke al. (2017); Bauschke & Borwein (1997), and (Dhillon & Tropp, 2008, Table 2.1)). Assumption 3iv( is standard for FW algorithms, and P C C naturally ensures that D& is well-defined on P. The original FW algorithm is given in Algorithm In what follows, let x arg min f(x and f = f(x)).
Algorithm 1: Frank Wolfe algorithm
Input: Initial point zo E P. objective function f. step-size Y E [0, 1]
for t = 0,... do 0z + arg m
2e+1 + (1 - 70 + 7e04
3.1 BREGMAN STEP-SIZE SIZE STRATEGY FOR "
Bregman Short Step-Size: Assume that (f, () is L-smad. Maximizing the right-hand side of Equation 2.2 in terms of y, we find
7 x (1++)Da((u,)
(Vf(z) o))
and ((e))f(=))) I 1+ (L(1 + D)),
Theoretically, when v, v P and 7 E [0, 1], the Frank-Wolfe step x4 = (1 7)x + yu P well-defined. We update 7 = min
(V)())))-)) 1/v (((+))
Tmax with some Tmax E (usually set Tmax =). This step-size strategy provides f(x) f(x+) 2 I (VFx)) v) for 0 S
(Vf(c).)-o) 1/v ((L+V)D((vx))
)(r Its proof can be found in Lemma B.8.
If Φ = -11 112, we have = 1 and = step-size. Although the short step-size does not require line searches, it requires knowledge of the value of L.
(V((=)))= which is often called the (Fuclidean) short L
Adaptive Bregman Step-Size: The exact value or the tight upper bound of T. is often unknown; however, the algorithm's performance heavily depends on it; an underestimation of L might lead to non-convergence, and an overestimation of might lead slow convergence. Moreover, worst- case L might be too conservative for regimes where the function is better behaved. For these rea- sons, Pedregosa et (2020) proposed an adaptive step-size strategy for FW algorithms in the case where é Il _l We present our algorithm in Algorithm 2. This step-size strategy can be used as a drop-in replacement. For example, inserting Lt, Mt, 7tt &- step step_sizee seeseiieeeeeeee Φ, Tt; Ut, 11-1,77 1) between lines and 3 in Algorithm 1, we obtain that Algorithm 2 searches L and satisfying Equa- tion 2.2. For Ø= = b -12. Algorithm 2 corresponds to a (Euclidean) adaptive step-size strategy (Pe- dregosa et al., 2020). Remark 3.2 -ell-definedness and termination of Algorithm 2). By the L-smad property of (f. and Lemma B.7, we know that Equation 2.2 holds for all M > L. and 2 0. Therefore, the
5

---

Published as a conference paper at ICLR 2026
condition in line 7 in Algorithm is well-defined and guaranteed to terminate. It suffices to update & in line 10 only if Equation 2.1 does not hold. Thus, A cannot become too small.
We have bound on the total number of eval- uations of Algorithm 2. Its proof can be found in Appendix B.3.
Algorithm 2: Adaptive Bregman step-size strategy
Output: Estimates L' and i* step-size
Theorem 3.3. Let L-1 be the initial L-smad estimate and ny be the total number of evalu-
Procedure step_ step_siieeee size(f. o, u, L, Tmax) Choose 3 E (0,1), 17 (0, 1], and 7 >
ations of Equation 2.2 up to iteration t. Then we have ny I max (1 log n/ log T) (t +
M t nt, k +
loop
1) max (log(TL/LLL)))eeeee... 0 log T, log log (t+++
min
M(1-x)Dp(r.z)
(V
Tmax
24 + (1 - [177)3 +
Pedregosa et al. (2020) showed that, asymp-
if (z+ x) S My DD (1, then
totically, no more than 16% of the itera- tions require more than one evaluation of the line search procedures when " = 0.9 and
L' t M, 10" tk
return 1,", "",
T = 2. This follows from the bound (1 log / T) < 1.16.
M t 7 M, K 3K
3.2 BREGMAN AWAY-STER FRANK-WOLFE ALGORITHM
In the case where P is polytope, the classical FW algorithm might zigzag when approaching the optimal face and, in consequence, converge slowly. The away-step FW algorithm overcomes this drawback. Away steps allow the algorithm to move away from vertices in a convex combination of Tr, which can effectively short-circuit the zigzagging. The convergence properties of this algorithm were unknown for long time, and it was only quite recently that Lacoste-Julien & Jaggi (2015) established the linear convergence of the away-step FW algorithm. Inspired by GuéLat Mar- cotte (1986); Lacoste-Julien & Jaggi (2015); Wolfe (1970), we propose variant of the away-step FW algorithm utilizing Bregman distances as given in Algorithm The main difference between Algorithm 3 and the existing stay FW algorithm lies in the update in line 8.
For the following discussion, we introduce some notions. In the same way as Braun et al. (2025), we define active set S Vert P. where Vert P denotes the set of vertices of P, and the away vertex as va E arg max (V (xxe) v), where Ie is a (strict) convex combina- tion of elements in S, ie., Zt Eves AoU with X O for all v is unknown, we can add line search procedures to search v until Equation 2.1 holds. It, Ut, Lr-1 7t,max) with
S and Eves A 1.
and L are unknown, can use Lr, Mr, Jt + step_size
T. min (V/(a)) 1/M M((+k)Daltere))
ma, instead of line in Algorithm 2. When b1ll
and v = 1, Algorith 3 corresponds to the Euclidean away-step FW algorithm.
4 LINEAR CONVERGENCE FOR CONVEX OPTIMIZATION
In this section, we assume that f is convex. Assumption 4.1. The objective function f is convex.
Let D Vsup Dz(a,y) be the diameter of P. We will now establish faster convergence rates than O(1/t) up to linear convergence depending in Equation B.2 and q in Definition 2.4. First, we establish the faster convergence of Algorithm 1 with the Bregman short step-size, i.e.,
1/v
Th min
or Algorithm in the case where the optimal solution lies
in the relative interior. Its proof can be found in Appendix D.2.
Theorem 4.2 (Linear convergence of FW algorithm with short step-size or adaptive step-size). Sup- pose that Assumptions 3.1 and 4.1 hold. Let 0 and let f satisfy the HEB condition with q 2 1+v and μ > 0 and be the diameter of P. Assume that there exists a minimizer x* E int P, i.e. there exists 0 with B(x", .r) P. Consider the iterates of Algorithm with short step-size

---

Published as a conference paper at ICLR 2026
Algorithm 3: Away-step Frank-Wolie algorithm with the Bregman distance
Input: To E arg g for E P
So { Aza.0 - for 1 = 0,.. do
of イ- arg min eep
u). 2s t max,ss
ES, (V (Vf(z)),
if [ ). Et
1; 2 (V (xe), Iz) then
rW
12 Ut de +- Jt i/= Tt.max t-1
PW
FW
else
Us + ur de + up - Uss Ma, f A0t.e/(1 (1 - )et
" t -mmin ((Ltr))
(Vf(()),d))
1/2
..mmux jo I++1 t 4d
if (zz) Zt w. 2 (Vf(z)), uf Iz) then
Ao,tt1 t (1 -o for all ii E (x
10
7t
vt rw $ St
S411 - SS.U ( pW]
if < if =1
11
Aug s+1 +
(1- 71) ) +
if et E St
12
else
Ad,t11 < (1 + We) for all a St \ {vt)), A + (1 70000 -
13
Se {
if Nota++== =
14
St-1 -
St
if Af44 > 0
7. min 2.)
1/v (141)))((1..))
1 or the adaptive Bregman step-size strategy (Algorithm
Then, it holds that, for all t 2 1,
max It 1
Ite a111/01275
141/v
LD
if 1+ v, if ft to. -1+
f(x)) - f
LD²
(1+v)t
if 1 =0(1/ma/0-1-0)) (1+ 21=))=1) (t-to))
+
where = 4/ and to == max (1ogi) ((c/)) D2y [DD)) + 2, 1}.
Next, we establish the linear convergence of Algorithm 3. Recall that the pyramidal width is the minimal 8 > 0 satisfying Lemma C.9 (see (Braun et al., 2025, Lemma 2.26) or Laacstee-uulinn & Jaggi, 2015, Theorem 3) for an in-depth discussion). Under Assumption 4.3, it holds that 8 < D, and this will be important in establishing convergence rates of Algorithm 3. We make the following assumption:
Assumption 4.3. The kernel generating distance a-strongly convex.
We have the linear convergence of Algorithm 3. Its proof can be found in Appendix D.3.
Theorem 4,4 (Linear convergence of the away-step FW algorithm). Suppose that Assump- tions 3.1, 4.1, and 4.3 hold. Let O and let P be a polytope and f satisfy the HEB condition with > 1 + or (v. ④) = (1, The convergence rate of Algorithm 3 is linear: for all t 2
1)/21
52 32L D=
LD²
if () (1,2),
f(x1) f
(I+v]Tt 17727 LD2
if < S lo. 4 > 1+
(I+ 20t) [[t to) /0 = 0(1 0(1/19/(4-1-0)
(I((1 ((
if to, q > 1 1
where e:= (g/1)///9 D and are the diameter and the pyramidal width of the polytope P, respec- tively, and to max [log/ v)D3
/LD2 22 1].
When o = -ll ||, i.e., v = 1, Theorems 4.2 and 4.4 correspond to existing results (Braun et al., 2025; Kerdreux al., 2022).

---

Published as a conference paper at ICLR 2026
5 LOCAL LINEAR CONVERGENCE FOR NONCONVEX OPTIMIZATION
In this section, we consider a nonconvex objective function. We establish global sublinear, local sublinear, and local linear convergence (see Theorem E.I and Theorem E.3 for global and local sublinear convergence, respectively). We show that the FW algorithm converges to a minimizer x when an initial point is close enough to x². We need weak convexity and local quadratic growth for local convergence.
Assumption 5.1. f is p-weakly convex and has local p-quadratic growth with Ç > 0.
Assumption 5.1 is not too restrictive because the (local) strong convexity or the (local) Polyak- Eojasiewicz (PL) inequality implies the (local) quadratic growth condition for weakly convex func- tions (Liao et al., 2024, Theorem 3.1). For more examples satisfying Assumption 5.1 and p S μ4, see Examples E.4 and E.5.
Remark 5.2. Linear convergence rates for nonconvex optimization problems are, to the best of our knowledge, the first such result for the Frank-Wolfe algorithm. Their proofs are technically challenging. Proposition C.8 is new and key for establishing linear rate. In the nonconvex case, one cannot derive primal-gap inequalities such as Lemma D.1. We overcome this by restricting our function class to weakly convex functions and proving Lemma C.2. There remains an obstacle that could be resolved by the assumption of the quadratic growth condition. Assumption 5,1 enables us to derive Lemma C.3 and Proposition C.8 (as well as Remark C.4), which are crucial for establishing linear convergence.
We have local linear convergence, and its proof can be found in Appendix E.3.
Theorem 5.3 (Local linear convergence of FW algorithm with short step-size or adaptive step-size), Suppose that Assumptions 3.1 and 5.1 hold. Let v E (0, 1] and let D be the diameter. Assume that there exists minimizer x² E int P, i.e. there exists r >> 0 with B(x*, .r) C P. Consider (11441))))
the iterates of Algorithm 1 with %/- = min {
or the adaptive Bregman 1/2 .1
step-size strategy (Algorithm 2). Then, if p/p < 1, it holds that, for all / 2 1,
max
2
1
+ P
1
2
2²
LD²
if v -y=1. 1,
t-1
((x1)-
1
1
up
LD²
if S t S tu E (0,1), if > l, (0.1),
1+
(1-pm) cttr /1 / 0(1/P//1-1)
(1+ 1-2 (1-() (t- 2071
where c= /2n/ (p - (p), M = (L(1 (0(+1100 =)) and to == max Logg (LL v)
P).
p/ D2 /2/3////00000/1 /LD))
Finally, we establish the local linear convergence of Algorithm 3. Its proof can be found in Ap- pendix E.4. We assume p S L, which is not restrictive (see Appendix E.2 and Example E.4). Theorem 5.4 (Local linear convergence by the away-step FW algorithm). Suppose that Assump- tions 3.1, 4.3, and 5.1 hold. Let v E (0, and let P IR" be a polytope. The convergence rate of Algorithm 3 with f is linear: if < fu 5 L, for all 2
8²) [(e-1)/2]
2 1 D2
LD2
if 1,
f(x1) f
2
1 (1 (1+ up
[(t- 1)/2
LD
if S t to, v E (0,1), 1),
1+0
(Li++t)(1-/NN) D²
(1+ 2112) (1- (o(()t)/2]] 1 of = 0(1/2//1-1) if 2 L, v E (0, 1),
where D and 8 are the diameter and the pyramidal width of P. respectively, and w == (μ - p)2/8p, and to := max{ [0g11+//////0/ (L² (1 + (1 p/1)2"/////////))))) ( v) -) /22DD* - 12 1}.
Without loss of generality, o = 1. p>> L. we can use (p + D2 instead of 2LD2 as the initial bound of f(x1)- f When Φ 11ll- 1|2. i.c., V = 1, Theorems 5.3 and 5.4 show linear convergence rates for Euclidean cases. Even if we use the Euclidean distance, our convergence results are novel in that linear convergence is achieved for the first time for certain type of noncomvex problem. Moreover, when P is (a, -uuniformly convex set (see Definition E.7) and ő = 1 1|?, we also establish local linear convergence (Theorems E.9 and E. 10) in Appendix E.5.
8

---

Published as a conference paper at ICLR 2026
1050
10"
Proeri Spreetl
10/
1041
3074
1071
3614
1.0
1044
1044
1051
105
1045
1030
4000
2003
4000 5000
Figure 1: Log plot of primal and FW gaps E, loss gas sensor data with Unaax 130.
Figure 2: Log plot of primal and FW gaps Ep loss gas sensor data with Umax 200.
Brogriy
Broggnt Openttty
Cperrty
Pmma
10P
10.
10
10
2003
4002
1000
2000
2002
4002 5003
20
139.000
20"
Stanetoro
Figure 3: Log plot of primal and FW gaps on phase Figure 4: Log plot of primal and FW gaps on phase retrieval for nm (1000, 10000).
retrieval for (m, n) (2000, 10000).
NUMERICAL EXPERIMENTS
In this section, we conduct numerical experiments to examine the performance of our algorithms. All numerical experiments were performed in Julia 1.11 using the FrankWolfe, j1 package (Be- sançon et al., 2022)* on MacBook Pro with an Apple M2 Max and 64GB LPDDR5 memory.
We compare BregFW (Algorithm 1) and BregAFW (Algorithm 3, whose results are shown in Figures 7) using the adaptive Bregman step-size strategy (Algorithm 2). with existing algorithms, EucFW, EucAFW, ShortFW, ShortAFW, OpenFw, OpenAFи, MD, and P ProjGD (their notation is described in Appendix F). In this section, we consider L, loss problems and phase retrieval, and we report additional experiments on nonnegative linear inverse problems, low-rank minimization, and NMF in Appendix F. Note that included OpenAFW only for comparison purposes; there is tablished convergence theory for the away-step FW algorithm with the open loop. Indeed, there are no proper drop steps (operations corresponding to line 14 in Algorithm 3), and the favorable prop- erties of the away-step FW algorithm are lost; see Braun et al. (2025). We use 3 = 0.9, = 0.9,
2, Tmax 1, and the termination criterion max,e P (xx) Zt v) I 10-1 throughout all experiments.
6.1 E, LOsS PROBLEM
We consider the lp loss problem (Kyng et al., 2015; Maddison et al., 2021) to find E P such that Ax ~ b, deñned by a convex optimization problem mingep || - bllg. where E RRxn b E T
and p > 1. Let f (xx = || - bll.. The gradient V / is not Lipschitz continuous on R2 when p + 2. Furthermore, when p < 2, f is not C but C² Therefore, for < < 2, Vf is also not Lipschitz continuous over compact sets. Since f is convex, the pair (f, Φ) is 1-smad with Φ ==
hhtpps://gi http://gttttut...e wtt.ttth.........///ooooo
je.

---

Published as a conference paper at ICLR 2026
We consider real-world gas sensor data.' The data size is (m, (13910, 128). We use the l constraint P = {ir E R" ||=|| I bmax] We compare BregEW with BucFW, OpenFW, and Pro JGD because ShortFW does not converge. The maximum number of iterations is 1000 for all methods except OpenFw, for which it is 5000. The initial point zn is an all-ones vector. We set p 1.1, Le.,, is C not C² Figures and show the primal and FW gaps per iteration and gaps per second for 0max = 130 and bmax = 200, respectively. Because V f is not Lipschitz continuous, Short and EucFü do not converge. The primal gap and the FW gap achieved by BregFW are the smallest among these methods because only BregFW w has a theoretical guarantee for this problem.
6.2 PIASE RETRIEVAL
We are interested in phase retrieval, which involves finding signal x E P C R" such that ((a,2)) = b,. i = 1....,m, m, where a, E R" describes the model and b E R" is a vector of measurements. Phase retrieval arises in many fields of science and engineering, such as image processing (Candés et al., 2015), X-ray crystallography (Patterson, 1934; 1944), and optics (Shecht- man al., 2015). To achieve the goal of phase retrieval,
focus on the nonconvex optimiza-
tion problem mingeP f(z) == 1/ E.((a, x) 2 - b,)).. Let o be defined by o-strongly convex ((x) & ||a]|| + |||l for S 1. For any L satisfying L 2 (3 + [|a:])?(b;,), the pair (f))) is L-smad on R. (Bolte et al., 2018, Lemma 5.1). In addition, {² + pf is positive semidefinite for 2 E, ||,,1//bb,, i.e., f is p-weakly convex. Thus, L 2 p/a holds with o = 1.
constraint, i.e., P {z E I" ||/|11 I |2 I 1}. We compare BregFW with EucFü, ShortFW, and OpenFW. The maximum number of iterations is 1000 for all methods except OpenFи, for which it is 5000. We generated a,, i = 1...., from an i.i.d. normal distribution and normalized them to have norm (random seed 1234). We also generated x" from an i.i.d. uniform distribution in [0, and normalized x² to have sum 1. The initial point Zg was generated by computing an extreme point of P that minimizes the linear approximation of Figures 3 and 4 show the primal and FW gaps per iteration and gaps per second for (m,n) (1000, 10000) and K- = 2000 and for (m, n) = (2000, 10000) and K = 2000, respectively. The primal gap and the FW gap by the adaptive Bregman step-size strategy are the smallest among these step-size strategies. In both cases, BregFW stopped before the 1000th iteration.
We use K-sparse polytope
7 CONCLUSION AND FUTURE WORK
Summary: We propose FW algorithms with an adaptive Bregman step-size strategy for smooth adaptable functions, which do not require Lipschitz continuous gradients. We have established convergence rates ranging from sublinear to linear, depending on various assumptions for convex and nonconvex optimization. We also propose a variant of the away-step FW algorithm using Bregman distances over polytopes and have established global convergence for convex optimization under the HEB condition and local linear convergence for nonconvex optimization under the local quadratic growth condition. Numerical experiments show that our algorithms outperform existing algorithms.
Limitations and future work: Our step-size strategy for L-smad functions requires the value of v, which must be estimated because it depends on the choice of the Bregman distance. Theoretically, linear convergence of the FW algorithm always holds for convex optimization if the exponent of the HEB condition q equals the scaling exponent of the Bregman distance 1 + v. i.e. 9 = 1 + v. For 1 v, if f S fo. linear convergence holds; otherwise, sublinear convergence. The condition q 1+v+ derived from the growth of f and é, is natural because é has a similar structure to f. On the other hand, for nonconvex optimization, we assume the local quadratic growth condition, i.e., the 2-HEB condition. Since this is derived from the weak convexity of f, relaxing the quadratic growth condition may not be possible. One direction is consider extension using the difference of convex functions (DC) optimization. Recently, Maskan et al. (2025) incorporated DC optimization into FW algorithms and established sublinear convergence. Our algorithms could potentially benefit from DC optimization techniques.
The dataset is freely available at htttps//arrcive... ics. hwt..ee.dddtaateee////// sensortarraytdri htw.rr/rrraayytataaaaaattaaaaaaa ffrersettttttttfeeeeeeetttttnnnt
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This project has been partially supported by the Japan Society for the Promotion of Science (JSPS) through Invitational Fellowships for Research in Japan program (L24503), JSPS KAKENHI Grant Number JP23K 19953 and JP25K21150 15;; JSPS KAKENHI Grant Number JP23H03351 and JST ER- ATO Grant Number JPMJERI90) Research reported in this paper was also partially supported by the Deutsche Forschungsgemeiinchatt (DFG) through the DFG Cluster of Excellence MATH+ (grant number EXC-2046/1, project ID 390685689).
LLM USAGE
We used large language models, CharGPT-5/5.15..2, solely to polish the grammar and wording of the author-written text (e.g., to improve clarity and tone). The model did not generate novel ideas, analyses, code, or results. All outputs were reviewed and edited by the authors, who take full responsibility for the content.
ETHICS STATEMENT
This study uses only publicly available datasets that contain no personally identifiable information. We did not collect any new human-subject data; therefore, IRB approval was not required. We also reviewed the datasets for potentially harmful content.
REPRODUCIBILITY STATEMENT
We include all evaluation code, configuration files, and scripts in the supplementary material. We provide the exact preprocessing steps for all datasets used. We fix and disclose random seeds for all experiments. Results are reported as mean + standard deviation over multiple runs.
REFERENCES
Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. Technical report, Innovations in Theoretical Computer Science, 2017.
H. H. Bauschke and J. M. Borwein. Legendre functions and the method of random Bregman pro- jections. Convex Anal., 4(1):27-67, 1997.
H. H. Bauschke and J. M. Borwein. Joint and separate convexity of the Bregman distance. Studies in Computational Mathematics, 8:23-36, 2001.
H. H. Bauschke, Bolte, and M. Teboulle. A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications. Math. Oper. Res., 42(2):330-33) 33,4488,, 2017.
A. Beck. First-Order Methods in Optimization, volume 25 of MOS-SIAM Series Optimization. SIAM, Philadelphia, PA, 2017.
M. Bertero, P. Boccacci, G. Desiderà. and G. Vicidomini. Image deblurring with Poisson data: from cells to galaxies. Inverse Probl., 25(12):12300 2009.
M. Besançon, A. Carderera, and S. Pokutta. FrankWolfe,jii A for Frank- Wolfe algorithms and conditional gradients. INFORMS Comput., 34(5):261 1-2620, 2022.
and flexible toolbox
R. Bot, E. R. Csetnek, and S. C. László. An inertial forward-backward algorithm for the mini- mization of the sum of two nonconvex functions. EURO J. Comput. Optim., 4(1):3-25, 2016.
J. Bolte, A. Daniilidis, and A. Lewis. The Lojasiewicz inequality for nonsmooth subanalytic func- tions with applications to subgradient dynamical systems. SIAM J. Optim., 17(4):1205-122) -123, 2007.
11

---

Published as a conference paper at ICLR 2026
J. Bolte, T.-P. Nguyen, Peypouquet, and B. W. Suter. From enror bounds to the complexity of first-order descent methods for convex functions. Math. Program., 165:471-507, 2017.
J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd. First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim., 28 (3):11112111,, 2018.
G. Braun, S. Pokutta, D. Tu, and S. Wright. Blended conditional gradients: The unconditioning of conditional gradients. In Proc. 36th Inf. Conf. Mach. Learn. (ICML), volume 97 of PMLR, pp- 735-743. PMLR, 2019.
G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari, and S. Pokutta. Conditional grudient methods: From core principles to Al applications, volume 35 of MOS-SIAM Series on Optimization. SIAM, Philadelphia, PA, 2025.
L. M. Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution of problems in convex programming. U.S.S.R. Comput. Math. Math. Phys., 7 (3):200-217, 1967.
E. J. Candés, X. Li, and M. Soltanolkotabi. Phase retrieval from coded diffraction patterns. Appl. Comput, Harmon. Anal., 39(2):277-299, 2015.
M. D. Canon and C. D. Cullum. A tight upper bound on the rate of convergence of Frank-Wolfe algorithm. SIAM J. Control Optim., 6(4):509-516, 1968.
C. W. Combettes and S. Pokutta. Boosting Frank- Wolfe by chasing gradients. In Proc. 37th Int. Conf. Mach. Learn. (ICML), volume 119 of PMLR, pp. 2111-2121. PMLR, 2020.
C. W. Combettes and Pokutta. Complexity of linear minimization and projection on some sets. Oper. Res. Lett., 49(4):565 56,,,,,,, 2021.
C. W. Combettes and S. Pokutta. Revisiting the approximate Carathéodory problem via the Frank- Wolfe algorithm. Math. Program., 197:191-214, 2023.
D. Davis and L. Jiang. local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth. Found. Comput. Math., 25:943-100 1024,, 2024.
D. Davis, D. Drusvyatskiy, K. J. MacPhee, and C. Paquette. Subgradient methods for sharp weakly convex functions. J. Optim. Theory Appl., 179(3):962 9922,,,92,,2, 2018.
D. Davis, D. Drusvyatskiy, and V. Charisopoulos. Stochastic algorithms with geometric step decay converge linearly on sharp functions. Math. Program., 207(1-2):145-190, 2024.
I. S. Dhillon and A. Tropp. Matrix nearness problems with Bregman divergences. SIAM J. Matrix Anal. Appl., 29(4): 120-1146. 2008
J. Diakonikolas, A. Carderera, and S. Pokutta. Locally accelerated conditional gradients. In Proc. 23rd Int Conf. Artif. Intell. Stat. (AISTATS), volume 108 of PMLR, pp. 1737-1747. PMLR, 2020.
R. A. Dragomir, A. d' Aspremont, and J. Bolte. Quartic first-order methods for low-rank minimiza- tion. Optim. Theory Appl., 189(2):341-33,, 2021.
M. Frank and P. Wolfe. An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1-2): 95-110, 1956.
K. Fujiki, S. Takahashi, and A. Takeda. Approximate Bregman proximal gradient algorithm with variable metric Armijo-Wolfe line search. arXiv preprint arXhv:2510.066155 2025.
D. Garber. Revisiting Frank-Wolfe for Polytopes: Striet Complementarity and Sparsity. In Adv. Neural Inf. Process. Syst., volume 33, pp. 18883-18893. Curran Associates, Inc., 2020.
D. Garber and E. Hazan. Faster rates for the Frank- Wolfe method over strongly-convex sets. In Proc. 32nd Int. Conf. Mach. Learn. (ICML), volume 37 of PMLR, pp. 541-549. PMLR, 2015.
12

---

Published as a conference paper at ICLR 2026
J. GuéLat and P. Marcotte. Some comments on Wolfe's "away step'. Math. Program., 35(1):110- 119, 1986.
E. Hanzely, P. Richtárik, and Xiao. Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. Comput. Optim. Appl., 7902):005-440, 2021.
F. Itakura and S. Saito. Analysis synthesis telephony based on the maximum likelihood method. In Proc. 6th Int. Congr. Acoust, 1968.
M. Jaggi. Revisiting Frank-Wolfe: Conf. Mach. Learn. (ICML), volume 28 of PMLR, pp. 427-435. PMLR, 2013.
Projection-free sparse convex optimization. In Proc. 30th Int.
T. Kerdreux, A. Aspremont, and S. Pokutta. Restarting Trank-Wolfe In Proc. 22nd Int. Conf. Artif. Intell. Stat. (AISTATS), volume 89 of PMLR, pp- 1275-1283. PMLR, 2019.
Kerdreux, A. d' d'Aspremont, and S. Pokutta. Projection- freee optimization on uniformly convex sets. In Proc. 24th Int. Conf. Artif. Intell. Stat. (AISTA7S), volume 130 of PMLR, pp. 19-27. PMLR, 2021.
T. Kerdreux, A. d' Aspremont, and S. Pokutta. Restarting Frank-Wolfes Faster rates under Hölderian error bounds. J. Optim. Theory Appl., 192:799-829 2022.
T. Kerdreux, A. d' Aspremont, and S. Pokutta. Local and global uniform convexity conditions. In Data Science and Optimization, Fields Institute Communications, pp. 85-120. Springer, Cham, 2026.
W. Krichene, A. Bayen, and L. Bartlett. Accelerated mirror descent in continuous and discrete time. In Adv. Neural Inf. Process. Syst., volume 28, pp. 2845-2442 2853, 2015.
S. Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Stat., 22(1):79-86, 1951.
R. Kyng, A. Rao, S. Sachdeva, and D. A. Spielman. Algorithmss for Lipschitz Learning on Graphs. In Proc. 28th Conf. Learn. Theory (COLT), volume 40 of PMLR, pp. 1190-1223, PMLR, 2015.
Lacoste-Julien. Convergence rate of Frank-Wolt for non-convex objectives. arXiv preprint arXiv:1607.00345. 2016.
Lacoste-Julien and M. Jaggi. On the global linear convergence of Frank Wolfe optimization variants. In Adv. Neural Inf. Process. Syst., volume 28, pp. 496-504. Curran Associates, Inc., 2015.
G. Lan. The complexity of large-scale convex programming under a linear optimization oracle. arXiv preprint arXiv:1309. 300.5550, 2013.
E. S. Levitin and B. T. Polyak. Constrained minimization methods. U.S.S.R. Comput. Math. Math. Phyx., 6-5):1-50, 1966.
Y. Liao, L. Ding, and Zheng. Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. In Proc. 6th Annu. Learn. Dyn. Control Conf. (L.DC), volume 242 of PMLR, pp. 993-1005, 2024.
S. Eojasiewiez. Une propriété topologique des sous-ensembles analytiques réels. In Les équations aux dérivées partielles, pp. 87-89. Editions du centre National de la Recherche Scientifique, Paris, 1963.
S. Lojasiewicz. Ensembles semi- analytiuussq Available at http::/ reineee. fr/mi mwcchhl..... coote/ ff 1965.
H. Lu, R. M. Freund, and Y. Nesterov. Relatively smooth convex optimization by first-order meth- ods, and applications. SIAM J. Optim., 28(1):333-354, 2018.
C. Maddison, D. Paulin, Y. W. Teh, and A. Doucet. Dual space preconditioning for gradient descent. SIAM J. Optim., 31(1)9911-1016, 2021.
13

---

Published as a conference paper at ICLR 2026
H. Maskan, Y. Hou, S. Sra, and A. Yurtsever. Revisiting Frank-Wolf for structured nonconvex optimization. arXiv preprint arXiv:2503.0922,,2000 2025.
M. C. Mukkamala and P. Ochs. Beyond alternating updates for matrix factorization with inertial Bregman proximal gradient algorithms. In Adv. Neural Inf. Process. Syst., volume 32, pp. 4268- 4278. Curran Associates, Inc., 2019.
A. S. Nemirovskij and Yudin. Problem Complexity and Method Efficiency Optimization. Wiley, New York, NY, 1983.
E. A. Nurminskii. The quasigradient method for the solving of the nonlinear programming problems. Cybern. Syst. Anal., ((1):145-150 1975.
A. L. Patterson. A Fourier series method for the determination of the components of interatomic distances in crystals. Phys. Rev., 46(5):372-376 1934.
A. L. Patterson. Ambiguities in the X-ray analysis of crystal structures. Phys. Rev., (55-6)):19520 1944.
F. Pedregosa, G. Negiar, A. Askari, and M. Jaggi. Linearly convergent Frank-Wolfe with backtrack- ing line-search. In Proc. 23rd Int. Conf. Artif. Intell. Stat. (AISTATS), volume 108 of PMLR, pp- 1-10. PMLR, 2020.
Pokutta. The Trank-Wolfe algorithm: A short introduction. Jahresber. Dtsch. Math.-Ver. 126(1): 2024.
B. T. Polyak. Gradient methods for the minimisation of functionals. U.S.S.R. Comput. Math. Math. Phys., 344)8864-878, 1963.
Rebegoldi, Bonettini, and M. Prato. A Bregman inexact linesearch-based -aakardd algorithm for nonsmooth nonconvex optimization. J. Phys. Conf. Ser., 1131:012013 2018.
V. Roulet and A. d' A'sprmmmot. Sharpness, restart and acceleration. SIAM J. Optim., 30(1):262-289, 2017.
Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev. Phase retrieval with application to optical imaging: A contemporary overview. IEEE Signal Process. Mag., 32(3): 87-109, 2015.
L. Stella, A. Themelis, and P. Patrinos. Forward-backward quasi-Newton methods for nonsmooth optimization problems. Comput. Optim. Appl., 6743)444--487 2017.
Takahashi and A. Takeda. Approximate Bregman proximal gradient algorithm for relatively smooth nonconvex optimization. Comput. Optim. Appl., 90()):227-256 2025.
Takahashi, M. Fukuda, and M. Tanaka. New Bregman proximal type algorithms for solving DC optimization problems. Comput. Optim. Appl., 83(3):893-931, 2022.
Takahashi, M. Tanaka, and S. Ikeda. Blind deconvolution with non-smooth regularization via Bregman proximal DCAs. Signal Processing, 202:108734 2023.
Takahashi, M. Tanaka, and S. Ikdaa. Majorization miiiiiizaiiiiiiiiiiiiiin Bregman proximal gradient algorithms for NMF with the Kullback-Leiilee divergence. J. Optim. Theory Appl., 208(1):1-34 2026.
K. Tsuji, K. Tanaka, and S. Pokutta. Pairwise conditional gradients without swap steps and sparser kernel herding. In Proc. 39th Int. Conf. Mach. Learn. (ICML), volume 162 of PMLR, pp. 21864- 21883. PMLR, 2022.
Y. Vardi, L. A. Shepp. and Kaufman. statistical model for positron emission tomography. J. Am. Stat. Assoc 80(389):8-20, 1985.
J. Vial. Strong and weak convexity of sets and functions. Math. Oper. Res., 8(2):231-259, 1983.
14

---

Published as a conference paper at ICLR 2026
A. A. Vyguzov and F. S. Stonyakin. An adaptive variant of the Frank-Wolfs method for relative smooth convex optimization problems. Comput. Math. Math. Phys., 65(3):591-602, 2025.
Wolfe. Convergence theory in nonlinear programming. Integer and nonlinear programming, pp. 1-36. North-Holland Publishing Company, Amsterdam, 1970.
Z. Y. Wu. Sufficient global optimality conditions for weakly convex minimization problems. J. Glob. Optim., 39(3):427-440, 2007.
L. Yang and K.-C Toh. Inexact Bregman proximal gradient method and its inertial variant with absolute and partial relative stopping criteria. Math. Oper. Res., 2025.
A RELATED WORK
Overview of Existing Bregman-Based Algorithm Studies: The Bregman gradient method was first introduced as the mirror descent by Nemirovskij & Yudin (1983). Accelerated mirror descent methods proposed by Krichene et al. (2015); Allen-Zhu & Orecchia (2017). Some first-order methods based on the Bregman distance do not require the global Lipschitz continuity of V.. Bolte al. (2018) proposed the Bregman proximal gradient algorithm (BPG) for nonconvex optimization problems and established its global convergence under the smooth adaptable property (see Defini- tion 2.3). Hanzely et al. (2021) introduced the accelerated BPGs. Takahashi et al. (2022) developed the BPG for the DC optimization and its accelerated version. The subproblem of BPG is often solvable in closed form. Takahashi & Takeda (2025); Fujiki et (2025) used approximations to Bregman distances to solve subproblems in closed form. Takahashi et al. (2026) developed the majorization-niine mininiiiionnnnniiiiiii BPG and its accelerated version, and applied them NMF Rebegoldi et al. (2018) proposed an inexact version of the Bregman proximal gradient algorithm.
B RESULTS FROM SMOOTH ADAPTABLE PROPERTY
B. PROPERTIES OF BREGMAN DISTANCES
The Bregman distance (a( y) measures the proximity between x E dom & and y E int dom ø Indeed, since @ convex, it holds that Dæ(æ, y) 2 0 for all E dom and y E int ø. Moreover, when & is strictly convex, Da(r, f y) = 0 holds if and only x = However, the Bregman distance
always symmetric and does not have to satisfy the triangle inequality. The Bregman distance is also called the Bregman divergence.
Example B.1. Well-known choices for & and Da are listed below; for more examples, see, e.g., (Bauschke et al., 2017, Example 1), (Bauschke Borwein, 1997, Section 6), and (Dhillon & Tropp. 2008, Table 2.1).
(i) Let (xx) || and dom ø = R". Then, the Bregman distance corresponds to the squared Euclidean distance, i.e., Do(Ø, v) ||| yl1
(ii) The Boltzmann-Shannor entropy (xx) Ei= log with 0og 0 = 0 and dom ø RT. Then, Dz(x, y) = Σ (I, log di - yi) is called the Kullback-Leibler (KL) divergence (Kullback & Leibler, 1951).
(iii) The Burg entropy <(x) - - logæ; and dom &
R Di=( log W5 1) is called the Itakura-Saito divergence (Itakura & Saito, 1968).
Then, Do(x, y)
(iv) Let (xx) 1 |||||| 4 + 2
1 || and dom ø = _R"" The Bregman distance D& is used in phase retrieval (Bolte et al., 2018), low-rank minimization (Dragomir et al., 2021), NMF (Mukka- mala & Ochs, 2019), and blind deconvolution (Takahashi et al., 2023).
We recall the triangle scaling property for Bregman distances from (Hanzely et al., 2021, Section 2), where several properties of the triangle scaling property are also shown.
15

---

Published as a conference paper at ICLR 2026
Definition B.2 (Triangle Scaling Property (Hanzely et al., 2021, Definition 2)). Given kemell generating distance & E ((C)), the Bregman distance D has the triangle scaling property if there exists constant > 0 such that, for all z, y, int dom and all y [0, 11, it holds that
Do((1 7)x yy, (1 - 7)xx + 72) S 7 7 (v)
(B.1)
Now, substituting <- on the left-hand side of Equation B.I, we obtain
Po((1 - 7)xx + my. x) (1 - +)) -(o)) --
where the inequality holds because of the convexity of d. Therefore, there exists 0 such that Do((1- - 7)xx + yV, S 7" Do(y, x) holds for all z, y int dom & and all 7 E [0, 1].
We will now show that a stronger version can be obtained if e is strictly convex, so that we can rephrase y with 1 1+ v where v > 0, i.e., the right-hand side is superlinear, which will be crucial for the convergence analysis later.
Lemma B.3, Given a kernel generating distance & E G(C)), if is strictly convex, then there exists v > 0 such that, for all x, E int dom @ and all y E [0, 1], holds that
Do((1 7)x + 78, x) 7 2 DD,,x)).
(B.2)
Proof. Equation B.2 holds if y = x or 7 E {0, In what follows, we assume * and
7))x + ry, x) for x, y e int dom o, y # < y < Let g(v) == 7 1+ 2)) Da((1
and all y E (0,1), 1). Using Dv(y, x) > 0 due to the striet convexity of o, we have, for any 2 0,
g((v) - - x) logy < O,
which implies g monotonically decreases. In addition, it holds that g(0) - 7 x) - - 7))(117)) + + 2))
- ((x) (Vo(x), x)) <((1 (0(11))x-0 +1) +(V(=))) x)
= (1 - 7))(() + 76(8) - 6((1 - 7)x + +v)) > 0,
where the last inequality holds because á is strictly convex, i.e. Φ((1 (111))x+ < (1 -))x)=) +
y Therefore, there exists > 0 such that g(v) 2 by the intermediate value theorem.
Because @ is quadratic when D& is symmetric (Bauschke & Borwein, 2001, Lemma 3.16), it always holds that D,((1 7)æ + z) 2> x) with v 1.
B.2 PROPERTIES OF SMOOTH ADAPTABLE PROPERTY
The convexity of Ló - and Ló + f plays central role in developing and analyzing algorithms, and the smooth adaptable property implies the extended descent lemma.
Lemma B.4 (Extended Descent Lemma (Bolte et al., 2018, Lemma 2.1)). The pair of functions (ʃ, Φ) is L-smad on C if and only if for all x. y E int dom Φ.
If(x) - f(v) - (Vf(v), x wil S LDo(x.y)
From this, it can be seen that the L-smad property for (f. Φ) provides upper and lower approxi- mations for I majorized by & with L > O. In addition, if o(x) = = ]|1=1 on int dom é = R"", Lemma B.4 corresponds to the classical descent lemma. While the L-smad property might seem unfamiliar at first, it is natural generalization of L-smoothness, and examples of functions f and satisfying the L-smad property are given, e.g., in (Bauschke et al., 2017, Lemmas and 8), (Bolte et al., 2018, Lemma 5.1), (Dragomir et al., 2021. Propositions 2.1 and 2.3), (Mukkamala & Ochs, 2019, Proposition 2.1), (Takahashi & Takeda, 2025, Proposition 24), (Takahashi et al., 2023, Theo- rem 1), and (Takahashi et al., 2026, Theorem 15).
Example B.5. Other examples be found in Sections 6.1, 6.2, Appendices F.1, F.4, and F.5.
16

---

Published as a conference paper at ICLR 2026
(i) Blind deconvolution: Let f R. R R be f(h, x) kl1Bh @ Ax - -yl? where C denotes the Hadamard product (also known as the element wise product). The function f can be decomposed into a DC function z),
fi (h, 2) - f2 x) with fi 2) (1]Bh @ Ax|l² + lly @ Bh] 2 + |x| llyll²) and f2(h, 1 || + A + 22ll Bh Axll?, where B Rmxxs A E Immxd and y E IR".
$ || + |||
Let (h, = [[]A]|2 ||
+ [1]b]]2 ||=||²) For any L satisfying
LN Σ
(3|b,1| + 3|,,1| + ||ال || + 1,,11,,11 + ||ay1l))
where b, and a, are the jth row vectors of B and A, respectively, (f1. ②) is L-smad (Taka- hashi et al., 2023, Theorem 1). Note that Bregman proximal DC algorithms require the smooth adaptable property of (S1, 6), instead of (J,
X (ii KL-NMF: Let f ET x R + R be f(W, = E (Xis log (W
Xi + (WH)s,, where X E R4x", f is bounded by f(W, H) = E, (Xas log Xij
Xij Ei= Oaly log W. Xi + (WH)s) with Caty E [0, 1). 11 1,..., m, = l,..,,
ou;
j == 11..... ,.. Let @WW H) = E,,(- log Wa + (W3) + Σis (- log His + + H Then,
n.
for any L > 0 satisfying
L max
max
aujXx
max
auy Xij
m, n2
the pair (f) is L-smad on R x R (Takahashi et al., 2026, Theorem 4.1). Note that the
BPGs (Takahashi et al., 2026) require the smooth adaptable property of (f. σ). instead of (f. o).
Remark B.6. In general, it is difficult to choose the best e such that (f, ()) is L-smad. On the other hand, it is known how to choose a suitable & empirically. An easy way find ø is to use elementary functions similar to f. See also the above examples, Section 6, and Appendix F.
The extended descent lemma immediately implies primal progress of FW algorithms under the L- smad property as a straightforward generalization of the L-smooth case.
Lemma B.7 (Primal progress from the smooth adaptable property). Let the pair of functions (f, Φ) be L-smad with strictly convex function & G(C') and let x+ = (1 7)x + yu with x, v int dom é and E [0, 1]. Then it holds:
f(x) f(++) 2 (Vf(z),, u) - Ly 12 (v,
Proof. Using Lemma B.4 and substituting x4 for x and for y. we have
f(x) - f(x 2 (V)(),, x v) (Z
It holds that D (x(x,, 2) < n D for some by Lemma B.3. Therefore, this provides the desired inequality.
We also have a progress lemma from the Bregman short step-size. Lemma B.8 (Progress lemma from the Bregman short step-size). Suppose that Assumption 3.1 holds. Define 2++1= = (1 Te) + Te. Then if 21+1 dom f.
f(x,) - f((++1) 2 1+
V Yo (V)()) - vv) for 0 OSTS
v1++vD )
(VI(z)) - vx)
Proof. Substituting x++1 = (1 - 71)= + + with Ie, D2 E P for x_ in Lemma B.7, we have
f(x.) - (((++)) 2 7 ( (V (I((z)), - vo) In 1+7 (o((t,
N/ (Zx) 2z -w) 1+v (Vf(x)), vx)
7t
oz),
1 v 76
where the second inequality holds because of an upper bound of 7.
17

---

Published as a conference paper at ICLR 2026
B.3 PROOF OF THEOREM 3.3
Proof of Theorem 3.3. By following the same argument as (Pedregosa et al., 2020, Theorem D),
have bound on estimating L as (1-loge // log () + 1) max (log(TL/LL-)) log Let n4 be the number of evaluations needed to estimate p. We have v gm.-1, which pro- /
vides n, = 1 l/ log B. Therefore, we obtain ne I max lo () 1) +
max (lo((TL/L-L))))) 0}/ log (1 log log (t + 1)}
C PROPERTIES FROM SHARPNESS
C.1 RESULTS FROM WEAK CONVEXITY
function is p-weakly convex and differentiable if and only if, for all æ, y E dom
f(v) f(x) 2 (Vf(r).y x)
x1|?.
Any C2 function defined on a compact set is weakly convex (Vial, 1983, Proposition 4.11) and Wu (2007). Since the proof of this fact is omitted therein, we provide the argument for the sake of completeness below.
Proposition C.I. Let P C. IR be compact set and f be proper and C2 function on P. Then, f is weakly convex on P.
Proof. Let Amin V2 "onin (²), where Amin (-) the smallest eigenvalue. The function g con- tinuous because Amin (.) and V f()) are continuous. Therefore, there exists the minimum value of g on P due to the continuity of g and the compactness of P. For p minzeP g(2)l, have f(r( + pl ž O for any E P. which implies f f -ll 1|2 is convex on P. i.e., f is p-weakly convex on P.
Minimizing nonconvex C2-function over compact set P is equivalent to minimizing weakly convex function over P. However, it is important to note that when p becomes large, the assumptions of algorithms may not be satisfied (see also Theorems E.3 and 5.4).
We have the key lemma for convergence analysis from weak convexity.
Lemma C.2 (Primal gap, dual gap, and Frank-Wolfe gap for weakly convex f). Suppose that Assumptions 3ii) (iv), and that f is p-weakly convex. Then for all x E P, it holds:
f(x) - < (Vf(z), x²) 2 ll x x²11
max Vf())) u) f111z 2²1|2. (C.1)
dEF
Proof. The first inequality follows from the weak convexity of and the second follows from the maximality of
C.2 PRIMAL GAP BOUND
We show in the following lemma that the HEB condition immediately provides bound on the primal optimality gap, which will be useful for establishing convergence rates of the proposed algorithms as well as the Lojasiewiez inequality (Bolte et al., 2007: Lojasiewicz, 1963; 1965), provided f convex.
Lemma C.3 (Primal gap bound from Hölder error bound). Let f be a convex function and satisfy the HEB condition with q 2 1 and μ O. Let x* be the unique minimizer of f over P. Then, the following argument holds in general, for all x E P:
(V (V)(x)
x x²) x:*
-
[(x) (xx---² 1
(C.2)
or equivalently,
(
1/9 (f(x) - 1-)
1-1
(V x=)
x x
18

---

Published as a conference paper at ICLR 2026
Proof. By first applying convexity and then the HEB condition for any x" X with f f(x²)
it holds:
(Vf(z), x²) f(x) -
fr -
(Vi(x), - x²))
|1 -
110- - --11
(V/(+), x²))
|1 (115(0) -f1) 2/9
1| - x²1
which implies
1/9
(Vf(z), xz)
(1(x) - -
| - xz
or equivalently
[(x) / 1
q
9-1 (Vf((). x - x²")
8-1
| - x='
Remark C.4. With the remark from above, immediately relate the HEB condition to the Eojasiewicz inequality (Bolte et al., 2007; Lojasiewicz, 1963; 1965); the Łojasiewicz inequality is used to establish convergence analysis (Bolte al., 2007). To this end, using Equation C.2, we
estimate |
(V))))====))
<
|----| [[]
= [Vf(=)]] to then obtain the weaker condition:
! --1
-(x) 8 <
[V(() = = e [(()))
(C.3)
1/4 and 0 2-1, Inequality Equation C.3 is called the e-F.ojasiewiez inequality with 0 E [0, 1). X S P. then the two conditions are equivalent. However, the optimal solution(s) are on the boundary of P as is not infrequently the case, then the two conditions are not equivalent as [(x)] might vanish for x X', whereas (V x²) does, i.e., the HEB condition is tighter than the one induced by the Łojasiewicz inequality.
(1)
where c
The next lemma shows that we can also obtain primal gap bounds in the weakly convex case together with (local) quadratic growth.
Lemma C.5 (Primal gap bound from the quadratic growth). Let be a p-weakly convex function that satisfies the local p-quadratic growth condition such that < μ. Let x be the unique minimizer of f over and let Ç 0. Then, the following holds: for all x [f S f* + <) P.
[(x) 1 2μ
((V((E))--0)}) 2
(C.4)
(1 (m=
||
x=
or equivalently,
2 ( 1/2
x x*) (1 (1-2) () (f(x) (1) (Vf()), 4
||. - x-
Proof. By first applying weak convexity and then the local quadratic growth condition for x" E X* with f(z")= f" and for all x E [f < f + n P. holds:
f(x) - = f(a)
P x² 112
< (Vf(z),z
2
< (Vf(x),
P
(f(x) - -
19

---

Published as a conference paper at ICLR 2026
which implies
(1- (1-2) (r) (Vf(), (Vf(z), -x") x²) 1x--x111 (C.5)
||x x+1l
Using the local quadratie growth condition again, have
(1 p (f(x)- -f (Vi(r), x²)
2 (f(x) -f1) 1/2
)
x
11
which provides
(m) 1/2
(f(x) f2) (Vf()), x x²))
11
2
11
x=1
equivalently
f(x) - f s 2/
( (1/((0))--1 )0))
(1 p)?
|
Remark C.6. In the same vein as the discussion in Remark C.4, immediately relate the local n-quadratic growth condition with Ç > O to the local
(PI.) inequality.
Using Equation C.4 in Lemma C.5, for all [ S S" + N,,,, we have
2p
f(x) 1"
(n M) |/(2))
(C.6)
which is equivalent to the PL. inequality (Polyak, 1963), also called the gradient dominance prop- erty (Combettes & Pokutta, 2020), with pーP- The PL inequality also equivalent to the Lojasiewicz inequality with 0 = 2. Strongly convex functions satisfy the PL inequality (Braun al., 2025, Lemma 23). Note that we will not have the primal gap bound under the HEB con- dition and weak convexity because an inequality like Equation C.5 does not follow from the HEB condition.
y2a
C.3 SCALING INEQUALITIES, GEOMETRIC HÖLDER ERROR BOUNDS, AND CONTRACTIONS
In the following, we will now bring things together to derive tools that will be helpful in establishing convergence rates.
SCALING INEQUALITIES
Scaling inequalities are key tool in establishing convergence rates of FW algorithms. We will introduce two such inequalities that we will use in the following. The first scaling inequality is useful for analyzing the case where the optimal solution lies in the relative interior of the feasible region. While its formulation in (Braun et al., 2025, Proposition 2. 16) required T-smoothness f. it is actually not used in the proof, and the results hold more broadly. We restate it here for the sake of completeness.
Proposition C.7 (Scaling inequality from convexity when x" E int P (Braun et al., 2025, Proposi- tion 2.))).. Let P C R be nonempty compact convex set. Let f IR" -> (-oo, +o0| be C and convex on P. If there exists r > 0 so that B(x", .r) C P for a minimizer x of f. then for all x E P, have
(V[(x), - 2 [[()[ T(VI(x), x x*) I
x=
where v E arg max xf(x), u).
When f is not convex, assuming that f is weakly convex and local quadratic growth, we have the scaling inequality for nonconvex objective function.
20

---

Published as a conference paper at ICLR 2026
Proposition C.8 (Scaling inequality from weak convexity when x" E int P). Let P C R" be a nonempty compact convex set. Let f R" + (-oc, too C², p-weakly convex, local f quadratic growth with > 0 on P. If there exists > 0 so that (xx r) c P for a minimizer x* of and S μr, then for all x E [ 1 f + [) P. we have
- o) 2 [ T(V((T), I (V[(2), xr
1 x²
where v E arg max ( (V)( u).
We consider x² - r2, where 2 is point with ||||| = and (Vf(z), = [V holds Proof.
that
(V)(z),)) - (Vf(z), r2) = (V(()).2")+r1VVV((
(C.7)
From weak convexity, for all x E [ - f + N we have
f() 2 (Vf(z), x²- x) ? I| x= 112
2
2 (VI()), - -x) L (((x)) - -
where the last inequality holds due the local quadratic growth condition. Because of p S p. this inequality implies
2 1 1- L)
0. By rearranging Equation C.7 and using (Vf(x), - x²) 2 0, we obtain
11
(Vʃ(z),z- u) 2 (V)(z), xt) -2) x²) + r|| V| f()=
In addition, it holds that
(Vf()), x*1
[| x- (+)
1 x²
where the first incquality holds because of the Cauchy-Schwee incquality.
Lacoste-Julien & Jaggi (2015) defined a geometric distance-like constant of a polytope, known as the pyramidal width, to analyze the convergence of the away-step Frank-Wolfe algorithm (and other variants that use the pyramidal width) over polytopes. It can be interpreted as the minimal ő >> 0 satisfying the following scaling inequality Equation C.8, which plays a central role in establishing convergence rates for the away-step FW algorithm; see Braun et al. (2025) for an in-depth discus- sion.
Lemma C.9 (Scaling inequality via pyramidal width (Braun al., 2025, Theorem 2.26), (La- coste-Julien & Jaggi, 2015, Theorem 3)). Let P C R" be a polytope and let 5 denote the pyramidal width of P. Let x E P. and let denote any set vertices of with x E conv S, where conv denotes the convex hull of S. Let vi be any vector, so that we define FW = arg millee (v/, v) and A arg max.es (V, v). Then for any y E P
(v, x -FW, 8 (3), v\
(C.8)
x yll
Note that Lemma C.9 does not require the convexity of f. and we will use it for nonconvex opti- mization. When d is -sstrnngly convex and (1/ x y) 2 0, Lemma C.9 implies
(1, x y)
| 211 > 80 (1), x y)
(v, a ..Wy2 2
2D
Note that the last inequality of the above also holds for 8²0 (0.z v)² the divergence.
i.e. with x and y swapped in
2Dx(v.2)*
21

---

Published as a conference paper at ICLR 2026
GEOMETRIC HÖLDER ERROR BOUND CONDITION
We will now introduce the more compact notion of geometric Hölder error bound condition, which simply combines the pyramidal width and the HEB condition of the function f; see also (Braun al., 2025, Lemma 2.27) for details when q = 2.
Lemma C.10 (Geometric Hölder error bound). Let P be polytope with pyramidal width å >> 0 and let f be a convex function and satisfy the HEB condition with eF arg (V and y arg max (vx),, 8) with S Vert P. so that ø E conv S, we have
(V (V](z), V FW
f(0) - f ?
Proof. Combining Equation C.8 with Lemma C.3 for & = Vf(x), we have
-(x) S (g) 2 (V
q 2 (Vf(x), e N of
| - x
FROM CONTRACTIONS TO CONVERGENCE RATES
Besides scaling inequalities and the geometric Hölder error bound, we also utilize the following lemma for convex and nonconvex optimization, which allows us to turn a contraction into conver- gence rate.
Lemma C.11 (From contractions to convergence rates (Braun et al., 2025, Lemma 2.21)). Let ( be decreasing sequence of positive numbers and co, Ct, 02. 0g be positive numbers with ei such that h1 S co and h4 h4+1 2 h4 c2h
80] for 2 then
co(1 )t1
if < S to:
h4
(1tc)loltttu))u7 011/2/06) if 2 to.
(c) (c1/02)'/0
where
(c1/c2)2/00
logi-ei
40 maxx
+ 2,
co
In particular, we have h, S c cift t to + Ooeze
and c (c1/c2)1
D PROOF OF CONVERGENCE ANALYSIS FOR CONVEX OPTIMIZATION
We would also like to stress that while we formulate some of the results for the that x" int P. the results can extended to the case that xx E ri P. iee. the relative interior of P, which we did not do for the sake of clarity. Basically, the analysis is performed in the affine space spanned by the optimal face of in that case; the interested reader is referred to Braun et al. (2025) for details on how to extend the results.
D.1 SUBLINEAR CONVERGENCE
We recall a key property for analyzing convergence rates in convex optimization.
Lemma D.1 (Primal gap. dual gap, and Frank Wolfe gap for convex f (Pokutta, 2024, Lemma 4.)) Suppose that Assumptions 3.1 (i), (iv), and that f is convex. Then for all P. it holds:
f(x) - f S (Vf(x), x - x²) & max ( v).
(D.1)
BEP
We establish a sublinear convergence rate of the FW algorithm under the smooth adaptable property. It is similar result to (Vyguzov & Stonyakin, 2025, Theorem 1). We conducted its proof following Braun et al. (2025); Jaggi (2013); Pokutta (2024). The FW algorithm uses the open loop step-size, Le., 7t in the following theorem.
22

---

Published as a conference paper at ICLR 2026
Theorem D.2 (Primal convergence of the Frank-Wor Wolfe algorithm). Suppose that Assumptions 3.1 and 4.1 hold. Let D = V /supa.er (z( y) be the diameter of P characterized by the Bregman distance Da and let v E (o, 1]. Consider the iterates of Algorithm 1 with the open loop step-size, 2 Le., "t = 241 Then, it holds that, for all /. 2 1,
f(x)) 1 2D
(D.2)
(t+2) 2)
and hence for any accuracy e we have f(x)) - f* $ for all 2 (2
Proof. For some (0, 1]. we have
[(x)) - ((++1) 7h (V) - Inttt Do(vi,
2n(f(z)) - - - - (e.,
where the first incquality holds because of Lemma B.7 and the last inequality holds because of Lemma D.I. Subtracting f on both sides, using (p( I D2, and rearranging leads to
[(a+1)) 5* (1) - f*) I=?+>
When 0, follows
ff LD2 22DD? Now, we consider t and obtain
f(x(-1) f < (1 - (f)))))))))))))))))))))
$ t
21+v
2+t (f(xz) - fr) (2+ to
LD
t 21+"LD2
2142
1)+ LD²
2+t (2 + 1)
2
((3 ((3+))((+1)
21+2DD12
(3 t)"
(2 1)
(3 + t)
where the last inequality holds due (3 () +) S (2 + ++" with 0 < VVSL. 1.
If - 2l and in Equation D.2, we have - S 4LD* (1 + 2). which is the same as a sublinear convergence rate of the classical FW algorithm.
Remark D.3. While the convergence rate Equation D.2 is the same as Vyguzov Stonyakin (2025), Vyguzov and Stonyakin assume that the triangle scaling property holds for Dg. In contrast, we require significantly weaker assumptions: enough assume that strietly convex due to Lemma B.3 in order to establish Theorem D.2.
D.2 PROOF OF THBOREM 4.2
Because Algorithm 2 is well-defined (see Remark 3.2), the convergence result of the FW algorithm using the adaptive step-size strategy (Algorithm 2) is essentially the same the one that uses Breg- man short steps (Thcorems 4.2 and 5.3); up to small errors arising from the approximation whose precise analysis skip for the sake of brevity.
Proof of Theorem 4.2. Let h4 == =((x)) - f". Using Lemma B.8, we have
h = (xxx) - [(x++1) 2 (VI(x;), x v2)
where 7/ min
(1 T(1t0)De(M:P))
.
We consider two cases: (i) 7/ < and (ii) 7 1.
ii N 1: Using %
(V.((a)).. [(1tv)D((MM.3))
have
(V](x)), x4 v1) 1t1/
hr - h4t1 2
1t [L(1 (e),
23

---

Published as a conference paper at ICLR 2026
V V[
1+ (I(1+ + ((]++)) // D2/2
pltl//
0-
I V Mc D2/2 h
where the second inequality holds from (f(z)), 21 - uz) 2 f in Proposition C.7, and the last inequality holds because f satisfies the c-tojasiewicz. inequality with = (q/P) (see Remark C.4), and M == (L(1 + 1/)
(ii 7t 1: Using Equation D.I, we have
h2 ho+1 = f(z) f( 2 I+v (Vf(z)). -vt) 2 1+v (f(xz) f*) = v
V
h
+
where the second inequality holds due to the convexity of From (i) and (ii), we have
111//2 (+
ht - h141 min
11 tu
h4
+ Mc.
When q 1 1 + U4 have
22+1/v 1+ v2' 1 v Mcl+1/u D2f0
h4 het1 2 min
V
hy.
This inequality and the initial bound f(x11) f fr S LD2 due to Lemma B.4 imply
111//2
h S max
LD
(1+V* I Mcd+l/v
On the other hand, when q v. have
h4 h4t1 2 min {
pl+1/v
8-1-" h
j. -he.
(1+v' 1+1 v M/ D2/1v
Using f(11) f S LD2 and Lemma C.11 with co LD2, c1 14 C2
-411/0
Itv -1/ Dafes
and 0o 8-1-u > 0 from > 1 + we have the claim.
pn
D.3 PROOF OF THEOREM 4.4
Proof of Theorem 4.4. By using the induced guarantee on the primal gap via Lemma C.10, we have
h4 f(x)) -5
9 1
+
(Vf(zz).
uf
FW
+
q
+
(x.).
A
6
P
8
(D.3)
where the last inequality holds because d, is either of (V)(x), A -F in Lines 4 and 7 of Algorithm 3. We obtain
of with (VI(x)), de) 2
14 1141 2
1 (VI(z)) d,) min 7t.aax
v
(Vf(x)).
T(11 + v) (Vi, Fee
(V)())), de) 1+1/0
min
mm I+ (Vf(x)),
I+ (I(1 D) (1r,
vhu
(4// 1/////11111// (L + D2)
min
M, 1 1+ 1+v
vhu
(44/2) 1i2 (+
=min
1 + Mtmaax
1+v (I(1 + v)
h
24

---

Published as a conference paper at ICLR 2026
where the first inequality holds due to Lemma B.8 with Ytmax (Frank-Wool steps) and A Ttmax 1 (away steps), and the second inequality holds because of Equation D.3 and (VI(x)), de) 2 (VI(x)), uz) 2 he-
In (v,q) (1, for Frank-oolfe steps, M.max 1 steps, we only rely on monotone progress hx+1 < htg because it is difficult to estimate ma, below. However, Tt,max cannot small too often, which is the key point. Let us consider 7: = 7t.max in an away step. In that case, vf is removed from the active set S in line 14. Moreover, the active set can only grow in Frank-Wolfe steps (line 11). It is impossible to remove more vertices from S than have been added Frank-Wolft Wolfe steps. Therefore, at most half of iterations until t iterations are in away steps, i.e., in all other steps, we have "t
p62/LD² 2 /32LD2 For away
(V (())).d)) < ,t,max and then nu62 2LDs
h4 h4+1 2 32I.12 h4. Because we have h4+1 I (1- (1-32t.nz) 321 h, for least half the iterations and h S he for the rest, we obtain
1 82 [(t-1)/2"
(1
-
LD².
32I. D)
(64/9))/48/2) + g-1-e Ite: I+v (E(I+0) h
In q >> 1 + v, we have h4 h++1 2 min
he for at least half
of the iterations (Frank-Vy Wolfe steps) and h4+1 S h for the rest (away steps). The initial bound f(11 - f < LD2 holds generally for the Frank-Wolfe algorithm (see the proof of Theorem D.2 and (Braun et al., 2025, Remark 2.4)). We use Lemma C.11 with co = LDd, ci
Itp" C2 =
2
(=5/2) " (1(++))33) and 6g 9-1-v > O from > 1 + and obtain the claim.
2y
Remark D.4 (Compatibility of parameters). The condition q 1 is necessary in that (U, # (1,2). The reason is as follows. In the case 4 = 1 + v, for Frank-Wolfe steps, we have
(w//)) 1 (L(1 + D2
(4)
1/v
1
(D.4)
D
2 (1 + 1)2 ( D(1-1//
which might be greater than because Da Py
2 if D and v are small enough. In order to
make Equation D.4 smaller than 1, v should be i.e., (v,g) (1, When v and g & 2, reduces to the q >> 1 + case.
E PROOF OF CONVERGENCE ANALYSIS FOR NONCONVEX OPTIMIZATION
E. GLOBAL CONVERGENCE
We show that Algorithm 1 with n = 1/(T + 1) thv globally converges to stationary point, where T E the number of iterations. Its proof is inspired by (Lacoste-Julice) 2016, Theorem 1) and (Pokutta, 2024, Theorem 4.7) and identical those for the case when 2111 1|2.
Theorem E.1 (Global sublinear convergence for nonconvex optimization). Suppose that Assump- tion 3.1 holds. Let 0 and D == / /uup Dz(2, y) be the diameter of P characterized by Da and let T E N. Then, the iterates of the FW algorithm with % = = y 1/(T + 1)rtz satisfy
G == min max max (V)()) v2) < 2 max (ho, LDD}} US e.
(T + 1)
where ho = f(x)) the primal gap at Zn-
Proof. Substituting I++1 for x44 and for in Lemma B.7, we have the following inequality:
f(x)) (x++1) 2 (Vf())) x, vz) I DD(
25

---

Published as a conference paper at ICLR 2026
Summing up the above inequality along t 1...., T and rearranging provides
(V((x)).z - -v) - f(xo) f(or+1) +
LD (z) Ut)
T LD = ho ,
I f(ro) -f + tg tt
Dividing by 7(T + 1) on the both sides, we obtain
hg GT S T+1 V[(z)) - 7(T +1) + >" LD?
which, for y 1/(T 1) 1)riz, implies
T GT T 1 (V - vn) s (ho + (T) xスx < 22 max LD² + 1) 1ic.
1=U
This is the desired claim.
As mentioned above, we generalize prior similar results. fact, the case where 1 ||2 and
V 1, we have 7/t VT+I and obtain as guarantee
min max ( - -x) s 2 maxx LD OSt o
VT +
which is the same rate as (Lacoste-Julien, 2016, Theorem 1).
E.2 LOCAL SUBLINEAR CONVERGENCE
We prove a lemma used in the proof of convergence analysis. Lemma E.2. For any E (0. 1] and & 2 0, it holds that
h(t) (++ (t I 1.
(E.1)
2)
Proof. We have
(t + (t+ lim
+ 2 ) (1-
1 "
v
lim h(t) = lim 1-000
to (t+ 2)
t00
1
+ =
We take the logarithm of h(t), that is, log h(t) = log(t 3) + log(t + v) (1 + 1/) log(t + +
and obtain
N(()
1+
-2 + 10v
+ (t+ 2) + 3) 2 -) > 0,
h(t)) t+3 1+2
where the last inequality holds for v (0, 1] and inequality implies (t()) > 0. Therefore, we have sup h(t) = 1, which implies h(t) < 1.
Since h(t) > for t 2 0, the above
Now we show sublinear convergence with Yt = rem D.2.
The proof is a modified version of Theo- 24f
2
Theorem E.3 (Local sublinear convergence). Suppose that Assumptions 3.1, 4.3, and 5.1 hold. Let E (0, 1] and let D = /supa.ueP v)) be the diameter of characterized by the Bregman distance Dg- Consider the iterates of Algorithm I with the open loop step-size, i.e., 247' Then, p/o < L and Be < v hold, it holds that, for all 2 1.
2
f(x)) - f 21+ uD,2 p(l + 2)
(E.2)
and hence for any accuracy 0 we have f(x)) f s for all 12 (2.2"
26

---

Published as a conference paper at ICLR 2026
Proof. Using Lemma B.7, we have
[(x)) - [x++1) 2 n ((V[(r)); 27 vz) -L [ Do(u,, xx))
2 (f(z)) - --
-blles - x² IP) FrttDDolee xz),
where the last inequality holds because of Equation C.I in Lemma C.2. Subtracting I and rear- ranging provides
[(x+11) - ( (1)))))())) f*) + PTt | | x012 + Li + =D("
(E.3)
< (1-(1-- (1- 11) (f(ai) - 1*) In 1
(E.4)
where the last inequality holds due to the quadratic growth condition. For t = 0, using Equation E.3, we have
f(x1) f" 2111000 1 -110-1111 + LD Io) - ( +b) D 2LDD & 2p LD",
(E.5)
where the second inequality holds because á is a-strongly convex and the last inequality holds because of 3 < 6/ - v) - 2///p. p. Now we consider t 2 1. Using Equation E.4 and 7 247 we have
2p
2 DLD²
21+2
f(21+1) - f¹
t+
p(t + 2) +
H
(++2)
2p
1 2
t +
+
p (1 2)
μ. 2
(1+ 3)+ +3//N) (t + 2)
P (1+3) 3)"
2 #LD2
p(1 3)
where the last inequality holds because of (1 + 3) 3p/n)) s (1+ v) 5) ( from Equation E.
We can apply the quadratic growth condition again as before and obtain
22+V 2
dist(x,, x²3) < (f(xz) fr) s p(t + 2)²²
and hence
21t0/2DD DVT
dist(rt, X²)
+ +
Note that Theorem E.3 does not require knowledge of the number of iterations T ahead of time compared to Theorem E.1. We stress, nonetheless, that the latter can also be adjusted using a dif- ferent step-size strategy to obtain an any-time guarantee; see Braun et al. (2025) for details for the standard Euclidean case, which can be generalized to setup. Moreover, we apply The- orem E.3 to the Euclidean FW algorithm, i.e., & = +lll l| and v 1. Using Equation E.2,
D == supz,er || y/ and Drne = V2D, we obtain
2 2uLDe Eus p(t + 2)
f(z.) ft
Theorem E.3 requires p/a L. and 3r 2 These assumptions are easy satisfy. Example E.4 (Example 3.1 in the arXiv version of Liao al. (2024)). Let us consider
"
--++11 if - 1 < -0.5,
f(x)
3(x + 1)?, otherwise.
27

---

Published as a conference paper at ICLR 2026
The function f is not convex but p-weakly convex with p 2. A global optimal solution of is
x² = -1 and its value is f(x²) =0. Moreover, f satisfies the quadratic growth condition with 0 < I 6. Because f is quadratic function, have L 6. It holds that 2 p S L and
1 3 < 11<2-1 (set μ 6). Therefore, the assumption of Theorem E.3 holds.
In order verify 32 < 2 v, it is easier examine the sufficient condition 32 < instead because the exact value of difficult to estimate. On the other hand, without loss of generality, we can assume 0 = 1. When o > 1, p/o < p S L holds. When o < 1, we can use Φ) - - 1 1| which is 1-strongly convex. When @ is convex but not strongly convex, we can use Φ = + 2 11111 11. Therefore, it suffices to verify p/a S p I L, which often holds (for example, see an example of phase retrieval in Section 6.2).
E.3 PROOF OF THEOREM 5.3
Theorems 5.3, 5.4, and E.9 require the weak convexity and the local quadratic growth condition of I with S μ.. We show several examples as follows.
Example E.5. We show some examples of p-weakly convex functions satisfying the (local) quadratic growth condition with p μ.
(i) Let fa) log(1 2²). f attains the minimum f 0 at x- = 0. The function
is 1 1/4-weakly convex because f"(x) = -1+a2y and its minimum is 1/4. Moreover,
2(1-x²)
(x - x² = x² < 2 log(1 + x²) = (f(x)) f*) holds for any x E [f s <]. Letting / = we have 6 logg(1 1l)g(1+>))-a)) -2² 2 for any E [f < 16]. Note that
16 is not an exact value. In this case, we have 1/4 p p< <リ= 1/3. Through simple calculations and visualization, we can obtain a larger value of than 1/3. This function is used for image restoration (Bof et al., 2016; Stella et al., 2017).
at x = 0. The function f (ii) Let f(x) = 1/²² + 2(1 - c-=²). f attains the minimum f³ =
is (8e-3/2 1)-weakly convex because f2(x) 1 4e 40 2x.²) ) and its minimum is
1 Se 3/2 -3/ -0.785. Moreover, (x-x") x² < (f -f)=)))) -f") holds for any x E [f s c)-
Letting J we have (r) 4(1-4
2 0 for any x E R. The function
f satisfies the global quadratic growth condition with 8e 3/2
1.
(iii) Let f be the function defined in Example E.4. We μ = AA for some pi (2, 6] because Jl can be from (0, 6]. It holds that 2 < p.
Because Algorithm 2 is well-defined (see also Remark 3.2), the convergence result of the FW algo- rithm with Algorithm 2 is the same as Theorem 5.3.
Proof of Theorem 5.3. Let he == f(x))= - fr. Using Lemma B.8, we have
h h f(x)) - f((++1) I+ (Vf(z)) v.)e
where 7t- min {1, 1, (Z(tt))o(leat)) $}
((
We consider two cases: (i) 7t < 1 and (ii) 7 1.
Y < 1: We have
ui V (T()),, - uv)
min ( (VI(ze), -v) 1/0
h4 h441
1.
L[ (
1+
141/2
1 (L(1 (v)
I+ u((+r)) D2/0
28

---

Published as a conference paper at ICLR 2026
V p11//2
1+ V Mc D2/02
where the third inequality holds due to Proposition C.8 and the definition of and the last inequality holds due to the local PL inequality from Remark C.6 with y2p and M = (L(1 + u))2/2.
(ii) the case where " i.e. (Vfflo)) (( 2 L, this implies
(Vf(z)), 24 - -w) 2 L(1 + (v,,
(E.6)
because of 1/v > 1. Using Lemma B.7 and Equation E.6, we have
h41 - h4 S LD (1t, r4) (V f 22 - vn)
v + v
( (zt), 2t uz))
<
V
|1 xx 112)
1
< 1 p
h4-
v
where the third inequality holds because of Equation C.1 in Lemma C.2, and the last inequality holds because of the local quadratic growth condition of f with μ >> O. Therefore, we have
(
h411 S I+
1
Pv p
h4
From (i) and (ii), we have
1+11/
h het1 2 min
1-
P
h
11+v v
+ v Mc M/
When == 1, we have he h4f1 min
(1
L
h4.
This inequality and the initial
2M2
bound f(x1) - 1 < L due to Lemma B.4 imply
{ (1+
h, S max
LD².
2
11
DM
On the other hand, when (0,1),
h4 - h1+1 2 min
v
1-2)
1
V
r1+1/v
h4 } J.m.
I+
"I+ Mcl+1//D2/1
Using f(x1) - fr < LD² and Lemma C.11 with co LDd, ci the 1.-.) C2
11t//v Ite D2 and Oo 20
1-
O, we have the claim.
When o = = 112 and we have local linear convergence with "t min (V (V)())).)
from Theorem 5.3. When Φ = 1 ||. ie., Do(x, y) = 211 - -yl Druc = v2D provides
1+ (+t)) (.)
22
LD
f(x)) < max 2
D2 11 2L
Emc
2
E.4 PROOF THEOREM 5.4
In the same way as Theorem 4.4, the pyramidal width is the minimal 8 >> 0 satisfying Lemma C.9 (see also (Braun et al., 2025, Lemma 2.26) or Laacoste-Julien Jaggi, 2015, Theorem 3)). An upper bound exists on the primal gap for weakly convex functions.
29

---

Published as a conference paper at ICLR 2026
Lemma E.6 (Upper bound on primal gap for weakly convex functions). Suppose that Assump- tions 3.1 and 5.1 hold. Let be a polytope with the pyramidal width 0. Let S denote any set of vertices of P with E conv S. Let & be any vector, so that define w arg g v) and e arg max t). If p/u 1, then it holds that, for all E [f f +
2μ
[(x) 1" S ( p) V (I)),,
Proof. Using the weak convexity and the local quadratic growth condition of f. it holds that, for all +
((x) -(x)) & (VS(x), xt - x²)
2 x²1
- $ (V - (((()) -((x)))
which implies
s (1 (f())-((x') S (VI(z),x-x")
where the first inequality follows from 1- p/p > 0. Using Equation C.8 with &f Vf(x) and y x= and the above inequality, we obtain
fV(()), v - )2
Vf((),, xx
82
11:0
x=1
11
L
(f(x) - f(x"))²
11
1x- - 1x=1"11
2 (f(x) - f(()))²
11
1-
L)
2
f(x) - f(x*)
P (f(x)) (((")))
where the third inequality holds because of the local quadratic growth condition.
Proof of Theorem 5.4. By letting he = fxxx) f and using Lemma E.6, we have
(u-p)282 (VI(a)), 0 22 (p:V) (VI(x;), do)²
24
h4 S
(E.7)
w62
where the second inequality holds because de is either 3, - of or u xe with (V de) >
(Vf(x), vy //2 in Lines 4 and 7 of Algorithm 3. From Lemma B.8 with m. (Frank- Wolfe steps) and mm,
Aupie
(away steps), we obtain
I-2,3
(V)()))
#
h1 h44 2 1+v
(Vf(z)), di) min
N.maxx L(1 + DD (o xx)
(V)( de) 1+1//0
min
mtmax 1 1+ di),
V
T (T.(1 + +D) s (Ve, 1/
V (how82) +
V/t.max
(1_)) her
min
1+
1+ (L v) D291/O
V (wo2) 14
V/H.max
(1-) P
min
1
hr 1 (L(1 - D)D2)1T0 h4
1 v
where the second inequality holds because (vf(z)), 2 (Vf(xz), x - v2) 2 h -1 vel > (1 1-2) 2 hr (from Lemma C.2 and the quadratic growth condition of f) and Equation E.7.
30

---

Published as a conference paper at ICLR 2026
In = 1, for Frank-Wai Wolfe steps, have Mt, (1 (1-2) ()) (1 (1-
(1
D2
2LD by < < < p S L and ò S D. For away steps, it seems that we only obtain monotone progress hu+1 he because it is difficult to estimate Tt,max below. However, ma, cannot be small too often. Let consider 7/ max in an away step. In that case, 2 is removed from the active set S line 14. Moreover, the active set can only grow in Frank-Wolfe steps (line II). It is impossible to remove more vertices from Se+1 than have been added in Frank- Wolfe steps. Therefore, at most half of iterations until iterations are in away steps, i.e., in all other steps, have "/
D 2
we²
w62
7t,max and then h1+1 (1
wh h2- Because ZLD=
2LDg(1(,4))
h for least half of the iterations and h441 S he for the rest, using h1 S 2LD from Equation E.5 and p < L, we obtain
have he+1 S (1
wdd 4T.D2
w 8 [(t-1)/2]
[(x.) - 2 5 4I. D)
LDZ
(w69) 4/2 1+v (1-2) () 144 14v (1(1+0)22)11 h
1-
In (0, 1), have h4 h441 2 min
} he for least
half of the iterations and h441 h for the rest. The initial bound f(a)) - T.) < 2TD
holds from Equation E.5 and p < L. We use Lemma C.11 with co = 2LD
v
Itv
(w + I+o (I(I+))DA) and 0o 1- and obtain the claim.
When é = = -11 and 1, the local linear convergence of Algorithm 3 is equivalent to
8²
[(t-1)/2]
((x)) ((x)) s
LD
2T. D
E.5 LOCAL LINEAR CONVERGENCE OVER UNIFORMLY CONVEX SETS
In the convex optimization case, Canon & Cullum (1968) established an early lower bound on the convergence rate of the FW algorithm. However, in the special case of P being strongly convex, Gar- ber & Hazan (2015) showed that one can improve upon that lower bound. Kerdreux et al. (2021) establish in the case of being uniformly convex. We will now carry over this result to establish local linear convergence for the case where f is weakly convex and L-smad on P.
To this end, we recall the definition of uniformly convex sets.
Definition E.7 ((a, p)- -uniformly convex set (Braun al., 2025, Definition 2.18), (Kerdreux al., 2021, Definition 1.1)). Let and be positive numbers. The set P C R" is (a, (a.p))-uiffe p)-uniformly convex with respect to the norm || || if for any x, y E P. any 7 1), and any E 12" with ||ж|| S 1 the following holds:
y ナ+ - v) + + - 7) a ul E
Moreover, P is said to be strongly convex if P is (a, 2)-uniformly convex.
We will use the scaling condition for uniformly convex sets to establish linear convergence.
Proposition E.8 (Scaling inequality (Braun et al., 2025, Proposition 2. (Kerdreux et al., 2021, Lemma 2. 1)). Let P a full dimensional compact (ax, pluufforrll convex set, u any non-zero vector, and v = arg m (u, v). Then for all x E P
(u, x - v) 2 al|/ r
Now we establish local linear convergence for weakly convex optimization on uniformly convex sets.
31

---

Published as a conference paper at ICLR 2026
Theorem E.9 (Local linear convergence over uniformly convex sets). Suppose that Assumptions 3.1 and 5.1 with 6 = b1ll 1| and int dom = R" hold and that P is (a. p)uuifoomly convex set. Let
f be bounded away from O, L..., | f fz))l 2 > 0 for all x E P. Let Druc suPx,yrr
||
yl
be the diameter of Consider the iterates of Algorithm with " = min (v 2. ve) Then, if μs and S L, it holds that
L1 1
max { + 11++))1-1 (
oC
L.Dec
if = 2,
1-1
f(x)) - S
24 LD
if if to.p22
[((--/p)) P/2 L/ac) 2/(0-2)
1HH1-pp//00/2-1////// to))/(t- 0(1/t0/(n-))
ift = 2o.p2
for all t 12 1 where
L 1(11- ((1-p/m)* p/1))=// [ 2/(a-2)
L/ac)
to max
logg(1+4)
+
LD Euc
Proof. Let 9: = (Vf(z)), Ft-
vi) and h; = f(x)) - f Lemma B.8 with ø = 111 and v
is followed by f(11)= fl (21+1) 2 9t n. Using Proposition E.8, we have
h2 - ha-1411 2
gt
min
9t
2
L
Ut 1
2/1 a 2/1 V (
9t
gt.
min
2
L
1
x²()²) min { (mi-2
2 -2110- x² x2112) 1-2/0 (ac)2/p
L 11 }
h4
||
2
{1- P) 1
1-2/p
(ac)21p
1 1- 2/P _1] hi,
1 min
where the third inequality holds from Lemma C.2 and [[V]())] 2 c. and the last inequality holds
because of the local quadratic growth property of f. The initial bound hi LD -2LD holds
from P S L and Equation E.5. For q 2, we have he- -hh11 2 P min {ac, hh, which implies
h441 I max (1 (11+
(1+))
1+ P
(1
ac
1
h4-
2
1
1 2L
Thus, we have the claim. For p > 2, we use Lemma C.11 with co = LD Fuce
Ci = 1 (1 2 (1-1)
R).
22 = (1- 1 1-2/p
2/2 and 0g = 1 - 2/p and obtain the claim.
L
Note that Assumption 3.1 with ø = b 1| and int dom á = R" holds when f is L-smooth over P. If p E I. does not hold, we can the initial bound hn < e+L D from Equation E.5. In that case, local linear rate in Theorem E.9 is unchanged. Moreover, we have local linear convergence without assuming [()]]
Theorem E.10 (Local linear convergence over uniformly convex sets without [[(() > 0). Sup- pose that Assumptions 3.1 and 5.1 with & = 11ll -12 and int dom Rh hold and that P is (a, -ununfoorlyy convex set. Let DEne = supa.SeP || yll be the diameter of P. Consider the - iterates of Algorithm 1 with 7t min [V)( -1 13 Then, if p < μ and p < L. it holds that
1
+ 1
LD
if < ( S lo. 2 2,
-
(1-0//))
1y = 0(1/p/(6-11) ift 2 to 2,
(1+(122)
32

---

Published as a conference paper at ICLR 2026
for all / 1 1 where
2in pор
and
L (11- p/1) P LC2 1/(x-1)
max
log (1+g))+))
+
LD Euc
Proof. Using an argument similar to Theorem E.9, we obtain
ge
he hot1 2
min
2
L L||2t
Vel 12
1- 2/p a 2/P
V f(x)
9t
9i
min
2
1-2/D a2 p2/
h1
|
x²1| x²1l2)
min
(tr-
G1
- x²112)
2
2
2
L
{1-
P. 1-2/p (ac
(ac=1)2/p
2 -
min
h2
1-1/p
1 -he.
L
where the third inequality holds from the PL. inequality Equation C.6 with = v2p Therefore,
1-2/p p=p
Lemma C.11 with co LD C 331 f.). c2 =c .0-111 (1-1) 0o 1/p and obtain the claim.
(ac-1)a7 1//0 and
F EXPERIMENTS
We use the following notation:
BregFW: the FW algorithm with the adaptive Bregman step-size strategy (Algorithm 2, our proposed)
BregAFW: the away-step FW algorithm with the adaptive Bregman step-size strategy (Al- gorithm 3 using Algorithm 2, i.e., Lt, V4, Yo + step_sizell o, Ft, U1 L,-1, m.xx), our proposed update)
EucFW: the FW algorithm with the adaptive (Euclidean) step-size strategy (Pedregosa et al., 2020)
EucAFW: the atay-step FW algorithm with the adaptive (Euclidean) step-size strategy (Pe- dregosa et al., 2020)
ShortFW: the FW algorithm with the (Euclidean) short step
ShortAFW: the away-step FW algorithm with the (Euclidean) short step
OpenFW: the FW algorithm with the open loop with 7, 2++
2
OpenAFW: the away-step FW algorithm with the open loop with % = 2+1
MD: the mirror descent (Nemirovskij & Yudin, 1983)
ProjGD: the projected gradient descent algorithm (see, e.g. Beck (2017))
F.1 NONNEGATIVE LINEAR INVERSE PROBLEMS
Given a nonnegative matrix A E RT RmXn and a nonnegative vector b E RT, the goal of nonnegative (Poisson) linear inverse problems is recover a signal E R such that Az b. This class of problems has been studied in image deblurring (Bertero et al., 2009) and positron emission tomogra- phy (Vardi et al., 1985) as well as optimization (Bauschke et al., 2017: Takahashi & Takeda, 2025). Since the dimension of x is often larger than the number of observations minate. From this point of view, we consider the constraint A, : fo R Σ3=1 Tソ $ 1). Recovering x can be formulated as a minimization problem:
the system is indeter-
min ZEAm
f(z) == d(Ax, b),
(F.I)
33

---

Published as a conference paper at ICLR 2026
BregFW
EucFW
10-
ShertFW OpenFW
10
Primal
MD
10.6
10a6
10
10
10
10"4
10-2
16
FW gap
10"
10
10
10
10
10
10-2
Iterations
Time
Figure Log-log plot of primal and FW gaps on nonnegative linear inverse problem for (m, (100, 1000).
Table 2:
Average values of the primal gap, the FW gap, and computational time (s) over 20 different instances of nonnegative linear inverse problems for (m, n) = (100, 1000). The results are reported as mean + standard deviation.
algorithm
primal gap
FW gap
time (s)
BregFW
6.9637e-08 + 2.0e-08
1.1455e-05 + 1.4e-06
1.4577e-01 + 4.1e-02
RucFW
3.0287e-07 + 9.4e-08
2.9223e-05 + 4.1e-06
1.0778e-01
5.8e-03
ShortFW
4.7470e-05 + 3.5e-06
4.6135e-04 + 7.2c-05
6.2518c-02 + 3.6e-03
OpenFW
4.9576e-07 + 6.3e-08
8.5382c-05
+ 1.3e-05
6,5036e-02
6.3e-03
MD
2.2494e-06 = 3.1e-07
1.7214e-04
+ 1.9e-05
1.8885e-01 + 6.4e-03
where d(x, y) = Σm (n; log Hi + yi -x;) is the KI. divergence. Problem Equation F. is Wi
convex, while Vf is not Lipschitz continuous on RT. The pair (f L-smad on RT with o(x)= 2y log Iy and maxisis> Em as from (Bauschke et al., 2017, Lemma 8).
We compared BregFW with EucFW, ShortFW, OpenFw, and the mirror descent algorithm (MD) (Nemirovskij & Yudin, 1983). The subproblem of MD can be solved in closed-form for (x RT ΣØ= 2i 1} by (Beck, 2017, Example 3.71), and this can readily extended to An. We used 1000 maximum iteration limit and we generated Á from an i.i.d. normal distri- bution and set Gij = |āsh Σm [āyl-- We also generated T from an i.i.d. uniform distribution in [0, 1] and set the ground truth x= = 0.87/ Ej= Iy so that x² E int An (random seed 1234). All components of the initial point vp were 1/n. For (m, n) (100, 1000), Figure 5 shows the primal v) per iteration (left) and the primal gap
gap f(x)) f and the FW gap max,e (V second (right). Table 2 shows the average values of the primal gap, the FW gap, and compu- tational time over 20 different instances for (m,n) (100, 1000). Here, BregFW outperformed other algorithms, both in iterations and time.
F.2 Ep LOSS PROBLEM
We use an l2 norm ball as a constraint, i.e., P fo R" EucFW, ShortFR. and OpenFW. We generated A from i..dd. normal distribution and normalized it so that ||a,]| = We also generated ø from an i.i.d. normal distribution and set x² 0.8ž | to ensure x² E int. P (random seed 1234). The initial point uo generated by computing extreme
||>|| < 1). We compared BreqFW with
34

---

Published as a conference paper at ICLR 2026
16
10
Primal
10-5
10-5
BregFW
EucFW
10"
ShortFW
10
10
OpenFW
10¹
10
10
10
10
101
10¹
Vil
FW
160
108
10a
10
10 10"4
10-2
Iterations
Time (s)
Figure 6: Log-log plot of primal and FW gaps on the Ep loss problem for (m,, = (1000, 100).
Table 3: Average values of the primal gap, FW gap, and computational time (s) over 20 different instances of lp loss problems for (m, n) (1000, 100). results are reported mean standard deviation.
algorithm
primal gap
FW gap
time (s)
BregEW
1.0589e-13 + 8.6e-15
3.7686e-01 8.6e-03
5.6037e-01 + 1.8e-02
EucFW 6.2980e-101 : 9.9c-11
8.5940c-01 = 1,0e-01
3.1421c-01 + 7.4c-03
ShortFW
2.4697e+01 1.2e+00
4.7621e+01
8.6e-01
9,2352e-02 3.7e-03
OpenFW
1.6961e-02 + 9.9e-04
4.0077e+00 = 1.0e-01
8.7292e-02
+ 3.5e-03
point of P that minimizes the linear approximation of f. For (n, m) = (100, 100) and = 1.1, Figure shows the primal gap (x,) and the FW gap pax, ( 24 e) per iteration and those gaps per second up to 1000 iterations. Table 3 also shows the average performance over 20 different instances. BregFW outperformed the other algorithms. Since V not Lipschitz continuous, ShortFW did not reduce the primal and FW gaps.
F.3 PHASE RETRIEVAL
We show the average performance for the setting of Section 6.2. Tables 4 and 5 show the average performance over 20 different instances of (m, n) (1000, 10000) and (m, n)) (2000, 10000), respectively.
We also compared BregAFW with EucAFW, ShortAFW, and OpenAFW. In only this setting, generated x" from an i.i.d. uniform distribution [0, 1] and did not normalize (random seed 1234); that is, x² might be in the face of P. Figure 7 shows another setting's 's results for (m, (200, 200) and K 110. Table 6 shows the average performance over 20 different instances for (m, (200, 200) and K 110. The primal gap by BregAFW is the smallest among these algorithms, while ShortAFW has the smallest value of the FW gap.
F.4 LOW-RANK MINIMIZATION
Given symmetric matrix M R goal is to find X E Raxr such that M ~ XXT. This is accomplished by minimizing the function
f(X) = |XXX -
1
min XEP
35

---

Published as a conference paper at ICLR 2026
10
16a5
BregAFW
EucAFW
ShortAFW
Primal
OpenAFW
10..0
10
10
10²
10
10
10a²
10
10²
FW gap
WDWtll
100
109
10
10
10a
10
10 Time
Iterations
Figure Log-log plot of primal and FW gaps on phase retrieval for (m, n) = (200, 200) and K 110 via AFW.
Table 4: Average values of the primal gap. FW gap, and computational time (s) over 20 different instances of phase retrieval for (m,n) n) (1000, 10000) and K 2000. The results are reported + standard deviation.
algorithm
primal gap
FW gap
time
BregFW 1.3107e-11
1.1c-12
2.1518c-02
5.9e-02
4. 1.6990e+01
1.5e+01
EucFW 1.7170e++00 + 3.9e+00
2.4612e+02 4.5e+02
4.4986e+01
+ 3.2e+01
ShortFW
3.2739e+05 1.9e+04
4.2232e+04
5.0e+02
1.0942e+01
+ 3.2e-001
OpenEW
5.2496c-10 3.9e-11
4.3802c+00 = 5.5e-02
6.0353e+01 = -16c+00
Table 5: Average values of the primal gap, FW gap, and computational time (s) over 20 different instances of
phase retrieval for (m, n (2000, 10000) and 2000. The results are reported as mean +
standard deviation.
algorithm
primal gap
FW gap
time
BregEW
9.5656e-08
7.9e-09
7.2592e+01 8.8e+00
EucFW 3.2499c+000 + 7.1e000
3.1344++02 = 4.8e+02
1.4348e+02 = 4.3e+01
Short
6.0937e+04 +: 2.3e+03
2.546le+04
2.3e+02
1.2648e+01
+: 2.4e-01
OpenFW 9.3513e-11 4.9e-12
2.6628e+00 1.7e-02
7.1916e401 + 1.3e+00
Table Average values of the primal gap. gap, and computational time (s) over different instances
phase retrieval for nm) = (200, 200) and K 110 via away-step FW algorithms. The results are reported as mean + standard deviation.
algorithm
primal gap
FW gap
time (s)
BregAFW
4.3430e+00 +: 1.7e+00
9.7578c-01 + 9e1e-0
2.3336c-01 + 6.4e-02
EucAFW
4.3968e+00 + 1.7e+00
+ 1.2212e+00+ 2.3e+00
3.9421e-01 + 1.6e-01
ShortAFW
4,4092e+00 + 1.7e+00
2.5978e-02 + 7.3e-03
7.3540e-02 + 3.5e-02
CpendFA
4.4094e+00 + 1.7e+00
7.1992e-02 4.9e-02
5.8998e-02 + 2.4e-03
where P Ber We assume that < This problem is known low-rank minimiza- tion (Dragomir et al., 2021). In this paper, we define P {X e R"xr ||||| S {), where ||- ||. denotes the nuclear norm and RR for the low-rank assumption.
36

---

Published as a conference paper at ICLR 2026
BregFW
EucFW
ShortFw OpenFW
Primal
10º
10º
10
169
10
10º
10
10-2
10
FW gap
10
10
10
10
10a
10
10
10
10
Iterations
Time (s)
Figure 8: Log-log plot of primal and FW gaps on low-rank minimization for (n,,7 = (1000,20).
Table 7: Average values of the primal gap, FW gap, and computational time (s) over 20 different instances of low-rank minimization for (n.r) (1000, 20). The results reported mean + standard deviation.
algorithm
primal gap
FW gap
time (s)
BregFW
5.6519e-01 4.2e-02
1.4727e+01
1.0e+00
1.2602e+01 4.5e-01
EucFW 5.7765e-01 + 4.6e-02
1.7237e+01
+ 2.0e+00
1.2280e+01 + 3.8
ShortFW 2.7101e+08 1.9e+06
2.1694e+09
1.5e+07
4.1379e+00 7.9e-02
OpenFW
1.9782c+00 + 3.6e-01
2.1212c+03
3.le+02
4.1770c+00 = 1.7c-01
We define
6(X) | 111
There exists a constant L such that the pair (f, Φ) is L-smad on R (Dragomir et al., 2021). Addi- tionally, f(X) is weakly convex any compact due to Proposition C.1, which follows from the twice continuous differentiability f.
We also compared BregFW with EucFW, ShortFW, and OpenFW. The parameter settings the same as those in the previous subsection. We generated X from an i.i.d. uniform distribution in [0, 1], normalized each column of X and M X* **(X+)T (random seed 42). The initial point Xo was generated from an i.i.d. uniform distribution in [0, 1]. We set & = 10Amax (M) for P. Figure shows the primal and FW gaps per iteration and gaps per second for (n,r) (1000, 20) up to the 1000th iteration. Table 7 presents the average performance over 20 different instances for (n,r) (1000, 20). BregEW performed slightly better than EucFw. OpenFW also performed as fast as BregEW and EucFW, but its performance was unstable. ShortF# did not converge due to the lack of Lipschitz continuity of V..
F.5 NONNEGATIVE MATRIX FACTORIZATION
Given a nonnegative matrix V E R nonnegative matrix factorization (NMF) aims to find nonnegative matrices W I and H E R such that V = WH. NMF can be formu- lated as a minimization problem of the loss function that measures the difference between V and W H, ie., min fWW = [[ VI? where P is compact convex subset of Rmxr Brxn The objective function is weakly convex P due to Proposition C.I. The
37

---

Published as a conference paper at ICLR 2026
10/
10
12
14
10
104
167
Time kd
Figure 10: Log-log plot of the primal and the FW gaps on NMF MovieLens 100K Dataset.
Figure Log-log plot of the primal and FW gaps on NMF for (m, n., r) = (100, 5000, 20).
Table 8: Average values of the primal gap, FW gap, and computational time (s) over 20 different instances of NMF for (,, (100, 5000, 20). The results are reported mean + standard deviation.
algorithm
primal gap
FW gap
time (s)
BregFW
1.2017e-04 + 5.7e-06 EucFW 1.2819c-04 4.6e-06
1.1515e-02 + 1.4e-02 5,0983e+01 + 1.1c+00
7.6259e-04 + 8.0e-04
4.3592c+01 + 1.0c+00
gradient Vf is not Lipschitz continuous, while (f. is smooth adaptable (Mukkamala & Ochs, 2019) with @(W, H) ] [[] | (1I + 1
We used a box constraint We compared BregFW with EucFW because ShortFW and OpenFW stopped at the 2nd iteration. We generated W* from an i.i.d. uniform distribution [0, 1] and normalized each column of W* (random seed 42). We also generated H from i.i.d. Dirichlet distribution. The initial point (Wo, Ho) was generated from an i..d. uniform distribution in [0, 1). Figure 9 shows the primal and FW gaps for (m, n, r) (100, 5000, 20) up to the 5000th iteration. Table shows the average performance over 20 different instances for (m, n, r) (100, 5000, 20) up to the 5000th iteration.
{(W, H) E Rmxr x R S Wi; S 3,0 Hi S 1}.
BregFW is slightly better than EucFW in terms of the primal gap, while the FW gap for EucFW is smaller than that for BregFW.
Furthermore, consider walld data using the MovieLens 100K Dataset. We set P ((W, H) E Raxr x Rx S Wy < 5.0, H|| S } For &(W, H) = 3 ([ + | IIV 11 + ( by (Mukkamala Ochs, 2019, Proposition 2.1). (f. is also L-smooth adaptable. Figure 10 shows the primal and FW gaps up to the 1000th iteration with Ç = 10 (VVT), where A.ax(.) is the largest eigenvalue. The primal gap of BregFW is 6.041269c005. and that of EucFW 6.041272c+05. this setting, the primal and FW gaps of BregEW are slightly better than those of EucEW.
2
38


Reviews:
[{"review_id": "fSjW6KQcVw", "reviewer": "Reviewer_BkRp", "summary": "The paper studies Frank-Wolfe algorithm under relatively smooth and (weakly-) convex assumptions. The authors proposes new stepsizes that utilize Bregman distance, which generalizes standard Euclidian setting. The paper derive convergence guarantees: sublinear and local linear rates under weaker assumptions than classical Lipschitz‐gradient smoothness and strong convexity, and demonstrate experimentally that their methods outperform existing FW algorithms.", "questions": "1. How sensitive is the performance of the adaptive Bregman step‐size strategy (Algorithm 2) to the parameters $\\beta, \\tau$,  (which control the inner loop for estimating $M$ and $\\kappa$)? Do the authors provide guidelines on tuning those for new problems?\n2. What is a complexity of Procedure step_size in Algorithm2?\n3. Do short step-sizes perform better than adaptive step-sizes on numerical experiments?\n4. In the nonconvex (weakly convex) setting, the local linear convergence assumes a local $\\mu$-quadratic growth condition. Practically, how can one check or ensure this condition holds in a given application? Also, given that there is a linear local convergence of the method, how one can identify when the algorithm reach this local neighborhood?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper extends the analysis of FW‐type methods to the class of (L-smad) functions and weakly convex objectives. These results are new and correct.\n2. The proposed Adaptive Bregman step-size strategy automatically adapts to L-smad constant, which does not require extensive hyper-parameter search or estimation of $L$.\n3. The paper shows not only global sublinear convergence but also local linear convergence in the convex case under a Hölder error-bound condition (HEB) and in the nonconvex case under a local quadratic growth condition. This gives stronger theoretical guarantees than many prior FW analyses.", "weaknesses": "1. Weak-convexity, quadratic growth and HEB assumptions while being more general then previous assumption, still are strong. Under these assumptions, linear convergence rate is not surprising.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qyA77AGjcV", "reviewer": "Reviewer_2nKH", "summary": "This work proposed a Frank-Wolfe algorithm for constrained optimization whose objective function is convex/weakly-convex and relatively smooth, the algorithm is further equipped with adaptive Bregman stepsize and away-step specifically for polytope cases. Convergence rates are provided both convex and weakly convex cases. Numerical experiments are complemented to verify the effectiveness of the proposed algorithms.", "questions": "See above", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Extend the scope beyond convex and L-smooth, which is more general and fit more practical problems.\n2. The stepsize is adaptive and \"drop-in\", which is easy to use.\n3. The writing is clear, the flow of the work is easy to follow.", "weaknesses": "1. Even though extending into nonconvexity, the results still require some strong conditions like HEB, such conditions are still a bit strong, and lacks nontrivial examples throughout the work to verify the effectiveness.\n2. The work seems to be a combination of FW with Bregman divergence, also many existing works on EB/QG conditions and relative smoothness, the novelty in terms of techniques may be limited a bit.\n3. Line 304, \"We will now establish faster convergence rates than O(1/t) up to linear convergence depending on the choice of parameters.\", but I may argue that the acceleration comes from the problem setting (additional EB condition compared to the vanilla convex setting), rather than your parameter setting.\n4. For the nonconvex part, Theorem 5.2 and 5.3 further require $\\rho<\\mu$, which has not been verified, it would be helpful to include discussion or examples illustrating when this inequality holds, or how one might estimate these quantities in practice. This would clarify the scope of applicability of the nonconvex guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7UmMcOmBxr", "reviewer": "Reviewer_gC98", "summary": "This paper proposes a Frank–Wolfe (FW) algorithm with an adaptive Bregman step-size strategy. The proposed algorithm covers relatively smooth and weakly convex setups, which are broader than the conventional $L$-smooth convex setup. It achieves local linear convergence under weak convexity and the local quadratic growth condition. Moreover, when the constraint set is a polytope, the paper proposes a variant of the away-step FW algorithm that overcomes the zigzagging issue of the classical FW algorithm. The latter algorithm also achieves local linear convergence under the aforementioned assumptions. While the convergence is local in the nonconvex case, both algorithms achieve global linear convergence when the objective function is convex and satisfies the Hölder error bound condition. Finally, the paper provides numerical experiments demonstrating its efficiency.", "questions": "- **Q1.** Could the authors elaborate on any novel proof techniques or specific technical challenges they had to overcome while establishing the results, particularly those related to the extension of the setup?\n\n- **Q2.** There exists a line of research that develops parameter-free methods without employing line search in other setups [1–5]. Do the authors anticipate particular challenges in removing the line search component from the proposed framework? If so, could they elaborate on the underlying reasons? (The reviewer thinks that this question may be out of the scope of this paper and is mainly motivated by the reviewer’s interest in hearing the authors’ intuition.)\n\n\n[1] Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. International Conference on Machine Learning, 2020.\n\n[2] Yura Malitsky and Konstantin Mishchenko. Adaptive proximal gradient method for convex optimization. Neural Information Processing Systems, 2024.\n\n[3] Puya Latafat, Andreas Themelis, Lorenzo Stella, and Panagiotis Patrinos. Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient. Mathematical Programming, 2024.\n\n[4] Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex optimization. Mathematical Programming, 2025.\n\n[5] Danqing Zhou, Shiqian Ma, and Junfeng Yang. AdaBB: Adaptive Barzilai-Borwein method for convex optimization. Mathematics of Operations Research, 2025.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- To the best of this reviewer's understanding, the γ-update in line 5 of Algorithm 2 and line 8 of Algorithm 3, which is motivated by equation (2.2), is a novel aspect of the proposed algorithm. It seems that this idea enables the proposed algorithms to establish convergence guarantees for the considered broad setup, and the fact that the paper indeed provides corresponding convergence results is meaningful. The paper also presents convincing experimental results.\n- The considered setup, L-smooth adaptable (i.e., both Lφ − f and Lφ + f are convex on the constraint set C), indeed appears to be an extension of the conventional setup, as mentioned in the paper.\n- The paper seems to be overall well structured.", "weaknesses": "- **W1.** While this reviewer believes that the results are meaningful and worth the effort, the reviewer is not fully convinced of the overall technical novelty. In short, to the best of the reviewer’s understanding, this paper leverages line search to develop an adaptive step size, which is arguably a classical technique in optimization. The reviewer is curious whether there were any new challenges the authors needed to overcome to handle this setup. The reviewer would be happy to be corrected if something has been overlooked, as noted in the related question Q1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BiNVCmqX78", "reviewer": "Reviewer_4P4Y", "summary": "This paper proposes new Frank–Wolfe (FW) algorithms that incorporate a Bregman-based adaptive step-size rule, removing the need for Lipschitz continuity of the gradient of the objective function. The authors extend FW to L-smooth adaptable functions, broadening applicability beyond standard L-smooth settings. They achieve sublinear to linear convergence rates under weaker conditions (e.g., Hölder error bound or local quadratic growth). This submission also provide both convex and weakly convex convergence analyses and an away-step variant for polytopes with provable linear rates. The paper include numerical validation on ℓp-loss and phase retrieval problems, showing empirical improvements over classical FW and its variants. In summary, it generalizes FW theory to handle non-Lipschitz and weakly convex objectives while retaining theoretical rigor and empirical competitiveness.", "questions": "There are no other questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This submission has significant theoretical generalization. The relaxation from Lipschitz smoothness to relative smoothness is well motivated and aligns FW with modern Bregman-based optimization. It unifies and extends several prior frameworks, offering linear convergence under weaker assumptions.\n\nThe authors provide rigorous analysis. The theoretical sections in this submission are mathematically precise, covering: convex and weakly convex settings, both FW and away-step variants, and multiple growth conditions (HEB, quadratic growth). The mathematical proofs appear comprehensive and grounded in established geometric constants (pyramidal width, etc.). The authors also provided the adaptive Bregman step size. This adaptive scheme is elegant by extending previous results  and self-tunes both L and ν parameters. The termination proof (Remark 3.2) ensures practicality. \n\nMoreover, the authors conduct numerical experiments and the empirical results are consistent with the theoretical analysis. The Experiments on non-Lipschitz settings convincingly show faster convergence and robustness where Euclidean FW fails.", "weaknesses": "There are no major weakness about this submission. The following is just some minor weaknesses:\n\nThe authors should add more numerical experiments. Only two primary experiments are shown (ℓp loss and phase retrieval). While results are positive, including comparisons on structured convex problems (e.g., LASSO, matrix completion) would better demonstrate generality.\n\nThis submission need more clarifications. Definitions (e.g., L-smad, kernel generating distances) are presented quickly with minimal intuition. Some long theorems could be summarized qualitatively before stating full formulas. Adding geometric or schematic illustrations (e.g., showing Bregman vs. Euclidean geometry) would enhance readability.\n\nThe authors should add more discussion of related work. The paper references many FW variants, but comparison to mirror descent or relative smoothness-based proximal algorithms is somewhat limited. Highlighting differences in oracle requirements and computational cost would clarify its niche.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2AgIrdWTns", "reviewer": "Reviewer_229D", "summary": "This paper proposed Frank-Wolfe (FW) algorithms with adaptive Bregman step-size strategies for a class of constrained optimization problems. The objective function satisfies the smooth adaptable property with respect to some Bregman distance function and the $q$-Holder error bound condition. For convex optimization, the proposed FW algorithms achieves global linear or sublinear convergence. For weakly-convex optimization, the proposed algorithms achieves global linear or sublinear convergence if the objective function satisfies the quadratic growth condition.", "questions": "- The global linear convergence rates of the proposed algorithms only holds for specific classes of functions: $q=2$ or $q= 1+ \\nu$ or $\\nu = 1$ or for initial iterates. Though the footnotes give explanation, the presented results in Table 1 may be misleading at the first glance. I suggest to add more description in the table.\n\n\n- Theorem 5.2 requires $\\rho < \\mu$ and Theorem 5.2 requires $\\rho < \\mu \\leq L$. These assumptions seem nontrivial.  \n\n(i) It is nice to see that Example D.4 satisfy the assumption.Is there a general class of functions satisfying the assumption? \n\n(ii) $\\rho, \\mu$ and $L$ characterize the convexity of $f$ to some extent: $\\rho$ is basically the $\\rho$-smad parameter when $\\phi$ is the quadratic function (typical Euclidean distance). $\\mu$ is requiring the strong convexity over the solution set, which is related to the star-convexity. Is there relation between $\\rho, \\mu$ and $L$? For example, would some property of $\\phi$ guarantee that $\\rho \\leq L$? Inituitive discussions are also welcome. \n\n- Typo: Line 223, 'right-hand size'", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-motivated, organized and well-written.\n\n- The proposed algorithm is parameter-free (with adaptive strategy for parameters) and provides global convergence guarantees under convex and nonconvex scenarios.", "weaknesses": "See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)