SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Abstract

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for composite objectives where a proximal operator is used on the regulariser. Unlike SDCA, SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem. We give experimental results showing the effectiveness of our method.

Advances In Neural Information Processing Systems, Nov 2014, Montreal, Canada

References in corpus (2)

• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction

Cited by in corpus (80)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Deep Adaptive Feature Embedding with Local Sample Distributions for Person Re-identification
• AIDE: Fast and Communication Efficient Distributed Optimization
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• A Primer on Coordinate Descent Algorithms
• Accelerated Methods for Non-Convex Optimization
• The proximal point method revisited
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Stochastic, Distributed and Federated Optimization for Machine Learning
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
• A Variance Reduced Stochastic Newton Method
• Proximal-Proximal-Gradient Method
• Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• Estimation of discrete choice models with hybrid stochastic adaptive batch size algorithms
• Variance Reduced methods for Non-convex Composition Optimization
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating
• Stochastic Gradient Descent: Going As Fast As Possible But Not Faster
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• An Adaptive Gradient Method with Energy and Momentum
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Fast Low-Rank Matrix Estimation without the Condition Number
• A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Decentralized Composite Optimization with Compression
• Momentum with Variance Reduction for Nonconvex Composition Optimization
• Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Accelerated Dual-Averaging Primal-Dual Method for Composite Convex Minimization
• Adaptive Stochastic Optimization
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Curvature-aided Incremental Aggregated Gradient Method
• SAGA and Restricted Strong Convexity
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization
• Stochastic Reweighted Gradient Descent
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Joint Sampling and Optimisation for Inverse Rendering
• The Minimax Complexity of Distributed Optimization
• ErrorCompensatedX: error compensation for variance reduced algorithms
• Asynchronous Distributed Optimization with Redundancy in Cost Functions
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• Exploiting the Structure via Sketched Gradient Algorithms
• Accelerated Variance Reduced Block Coordinate Descent
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning
• Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
• Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
• Periodic Q-Learning
• Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
• Nonsmoothness in Machine Learning: specific structure, proximal identification, and applications
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
• ${\bar{G}}_{mst}$:An Unbiased Stratified Statistic and a Fast Gradient Optimization Algorithm Based on It
• Greedy Step Averaging: A parameter-free stochastic optimization method
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• Adaptive Learning Rate and Momentum for Training Deep Neural Networks
• Subsampled online matrix factorization with convergence guarantees
• Stochastic Doubly Robust Gradient
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• A Stochastic Gradient Method with Biased Estimation for Faster Nonconvex Optimization
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning
• An Asynchronous Distributed Framework for Large-scale Learning Based on Parameter Exchanges
• A Multilevel Approach to Training
• A Unified Framework for Stochastic Matrix Factorization via Variance Reduction
• Random gradient extrapolation for distributed and stochastic optimization
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization