Optimization with First-Order Surrogate Functions

Abstract

In this paper, we study optimization methods consisting of iteratively minimizing surrogates of an objective function. By proposing several algorithmic variants and simple convergence analyses, we make two main contributions. First, we provide a unified viewpoint for several first-order optimization techniques such as accelerated proximal gradient, block coordinate descent, or Frank-Wolfe algorithms. Second, we introduce a new incremental scheme that experimentally matches or outperforms state-of-the-art solvers for large-scale optimization problems typically arising in machine learning.

to appear in the proceedings of ICML 2013; the arxiv paper contains the 9 pages main text followed by 26 pages of supplemental material. International Conference on Machine Learning (ICML 2013) (2013)

References in corpus (4)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Proximal Stochastic Dual Coordinate Ascent
• Projection-free Online Learning

Cited by in corpus (39)

• Robust Aggregation for Federated Learning
• Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
• Federated Multi-Task Learning under a Mixture of Distributions
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• Stop Wasting My Gradients: Practical SVRG
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
• A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA
• A globally convergent incremental Newton method
• Stochastic Subsampling for Factorizing Huge Matrices
• A Random Block-Coordinate Douglas-Rachford Splitting Method with Low Computational Complexity for Binary Logistic Regression
• Universal gradient descent
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Block Alternating Bregman Majorization Minimization with Extrapolation
• Reducing the variance in online optimization by transporting past gradients
• Online matrix factorization for Markovian data and applications to Network Dictionary Learning
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Stochastic Subspace Descent
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• An Inertial Block Majorization Minimization Framework for Nonsmooth Nonconvex Optimization
• MISO is Making a Comeback With Better Proofs and Rates
• Adaptive Step Sizes in Variance Reduction via Regularization
• Subspace Clustering by Block Diagonal Representation
• MAP Clustering under the Gaussian Mixture Model via Mixed Integer Nonlinear Optimization
• On the Convergence of SARAH and Beyond
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Composite Difference-Max Programs for Modern Statistical Estimation Problems
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• Non-convex optimization via strongly convex majoirziation-minimization
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• A Multilevel Approach to Training
• Variance Reduction in Deep Learning: More Momentum is All You Need
• Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent
• Truncated Inference for Latent Variable Optimization Problems: Application to Robust Estimation and Learning
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning
• Optimal Combination of Image Denoisers