Pith. sign in

REVIEW 1 major objections 4 minor 53 references

Adaptive Open-Loop Step-Sizes for Accelerated Convergence Rates of the Frank-Wolfe Algorithm

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The log-adaptive Frank-Wolfe step-size dominates every fixed parameter rule.

desk verdict A useful new default step-size for Frank-Wolfe, with a fixable proof bug in the general theorem and an unproven endpoint claim. read the letter →

arxiv 2505.09886 v1 pith:RX7JGHYR submitted 2025-05-15 math.OC

Elias Wirth , Javier Peña , Sebastian Pokutta This is my paper · ORCID
classification math.OC MSC 90C2590C3065K0568W40
keywords Frank-Wolfealgorithmopen-loopstep-sizeslog-adaptivestep-sizegrowthpropertyacceleratedconvergenceratesprimal-dualgapconditionalgradientsconstrainedconvexoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to answer a practical question: which open-loop step-size should a Frank-Wolfe user pick when solving constrained convex problems? It argues that the log-adaptive rule $\eta_t=\frac{2+\log(t+1)}{t+2+\log(t+1)}$ converges at least as fast as any fixed-parameter rule $\eta_t=\frac{\ell}{t+\ell}$ with $\ell\ge 2$, up to polylogarithmic factors, and strictly faster in strong growth settings. To prove this, the paper generalizes earlier accelerated-rate results from fixed $\ell$ to step-sizes $\eta_t=\frac{g(t)}{t+g(t)}$ for non-decreasing $g$ with non-increasing $\eta_t$, yielding the main rates in Theorem 3.2 and Theorem 4.1. If correct, this gives a parameter-free default step-size that needs no tuning and is already implemented in a public Frank-Wolfe software package.

What carries the argument

The load-bearing object is the strengthened cumulative-product bound (Lemma 3.1): for $\eta_t=\frac{g(t)}{t+g(t)}$ with $g$ non-decreasing, and any $S\le t$, $\epsilon\in(0,g(S))$, the tail product $\prod_{i=S}^{t}\big(1-(1-\frac{\epsilon}{g(i)})\eta_i\big)\le\big(\frac{\eta_t}{\eta_{S-1}}\big)^{g(S)-\epsilon}$. This bound replaces the fixed-$\ell$ product bound used in earlier work and makes the decay exponent grow with $g(S)$. It is combined with the objective reduction identity $f(x+\eta(v-x))=f(x)-\eta\,\mathrm{gap}(x)+D_f(x+\eta(v-x),x)$ and with strong or weak growth properties that control the Bregman remainder. The assumptions that $g$ is non-decreasing and that $\eta_t$ is non-increasing are exactly what the product bound needs.

What would settle it

Run FW with the log-adaptive step-size on constrained least squares over an $\ell_2$-ball with the unconstrained optimum outside the ball, which is a strong $(M,1)$-growth instance; Theorem 3.2 predicts that primaldualt decays faster than any fixed polynomial. If the observed curve instead levels off at the $O(t^{-2})$ or $O(t^{-1})$ slope exhibited by fixed-$\ell$ rules, the central claim is wrong. A more direct check is to compute the tail product in Lemma 3.1 numerically for $g(t)=2+\log(t+1)$ and verify the stated inequality for large $t$; any violation would pinpoint the proof step.

Watch

Extended reading notes

Core claim

The central claim is that Frank-Wolfe with the log-adaptive step-size $\eta_t=\frac{2+\log(t+1)}{t+2+\log(t+1)}$ converges at least as fast as FW with $\eta_t=\frac{\ell}{t+\ell}$ for every integer $\ell\ge 2$, up to polylogarithmic factors, and strictly faster in strong $(M,r)$-growth settings. Concretely, Theorem 3.2 bounds the primal-dual suboptimality gap by $O\big(g(t-1)^{\frac{1}{1-r}}\eta_{t-1}^{\min\{g(S)-\epsilon,\frac{1}{1-r}\}}\big)$ for any admissible $g$; with $g(t)=2+\log(t+1)$, $\epsilon=1$, and $S=\lceil\exp(\frac{1}{1-r})\rceil$, this is $\tilde{O}(t^{-\frac{1}{1-r}})$, and in the strong $(M,1)$ endpoint it becomes $\tilde{O}(t^{-k})$ for any $k$. In the weak growth setting, Theorem 4.1 gives $\tilde{O}(t^{-\frac{1}{1-r}}+t^{-2})$. The proof works for arbitrary non-decreasing $g$ satisfying the paper's assumptions A1 and A2, so the log-adaptive rule is one instantiation of a general family that inherits the acceleration.

Load-bearing premise

The entire acceleration rests on the instance satisfying a strong or weak growth property: if the objective and feasible region do not obey one of these inequalities, only the classical $O(t^{-1})$ rate is guaranteed, and the paper's own collaborative-filtering experiments are not yet known to satisfy the assumption.

Editorial extensions

If this is right

  • No fixed parameter $\ell\in\mathbb{N}_{\ge 2}$ can be considered optimal anymore: the log-adaptive rule matches every fixed-$\ell$ rate up to polylogarithmic factors and beats it in strong growth settings.
  • In strong $(M,r)$-growth problems, the log-adaptive rule reaches $\tilde{O}(t^{-\frac{1}{1-r}})$, which is arbitrarily fast sublinear as $r$ approaches $1$; fixed-$\ell$ rules only deliver $O(t^{-\ell})$.
  • In weak growth settings, the log-adaptive rule achieves $\tilde{O}(t^{-\frac{1}{1-r}}+t^{-2})$, matching the best fixed-$\ell$ rules up to polylogarithmic factors.
  • The rule needs no problem-dependent parameters, no line search, and no extra per-iteration cost, so it can serve as a drop-in default open-loop step-size.
  • The rate statements are affine-invariant and apply to the primal-dual gap in the strong growth setting and to the suboptimality gap in the weak growth setting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the proof only requires $g$ non-decreasing with $\eta_t$ non-increasing, other slowly growing choices such as $g(t)=2+\log\log(t+2)$ should also be covered; they would trade asymptotic rate for an even slower step-size progression, which could help when the growth constant $M$ is unknown or large.
  • The log-adaptive rule behaves like an open-loop proxy for closed-loop heuristics that enlarge the step size as the objective flattens; if growth constants are unknown, it may capture some of that acceleration without estimating $M$.
  • A natural testable extension is to combine the rule with stochastic or block-coordinate FW variants, where the Bregman term carries extra variance; the cumulative-product mechanism could still yield rate statements under an expected growth condition.
  • The authors flag that collaborative filtering is not yet known to satisfy the growth assumptions, so the fast rates observed in those experiments are not covered by the theorems; closing that gap would substantially widen the practical reach of the rule.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies the Frank-Wolfe algorithm with open-loop step-sizes of the form η_t = g(t)/(t+g(t)) for a non-decreasing function g satisfying two structural assumptions (A1 and A2). Its main results are Theorem 3.2, an affine-invariant bound on the primal-dual gap under the strong (M,r)-growth property, and Theorem 4.1, an analogous bound on the suboptimality gap under the weak (M,r)-growth property together with strong (M,0)-growth. The authors propose the log-adaptive rule g(t)=2+log(t+1) and show that it achieves O~(t^{-1/(1-r)}) in the strong case and O~(t^{-1/(1-r)}+t^{-2}) in the weak case, matching or exceeding every fixed-ℓ rule η_t=ℓ/(t+ℓ) up to polylogarithmic factors. Numerical experiments on constrained regression and collaborative filtering, together with an implementation in FrankWolfe.jl, illustrate the proposed rule.

