A Unifying Perspective on Descent Directions for Constrained Minimization and Switching Criteria

Abstract

Descent directions are fundamental to first-order methods for constrained convex optimization. In this work, we provide a unified perspective of these directions as they arise within the projected and conditional gradient methods. We show that the directional derivative of the Euclidean projection of the negative gradient is the steepest feasible descent direction, and induces a natural optimality measure independent of polytope-specific geometric constants. We characterize the properties of the projection of the gradient over the polytope, and show that Frank-Wolfe vertices are essentially the limit of this projection curve. Motivated by these insights, we develop hybrid algorithms that interpolate between projected gradient descent and conditional gradients, using computable switching criteria. The proposed methods achieve linear convergence without relying on the pyramidal width or similar constants. We further show that the number of breakpoints in the projection curve over the simplex and the hypercube is linear in the dimension.

References in corpus (7)

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
• A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe
• Conditional Accelerated Lazy Stochastic Gradient Descent
• Blended Conditional Gradients: the unconditioning of conditional gradients
• Boosting Frank-Wolfe by Chasing Gradients
• A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition