Abstract
Frank-Wolfe algorithm (FW) and its variants have gained a surge of interests in machine learning community due to its projection-free property. Recently people have reduced the gradient evaluation complexity of FW algorithm to $\log(\frac{1}{\epsilon})$ for the smooth and strongly convex objective. This complexity result is especially significant in learning problem, as the overwhelming data size makes a single evaluation of gradient computational expensive. However, in high-dimensional statistical estimation problems, the objective is typically not strongly convex, and sometimes even non-convex. In this paper, we extend the state-of-the-art FW type algorithms for the large-scale, high-dimensional estimation problem. We show that as long as the objective satisfies restricted strong convexity, and we are not optimizing over statistical limit of the model, the $\log(\frac{1}{\epsilon})$ gradient evaluation complexity could still be attained.
1. Introduction
In high-dimensional statistical estimation, researchers often seek to recover structured parameters—such as sparse vectors or low-rank matrices—from high-dimensional observations. Traditionally, this is achieved through structural risk minimization using Projected Gradient Descent (PGD). However, PGD faces a significant computational bottleneck: the projection step. For instance, in nuclear norm regularization, the projection requires a full Singular Value Decomposition (SVD), which is computationally prohibitive for large-scale datasets.
The Frank-Wolfe (FW) algorithm offers a "projection-free" alternative by utilizing a Linear Oracle (LO) instead of a projection. For matrix problems, the LO only requires finding the leading singular vector, a much cheaper operation. Despite this advantage, traditional FW algorithms suffer from slow $O(1/\epsilon)$ convergence. While modern variants like Conditional Gradient Sliding (CGS) have achieved logarithmic convergence, they previously required global strong convexity—a property rarely found in high-dimensional settings where the number of features $p$ often exceeds the sample size $n$.
2. Methodology
This work extends the analysis of fast projection-free algorithms to the regime of Restricted Strong Convexity (RSC). RSC is a standard assumption in statistical theory where the objective function behaves as if it were strongly convex, but only along specific "structured" directions (e.g., towards the sparse or low-rank solution).
We analyze two primary algorithms under this framework:
- Conditional Gradient Sliding (CGS): A batch algorithm that combines Nesterov’s acceleration with Frank-Wolfe steps to solve the projection subproblem approximately.
- Stochastic Variance Reduced Conditional Gradient Sliding (STORC): A stochastic variant that employs SVRG-style variance reduction to minimize full gradient evaluations.
The key innovation lies in proving that RSC is sufficient to unlock the $O(\log 1/\epsilon)$ gradient complexity previously reserved for globally strongly convex functions. Furthermore, the analysis is extended to non-convex losses, which are prevalent in robust statistics and matrix regression with noisy sensing matrices.
3. Results and Discussion
Theoretical analysis shows that CGS and STORC maintain high efficiency in high-dimensional regimes:
- Gradient Complexity: CGS achieves $O(n \sqrt{L/\hat{\sigma}} \log(1/\epsilon))$ evaluations, while STORC achieves $O((n + (L/\hat{\sigma})^2) \log(1/\epsilon))$ for convex losses.
- Linear Oracle Efficiency: Both algorithms maintain an optimal $O(LD^2/\epsilon)$ complexity for linear oracle calls.
Empirical evaluations were conducted using synthetic Matrix Regression simulations, recovering low-rank matrices with up to 90,000 parameters. The results demonstrate that STORC and CGS consistently outperform projection-based methods like SVRG and PGD in wall-clock time. This speedup is attributed to the Linear Oracle's efficiency; computing a top singular vector via the power method is orders of magnitude faster than a full SVD. Additionally, the algorithms proved robust to non-convexity, handling lower-smooth functions with minimal computational overhead.
4. Conclusion
By bridging the gap between optimization theory and high-dimensional statistics, this paper demonstrates that projection-free algorithms can achieve fast convergence rates without the need for global strong convexity. The use of Restricted Strong Convexity allows these algorithms to reach the statistical limit of a model with significantly reduced computational cost. Future work may explore automated parameter tuning and the application of these methods to non-decomposable constraint sets in massive real-world datasets.
Summary updated