Beyond Short Steps in Frank-Wolfe Algorithms
Authors: David Martínez-Rubio
Sebastian Pokutta
Venue: ICLR 2026 Poster (2026)
Keywords: Frank-Wolfe algorithm
optimism
primal-dual algorithms
Primary area: optimization

Abstract: We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank-Wolfe algorithms with step sizes that incorporate primal-dual guarantees, offering practical stopping criteria. We present a new Frank-Wolfe algorithm utilizing an optimistic framework and provide a primal-dual convergence proof. Additionally, we propose a generalized short-step strategy aimed at optimizing a computable primal-dual gap. Interestingly, this new generalized short-step strategy is also applicable to gradient descent algorithms beyond Frank-Wolfe methods. Empirical results demonstrate that our optimistic algorithm outperforms existing methods, highlighting its practical advantages.

Published as a conference paper at ICLR 2026
BEYOND SHORT STEPS IN BRANK-WOLDE ALGORITHMS
David Martinez-Rubio
Sebastian Pokutta
IMDEA Software Institute, Madrid, Spain
Zuse Institute Berlin and Technische Universität Berlin, Berlin, Germany pokutta azib.dd.
david devid.marree nez rubio@ imdea. org
ABSTRACT
We introduce novel techniques to enhance Frank- Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank- Wolfe algorithms with step sizes that incorporate primal-dual guarantees, offering practical stopping criteria. We present new Frank-Woon algorithm utilizing an optimistic framework and provide primal-dual convergence proof. Additionally, we propose a generalized short-step strategy aimed at optimizing a computable primal-dual gap. Interestingly, this new generalized short-step strategy is also applicable to gradient descent algorithms beyond Frank-Wolfs methods. Empirical results demonstrate that our optimistic algorithm outperforms existing methods, highlighting its practical advantages.
INTRODUCTION
We are interested in solving the following optimization problem:
min [(x),
where X' is a compact convex set and f is a convex and L-smooth function. The Frank- Wolfe (FW) algorithm (Frank & Wolfe, 1956), also known as the conditional gradient algorithm (Levitin & Polyak, 1966), is a key algorithm for this problem class, particularly for problems where projection onto constraint set is computationally expensive, as it does not require projections. It leverages linear minimization oracle (LMO) for X, which upon presentation with linear function e returns arg min (c, v), and gradient oracle for f. which given point E dom(f) returns ff(x). Given its low cost per iteration it is often highly effective in various machine learning applications. These include optimal transport (Luise al., 2019), neural network pruning (Ye et al., 2020), adversarial attacks (Chen et al., 2020), non-negative matrix factorization (Nguyen et al., 2022), particle filtering (Lacoste-Julien al., 2015), and distributed learning (Bellet al., 2015), among others.
more general version of the Frank Foafk-Wolfe algorithm handle the optimization of f(x) (ar) for a convex function th. In this case however, we require access to a gradient oracle for f and an oracle that can solve arg min,, [(w, v) + (1())} for any w Rd, as discussed in (Nesterov, 2018). We recover the classical FW algorithm by choosing (x) as the indicator function of the set X.
In this work, we will focus on primal-dual analyses for FW algorithms. In contrast classical analyses where a step-size strategy and corresponding convergence rate need to be heuristically estimated and then proven by induction, in the primal-dual setup they emerge as a natural consequence of the analysis. This approach does not only provide tighter dual gaps and hence stopping criteria but also enhances the convergence properties of the algorithm. In particular, rather than considering primal progress without clear indication how good the solution is, primal-dual progress refers to the reduction in the primal-dual gap, which is a measure of how close the current solution is to optimality; this will be our measure here. A well-known strategy for FW algorithms is the so-called short step, which essentially chooses the step size to maximize primal guaranteed progress from the descent lemma, see (Frank& & Wolfe, 1956)); and also (Braun et al., 2022) for in-depth discussion.
We introduce the concept of primal-dual short steps, that maximize primal-dual guaranteed progress based a model obtained from the primal-dual analysis. We also show that this new step-size

---

Published as a conference paper at ICLR 2026
strategy is also applicable to gradient descent algorithms. Moreover, recent advancements have introduced adaptive step-size strategies, such as, e.g.. (Pedregosa et al., 2020) (see also (Pokutta, 2024) for numerically improved version), which further refine the stert-step. These strategies aim to decrease a model of the function adaptively, enhancing the algorithm's 's performance and stability and in particular allow for leveraging local curvature information. However, they come at the extra cost of a line search like procedure and are subject to the same lower bounds as the classical short steps (Guélat Marcotte, 1986).
MAIN CONTRIBUTIONS
Optimistic Frank- Wolfe Algorithm We introduce a novel Woole method that leverages the concept of optimism (Rakhlin & Sridharan, 2013; Steinhardt & Liang, 2014). This algorithm is designed to adapt effectively to varying conditions and provides a robust analysis of the convergence rate associated with primal-dual gap.
Primal-Dual Short Steps We propose a new class of step-size rules for existing Frank- Wolfe algorithms, termed primal-dual short steps. These steps are based on the sequential minimization of primal-dual gap defined in the algorithm's 's analysis. This approach is flexible and extends to gradient descent algorithms, allowing for line search over the primal-dual gap in both algorithm classes.
Numerical Experiments We conduct numerical experiments that showcase the practical advan- tages of the proposed optimistic Frank- Wolfe algorithm. In our tests, the results consistently show the effectiveness of this new variant in minimizing the primal-dual gap more efficiently than tradi- tional methods. In particular, in most experiments the empirical order of convergence is better, as demonstrated by the steeper slope in a log plot.
Additionally, we have obtained primal-dual analyses for algorithms and results where so far only classical primal convergence analysis where available, often improving constants and providing effective stopping criteria for these algorithms. These findings are detailed in Appendix E.
RELATED WORK
The Frank-Wolf algorithm, introduced by Frank & Wolfe (1956) where also short steps were intro- duced, is foundational method projection-free optimization, particularly for problems involving convex constraints. Levitin & Polyak (1966) further extended the method, which they referred to as conditional gradient algorithm. A significant advancement for the Frank Wolfe algorithm was made by Jaggi (2013), who introduced the FW gap and provided convergence guarantees this measure, marking the first instance of FW guarantees for a primal-dual gap.
The development of primal-duel dual methods for conditional gradient algorithms has been explored in works such as Nesterov (201 8) and Diakonikolas & Orecchia (2019), which have contributed to the broader understanding of these algorithms. Additionally, Abernethy & Wang (2017) described Frank- Wolfe variant that incorporates cumulative gradients, albeit with equal weights, resulting in an additional logarithmic factor complexity.
Several methods apply the LMO at convex combination of previously obtained directions. In particular, variants of the Frank-Wolfe algorithm have been developed by Mokhtari et al. (2020), Lu & Freund (2021), and Négiar et al. (2020) using stochastic gradients. Notably, the analysis of Lu Freund (2021) reduces to the optimal rate the deterministic case, up constant factors. Wang et al. (2024) also presented cumulative-gradee Further contributions include the work Li (2021), who provided a primal-dual analysis the deterministic algorithm, heavy-ball Frank-Woll (HB-FW), using convex combination of gradients.
FW algorithm, with additional logarithmic factors.
In the context of online learning, the concept of optimism, which involves using hints such as past losses to predict future losses, originated in (Azoury & Warmuth, 2001; Chiang et al., 2012; Rakhlin & Sridharam, 2013). This idea had already been developed in saddle point optimization, as seen in the work of Popov (1980). A duality was found and further explored between mirror descent and Frank- Wolfe algorithms by Bach (2015) and Peña (2019). Wang et al. (2024) and Gutman & Peña (2023) have also shown that FW and mirror descent, among other methods, can be unified under
2