Significance. The central contribution is a clean extension of the cumulative-product technique of Wirth, Pena, and Pokutta to time-varying g, with Lemma 3.1 as a self-contained strengthening that appears to be new. If the (M,1) endpoint is resolved, the log-adaptive step-size is a genuinely attractive default: it requires no tuning of ℓ, is affine-covariant, and its analysis covers all r∈[0,1) and the weak-growth case up to the natural O(t^{-2}) cap. The paper is also commendable for shipping reproducible code and integrating the rule into FrankWolfe.jl, which lowers the barrier to adoption. The main caveat is that the advertised arbitrarily-fast rates in the strong (M,1) case are not covered by Theorem 3.2 as stated.

major comments (1)
  1. [Table 1 and Theorem 3.2] Table 1, the introduction, and the abstract's 'at least as fast as every fixed-ℓ rule' claim cover the strong (M,1)-growth endpoint, where the table reports O~(t^{-k}) for every k∈N and attributes this to Theorem 3.2. However, Theorem 3.2 is stated for r∈[0,1[ and its proof uses the exponent 1/(1-r), which is undefined at r=1; no separate endpoint argument is given. This is load-bearing because the arbitrarily-fast-sublinear statement for (M,1) is part of the headline comparison with fixed-ℓ rules. Please either prove the endpoint (for instance by a dedicated induction replacing 1/(1-r) with an arbitrary k) or explicitly restrict the claims and Table 1 to r∈[0,1).
minor comments (4)
  1. [§3, proof of Theorem 3.2, Case 2b] In the subcase g(S)-ε ≥ 1/(1-r), the displayed equality for the maximum over R is not correct as an equality; the maximum is attained at R=t and equals η_t^{g(S)-ε}/η_{t-1}^{g(S)-ε-1/(1-r)}, which is at most η_t^{1/(1-r)}. Replacing the '=' by '≤' (or bounding the maximum directly) fixes the display, and the final bound is unaffected.
  2. [§2.2, blueprint product bound] The displayed 'New cumulative product bound' in Section 2.2 uses ε/g(t) inside the product, while Lemma 3.1 and the subsequent proofs use ε/g(i); these should be made consistent.
  3. [Theorem 4.1 statement] The statement says g:R_{\ge0}→R_{\ge0}, but Assumptions A1/A2 and the arguments of g are on N and require g(i)≥2; also, the 'In particular' case uses g(t)=2+log(t), while the log-adaptive rule elsewhere is g(t)=2+log(t+1). Align these notations.
  4. [§5, numerical experiments] The figures show single runs without error bars or multiple restarts, so the visual 'at least as fast' comparisons should be read as illustrative; adding a brief note on this would strengthen reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the main rates are proven in-paper and the log-adaptive step-size is an ansatz, not a renamed or fitted input.

full rationale

The paper's central claims (Theorem 3.2 and Theorem 4.1) are derived in the text from the objective reduction identity (2.1), the growth assumptions (2.2)/(2.3), and a new cumulative-product bound (Lemma 3.1), which is proven in full. The log-adaptive step-size (1.3) is introduced as a concrete choice of g(t)=2+log(t+1), not fitted to the target rates; the rates in Table 1 are consequences of the induction, not identities built into the definitions. Self-citations [50,51] supply the blueprint and the growth-property framework, but no conclusion is imported wholesale: the strengthened product bound and the adaptive-rate inductions are new and the paper's proofs contain the essential argument. The collaborative-filtering caveat (Remark 5.1) is an honest scope limitation, not a circularity. The proof issue in Theorem 3.2 Case 2b noted by the skeptical reader concerns the validity of the maximization for g(S)-epsilon < 1/(1-r); that is a correctness risk, not a circular reduction, and it does not affect the log-adaptive instantiation, which uses S and epsilon such that g(S)-epsilon >= 1/(1-r).

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central results have no data-fitted parameters and introduce no new entities. The proof relies on the growth-property assumptions, which the paper itself acknowledges are not verified for all applications (Remark 5.1). The free parameters listed are analysis artifacts that tune the bound, not the algorithm.

