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 (44)

• 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
• 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
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• The proximal point method revisited
• Stochastic, Distributed and Federated Optimization for Machine Learning
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• 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
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• Variance Reduced methods for Non-convex Composition Optimization
• Stochastic Gradient Descent: Going As Fast As Possible But Not Faster
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Fast Low-Rank Matrix Estimation without the Condition Number
• A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• SAGA and Restricted Strong Convexity
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Curvature-aided Incremental Aggregated Gradient Method
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization
• Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
• 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
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
• Random gradient extrapolation for distributed and stochastic optimization
• Greedy Step Averaging: A parameter-free stochastic optimization method
• Subsampled online matrix factorization with convergence guarantees
• A Unified Framework for Stochastic Matrix Factorization via Variance Reduction
• An Asynchronous Distributed Framework for Large-scale Learning Based on Parameter Exchanges