<p>Recent papers have shown that the Frank–Wolfe algorithm (<Emphasis FontCategory="NonProportional">FW</Emphasis>) with open-loop step-sizes exhibits rates of convergence faster than the iconic <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}(t^{-1})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>t</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rate. In particular, when the minimizer of a strongly convex function over a polytope lies on the boundary of the polytope, the <Emphasis FontCategory="NonProportional">FW</Emphasis> algorithm with open-loop step-sizes <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\eta _t = \frac{\ell }{t+\ell }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>η</mi> <mi>t</mi> </msub> <mo>=</mo> <mfrac> <mi>ℓ</mi> <mrow> <mi>t</mi> <mo>+</mo> <mi>ℓ</mi> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\ell \in \mathbb {N}_{\ge 2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>∈</mo> <msub> <mi mathvariant="double-struck">N</mi> <mrow> <mo>≥</mo> <mn>2</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> has accelerated convergence <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {O}(t^{-2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>t</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in contrast to the rate <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\Omega (t^{-1-\epsilon })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>t</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo>-</mo> <mi>ϵ</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> attainable with more complex line-search or short-step step-sizes. Given the relevance of this scenario in data science problems, research has grown to explore the settings enabling acceleration in open-loop <Emphasis FontCategory="NonProportional">FW</Emphasis>. However, despite <Emphasis FontCategory="NonProportional">FW</Emphasis>’s well-known affine invariance, existing acceleration results for open-loop <Emphasis FontCategory="NonProportional">FW</Emphasis> are affine-dependent. This paper remedies this gap in the literature, by merging two recent research trajectories: affine invariance (Peña in SIAM J. Optim. 33(4):2654–2674, 2023) and open-loop step-sizes (Wirth et al. in Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023). In particular, we extend all known non-affine-invariant convergence rates for <Emphasis FontCategory="NonProportional">FW</Emphasis> with open-loop step-sizes to affine-invariant results.</p>

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

期刊论文
出版模式：

开放获取
发表日期：

2025年1月6日

查看全文

Elias Wirth,
Javier Peña,
Sebastian Pokutta

摘要

Recent papers have shown that the Frank–Wolfe algorithm (FW) with open-loop step-sizes exhibits rates of convergence faster than the iconic $\mathcal {O}(t^{-1})$ $O (t^{- 1})$ rate. In particular, when the minimizer of a strongly convex function over a polytope lies on the boundary of the polytope, the FW algorithm with open-loop step-sizes $\eta _t = \frac{\ell }{t+\ell }$ $η_{t} = \frac{ℓ}{t + ℓ}$ for $\ell \in \mathbb {N}_{\ge 2}$ $ℓ \in N_{\geq 2}$ has accelerated convergence $\mathcal {O}(t^{-2})$ $O (t^{- 2})$ in contrast to the rate $\Omega (t^{-1-\epsilon })$ $Ω (t^{- 1 - ϵ})$ attainable with more complex line-search or short-step step-sizes. Given the relevance of this scenario in data science problems, research has grown to explore the settings enabling acceleration in open-loop FW. However, despite FW’s well-known affine invariance, existing acceleration results for open-loop FW are affine-dependent. This paper remedies this gap in the literature, by merging two recent research trajectories: affine invariance (Peña in SIAM J. Optim. 33(4):2654–2674, 2023) and open-loop step-sizes (Wirth et al. in Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023). In particular, we extend all known non-affine-invariant convergence rates for FW with open-loop step-sizes to affine-invariant results.