free parameters (2)
  • epsilon (proof parameter) = 1 in the log-adaptive corollary
    The constant ε∈]0,g(S)[ appears in the cumulative product bound and in the exponents k=min{g(S)-ε,...}; it is an analysis parameter chosen by hand, not fitted to data.
  • S (starting iteration for the analysis) = ceil(exp(1/(1-r))) in the log-adaptive corollary
    S is chosen so that g(S) is large enough to make g(S)-ε dominate the exponent; larger S yields faster rates at the cost of a later bound. It is a proof artifact, not a user-specified parameter.
assumptions (4)
  • domain assumption Strong (M,r)-growth property (2.2) holds for the problem instance.
    Invoked in Theorem 3.2 and throughout the strong-growth proof; the accelerated rates are conditional on it.
  • domain assumption Weak (M,r)-growth property (2.3) and strong (M,0)-growth property hold simultaneously.
    Required by Theorem 4.1; without both, the weak-growth rate bound (4.1) does not follow.
  • domain assumption g is non-decreasing (A1) and t/g(t) is non-decreasing (A2), implying η_t non-increasing.
    These assumptions on the step-size-generating function g are used in Lemma 3.1 and in the worst-case maximization steps of Theorems 3.2 and 4.1. The log-adaptive g(t)=2+log(t+1) satisfies both.
  • standard math Standard convex analysis facts: objective reduction identity (2.1), subopt/primaldual inequalities, and log(1-x) ≤ -x.
    Used across the proofs without derivation; these are textbook results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Open-Loop Step-Sizes for Accelerated Convergence Rates of the Frank-Wolfe Algorithm." pith.science (2026). https://pith.science/paper/RX7JGHYR

@misc{pith2026250509886,
  author       = {Pith},
  title        = {Pith review of: Adaptive Open-Loop Step-Sizes for Accelerated Convergence Rates of the Frank-Wolfe Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RX7JGHYR}},
  note         = {Machine review of arXiv:2505.09886}
}
abstract

Recent work has shown that in certain settings, the Frank-Wolfe algorithm (FW) with open-loop step-sizes $\eta_t = \frac{\ell}{t+\ell}$ for a fixed parameter $\ell \in \mathbb{N},\, \ell \geq 2$, attains a convergence rate faster than the traditional $O(t^{-1})$ rate. In particular, when a strong growth property holds, the convergence rate attainable with open-loop step-sizes $\eta_t = \frac{\ell}{t+\ell}$ is $O(t^{-\ell})$. In this setting there is no single value of the parameter $\ell$ that prevails as superior. This paper shows that FW with log-adaptive open-loop step-sizes $\eta_t = \frac{2+\log(t+1)}{t+2+\log(t+1)}$ attains a convergence rate that is at least as fast as that attainable with fixed-parameter open-loop step-sizes $\eta_t = \frac{\ell}{t+\ell}$ for any value of $\ell \in \mathbb{N},\,\ell\geq 2$. To establish our main convergence results, we extend our previous affine-invariant accelerated convergence results for FW to more general open-loop step-sizes of the form $\eta_t = g(t)/(t+g(t))$, where $g:\mathbb{N}\to\mathbb{R}_{\geq 0}$ is any non-decreasing function such that the sequence of step-sizes $(\eta_t)$ is non-increasing. This covers in particular the fixed-parameter case by choosing $g(t) = \ell$ and the log-adaptive case by choosing $g(t) = 2+ \log(t+1)$. To facilitate adoption of log-adaptive open-loop step-sizes, we have incorporated this rule into the {\tt FrankWolfe.jl} software package.

Figures

Figures reproduced from arXiv: 2505.09886 by the authors.

Figure 1
Figure 1. Constrained regression over the ℓ2-ball. Convergence rate comparison of FW with different step-sizes for (5.1) for different locations of the unconstrained optimizer in the relative interior, on the relative boundary, and in the relative exterior of the feasible region and for the three different optimality measures gapt , primaldualt , and suboptt on the Boston-housing dataset. Axes are in log scale. For β ∈ {1000,… view at source ↗
Figure 2
Figure 2. Constrained regression over the ℓ5-ball. Convergence rate comparison of FW with different step-sizes for (5.1) for different locations of the unconstrained optimizer in the relative interior, on the relative boundary, and in the relative exterior of the feasible region and for the three different optimality measures gapt , primaldualt , and suboptt on the Boston-housing dataset. Axes are in log scale. similar phenom… view at source ↗
Figure 3
Figure 3. Collaborative filtering over nuclear norm balls of radii 1000 and 3000. Convergence rate comparison of FW with different step-sizes for (5.2) over nuclear norm balls of radii 1000 and 3000 for the three different optimality measures gapt , primaldualt , and suboptt on the movielens dataset. Axes are in log scale. Acknowledgements Research reported in this paper was partially supported by the Deutsche Forschungsge￾me… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 50 canonical work pages

  1. [44]

    The Frank-Wolfe algorithm: a short introduction

    Sebastian Pokutta. The Frank-Wolfe algorithm: a short introduction. Jahres- bericht der Deutschen Mathematiker-Vereinigung , 126:3–35, 1 2024

    work page 2024

  2. [1]

    Unsupervised learning from narrated instruc- tion videos

    Jean-Baptiste Alayrac, Piotr Bojanowski, Nishant Agrawal, Josef Sivic, Ivan Laptev, and Simon Lacoste-Julien. Unsupervised learning from narrated instruc- tion videos. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4575–4583, 2016. 15

    work page 2016

  3. [2]

    Linear convergence of a Frank-Wolfe type algorithm over trace-norm balls

    Zeyuan Allen-Zhu, Elad Hazan, Wei Hu, and Yuanzhi Li. Linear convergence of a Frank-Wolfe type algorithm over trace-norm balls. Proceedings of Advances in Neural Information Processing Systems, 30, 2017

    work page 2017

  4. [3]

    Learning with submodular functions: A convex optimization perspective

    Francis Bach et al. Learning with submodular functions: A convex optimization perspective. Foundations and Trends ® in Machine Learning , 6(2-3):145–373, 2013

    work page 2013

  5. [4]

    On the equiva- lence between herding and conditional gradient algorithms

    Francis Bach, Simon Lacoste-Julien, and Guillaume Obozinski. On the equiva- lence between herding and conditional gradient algorithms. In Proceedings of the International Conference on Machine Learning , pages 1355–1362. PMLR, 2012

    work page 2012

  6. [5]

    Distribution-based sketching of single-cell samples

    Vishal Athreya Baskaran, Jolene Ranek, Siyuan Shan, Natalie Stanley, and Ju- nier B Oliva. Distribution-based sketching of single-cell samples. In Proceedings of the 13th ACM International Conference on Bioinformatics, Computational Bi- ology and Health Informatics , pages 1–10, 2022

    work page 2022

  7. [6]

    Frankwolfe

    Mathieu Besan¸ con, Alejandro Carderera, and Sebastian Pokutta. Frankwolfe. jl: A high-performance and flexible toolbox for Frank–Wolfe algorithms and conditional gradients. INFORMS Journal on Computing , 34(5):2611–2620, 2022

    work page 2022

  8. [7]

    Guaranteed non-convex optimization: Submodular maximization over continuous domains

    Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed non-convex optimization: Submodular maximization over continuous domains. In Proceedings of the International Conference on Artificial Intelligence and Statistics , pages 111–120. PMLR, 2017

    work page 2017

Show all 53 references
  1. [8]

    Weakly-supervised alignment of video with text

    Piotr Bojanowski, R´ emi Lajugie, Edouard Grave, Francis Bach, Ivan Laptev, Jean Ponce, and Cordelia Schmid. Weakly-supervised alignment of video with text. In Proceedings of the IEEE International Conference on Computer Vision , pages 4462–4470, 2015

    2015

  2. [9]

    Conditional gradient methods

    G´ abor Braun, Alejandro Carderera, Cyrille W Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods. arXiv preprint arXiv:2211.14103 , 2022

    2022 arXiv

  3. [10]

    Nonnegative tensor comple- tion via integer optimization

    Caleb Xavier Bugg, Chen Chen, and Anil Aswani. Nonnegative tensor comple- tion via integer optimization. In Proceedings of Advances in Neural Information Processing Systems, 2022

    2022

  4. [11]

    Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions

    Alejandro Carderera, Mathieu Besan¸ con, and Sebastian Pokutta. Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions. Proceedings of Advances in Neural Information Processing Systems , 34:5390–5401, 2021

    2021

  5. [12]

    Sublinear optimization for machine learning

    Kenneth L Clarkson, Elad Hazan, and David P Woodruff. Sublinear optimization for machine learning. Journal of the ACM (JACM) , 59(5):1–49, 2012

    2012

  6. [13]

    Complexity of linear minimization and projection on some sets

    Cyrille W Combettes and Sebastian Pokutta. Complexity of linear minimization and projection on some sets. Operations Research Letters, 49(4):565–571, 2021

    2021

  7. [14]

    Conditional gradient algorithms with open loop step size rules

    Joseph C Dunn and S Harshbarger. Conditional gradient algorithms with open loop step size rules. Journal of Mathematical Analysis and Applications , 62(2):432–444, 1978

    1978

  8. [15]

    An algorithm for quadratic programming

    Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2):95–110, 1956. 16

    1956

  9. [16]

    An extended Frank-Wolfe method with “in-face” directions, and its application to low-rank matrix comple- tion

    Robert M Freund, Paul Grigas, and Rahul Mazumder. An extended Frank-Wolfe method with “in-face” directions, and its application to low-rank matrix comple- tion. SIAM Journal on Optimization , 27(1):319–346, 2017

    2017

  10. [17]

    Faster rates for the Frank-Wolfe method over strongly-convex sets

    Dan Garber and Elad Hazan. Faster rates for the Frank-Wolfe method over strongly-convex sets. In Proceedings of the International Conference on Machine Learning. PMLR, 2015

    2015

  11. [18]

    Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes

    Dan Garber and Ofer Meshi. Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. InProceedings of the International Conference on Neural Information Processing Systems , pages 1009–1017. PMLR, 2016

    2016

  12. [19]

    Fast generalized conditional gradient method with applications to matrix recovery problems

    Dan Garber, Shoham Sabach, and Atara Kaplan. Fast generalized conditional gradient method with applications to matrix recovery problems. arXiv preprint arXiv:1802.05581, 3, 2018

    2018 arXiv

  13. [20]

    Conditional gradient type methods for composite nonlinear and stochastic optimization

    Saeed Ghadimi. Conditional gradient type methods for composite nonlinear and stochastic optimization. Mathematical Programming, 173:431–464, 2019

    2019

  14. [21]

    Efficient sparse low-rank tensor completion using the Frank-Wolfe algorithm

    Xiawei Guo, Quanming Yao, and James Kwok. Efficient sparse low-rank tensor completion using the Frank-Wolfe algorithm. In Proceedings of the AAAI Con- ference on Artificial Intelligence , volume 31, 2017

    2017

  15. [22]

    The movielens datasets: History and context

    F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems , 5(4):1–19, 2015

    2015

  16. [23]

    An extension of the Frank and Wolfe method of feasible directions

    Charles A Holloway. An extension of the Frank and Wolfe method of feasible directions. Mathematical Programming, 6(1):14–27, 1974

    1974

  17. [24]

    Robust estimation of a location parameter

    Peter J Huber. Robust estimation of a location parameter. Breakthroughs in statistics: Methodology and distribution , pages 492–518, 1992

    1992

  18. [25]

    Revisiting Frank-Wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceedings of the International Conference on Machine Learning , pages 427–

  19. [26]

    Efficient image and video co- localization with Frank-Wolfe algorithm

    Armand Joulin, Kevin Tang, and Li Fei-Fei. Efficient image and video co- localization with Frank-Wolfe algorithm. In Computer Vision – ECCV 2014 , pages 253–268, Cham, 2014. Springer International Publishing

    2014

  20. [27]

    Projection- free optimization on uniformly convex sets

    Thomas Kerdreux, Alexandre d’Aspremont, and Sebastian Pokutta. Projection- free optimization on uniformly convex sets. In Proceedings of the International Conference on Artificial Intelligence and Statistics , pages 19–27. PMLR, 2021

    2021

  21. [28]

    On the global linear convergence of Frank- Wolfe optimization variants

    Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank- Wolfe optimization variants. In Proceedings of Advances in Neural Information Processing Systems, pages 496–504, 2015

    2015

  22. [29]

    Block- coordinate Frank-Wolfe optimization for structural svms

    Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block- coordinate Frank-Wolfe optimization for structural svms. In Proceedings of the International Conference on Machine Learning , pages 53–61. PMLR, 2013

    2013

  23. [30]

    Sequential kernel herd- ing: Frank-Wolfe optimization for particle filtering

    Simon Lacoste-Julien, Fredrik Lindsten, and Francis Bach. Sequential kernel herd- ing: Frank-Wolfe optimization for particle filtering. In Proceedings of the Interna- tional Conference on Artificial Intelligence and Statistics , pages 544–552. PMLR, 2015. 17

    2015

  24. [31]

    The complexity of large-scale convex programming under a linear optimization oracle

    Guanghui Lan. The complexity of large-scale convex programming under a linear optimization oracle. arXiv preprint arXiv:1309.5550 , 2013

    2013 arXiv

  25. [32]

    Constrained minimization methods

    Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics , 6(5):1–50, 1966

    1966

  26. [33]

    A momentum-guided Frank-Wolfe algorithm

    Bingcong Li, Mario Coutino, Georgios B Giannakis, and Geert Leus. A momentum-guided Frank-Wolfe algorithm. IEEE Transactions on Signal Pro- cessing, 69:3597–3611, 2021

    2021

  27. [34]

    Robust collaborative filtering

    Bhaskar Mehta, Thomas Hofmann, and Wolfgang Nejdl. Robust collaborative filtering. In Proceedings of the ACM Conference on Recommender Systems, pages 49–56, 2007

    2007

  28. [35]

    Learning from video and text via large-scale discriminative clustering

    Antoine Miech, Jean-Baptiste Alayrac, Piotr Bojanowski, Ivan Laptev, and Josef Sivic. Learning from video and text via large-scale discriminative clustering. In Proceedings of the IEEE International Conference on Computer Vision , pages 5257–5266, 2017

    2017

  29. [36]

    Conditional gradient method for stochastic submodular maximization: Closing the gap

    Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Conditional gradient method for stochastic submodular maximization: Closing the gap. In Proceed- ings of the International Conference on Artificial Intelligence and Statistics , pages 1886–1895. PMLR, 2018

    2018

  30. [37]

    Scalable robust ma- trix recovery: Frank–Wolfe meets proximal methods

    Cun Mu, Yuqian Zhang, John Wright, and Donald Goldfarb. Scalable robust ma- trix recovery: Frank–Wolfe meets proximal methods. SIAM Journal on Scientific Computing, 38(5):A3291–A3317, 2016

    2016

  31. [38]

    Complexity bounds for primal-dual methods minimizing the model of objective function

    Yu Nesterov. Complexity bounds for primal-dual methods minimizing the model of objective function. Mathematical Programming, 171(1-2):311–330, 2018

    2018

  32. [39]

    Minding the gaps for block Frank-Wolfe optimization of structured svms

    Anton Osokin, Jean-Baptiste Alayrac, Isabella Lukasewitz, Puneet Dokania, and Simon Lacoste-Julien. Minding the gaps for block Frank-Wolfe optimization of structured svms. In Proceedings of the International Conference on Machine Learning, pages 593–602. PMLR, 2016

    2016

  33. [40]

    Fast stochastic frank-wolfe algorithms for non- linear svms

    Hua Ouyang and Alexander Gray. Fast stochastic frank-wolfe algorithms for non- linear svms. In Proceedings of the 2010 SIAM International Conference on Data Mining, pages 245–256. SIAM, 2010

    2010

  34. [41]

    Step-size adaptivity in projection-free optimization

    Fabian Pedregosa, Armin Askari, Geoffrey Negiar, and Martin Jaggi. Step-size adaptivity in projection-free optimization. arXiv preprint arXiv:1806.05123, 2018

    2018 arXiv

  35. [42]

    Affine invariant convergence rates of the conditional gradient method

    Javier F Pena. Affine invariant convergence rates of the conditional gradient method. SIAM Journal on Optimization , 33(4):2654–2674, 2023

    2023

  36. [43]

    Weakly-supervised learning of visual relations

    Julia Peyre, Josef Sivic, Ivan Laptev, and Cordelia Schmid. Weakly-supervised learning of visual relations. In Proceedings of the IEEE International Conference on Computer Vision , pages 5179–5188, 2017

    2017

  37. [45]

    Background subtraction via fast robust matrix completion

    Behnaz Rezaei and Sarah Ostadabbas. Background subtraction via fast robust matrix completion. In Proceedings of the IEEE International Conference on Com- puter Vision Workshops , pages 1871–1879, 2017. 18

    2017

  38. [46]

    Instance- level video segmentation from object tracks

    Guillaume Seguin, Piotr Bojanowski, R´ emi Lajugie, and Ivan Laptev. Instance- level video segmentation from object tracks. In Proceedings of the IEEE Confer- ence on Computer Vision and Pattern Recognition , pages 3678–3687, 2016

    2016

  39. [47]

    Large-scale convex mini- mization with a low-rank constraint

    Shai Shalev-Shwartz, Alon Gonen, and Ohad Shamir. Large-scale convex mini- mization with a low-rank constraint. arXiv preprint arXiv:1106.1622 , 2011

    2011 arXiv

  40. [48]

    Pairwise conditional gradients without swap steps and sparser kernel herding

    Kazuma K Tsuji, Ken’ichiro Tanaka, and Sebastian Pokutta. Pairwise conditional gradients without swap steps and sparser kernel herding. In Proceedings of the International Conference on Machine Learning, pages 21864–21883. PMLR, 2022

    2022

  41. [49]

    Approximate vanishing ideal computations at scale

    Elias Wirth, Hiroshi Kera, and Sebastian Pokutta. Approximate vanishing ideal computations at scale. In Proceedings of the International Conference on Learning Representations, 2023

    2023

  42. [50]

    Acceleration of Frank- Wolfe algorithms with open-loop step-sizes

    Elias Wirth, Thomas Kerdreux, and Sebastian Pokutta. Acceleration of Frank- Wolfe algorithms with open-loop step-sizes. In Proceedings of the International Conference on Artificial Intelligence and Statistics , pages 77–100. PMLR, 2023

    2023

  43. [51]

    Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes

    Elias Wirth, Javier Pena, and Sebastian Pokutta. Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes. Math- ematical Programming, pages 1–45, 2025

    2025

  44. [52]

    Conditional gradients for the approximately vanishing ideal

    Elias Wirth and Sebastian Pokutta. Conditional gradients for the approximately vanishing ideal. In Proceedings of the International Conference on Artificial In- telligence and Statistics , pages 2191–2209. PMLR, 2022

    2022

  45. [53]

    Convergence theory in nonlinear programming

    Philip Wolfe. Convergence theory in nonlinear programming. Integer and Non- linear Programming, pages 1–36, 1970. 19

    1970

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.