---

Published as a conference paper at ICLR 2026
common framework. In this work, generalize anytime ouline-to-bated conversion (Nesterov & Shikhman, 2015; Cutkosky, 2019) for connecting FW algorithms with online learning ones.
Works that have studied modifications of the gradients to obtain faster convergence of FW algorithms and linking them back to gradient descent methods and gradient mappings include Combettes & Pokutta (2020); Mortagy al. (2020) and in Diakonikolas al. (2020) local acceleration in the Nesterov sense has been demonstrated for FW algorithms for strongly convex functions while whether local acceleration possible for non-strongly convex but smooth functions remains an open question.
PRELIMINARIES AND GROUNDWORK
In this section, we introduce the necessary notation and an overview of some FW algorithms. In the following let X' be compact convex set with diameter D. Further, let f X be a differentiable function defined on an open set containing X. We assume that / is convex and L-smooth on X' with respect norm -| This means that for all 2, y X, the following inequality holds:
5 f(y) - f(x)(( (V)()))v)))) x) S 2
yl1?.
These two conditions imply f has an L-Lipschitz gradient f[v - vf(Uill S L||e - yll. where || ||+ denotes the dual norm.
If not stated otherwise let x² E arg min f(z) ) be a minimizer of f over X. Further, let Lx(x) be the indicator function of the set X' that if x E X' and +o0 otherwise, and let 1B be the event indicator function that 1 the event B holds and otherwise. We denote [T] def (1, 21....... .T. We denote by (=)( the subdifferential of no at x so that y E 0v((x), we have (vv) 2 ((x) + (0. x))
We provide now a sketch of the proof structure for some primal-dual analysis of FW well as HB-FW and other methods, and in Appendix B we provide full details of this overview. With respect to (Li et al., 2021), we provide a slightly more general analysis of HB-FW by allowing for a composite term and we provide an analysis of FW when decreasing regularization is used. We start by defining a lower bound Le on the optimal value that we have access to at time t, and for iterates It, 2 1, we define primal-dual gap as
G2 f(x+11) Lt
(1)
where (x(411 is one step ahead of the lower bound, which is a subtle shift that differs slightly from get very simple primal-dual analyses of and convergence results for
known analysis and allows the new and old algorithms we present in this work. In the sequel, if not stated otherwise, let a₃ > 0 to be determined later and define A, = Ar-1 + a₂ Et we use the following lower bounds, or rather, the choice of lower bound defines the iterate et of the algorithm:
O ag. For instance, for FW and HB-FW
A.f(x')
Σ (x) +
Σ ar a ((()), -xe)
t=0
Σ
arl + min
de (F())(())) v -- -xe) - A.L
HB
(2)
VE
t=0
(=0
Σ arf((e) + Σ t=
ag min vExt
(in w- vz) der A.L FW
Σ E=0
(rs())))
aeg(or).
2=0
where the term above g(xe) max,ex (Vf(x)) - u) (2 f(xz) - f(x)) is the so-called FW
gap, which is also primal dual gap, the best of which for l E [t] was shown to converge by Jaggi
(2013) at a O O<4") rate for FW. Above I holds by convexity. 2 takes a min. This expression is
A times the lower bound L in HB-FW is and its arg min corresponds to the iterate v, of HB-FW, cf. Algorithm 1, whereas after 3 we have A, times the lower bound L used in the FW algorithm and the arg min of the E-th summand is the iterate v, of FW, ef. Algorithm 1.
3

---

Published as a conference paper at ICLR 2026
Algorithm 1 Frank-Wolf and Heavy-Ball FW algorithms
Input: Function f. feasible X, initial point zo. Weights az Tt-
do 2: Choose either (HB-FW) or (FW) for the entire run:
for t
3: Ut f arg min D a, (V(()))))
"EX
4: Vi arg min ( (V)(2)),
5: I++1 < 7/) J 7/2
6: end for
If we now show bound
A,G, AL-1 Eg for all / 1.220 0,
then we have f(r(+1) f(x)) S G. Ei Eg.. Our aim thus have small E, and large At. Note A-1 by definition. If f is L-smooth with respect ||- and D def max, wex / || y/I, then choosing = 2t 2, Yt = a,/A, one can show that both FW and HB-FW in Algorithm satisfy (3) with E, = 1.12aa and consequently G, S 2LD cf. Appendix B. The term f( - f(x))
2.A
t+2
cannot be computed in general since we usually do not have access to the value f(x*). However, the primal-dual bound G; computable and thus it can be used as stopping criterion.
Remark 2.1 (Altemattve step-size strategies). The analysis uses the guaranteed primal progress, that A.
is, the descent that is guaranteed on o f(1++1) - fxxe,, in particular with the choice "tt = 3t = 2 by using the upper bound that the smoothness inequality provides. Any step size strategy whose whoseprimal progress is greater than this guaranteed progress yields better convergence rale. For instance, the so-called short step-size strategy, maximizes this guaranteed progress along the segment joining xt. and ut. Indeed the best lower bound f(x)) (z1+11 given by smoothness is
742
7(f(z)), - v1) + +2² 2 vel
max (E(0,1]
2
And the arg max is = min performing a line search over the segment joining 2, and vt. Even if the line search is performed with error iteration t, this error only contributes additively to the corresponding Et, and so its global impact can be easily quantified.
(
21 (1 which the short step-size. Another alternative is
Although short steps induce monotonic primal progress by definition, they do not necessarily induce monotonic primal-dual progress, which is the important measure to look at when we require stopping criterion. To remedy this, in Section 4 we introduce a new primal-dual short step strategy that induces monotonic primal-dual progress.
On the other hand all of previous FW approaches exploit smoothness of f the same way: quadratic upper bound on the function is computed and the yielded guaranteed progress is used to compensate from some other errors in the analysis. In Section 3, we introduce framework that goes beyond this by making use of optimism. The algorithm has the potential of better adapt to the environment, as we show in the experiments section, where Optimisitic Frank- Wolfe performs better than other approaches.
AN OPTIMISTIC BRANK-WOLFE ALGORITHM
In this section, we propose a new Folfe method that at each iteration, uses prediction of the next gradient in order to minimize suitable regularized lower model of the objective. The more accurate this prediction is, the better the resulting convergence rate. For functions with Lipschitz continuous gradients, the previous gradient serves as a sufficiently accurate predictor for the next one. We sketch the main ideas of our new algorithm and provide all details in Appendix C.
The algorithm and analysis is based on optimistic versions of the Online Mirror Descent (OMD) algo- rithm and of the Follow the Regularized Leader (FTRL) algorithm. We provide slight generalization over these online learning algorithms in order to allow for con-differentiable regularizers, in order to cover typical cases where Frank- Frank-Wolfe is applied. To that effect, make use of the following
4

---

Published as a conference paper at ICLR 2026
Bregman divergence definition, that specifies subgradient of á of the regularizer for its definition: (1 y, @) del (z) (vy) (ó, x - v), where & E (y) Note that in the pseudocode of Algo- rithm 2 we write De (v. 0r E (b(()-1) to mean that the algorithm can use D (v. 1 0t) for any Φe (v)(v)1).
Online learning algorithms typically use regularizers & that are strongly convex or enjoy any other curvature property such as uniform convexity, in order to obtain a low enough regret. Even though we do not assume strong convexity any other curvature property of the regularizer yb (in fact, to can be 0 in the feasible set), we show that we can apply an optimistic approach that leads to the optimal convergence rate in this setting, and we show in Section 5 that our algorithm empirically outperforms other approaches.
The starting point of the method, in (2), is defining lower bound on the optimal value, which do by taking inspiration on the anytime online-to seaee-to-bbll to-batch conversion of Cutkosky (2019), that connects the regret of online learning algorithms with convergence guarantees of optimization methods. This naturally leads to the definition I; 1 Ei= a A, Ut + Ac A--xx,1 A,
At -1 for all 2 1 in Algorithm 2. We are also able show that at each iteration, the theory allows for making use of point y with lower function value than the previous ft-1- in place of using #t-1, and we show that this does not hurt the convergence guarantee, so allows for heuristics like performing line search over the segment z;-1 and Ut. or other future heuristics that may be built on top of this algorithm. The definition of 1n comes from the optimistic online learning algorithmic schemes.
In similar fashion to the one in (1), using said lower bound we define primal-dual gap that we denote G. for both variants of the algorithm, cf. Appendix C.2. We provide guarantees on this primal-dual gap by the regret of the optimistic procedure, gradient Lipschitzness of the function, along with the loss weighting and compactness of the domain.
We use an optimistic FTRL, algorithm (Algorithm 2) or optimistic MD algorithm (Algorithm 2) with constant step size, designed to work for subdifferentiable losses. Interestingly, while it is well-known that for constant step size and unconstrained problems, FTRL and OMD have the same updates, we note the more general property that in the constrained setting, FTRL is an instance of OMD with subdifferentiable regularizers for a precise choice of subgradients, cf. Remark C.5.
Algorithm 2 Optimistic Frank-Wolfe algorithms
Input: Convex subdifferentiable regularizer v such that arg min, (wc .) (xx) exists for all W E Rd. A convex function f. differentiable and L-smooth with respect to a norm || in dom(1)) Initial point zu vo E dom(v)). Unbiased stochastic gradient oracle D(x) with finite variance a².
1: An 0; 0g <- g0 0; 9n = (20o)
2: for + 1 to T do
3: 0: 21: A, + A 1 a Ei=1 a; = +(t+1)
4: o Choose either 5 or for the entire run, for o, ((
5:
point in arg min (E (((0+111)) + ael v) + (v)}
6:
Tt + point in arg min ( (9t-t-19 tar d) + (1, (1-1: 01)}
7:
Vt-1 Z1-1
o Also valid: Vt-1 f- point such that f(1-11) S f((-11 (in det. algs.)
8: Dt +
A
A. yt-1 + 2
that is, Fe + 1--1 + 2
9: 91+1 + (xx))
10: end for
11: return 2T-
One subtlety of GOP is that it is not directly computable as is, since the direction we apply the LMO depends on the hint that we choose, that is, prediction for the next gradient. We can compute simple close bound of it at every iteration, or if we want to compute it after certain number of iterations, we can do it by performing an extra LMO, ef. Remark C.6. The guarantee we obtain on the algorithm is the following. We allow for stochastic oracle that computes an unbiased estimate of the gradient with the finite variance assumptions E[]lO(z) fx())]]] < o². The deterministic result corresponds to a 0.
Theorem 3.1. [ Let X be compact and convex, and let vb X - R be a closed convex function, subdifierentiable in X. Let f be convex and L-smooth in the set X' of diameter D) with respect to
5

---

Published as a conference paper at ICLR 2026
norm || that access via unbiased stochastic gradient oracle (xx) with finite variance の² 2 0. The iterates 2, of Algorithm satisfy:
- [(x))( E[GPP) 1xx²) ((11))
4LD²
V20D
t(t ([++1)
++1
for the variant in Line 5. For the variant in Line we obtain the same except that xb(x²) ) 2/1 is substituted by D (2* 2o; 60). where du @v)(
We note that the term involving v is just consequence of our choice of step sizes, which used for simplicity. It possible to keep the O 7+1 rate and have an arbitrarily fast polinomial-ons decay on the term involving vi by making different choice of step sizes, see Appendix C.2.
4 PRIMAL-DUAL SHORT STEPS
A key step of the analysis in most Frank- Wolfe algorithms for smooth problems, such as in Section 2, consists of using the smoothness inequality order to guarantee some descent that compensates other per-iteration eπrоrs that appear. Several step-size rules have been devised, that may change depending on the specific setting. However, three families of step sizes stand out in almost every setting, which correspond to the ones we discussed in Section 2: (A) open-loop step-sizes, that only depend on the iteration count, (B) short steps, that minimize the upper bound given by the last computed gradient V (xz)) and the smoothness inequality with respect to some norm, along the segment in between the current point 2; and the computed Frank- Wolfe vertex Ur E arg max,ex { (z)) v) and (C) line search in the aforementioned segment to maximize primal progress.
In the sequel, we devise a new class of step sizes, which are a generalization (B). The idea of (B) is to greedily maximize the guaranteed primal progress along the segment in between Fy and tt where we know we are feasible. The key idea of our new step-size rule consists of taking the primal-dual gap (1) that is defined for the analyses with the structure of (3), and choosing the step size in order to maximize the guaranteed progress in terms of this primal-dual gap.
We also show that our primal-dual gap bound iteration / convex with respect the step size, which implies that one can efficiently do line search to maximize the primal-dua progress. In order show the flexibility of this paradigm, also generalize these ideas the gradient descent algorithm.
4.1 PRIMAL-DUAL. SHORT STEPS FOR FW ALGORITHMS
Let consider first the case of FW and HB-FW. In this section, we denote Gt, and ø, and i, the respective primal-dual gaps, and iterates. From the analyses in Appendix B, cf. (8) or (11), we have the following
La 2A,
A,G, - A S
1t .r.12
and defining 7t der a,/A,, dividing the above by A, on both sides, and rearranging gives
To 11ve 12
G. (1 ((1-))GT1 7
(4)
The right-hand side is minimized for the choice
7t -min { (1, G
(5)
L xell2
which is what we refer to the primal-dual short step for these two algorithms, and focuses on maximizing guaranteed progress of the primal-dual gap, as discussed above. We show that this step- size is sound in the sense that we still keep the optimal convergence guarantees of other approaches. We also show that we can perform a line search over the primal-dual gap bound obtained before using the smoothness inequality in the analyses.

---

Published as a conference paper at ICLR 2026
Proposition 4.1. [4] Let f be convex and differentiable. The FW and HB-FW algorithms satisfy
1/ - -xa) (xx) + f((1 7)) + 7ut), for all yE E [0, 1 t > 1 and the RHS is convex on 7,. further f is L-smooth w.r.f. a norm || ||. and
G. S (1 - (1--)))-1-11-- -
(6)
D def xEX ||z
yll, then using (5) or line search on the RHS of (6), we obtain: G, S 4LD*
[42
The convergence above for the line search is derived from the one for the primal-dual short step, since the right hand side (5) upper bounds the one of (6).
We note that, naturally, if we define the gap as G2 f( analyzing the algorithm with the strategy in (3), yields that the primal-dual short steps become regular short steps. In that case, even though we do not know the value f(x") (z²)) in the gap definition, the step can still be defined without this knowledge, cf. Remark D.I.
which is the primal gap, then
4.2 PRIMAL-DUAL SHORR STEPS FOR GRADIENT DESCENT
We now extend our primal-dual short steps gradient descent (GD) whose updates are given by It-1 + Jt ag V ( ). We use the Euclidean norm in this section for the problem mingeR* fx) where convex and L-smooth. One possible analysis of GD relies on defining primal-dual gap similarly to the one in Appendix B.2, and then show A,G, S. A.-1G,-1 for de = 1/b L and
A 41 x 122 for an imitial point 21 and a minimizer x". We provide a sketch of the steps that we take and leave the details to Appendix D.I. The lower bound on f(z²) that we use is
Arf(z*) 2 Σ (z)( +
a. (V)(a)) 2+11 - xz) + |1 21112 D del A,L:,
A=1
where D is an upper bound on the initial distance to a minimizer G.= = =((1+11) - L1, we arrive to
||
x I|2. Defining the gap as
At G. |
ArAr-1
aj
af
G, <
A
A
2
2A,
for & > and a similar expression for = 1. Recall that A; def Ei ae, So at this stage, one can optimize a, in order to minimize the right hand side, by solving simple cubic equation, which is what we term the primal-dual short steps for GD. We show that the optimal value satisfies a; 2 21. which ultimately yields a convergence rate no slower than G. LDD, as we formalize in the following. We also show, as above, that we can perform a line search for minimizing a better bound on the primal-dual gap. yielding no worse convergence rates. Recall that (#++1) f(=)) S G..
Proposition 4.2. [1] Let f be convex and differentiable. The primal-dual gap of GD is bounded by (25) which is convex on the step at If further f is L-smooth with respect to || 112. GD using the primal-dual short step-size or line search on the aforementioned bound then the step size satisfies
and we have G2 < LD²
a, 2 2Z
notable difference between the line search on these primal-dual bounds in GD and FW algorithms is that convexity was shown in Proposition 4. to hold with respect to the parameter y which corresponds Ar whereas for GD in Proposition 4.2, the convexity shown hold for the parameter a;
EXPERIMENTS
Here we provide experiments demonstrating the good performance of the optimistic variant. All experiments were performed in Julia based on the FrankWol fee. jl package run MacBook Pro with an Apple MI chip with Julia 1.11.1. The code will be made publicly available upon publication. In our experiments we compare the optimistic FW variant (with OFTRL) with the heavy ball variant, and the vanilla FW algorithm. For the FW variant, apart from the agnostic step size rule 7 def 2 we also consider the adaptive line search (indicated by adapti ive ve in the plots) from (Pokutta, 2024), a numerically improved variant of (Pedregosa et al., 2020), which is the default line search in the Frankñol 1 fe. j1 package. As shown in (Guélat & Marcotte, 1986), line search is subject
T#2
7

---

Published as a conference paper at ICLR 2026
Hooy ftll
Opieisio PW
$44.45
364.45
(ataptin)
Phma
S41.44
$46.44
344.4
10"
10a
10
10
169
10-22
10"4
10'19
10-2
10
Time (ood)
Figure 1: Comparison over the probability simplex with objective ((x = || soll.. where xo is random point outside the probability simplex. The optimistic method converges faster in iterations and time.
lower bound that does not hold for, e.g., open-loop step-sizes and in particular the heavy ball variant and the optimistic variants. In fact, there are cases where the line search variant slower than the vanilla variant asymptotically shown in (Bach, 2021) and later in (Wirth et al., 2023; 2024) for the aonaayypttoiic case; we observe a similar behavior in our experiments as they satisfy the conditions of (Wirth et al., 2023; 2024); see also (Kerdreux et al., 2021).
over various polytopes P. so that in particular v(x) def px is the indicator function of the respective polytope. the following, we will use the dual gap the definition of G, def f(xx) - I.ç as in (2). In the case of the heavy ball variant from Appendix B.1 we set (VI(z;;), v xz), and we refer to this lower bound as H. if not clear from the context. Clearly this is lower bound and in fact this is precisely the heavy ball vertex that is computed in the heavy ball algorithm. It is important to note that this lower bound and the associated dual gap valid for any algorithm as simply a convex combination of linear lower bound functions minimized over P. For comparability and due to its natural form and being valid for any algorithm, we use this definition of the gap also for reporting the results of the optimistic variant in experiments.
Our numerical experiments
for all i < 6, and v, arg min,eP Σi A. fxx) + Σ
In the case of the vanilla FW variant (either with open loop step sizes or with line search) the e in the expression above chosen be the FW vertices, i.e., arg min fzx) + (V
24), minimizing each summand separately. This bound is thus separable in contrast to the heavy ball one we will discuss further below Remark 5. and we can use f(==) 2 maxosist f(x;) (V](x;; Tz), as lower bound so that the gap becomes the running minimum of the FW gaps across the iterations, which we refer to as L.W.
Remark 5.1 (Strength of lower bounds). Suppose that g(æz) denotes generic gap function that bounds the primal gup at It, ie., f(x)) f(x*) S g(ax). We will choose the specific gap function later depending on the context. Observe that the gap function immediately gives a lower bound for f(x*) simply by rewriting as f(x*) f(xx)) -g(z)). Then in line with the above if we make the choice for the lower bound L, as A.f(x") Et-n O fxx) Et arg(xz) A, then in this case, the lower bound L, cannot be stronger than taking the best lower bound observed so far, since f(x")= Z max:=0..... (xz) g( 2 A. Ei=o (x)) ({xz)), This is the case because the lower bound a convex combination of lower bound terms from individual iterations.
As mentioned, this is different, e.g.. for the heavy ball lower bound function, which does not decompose in individual iterations as the Frank- Wolfe vertex is computed for the cumulative function across rounds. The reason why the primal-dual gap for HB-FW can be significantly better (as in: lower)
8

---

Published as a conference paper at ICLR 2026
Opteanii:
Vanills
Punel
1,632
1,052
1,600
1,629
1,028
10"
107
Dal Cap
30
107
10
10-3
207
10f
hantions
Time (sec)
Figure 2:
Comparison over k-sparse polytope with = 10 with objective f(x) = ||Ar bl2. where A and are random. The optimistic method converges faster in iterations and time.
than the Frank- Frank-Wolfe gap is illustrated the following example: The FW algorithm, commonly used with polytopal constraints, sometimes suffers from the so-called zigzag problem (Wolfe, 1970; Guélat Marcolte, 1986) (see also Braun al. (2022) for an in-depth discussion), that usually due to minimizer being in the relative interior of a face while the points vs, being the result of an LMO, are chosen as vertices of the polytope. In this scenario, is possible that f ) is aligned with the direction Ut for all t, while convex combination gradients is close being perpendicular to the optimal face making the lower bound HB be closer to the optimal value.
In the plots we show the primal value and the dual gap vs. the number of iterations and time. Points with excessively large values are not shown in the plots, leading to apparent different starting points. We use log-log plots so that the slope is equal to polynomial order of convergence. As our variants compute one gradient per iteration, the number of iterations is equal to the number of gradient evaluations. Throughout our experiments we see that the optimistic variant significantly outperforms the heavyball variant, the vanilla FW, and often, although not always, also the FW variant with the adaptive line search strategy from (Pokutta, 2024) in the order convergence.
We also experiments for the primal-dual short step from Section 4. However, found that behaved similarly than the vanilla FW variant with standard short-steps (or line search), without outperforming this already good heuristic; see Figure 3 in Appendix F. The reason because the primal-dual gap measure is better, the step size is actually often smaller, leading to no faster convergence; this reminiscent of the lower bound in (Guélat Marcotte, 1986).
be that
We also tested whether optimism is really the main source of improvement or whether most of explained by using the heavy ball lower bound which shows be stronger than the vanilla FW lower bound. In fact, we show in Figure 4 in Appendix F, that indeed optimism is what is making the algorithm be faster. In fact the heavy ball lower bound applied the vanilla FW variant is weaker that the normal FW gap in our tests. This strongly suggests that it is really the trajectory of the optimistic variant that is better. For more experiments, we refer to Appendix G.
We tested various combinations of functions and feasible regions. For the functions, we used (a) quadratic optimization consisting essentially on (b) ill-conditioned quadratic optimization and (c) portfolio optimization problems, which are all widespread benchmarks for Frank- Wolfe algorithms (Braun et al., 2022), see Appendix F. In terms of the feasible regions, we considered (i) the probability simplex P {Ir Rd Σ, 24 1, x 0}. (ii) and the more complex k-sparse polytope P which the convex hull of all 0/1-vectors with & non-zere zero entries. We detail the instance parameters the captions of the figures.

---

Published as a conference paper at ICLR 2026
In our experiments we report results for regression problems. The reason for this is to allow to build specific setups where the different convergence behaviors of FW variants are known to emerge. We also performed preliminary experiments over portfolio optimization instances (here the objective the negative log-likelihood
the portfolio returns) and also Optimal Experiment Design instances (Hendrych al., 2024) (here the objective arises via matrix means) and found that the optimistic variant also outperforms the other variants similarly.
The optimistic approach presents a good alternative for current Frank-Wolfe methods that is theoreti- cally justified and enjoys faster convergence in practice.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 05M144AM..55200BMM and the Deutsche Forschungseemeisccaatt (DFG) through the DFG Cluster of Excellence +ATH+ (EXC-2046/1 and EXC-2046/2, project id 390685689). David Bartinez-Rubil was partially funded by the project IDEA-CM (TBCC20044CCM--99)
REFERENCES
Jacob D. Abernethy and Jun-Kun Wang. On frank- wolfe and equilibrium computation. In Isabelle Guyon, Ulrike Von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vish- wanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6584-6593, 2017. URL https:// www.reeeddnns.nuuiis...c.... 7371 21666bb3722aa9ddddd33ee/eeeeeee.
Katy S. Azoury and Manfred K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Mach. Learn., (333):2112246 2001. doi: 10.102//A: 1010896012157. URL
htpp:///ooiooo///// http://ddo..rg//.1023//333// /0.11223/A:000000600125555
Francis Bach. On the effectiveness of richardson extrapolation in data science. SIAM Journal on Mathematics of Data Science, 3(4):1251-1277, 2021.
Francis R. Bach. Duality between subgradient and conditional gradient methods. SIAM J. Optim., 25 (1):115-129, 2015. doi: 10.1137/130941961 URL https://doi.or// http://ddoo.rr/0.1133////1/ 10.1113//1309419000
Aurélien Bellet, Yingyu Liang Alireza Bagheri Garakani, Maria-Florina Balcan, and Fei Sha. A distributed frank-wolfe algorithm for communication--fficiee sparse learning. In Suresh Venkatasubramannin and Jieping Ye (eds.), Proceedings of the 2015 SIAM International Conference on Data Mining, Vancouver, BC, Canada, April 30 May 2, 2015, pp. 478-486. SIAM, 2015. doi: 10. 0tt.//19.816661 977116661111100054 URL https://doi..or//1... wt..or////..11/////.. 111711997711111 1974010.54.
Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokthari, and Sebastian Pokutta. Conditional gradient methods. preprint, 11 2022.
Alejandro Carderera, Mathieu Besançon, and Sebastian Pokutta. Simple steps are all you need: Frank- wolfe and generalized ceff-concordan functions. Advances in Neural Information Processing Systems, 34:5390-5401, 2021.
Jinghui Chen, Dongruo Zhou, Jinfeng Yi, and Quanquan Gu. A frank-wolfe framework for efficient and effective adversarial attacks. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, AAAI Press, 2020. doi: 1600/AA/A
New York, NY, USA, February 7-12, 2020, pp. 5341.4.5753. URL http:://oii.orrr org/ 10. (0009//aai.v3300 v3.04..4...
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), COLT 2012 The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pp. 6.1-6.20. JMLR.org. 2012. URL pttp:// v2tpeppreee//22///iu/a 12/ chiangg
Cyrille W Combettes and Sebastian Pokutta. Boosting Frank-Wolfe by Chasing Gradients. Proceed- ings of ICML, 3 2020.
Ashok Cutkosky. Anytime online-to-batch, optimism and acceleration. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 1446 1454, PMLR, 2019. URL http://pnocedings..lrreeep v97/ cutkosky I html.
11

---

Published as a conference paper at ICLR 2026
Jelena Diakonikolas and Lorenzo Orecchia. The approximate duality gap technique: A unified theory of first-order methods. SIAM J. Optim., 29(1):660-66)) 1886606689,000 2019. doi: 10.1137/18M1172331 URL http://ddd..rr11..113/////////
Jelena Diakonikolas, Alejandro Carderera, and Sebastian Pokutta. Locally Accelerated Conditional Gradients. Proceedings of AISTATS, 2020.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, ((1-2):5--110, 1956.
Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets, In International Conference on Machine Learning, pp. 541-549. PMLR, 2015.
Jacques Guélat and Patrice Marcotte. Some comments on Wolfe's "away step'. Mathematical Programming, 35(1): (0()):10-1199 10-119, 1986.
David H. Gutman and Javier F. Peña. Perturbed fenchel duality and first-order methods. Math. Program., (98(1):443 2023. doi: 10.107//111000002-017999 URL https://oii.org// 10. 01177/111107022-0177777
Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta. Solving the optimal experiment design problem with mixed mixed-integer convex methods. In Leo Liberti (ed.). 22nd International Symposium on Experimental Algorithms (SEA 2024), volume 301 of Leibniz International Proceedings in
Informatics (LIPlcs), pp. 16:1-16:22, Dagstuhl, Germany, 2024. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978-3-95977-322 https://dross.ucgstuh.... dagstuhl ettiee////niiiieeeeeeanee
doi: 10.4230/LIPIcs.SEA. SEA.2024.16. URL 1...4443///11..... SEA.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, 2C11, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pp. 427-435. JMLR.org. 2013. URL
jaggil3.
Thomas Kerdreux, Alexandre d' Aspremont, and Sebastian Pokutta. Local and Global Uniform Convexity Conditions. preprint, 2021.
Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of frank-wolfe optimization variants. Advances in neural information processing systems, 28, 2015.
Simon Lacoste-Julien, Fredrik Lindsten, and Francis Bach. Sequential kernel herding: Frank- wolfe optimization for particle filtering. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2015, San Diego California, USA, May 9-12, 2015, volume 38 of JMLR Workshop and Conference Proceedings. JMLR.org, 2015. URL
http:p/rceeeiinng....rereeee //////////////// laloste--uliinnteee 15. htmll
Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
Bingcong Li, Alireza Sadeghi, and Georgios B. Giannakis. Heavy ball momentum for conditional gradient. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pp. 21244-21255, 2021. URL Abstract.mmm..
Haihao Lu and Robert M. Freund. Generalized stochastic frank-wolfe algorithm with stochastic "substitute" gradient for structured convex optimization. Math. Program., 117())317-349, 2021. doi: 10.1007//1000770000001444
URL
Giulia Luise, Saverio Salzo, Massimiliano Pontil, and Carlo Ciliberto. Sinkhorn barycenters with free support via foalk-wolfe algorithm. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'ché-B-Buu Buc, Emily B. Fox, and Roman Garnett (eds.), Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 9318-9329, 2019. URL https: // mennreedinngs.uuris... pappr/009///// hwwhhhhhhwggff.h////2/2/2222/2/0 Abbttrtttteee-tttthhhiaee himl.
12

---

Published as a conference paper at ICLR 2026
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. J. Mach. Learn. Res., 21:105:1-105:49) 2020.
URL http:///r...rrpppp/////psaa// 78.76...tmmm
Hassan Mortagy, Swati Gupta, and Sebastian Pokutta. Walking in the Shadow: New Perspective on Descent Directions for Constrained Minimization. Proceedings of NeurIPS, 6 2020.
Geoffrey Négiar, Gideon Dresdner, Alicia Y. Tsai, Laurent El Ghaoui, Francesco Locatello, Robert Freund, and Fabian Pedregosa. Stochastic frank-wolfe for constrained finite-sum minimization. In Proceedings of the 37th International Conference 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 7253-7262. PMLR, 2020. URL procee/d/proe..iggs..... wttp:ngsss......rr.s..... v 19/ 1egnairra00aaiin
Machine Learning, ICML 2020, 13-18 July
Yu Nesterov and Vladimir Shikhman. Quasi- monotone subgradient methods for nonsmooth convex minimization. Journal of Optimizution Theory and Applications, 165(3):917-940, 2015. URL
hupss///ink.springeraa article/ 1007/
Yurii E. Nesterov. Complexity bounds for primal-dual methods minimizing the model objective function. Math. Program., 171(1-2):11-330 2018. doi: 10.1007/510007-017-11133 URL
htipo///oi.orr// 10. 1007///00107-017771888-6
Tri Nguyen, Xiao Fu, and Ruiyuan Wu. Memory-efficient convex optimization for self-dictionary separable nonnegative matrix factorization: A frank-wolfe approach. IEEE Trans. Signal Process., 70:3221-3236, 2022. doi: 10.1 10.1109/TSP22222.317788 URL https:///oi.rrg/ 10.1109/TSPP.02. 3177845.
Francesco Orabona. A modern introduction to online learning. CoRR, abs/1912.13213, 2019, URL http://axxiv.org/ wbs//a/s...//////// 1912.13213.
Fabian Pedregosa, Geoffrey Negiar, Armin Askari, and Martin Jaggi. Linearly convergent frank- wolfe with backtracking line-search. In International conference on artificial intelligence and statistics, pp. 1-10. PMLR, 2020.
Javier F Peña. Affine invariant convergence rates of the conditional gradient method. SIAM Journal on Optimization, 33(4):2654-2674, 2023.
Javier F Peña and Daniel Rodríguez. Polytope conditioning and linear convergence of the Frank-
Wolfe algorithm. Mathematics of Operations Research, 44(1):1-18, 2018. doi: 10. 1287mooo 2017.0910.
Javier Peña. Generalized conditional subgradient and generalized mirror descent: duality, conver- gence, and symmetry. arXiv preprint arXiv:1903.00459 2019.
S. Pokutta. The Frank-Wolfe algorithm: short introduction. Jahresbericht der Deutschen Mathematiker-Vereinnn
126:3-35, 2024.
Leonid Denisovich Popov. A modification of the arrow-hurwitz method of search for saddle points. Mat. Zametki, 2875)7777 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Shai Shalev-Shwartz and Ingo Steinwart (eds.), COLT 2013 The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pp. 993-1019. JMLR.org, 2013. URL http://pmoeeddinggmmmpeesss Rakhlin13.huml
Jacob Steinhardt and Perey Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In Proceedings of the 31th International Conference on Machine Learning. ICML 2014, Beijing, China, 21-26 June 2014, volume 32 JMLR Workshop and Conference Proceedings, pp- 1593-1601, Jrg,. 2014. URL http::/ppooeeediggs....poo /t2 4.mmll.
Kun Wang, Jacob D. Abernethy, and Kfrr Y. Levy. No-regret dynamics in the fenchel game: unified framework for algorithmic convex optimization. Math. Program., 205 268, 2024. doi: 100700 10000//011000023-11199771 URL htlps://doi.orrg http::///da...oooo...00000000000 100000077//111000000000000777
13

