The reviewed record of science sign in
Pith

arxiv: 2605.24819 · v1 · pith:FUT2V7TT · submitted 2026-05-24 · math.OC

Random-Subspace Frank--Wolfe over Strongly Convex Sets

Pierre-Louis Poirion , Sebastian Pokutta , Akiko Takeda This is my paper

Reviewed by Pith2026-06-30 00:18 UTCgrok-4.3pith:FUT2V7TTopen to challenge →

classification math.OC
keywords Frank-Wolfe algorithmprojection-free optimizationrandom subspacesstrongly convex setslinear minimization oracleconvergence ratessmooth convex optimization
0
0 comments X

The pith

Frank-Wolfe methods achieve standard rates by replacing full-space linear minimization oracles with exact oracles over random low-dimensional affine sections of strongly convex sets.

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

The paper presents random-subspace Frank-Wolfe, which runs linear minimization over random affine sections of the feasible set rather than the full ambient space. For smooth convex objectives over compact strongly convex sets, a dimension-explicit bound controls the resulting oracle approximation error and yields the classic O(1/k) open-loop rate together with high-probability and almost-sure versions. The same curvature inheritance also produces linear convergence under short steps and a gradient lower bound, and the sublinear theory extends to finite-sum stochastic gradients. Random sections additionally tighten the local quadratic model used for step-size selection via the compressed Hessian.

Core claim

Over compact strongly convex feasible sets, random affine sections inherit sufficient curvature that an exact linear minimization oracle computed on a random d-dimensional section supplies an approximate oracle whose error admits an explicit dimension-dependent bound; this bound is enough to recover the standard sublinear convergence rate for smooth convex problems and the linear rate under short steps.

What carries the argument

Random affine sections of the feasible set, which permit exact low-dimensional linear minimization while preserving ambient feasibility and inheriting strong-convexity curvature bounds.

If this is right

  • The method recovers the standard O(1/k) open-loop rate for smooth convex objectives.
  • High-probability and almost-sure convergence statements follow from the same geometric control.
  • Linear convergence holds when short steps are combined with a gradient lower bound.
  • The sublinear theory extends directly to finite-sum stochastic gradients.
  • For quadratic objectives over balls or ellipsoids the curvature constants become explicit d-by-d quantities from the compressed Hessian.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sectioning technique could be applied to other projection-free algorithms whose bottleneck is the linear minimization oracle.
  • The explicit dimension dependence in the error bound allows a quantitative trade-off between subspace dimension and per-iteration cost.
  • Adaptive step-size rules that use the sampled compressed Hessian become feasible for quadratic problems.
  • Empirical tests on sets with varying curvature strength would isolate how much strong convexity is needed for the rate to hold.

Load-bearing premise

The feasible set must be compact and strongly convex so that random sections inherit enough curvature to bound the linear-minimization approximation error.

What would settle it

A concrete numerical example or analytic counter-example on a convex but not strongly convex set in which the observed convergence rate is strictly worse than O(1/k) or fails to hold with high probability.

Figures

Figures reproduced from arXiv: 2605.24819 by Akiko Takeda, Pierre-Louis Poirion, Sebastian Pokutta.

