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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2006.08426 [math.OC]

(or arXiv:2006.08426v5 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2006.08426 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.