2020/11/06 by Thomas Kerdreux, Kerdreux, Thomas, Lewis Liu +5 · 3 citations
Computer Science · Engineering · #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Robotics and Sensor-Based Localization #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2011.03351
openalex publication_date 2020/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is known that the Frank-Wolfe (FW) algorithm, which is affine-covariant, enjoys accelerated convergence rates when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW's affine-covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function surprisingly converge to an affine invariant step size, despite using affine-dependent norms in the step size's computation. This indicates that we do not necessarily need to know the set's structure in advance to enjoy the affine-invariant accelerated rate.