Optimal First-Order Algorithms as a Function of Inequalities

Abstract

In this work, we present a novel algorithm design methodology that finds the optimal algorithm as a function of inequalities. Specifically, we restrict convergence analyses of algorithms to use a prespecified subset of inequalities, rather than utilizing all true inequalities, and find the optimal algorithm subject to this restriction. This methodology allows us to design algorithms with certain desired characteristics. As concrete demonstrations of this methodology, we find new state-of-the-art accelerated first-order gradient methods using randomized coordinate updates and backtracking line searches.

References in corpus (8)

• Optimized first-order methods for smooth convex minimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Generalizing the optimized gradient method for smooth convex minimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums