Projection-Free Adaptive Gradients for Large-Scale Optimization

2020/09/29 by Combettes, Cyrille W., Spiegel, Christoph, Pokutta, Sebastian · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2009.14114

Abstract

The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization.

Cited by

• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe

Related

• Frank-Wolfe Style Algorithms for Large Scale Optimization
• A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization
• Scalable Projection-Free Optimization
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features
• Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization