Projection-Free Algorithms in Statistical Estimation
This work addresses computational efficiency for large-scale, high-dimensional statistical estimation problems, representing an incremental extension of existing methods.
The paper tackles the challenge of applying projection-free Frank-Wolfe algorithms to high-dimensional statistical estimation where objectives are not strongly convex, showing that under restricted strong convexity, a gradient evaluation complexity of log(1/ε) can still be achieved.
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}ε)$ for the smooth and strongly convex objective. This complexity result is especially significant in learning problem, as the overwhelming data size makes a single evluation 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 {\em restricted strong convexity}, and we are not optimizing over statistical limit of the model, the $\log(\frac{1}ε)$ gradient evaluation complexity could still be attained.