Accelerated affine-invariant convergence rates of the Frank–Wolfe algorithm with open-loop step-sizes
研究了弗兰克-沃尔夫算法在开环步长下的收敛速率，将现有非仿射不变结果推广到仿射不变情形，对数据科学中的优化问题有参考价值。
Abstract Recent papers have shown that the Frank–Wolfe algorithm () with open-loop step-sizes exhibits rates of convergence faster than the iconic $$\mathcal {O}(t^{-1})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> rate. In particular, when the minimizer of a strongly convex function over a polytope lies on the boundary of the polytope, the algorithm with open-loop step-sizes $$\eta _t = \frac{\ell }{t+\ell }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mi>ℓ</mml:mi> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:math> for $$\ell \in \mathbb {N}_{\ge 2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>∈</mml:mo> <mml:msub> <mml:mi>N</mml:mi> <mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> has accelerated convergence $$\mathcal {O}(t^{-2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> in contrast to the rate $$\Omega (t^{-1-\epsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 . However, despite ’s well-known affine invariance, existing acceleration results for open-loop 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 with open-loop step-sizes to affine-invariant results.