Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps
This provides a more efficient optimization method for machine learning practitioners dealing with generalized self-concordant functions, though it is incremental as it builds on existing Frank-Wolfe frameworks.
The paper tackles the problem of optimizing generalized self-concordant functions, common in learning tasks, by proposing a simple Frank-Wolfe variant with an open-loop step size, achieving a $\mathcal{O}(1/t)$ convergence rate for primal and Frank-Wolfe gaps without needing second-order information or parameter estimation.
Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy $γ_t = 2/(t+2)$, obtaining a $\mathcal{O}(1/t)$ convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where $t$ is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.