Fast Projection-Free Approach (without Linear Minimization Oracle) for Optimization over General Compact Convex Set
Chenghao Liu, Enming Liang, Minghua Chen
Projection-free first-order methods offer compelling advantages for constrained optimization. These methods excel on limited convex sets, demonstrating scalability, fast convergence, and iteration-wise feasibility without projection costs. However, their extension to general convex sets faces significant challenges. For example, Frank-Wolfe methods require linear optimization oracles at each iteration, while penalty-based approaches often exhibit poor solution feasibility. This raises a fundamental question: can projection-free methods be extended to optimization over a general convex set without expensive oracles?We address this challenge by introducing a novel projection-free method: **Hom-PGD**.  It leverages a homeomorphism between the constraint set and a unit ball to transform the original optimization problem into a ball-constrained formulation. This transformation enables efficient projection-free first-order optimization in the transformed space while maintaining the original problem's structure. We establish theoretical guarantees that Hom-PGD achieves *optimal* convergence rates matching gradient descent with constant step-size: $\mathcal{O}(\log 1/\epsilon)$ for strongly convex objectives,$\mathcal{O}(1/\epsilon)$ for convex objectives, and $\mathcal{O}(1/\epsilon^2)$ for non-convex objectives, with $\mathcal{O}(n^2)$ per-iteration complexity. The framework also extends to certain non-convex sets, broadening its applicability to challenging optimization problems. Extensive numerical experiments on both convex and non-convex problems show that Hom-PGD achieves a similar convergence rate but with significantly lower per-iteration time compared with existing projection-free algorithms.This advancement significantly expands the scope of projection-free methods, making them viable for a broader range of constrained optimization applications.