1. Reducing Discretization Error in the Frank-Wolfe Method
- Author
-
Chen, Zhaoyue and Sun, Yifan
- Subjects
Mathematics - Optimization and Control ,Computer Science - Artificial Intelligence ,Computer Science - Machine Learning - Abstract
The Frank-Wolfe algorithm is a popular method in structurally constrained machine learning applications, due to its fast per-iteration complexity. However, one major limitation of the method is a slow rate of convergence that is difficult to accelerate due to erratic, zig-zagging step directions, even asymptotically close to the solution. We view this as an artifact of discretization; that is to say, the Frank-Wolfe \emph{flow}, which is its trajectory at asymptotically small step sizes, does not zig-zag, and reducing discretization error will go hand-in-hand in producing a more stabilized method, with better convergence properties. We propose two improvements: a multistep Frank-Wolfe method that directly applies optimized higher-order discretization schemes; and an LMO-averaging scheme with reduced discretization error, and whose local convergence rate over general convex sets accelerates from a rate of $O(1/k)$ to up to $O(1/k^{3/2})$., Comment: The 26th International Conference on Artificial Intelligence and Statistics (AISTATS) 2023. arXiv admin note: text overlap with arXiv:2205.11794
- Published
- 2023