Frank Wolfe Meets Metric Entropy
This addresses a theoretical bottleneck in optimization for machine learning and statistics, providing lower bounds that challenge assumptions about Frank-Wolfe's efficiency, with implications for algorithms like gradient boosting and matching pursuit.
The paper tackles the problem of establishing when the Frank-Wolfe algorithm can achieve dimension-free linear iteration complexity, showing that for Gaussian or spherical random polytopes with poly(d) vertices, it requires up to Ω̃(d) iterations to achieve O(1/d) error with high probability, and also establishes this for the nuclear norm ball.
The Frank-Wolfe algorithm has seen a resurgence in popularity due to its ability to efficiently solve constrained optimization problems in machine learning and high-dimensional statistics. As such, there is much interest in establishing when the algorithm may possess a "linear" $O(\log(1/ε))$ dimension-free iteration complexity comparable to projected gradient descent. In this paper, we provide a general technique for establishing domain specific and easy-to-estimate lower bounds for Frank-Wolfe and its variants using the metric entropy of the domain. Most notably, we show that a dimension-free linear upper bound must fail not only in the worst case, but in the \emph{average case}: for a Gaussian or spherical random polytope in $\mathbb{R}^d$ with $\mathrm{poly}(d)$ vertices, Frank-Wolfe requires up to $\tildeΩ(d)$ iterations to achieve a $O(1/d)$ error bound, with high probability. We also establish this phenomenon for the nuclear norm ball. The link with metric entropy also has interesting positive implications for conditional gradient algorithms in statistics, such as gradient boosting and matching pursuit. In particular, we show that it is possible to extract fast-decaying upper bounds on the excess risk directly from an analysis of the underlying optimization procedure.