---

Published as a conference paper at ICLR 2026
Elias Wirth, Thomas Kerdreux, and Sebastian Pokutta. Acceleration of Frank- Wolfe algorithms with open loop step-sizes. Proceedings of AISTATS, 2023.
Elias Wirth, Javier Peña, and Sebastian Pokutta. Accelerated affine-invariant convergence rates of the
frank-wolfe algorithm with open-loop step-sizes. Mathematical Programming A, 12 2024.
Philip Wolfe. Convergence theory in nonlinear programming. Integer and nonlinear programming. pp. 1-36, 1970.
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam R. Klivans, and Qiang Liu. Good subnetworks provably exist: Pruning via greedy forward selection. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 10820-108300 PMLR, 2020. URL http://pmoceddinn..mprrrrss//// yebbe20..tmm...
14


Reviews:
[{"review_id": "IOKe32b4pm", "reviewer": "Reviewer_n1pE", "summary": "This paper studies an optimistic variant of the Frank-Wolfe method and establishes a worst-case convergence guarantee in terms of the primal dual gap $G_t = f(x_t) - L_t$, where $L_t$ is a computable lower bound on the optimal value $f(x_*)$. The analysis focuses on the primal-dual gap because it can be evaluated and used as a stopping criterion, unlike the primal gap $f(x_t) - f(x_*)$. In particular, the authors propose Algorithm 2, which uses the short step size in (5) to ensure a monotonic decrease of the primal-dual gap. The paper further demonstrates the generality of the approach by showing that it also applies to gradient descent.", "questions": "- Line 43: What do you mean by \"corresponding convergence rate need to be heuristically estimated\"?\n- Line 46: What do you mean by \"enhancing the convergence properties\"? I don't see any results that supports this claim.\n- Line 65: Could you justify how your method adapt effectively to varying conditions and provides a robust analysis?\n- Line 78: As written, it seems to suggest that your method improves the theoretical constant, although you refer Appendix E. I recommend explicitly stating that this improvement is observed empirically.\n- Lines 230-234 with line 7 in Algorithm 2: This part is particularly difficult to follow.\n- Figure 1: Why does the optimistic method much more efficient per iteration compared to the plain one, given that Algorithm 2 is more complex? I also recommend plotting the primal gap $f(x_t) - f(x_*)$, rather than $f(x_t)$.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Regardless of the weaknesses mentioned below, I believe this paper, by proposing a new optimistic variant of the Frank-Wolfe method with a convergence guarantee on the computable measure, has its own merit, and warrants further investigation in this direction.", "weaknesses": "- I agree that the primal-dual gap can serve as a practical stopping criterion, but I don't follow the authors' claim that this justifies the need for a method with a guaranteed convergence rate for that gap. First, the primal-dual gap is not a tight bound on the primal gap $f(x_t) - f(x_*)$, and it can be computed regardless of whether we have a theoretical guarantee on its decrease. Moreover, the paper does not show that existing methods do not efficiently decrease the primal-dual gap (in theory).\n\n- I also find the repeated claim that the proposed optimistic approach better adapts to the environment unconvincing. I would appreciate a more precise and unambiguous explanation of what type of adaptivity is meant here.\n\n- For the above reasons, I am not fully convinced by the motivation or the importance of the contribution.", "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": "g4ttkf3xXs", "reviewer": "Reviewer_62CQ", "summary": "The paper proposes an optimistic Frank-Wolfe algorithm that leverages optimistic online learning methods (FTRL, OMD). In particular, one can substitute the LMO oracle part into optimistic FTRL/OMD on linear losses to construct the proposed OFW. The OFW analysis establishes a classical $O(1/t)$ rate of convergence for the primal-dual gap via online-to-batch conversion and shows better performance in empirical studies, especially in terms of the dual gap. The paper also suggests a primal-dual short step schedule designed from a descent-lemma-like inequality tailored for the Frank-Wolfe (primal-dual) gap. This better suits FW type algorithms than classical step sizes that come from ‘primal’ descent-lemmas (i.e., smoothness) and provides a stopping criterion computable on the fly.", "questions": "- The second term in the proposed upper bound for optimistic FW (in Theorem 3.1) is $\\frac{4LD^2}{t+1}$ which looks identical to that of vanilla FW, but in the experiments optimistic FW clearly looks faster. Could there be a way to theoretically show a strict improvement over FW/HB-FW in terms of either faster convergence under certain settings (sparse problems, etc) or guaranteed convergence in a broader setting with weaker assumptions or maybe something else? (In simple online learning settings, FTRL and OMD can have constant improvements in the regret upper bound compared to vanilla online GD in certain cases, e.g., the function $f$ has sparse gradients, if I am correct.)\n- Is it a bad idea to choose $L_2$ or $L_1$ (or maybe combined) norm regularizers for optimistic FW, instead of the polytope indicator? I think this might sometimes better capture the benefits of using FTRL/OMD type updates, while using an indicator as the regularizer seems to make less distinction (though not exactly equivalent) with vanilla FW. What can you expect if we use different regularizers, or is there a reason why the paper does not consider these?\n- What exactly are the benefits we get from using primal-dual step sizes? What I can see is that we can drop the constant $4$ from the upper bound of $G_t$ if we use GD with primal-dual step sizes (or line search), but is this the best we can get from this? Also, is there a way to find a ‘primal-dual-optimized’ $a_t$ for the optimistic FW versions? While merging the two ideas might be irrelevant or unbeneficial, I still think there should have been bits of explanation about why this is the case, and if these are two completely separate ideas, it seems unclear how primal-dual step sizes can be useful.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The writing is clear and easy to read overall. The ideas of each sections are well presented through selected key inequalities from the proof, which makes a much better reading experience.\n- The paper includes numerical experiments that support the theoretical results.", "weaknesses": "See **Questions.**", "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": "Y3Zz9KR9La", "reviewer": "Reviewer_CvWP", "summary": "This paper introduces new techniques for improving Frank-Wolfe (FW) algorithms by incorporating function smoothness beyond traditional short steps. The authors propose two main innovations. First it proposed the Optimistic Frank-Wolfe Algorithm (OFW), a novel method inspired by optimistic online learning, leveraging predicted gradients to improve convergence in smooth convex optimization. It adapts to changing curvature and achieves a provable 1/t^2 like primal-dual convergence rate. Second it introduced the Primal-Dual Short Steps (PDSS), a new class of step-size rules that optimize the primal-dual gap directly, leading to theoretically justified and generalizable improvements. The same principle extends to gradient descent. Experiments over standard convex benchmarks (simplex, k-sparse polytopes, portfolio optimization) show that the optimistic variant consistently outperforms classical and heavy-ball FW methods, both in iteration count and runtime.", "questions": "There are no other questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This submission has conceptual innovation. The introduction of optimism into the FW setting is novel and well-motivated through online learning theory (OMD/FTRL frameworks). The primal-dual short-step idea elegantly unifies step-size selection with primal-dual analysis, offering tighter convergence and computable stopping criteria. The authors presented the rigorous theoretical framework. The analysis is carefully constructed through primal-dual gap bounds, clearly improving on classical FW and heavy-ball variants. Results from Theorems and Propositions provide clean, interpretable convergence bounds with constant factors comparable to or better than prior work. \n\nThe authors also conduct the numerical experiments using standard benchmarks implemented in Frank Wolfe, ensuring reproducibility. The optimistic algorithm shows steeper log–log slopes (faster empirical order of convergence) and strong wall-clock performance improvements. The empirical results from the numerical experiments are consistent with the theoretical analysis.", "weaknesses": "There are no major weakness for this submission.\n\nOn minor weakness if that this submission has limited experimental scopes. Only convex smooth problems are tested; no constrained stochastic or non-convex scenarios. The proposed primal-dual short steps did not outperform standard heuristics in practice — acknowledged but not deeply analyzed. It is suggested to add more numerical experiments with more experimental scopes like including non-smooth and stochastic benchmarks to demonstrate generality and comparing against projection-free adaptive gradient methods or away-step FW variants to position contributions more competitively.", "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": "454zYh5ZSB", "reviewer": "Reviewer_C2jy", "summary": "This paper revisits the Frank–Wolfe (FW) family of algorithms and develops two main innovations: (i) optimistic Frank–Wolfe (OFW): A new FW variant that incorporates optimism from online learning, predicting future gradients to adaptively refine updates. The algorithm enjoys a primal–dual convergence analysis and retains the rate under convex smooth settings. (ii) primal–dual short steps: A generalization of the classical “short-step” rule that maximizes primal–dual progress instead of just primal progress. This approach yields an interpretable stopping criterion based on a computable primal–dual gap and extends naturally to gradient descent.\n\nThe paper provides rigorous analyses, unifying online learning and Frank–Wolfe perspectives via the optimistic mirror descent/FTRL framework, and demonstrates the practical advantages of OFW through experiments on convex quadratic problems and polytopal constraints.", "questions": "1. Can the optimism mechanism extend to nonconvex or stochastic FW settings?\n2. How does the optimistic FW relate to momentum-based FW (e.g., Heavy-Ball FW) beyond shared lower bounds?\n3. Could the primal–dual gap be efficiently estimated without full LMO recomputation at each iteration?\n4. Do you foresee any extension to affine-invariant step-size strategies as in Pena (2023)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The incorporation of optimism into Frank–Wolfe algorithms is both original and theoretically well-motivated. It bridges FW with the online-to-batch conversion framework (Cutkosky, 2019), enriching the algorithmic toolbox for projection-free methods.\n\n2. The proposed analysis elegantly derives both convergence guarantees and computable stopping criteria from a primal–dual perspective. The connection between FW, heavy-ball FW, and gradient descent is clarified through shared gap-based arguments.\n\n3. The theoretical results are sound and internally consistent. The paper’s exposition (especially Section 3-4) carefully motivates each step-size rule and provides transparent algorithmic derivations.\n\n4. Experiments on probability simplices and $k$-sparse polytopes convincingly show that the optimistic variant converges faster (both in iteration and wall-clock time) than standard and heavy-ball FW variants. The results are reproducible and coded in Julia.", "weaknesses": "1. The experiments are small-scale, focusing on synthetic convex problems. More realistic applications (e.g., structured prediction, optimal transport, or matrix completion) would better support the method’s practical relevance.\n\n2. Despite being theoretically elegant, the primal–dual short-step variant performs comparably or slightly worse than vanilla FW with line search, suggesting limited practical value.\n\n3. The optimistic connection could be explained more clearly and the connection to predictive gradient methods could be emphasized further.\n\n4. The paper is dense with notations, which can make it difficult for non-specialists to follow. A clearer summary table or pseudocode for each variant would help.", "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)