We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

math.OC

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Mathematics > Optimization and Control

Title: Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization

Abstract: Descent directions such as movement towards Frank-Wolfe vertices, away steps, in-face away steps and pairwise directions have been an important design consideration in conditional gradient descent (CGD) variants. In this work, we attempt to demystify the impact of movement in these directions towards attaining constrained minimizers. The best local direction of descent is the directional derivative of the projection of the gradient, which we refer to as the $\textit{shadow}$ of the gradient. We show that the continuous-time dynamics of moving in the shadow are equivalent to those of PGD however non-trivial to discretize. By projecting gradients in PGD, one not only ensures feasibility but is also able to "wrap" around the convex region. We show that Frank-Wolfe (FW) vertices in fact recover the maximal wrap one can obtain by projecting gradients, thus providing a new perspective on these steps. We also claim that the shadow steps give the best direction of descent emanating from the convex hull of all possible away-steps. Viewing PGD movements in terms of shadow steps gives linear convergence, dependent on the number of faces. We combine these insights into a novel $S\small{HADOW}$-$CG$ method that uses FW steps (i.e., wrap around the polytope) and shadow steps (i.e., optimal local descent direction), while enjoying linear convergence. Our analysis develops properties of the curve formed by projecting a line on a polytope, which may be of independent interest, while providing a unifying view of various descent directions in the CGD literature.
Subjects: Optimization and Control (math.OC); Machine Learning (cs.LG)
Cite as: arXiv:2006.08426 [math.OC]
  (or arXiv:2006.08426v3 [math.OC] for this version)

Submission history

From: Hassan Mortagy [view email]
[v1] Mon, 15 Jun 2020 14:26:56 GMT (1531kb,D)
[v2] Wed, 24 Feb 2021 18:30:48 GMT (4576kb,D)
[v3] Mon, 11 Oct 2021 13:51:45 GMT (2601kb,D)

Link back to: arXiv, form interface, contact.