Figure 1
Figure 1. Figure 1: Numerical illustrations of RSFW. The panels show: smallest feasible short-step constant, section-wise curvature, [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Failure mode of vanilla RSFW outside the smooth strongly convex setting. Left: objective [PITH_FULL_IMAGE:figures/full_fig_p053_2.png] view at source ↗
read the original abstract

Frank--Wolfe methods avoid projections, but over curved feasible regions the full-space linear minimization oracle (LMO) can itself become the computational bottleneck. We introduce random-subspace Frank--Wolfe (RSFW), the first Frank--Wolfe framework, to our knowledge, that replaces the ambient LMO by exact LMOs over random low-dimensional affine sections of a general feasible set, while preserving feasibility in the original space. For smooth convex objectives over compact strongly convex feasible sets, we prove a dimension-explicit approximate-oracle inequality and derive the standard \(O(1/k)\) open-loop rate, with high-probability and almost-sure counterparts. Under short steps and a gradient lower bound, the same geometric control yields linear convergence, and we extend the sublinear theory to finite-sum stochastic gradients. We also show that random sections can improve the local curvature model controlling short steps: for smooth objectives, the quadratic model along a sampled section is governed by the compressed Hessian, yielding computable \(d\times d\) curvature constants for quadratic objectives over balls and ellipsoids. These results provide a geometric theory of oracle-side randomization in projection-free optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces random-subspace Frank-Wolfe (RSFW), replacing the ambient linear minimization oracle with exact LMOs over random low-dimensional affine sections of a compact strongly convex feasible set while preserving feasibility. For smooth convex objectives it claims a dimension-explicit approximate-oracle inequality that yields the standard O(1/k) open-loop rate (with high-probability and almost-sure versions); under short steps and a gradient lower bound the same control gives linear convergence. The sublinear theory is extended to finite-sum stochastic gradients, and random sections are shown to improve the local curvature model via the compressed Hessian, yielding explicit d×d curvature constants for quadratic objectives over balls and ellipsoids.

Significance. If the approximate-oracle inequality holds with constants that remain controlled (at worst polynomially) in ambient dimension d and section dimension m, the work supplies the first geometric theory of oracle-side randomization for projection-free methods over curved sets. The explicit dimension dependence, high-probability/a.s. guarantees, stochastic-gradient extension, and computable curvature constants for quadratic cases would be genuine contributions to the analysis of Frank-Wolfe variants.

major comments (2)
  1. [section deriving the approximate-oracle inequality (referenced in the abstract)] The approximate-oracle inequality (the central technical claim supporting all rates) is stated to follow from compactness plus strong convexity of the feasible set, yet the transfer of the strong-convexity modulus to a uniformly random m-dimensional affine section is not shown to remain bounded independently of d or to degrade at most polynomially; if the effective modulus deteriorates exponentially in d or 1/m the claimed dimension-explicit constants become vacuous for the high-dimensional regime targeted by the paper.
  2. [paragraph on linear convergence under short steps] The linear-convergence claim under short steps and a gradient lower bound inherits the same geometric control, but the interaction between the random-section LMO error and the gradient lower bound is not quantified; without an explicit uniform lower bound on the gradient norm along the random sections the linear rate may fail to hold with the stated probability.
minor comments (2)
  1. Notation for the random affine section and the induced LMO should be introduced with a single consistent symbol rather than multiple ad-hoc abbreviations.
  2. [curvature-model paragraph] The statement that the quadratic model is 'governed by the compressed Hessian' would benefit from an explicit equation relating the section curvature constant to the eigenvalues of the projected Hessian.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments identify points where the geometric control in the approximate-oracle inequality and its consequences for linear convergence require additional explicit justification. We address each comment below and indicate the revisions that will be made.

read point-by-point responses

  1. Referee: [section deriving the approximate-oracle inequality (referenced in the abstract)] The approximate-oracle inequality (the central technical claim supporting all rates) is stated to follow from compactness plus strong convexity of the feasible set, yet the transfer of the strong-convexity modulus to a uniformly random m-dimensional affine section is not shown to remain bounded independently of d or to degrade at most polynomially; if the effective modulus deteriorates exponentially in d or 1/m the claimed dimension-explicit constants become vacuous for the high-dimensional regime targeted by the paper.

    Authors: We agree that an explicit argument controlling the strong-convexity modulus of a random m-dimensional affine section is necessary to make the dimension dependence fully rigorous. The current derivation in the section on the approximate-oracle inequality invokes strong convexity of the ambient set but does not supply a separate lemma quantifying the worst-case degradation of the modulus under uniform random sampling of the section. We will insert such a lemma (with a polynomial-in-d, polynomial-in-1/m lower bound obtained via concentration on the Grassmannian and compactness) in the revised manuscript. This will confirm that the constants in the O(1/k) and high-probability statements remain dimension-explicit as claimed. revision: yes

  2. Referee: [paragraph on linear convergence under short steps] The linear-convergence claim under short steps and a gradient lower bound inherits the same geometric control, but the interaction between the random-section LMO error and the gradient lower bound is not quantified; without an explicit uniform lower bound on the gradient norm along the random sections the linear rate may fail to hold with the stated probability.

    Authors: The linear-convergence argument combines the approximate-oracle inequality with a uniform gradient lower bound to obtain a contraction. While the high-probability control on the LMO error is already dimension-explicit, the manuscript does not verify that the gradient lower bound remains valid (with comparable probability) when restricted to the random sections. We will add a short argument showing that, under the standing compactness and smoothness assumptions, the set of sections on which the restricted gradient norm drops below the global lower bound has measure decaying exponentially in m; this restores the claimed linear rate with high probability. A minor adjustment to the probability statement will be made accordingly. revision: partial

Circularity Check

0 steps flagged

No circularity: proofs rest on standard geometric assumptions

full rationale

The paper derives an approximate-oracle inequality and O(1/k) rates from compactness and strong convexity of the feasible set, with the random-section curvature control following directly from those properties. No step reduces by the paper's own equations to a fitted quantity, self-definition, or load-bearing self-citation; the central claims remain independent of the target results and are not renamed empirical patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard mathematical assumptions of smoothness and strong convexity of the feasible set; no free parameters, invented entities, or ad-hoc axioms are introduced beyond those.

axioms (2)
  • domain assumption The objective is smooth and convex; the feasible set is compact and strongly convex.
    Invoked to guarantee that random affine sections inherit curvature sufficient for the approximate-oracle inequality.
  • standard math Standard results on Frank-Wolfe convergence over convex sets.
    Used as background to derive the O(1/k) rate from the new oracle inequality.

pith-pipeline@v0.9.1-grok · 5733 in / 1390 out tokens · 29649 ms · 2026-06-30T00:18:37.826160+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references

  1. [1]

    A note on the Hanson–Wright inequality for random vectors with dependencies

    Radosław Adamczak. A note on the Hanson–Wright inequality for random vectors with dependencies. Electronic Communications in Probability, 20(72):1–13, 2015

    2015

  2. [2]

    Searching for exotic particles in high-energy physics with deep learning

    Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature Communications, 5:4308, 2014

    2014

  3. [3]

    Covertype

    Jock Blackard. Covertype. UCI Machine Learning Repository, 1998

    1998

  4. [4]

    Covertype

    Jock Blackard. Covertype. UCI Machine Learning Repository, 1998. Dataset; licensed under CC BY 4.0

    1998

  5. [5]

    Projection free methods on product domains

    Immanuel Bomze, Francesco Rinaldi, and Damiano Zeffiro. Projection free methods on product domains. Computational Optimization and Applications, 91:511–540, 2025

    2025

  6. [6]

    Bomze, Francesco Rinaldi, and Damiano Zeffiro

    Immanuel M. Bomze, Francesco Rinaldi, and Damiano Zeffiro. Frank–Wolfe and friends: A journey into projection-free first-order optimization methods. Annals of Operations Research, 343:607–638, 2024

    2024

  7. [7]

    Blended conditional gradients: The unconditioning of conditional gradients

    G´abor Braun, Sebastian Pokutta, Dan Tu, and Stephen Wright. Blended conditional gradients: The unconditioning of conditional gradients. In Proceedings of the 36th International Confer- ence on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 735–743. PMLR, 2019

    2019

  8. [8]

    Lazifying conditional gradient algorithms

    G´abor Braun, Sebastian Pokutta, and Daniel Zink. Lazifying conditional gradient algorithms. In Doina Precup and Yee Whye Teh, editors,Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 566–575. PMLR, 2017

    2017

  9. [9]

    Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings

    Coralia Cartis, Estelle Massart, and Adilet Otemissov. Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings. Mathematical Programming, 198:997–1058, 2023

    2023

  10. [10]

    Global optimization using random embeddings

    Coralia Cartis, Estelle Massart, and Adilet Otemissov. Global optimization using random embeddings. Mathematical Programming, 200:781–829, 2023

    2023

  11. [11]

    Scalable subspace methods for derivative-free nonlinear least-squares optimization

    Coralia Cartis and Lindon Roberts. Scalable subspace methods for derivative-free nonlinear least-squares optimization. Mathematical Programming, 199(1–2):461–524, 2023

    2023

  12. [12]

    Combettes and Sebastian Pokutta

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

    2021

  13. [13]

    Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition

    Michał Derezi´nski and Elizaveta Rebrova. Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition. SIAM Journal on Mathematics of Data Science, 6(1):127–153, 2024

    2024

  14. [14]

    Faster one-sample stochastic conditional gradient method for composite con- vex minimization

    Gideon Dresdner, Maria-Luiza Vladarean, Gunnar R¨atsch, Francesco Locatello, V olkan Cevher, and Alp Yurtsever. Faster one-sample stochastic conditional gradient method for composite con- vex minimization. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, ...

    2022

  15. [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

    1956

  16. [16]

    Theoretical analysis of the random- ized subspace regularized Newton method for non-convex optimization

    Terunari Fuji, Pierre-Louis Poirion, and Akiko Takeda. Theoretical analysis of the random- ized subspace regularized Newton method for non-convex optimization. Open Journal of Mathematical Optimization, 6(8):1–35, 2025

    2025

  17. [17]

    Faster projection-free convex optimization over the spectrahedron

    Dan Garber. Faster projection-free convex optimization over the spectrahedron. In Advances in Neural Information Processing Systems 29, pages 874–882. Curran Associates, Inc., 2016

    2016

  18. [18]

    A randomized linearly convergent Frank-Wolfe-type method for smooth convex minimization over the spectrahedron

    Dan Garber. A randomized linearly convergent Frank-Wolfe-type method for smooth convex minimization over the spectrahedron. Mathematical Programming, 2026. Published online 13 April 2026

    2026

  19. [19]

    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 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 541–549. PMLR, 2015

    2015

  20. [20]

    Gower and Peter Richt´arik

    Robert M. Gower and Peter Richt´arik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36(4):1660–1690, 2015

    2015

  21. [21]

    Projection-free online learning

    Elad Hazan and Satyen Kale. Projection-free online learning. In Proceedings of the 29th International Conference on Machine Learning, pages 521–528, 2012

    2012

  22. [22]

    Variance-reduced and projection-free stochastic optimization

    Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1263–1271. PMLR, 2016

    2016

  23. [23]

    Revisiting Frank-Wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceed- ings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 427–435. PMLR, 2013

    2013

  24. [24]

    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 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 19–27. PMLR, 2021

    2021

  25. [25]

    Affine invariant analysis of Frank-Wolfe on strongly convex sets

    Thomas Kerdreux, Lewis Liu, Simon Lacoste-Julien, and Damien Scieur. Affine invariant analysis of Frank-Wolfe on strongly convex sets. In Marina Meila and Tong Zhang, editors,Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 5398–5408. PMLR, 2021

    2021

  26. [26]

    A stochastic subspace approach to gradient-free optimization in high dimensions

    David Kozak, Stephen Becker, Alireza Doostan, and Luis Tenorio. A stochastic subspace approach to gradient-free optimization in high dimensions. Computational Optimization and Applications, 79(2):339–368, 2021

    2021

  27. [27]

    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 Advances in Neural Information Processing Systems 28, pages 496– 504, 2015

    2015

  28. [28]

    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 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 53–61. PMLR, 2013

    2013

  29. [29]

    Adaptive and oblivious randomized subspace methods for high-dimensional optimization: Sharp analysis and lower bounds

    Jonathan Lacotte and Mert Pilanci. Adaptive and oblivious randomized subspace methods for high-dimensional optimization: Sharp analysis and lower bounds. IEEE Transactions on Information Theory, 68(5):3281–3303, 2022

    2022

  30. [30]

    High-dimensional optimization in adaptive random subspaces

    Jonathan Lacotte, Mert Pilanci, and Marco Pavone. High-dimensional optimization in adaptive random subspaces. In Advances in Neural Information Processing Systems 32, pages 10846– 10856, 2019. 11

    2019

  31. [31]

    The Concentration of Measure Phenomenon , volume 89 of Mathematical Surveys and Monographs

    Michel Ledoux. The Concentration of Measure Phenomenon , volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001

    2001

  32. [32]

    Stochastic Frank-Wolfe for composite convex minimization

    Francesco Locatello, Alp Yurtsever, Olivier Fercoq, and V olkan Cevher. Stochastic Frank-Wolfe for composite convex minimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alch´e Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 14246–14256. Curran Associates, Inc., 2019

    2019

  33. [33]

    Muirhead

    Robb J. Muirhead. Aspects of Multivariate Statistical Theory. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York, 1982

    1982

  34. [34]

    A framework for Bayesian optimization in embedded subspaces

    Amin Nayebi, Alexander Munteanu, and Matthias Poloczek. A framework for Bayesian optimization in embedded subspaces. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4752–4761. PMLR, 2019

    2019

  35. [35]

    Randomized sketch descent methods for non-separable linearly constrained optimization

    Ion Necoara and Martin Tak´aˇc. Randomized sketch descent methods for non-separable linearly constrained optimization. IMA Journal of Numerical Analysis, 41(2):1056–1092, 2021

    2021

  36. [36]

    Tsai, Laurent El Ghaoui, Francesco Locatello, Robert Freund, and Fabian Pedregosa

    Geoffrey N´egiar, Gideon Dresdner, Alicia Y . Tsai, Laurent El Ghaoui, Francesco Locatello, Robert Freund, and Fabian Pedregosa. Stochastic Frank-Wolfe for constrained finite-sum minimization. In Hal Daum ´e III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Res...

    2020

  37. [37]

    Efficiency of coordinate descent methods on huge-scale optimization problems

    Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341–362, 2012

    2012

  38. [38]

    Linearly convergent Frank-Wolfe with backtracking line-search

    Fabian Pedregosa, Geoffrey Negiar, Armin Askari, and Martin Jaggi. Linearly convergent Frank-Wolfe with backtracking line-search. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1–10. PMLR, 2020

    2020

  39. [39]

    Wainwright

    Mert Pilanci and Martin J. Wainwright. Randomized sketches of convex programs with sharp guarantees. IEEE Transactions on Information Theory, 61(9):5096–5115, 2015

    2015

  40. [40]

    Wainwright

    Mert Pilanci and Martin J. Wainwright. Iterative hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 17(53):1– 38, 2016

    2016

  41. [41]

    Wainwright

    Mert Pilanci and Martin J. Wainwright. Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205–245, 2017

    2017

  42. [42]

    Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

    Peter Richt´arik and Martin Tak´aˇc. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming, 144(1–2):1–38, 2014

    2014

  43. [43]

    Improved convergence analysis of lasserre’s measure-based upper bounds for polynomial minimization on compact sets

    Lucas Slot and Monique Laurent. Improved convergence analysis of lasserre’s measure-based upper bounds for polynomial minimization on compact sets. Mathematical Programming, 193:831–871, 2022

    2022

  44. [44]

    Stich, Christian L

    Sebastian U. Stich, Christian L. M¨uller, and Bernd G¨artner. Optimization of convex functions with random pursuit. SIAM Journal on Optimization, 23(2):1284–1309, 2013

    2013

  45. [45]

    ´Etude Critique de la Notion de Collectif

    Jean Ville. ´Etude Critique de la Notion de Collectif . Gauthier-Villars, Paris, 1939. Ville’s inequality appears on p. 100

    1939

  46. [46]

    Bayesian op- timization in high dimensions via random embeddings

    Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, and Nando de Freitas. Bayesian op- timization in high dimensions via random embeddings. InProceedings of the Twenty-Third Inter- national Joint Conference on Artificial Intelligence, pages 1778–1784. AAAI Press/International Joint Conferences on Artificial Intelligence, 2013. 12

    2013

  47. [47]

    Daniel Whiteson. HIGGS. UCI Machine Learning Repository, 2014. Dataset; licensed under CC BY 4.0

    2014

  48. [48]

    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 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 77–100. PMLR, 2023

    2023

  49. [49]

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

    Elias Wirth, Javier Pe ˜na, and Sebastian Pokutta. Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes. Mathematical Programming, 214:201–245, 2025

    2025

  50. [50]

    Splitting the conditional gradient algorithm

    Zev Woodstock and Sebastian Pokutta. Splitting the conditional gradient algorithm. SIAM Journal on Optimization, 35(1):347–368, 2025

    2025

  51. [51]

    Sketchy decisions: Convex low-rank matrix optimization with optimal storage

    Alp Yurtsever, Madeleine Udell, Joel Tropp, and V olkan Cevher. Sketchy decisions: Convex low-rank matrix optimization with optimal storage. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , volume 54 of Proceedings of Machine Learning Research, pages 1188–1196. PMLR, 2017

    2017

  52. [52]

    Approximate Frank-Wolfe algorithms over graph-structured support sets

    Baojian Zhou and Yifan Sun. Approximate Frank-Wolfe algorithms over graph-structured support sets. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 27303–27337. PMLR, 2022. 13 Appendix roadmap. Appendix A discusses additional related work. Appendix B collects the determi...

    2022

  53. [53]

    S ∈ (0, 1) almost surely and S ∼ Beta d 2 , n−d 2 . (52)

  54. [54]

    T ∈ [−1, 1] is independent of S and satisfies E[T ] = 0, E[T 2] = 1 n − 1 , E[T 4] = 3 (n − 1)(n + 1). (53)

  55. [55]

    If d ≤ n − 2, then B ∼ Beta d−1 2 , n−d−1 2 , while if d = n − 1, we use the degenerate convention B ≡ 1

    B is independent of (S, T). If d ≤ n − 2, then B ∼ Beta d−1 2 , n−d−1 2 , while if d = n − 1, we use the degenerate convention B ≡ 1

  56. [56]

    (55) 21 Proof

    Defining α := ρ √ S + σ √ 1 − S T, (54) one has X = α2 + σ2(1 − T 2)B. (55) 21 Proof. By Lemma 3, applied to the pair (e1, e2), there exist independent random variables (R, T, B) such that R ∼ Beta d 2 , n−d 2 , with the same degenerate convention B ≡ 1 when d = n − 1. E[T ] = 0, E[T 2] = 1 n − 1 , E[T 4] = 3 (n − 1)(n + 1), and ∥P e1∥2 = R, (56) ⟨P e1, P...