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

• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization

Cited by in corpus (265)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Stochastic Variance Reduction for Nonconvex Optimization
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• Deep Adaptive Feature Embedding with Local Sample Distributions for Person Re-identification
• Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
• D${}^2$: Decentralized Training over Decentralized Data
• A Universal Catalyst for First-Order Optimization
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Barzilai-Borwein Step Size for Stochastic Gradient Descent
• Variance Reduction for Faster Non-Convex Optimization
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Online Learning with Inexact Proximal Online Gradient Descent Algorithms
• AIDE: Fast and Communication Efficient Distributed Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Stochastic Gradient Descent as Approximate Bayesian Inference
• Not All Samples Are Created Equal: Deep Learning with Importance Sampling
• Fixed Point Strategies in Data Science
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Natural Compression for Distributed Deep Learning
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• A Progressive Batching L-BFGS Method for Machine Learning
• A Simple Practical Accelerated Method for Finite Sums
• Supervised Learning Under Distributed Features
• A Primer on Coordinate Descent Algorithms
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• Stochastic Dual Ascent for Solving Linear Systems
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Stochastic Averaging for Constrained Optimization with Application to Online Resource Allocation
• Second-Order Stochastic Optimization for Machine Learning in Linear Time
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• A globally convergent incremental Newton method
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• An Alternative View: When Does SGD Escape Local Minima?
• An optimal randomized incremental gradient method
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Analysis of Stochastic Gradient Descent in Continuous Time
• RENT -- Repeated Elastic Net Technique for Feature Selection
• 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
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Towards Riemannian Accelerated Gradient Methods
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
• Learning in Wireless Control Systems over Non-Stationary Channels
• A Variance Reduced Stochastic Newton Method
• Proximal-Proximal-Gradient Method
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Recent theoretical advances in decentralized distributed convex optimization
• Linearly convergent stochastic heavy ball method for minimizing generalization error
• A Multi-Batch L-BFGS Method for Machine Learning
• Importance Sampling for Minibatches
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Stochastic Learning Approach to Binary Optimization for Optimal Design of Experiments
• Optimal mini-batch and step sizes for SAGA
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Feature-Distributed SVRG for High-Dimensional Linear Classification
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• Machine learning methods for constructing probabilistic Fermi-LAT catalogs
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales
• Estimation of discrete choice models with hybrid stochastic adaptive batch size algorithms
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• (Corrected Version) Push-LSVRG-UP: Distributed Stochastic Optimization over Unbalanced Directed Networks with Uncoordinated Triggered Probabilities
• Inertial Stochastic PALM (iSPALM) and Applications in Machine Learning
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Variance-Reduced Stochastic Learning under Random Reshuffling
• Variance Reduced methods for Non-convex Composition Optimization
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• Stochastic Gradient Descent: Going As Fast As Possible But Not Faster
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating
• Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Towards closing the gap between the theory and practice of SVRG
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• An Adaptive Gradient Method with Energy and Momentum
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• GENO -- GENeric Optimization for Classical Machine Learning
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• When Does Stochastic Gradient Algorithm Work Well?
• Faster Learning by Reduction of Data Access Time
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Trading-off variance and complexity in stochastic gradient descent
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• Analysis of regularized federated learning
• Stochastic Second-Order Optimization via von Neumann Series
• Stochastic Stein Discrepancies
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication
• An Approximate Shapley-Folkman Theorem
• A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity
• Random Shuffling Beats SGD after Finite Epochs
• Exact Gauss-Newton Optimization for Training Deep Neural Networks
• Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Almost Tune-Free Variance Reduction
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• An Analysis of Stochastic Variance Reduced Gradient for Linear Inverse Problems
• Fast Low-Rank Matrix Estimation without the Condition Number
• The Speed-Robustness Trade-Off for First-Order Methods with Additive Gradient Noise
• Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identification
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Stochastic Algorithms for Self-consistent Calculations of Electronic Structures
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Linear convergence of SDCA in statistical estimation
• Stochastic Variance-Reduced ADMM
• Tracking the gradients using the Hessian: A new look at variance reducing stochastic methods
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
• Adaptive Stochastic Optimization
• Momentum with Variance Reduction for Nonconvex Composition Optimization
• Accelerated Dual-Averaging Primal-Dual Method for Composite Convex Minimization
• Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient
• On the Convergence of SARAH and Beyond
• Speed learning on the fly
• Learning and Management for Internet-of-Things: Accounting for Adaptivity and Scalability
• On the Acceleration of L-BFGS with Second-Order Information and Stochastic Batches
• DynaNewton - Accelerating Newton's Method for Machine Learning
• Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
• Decentralized Composite Optimization with Compression
• Stochastic quasi-Newton with adaptive step lengths for large-scale problems
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Noisy Accelerated Power Method for Eigenproblems with Applications
• A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Accelerating Convergence of Replica Exchange Stochastic Gradient MCMC via Variance Reduction
• Stochastic Reweighted Gradient Descent
• Extragradient with player sampling for faster Nash equilibrium finding
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
• A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
• SAGA and Restricted Strong Convexity
• SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization
• Leveraging Sparse Linear Layers for Debuggable Deep Networks
• First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization
• Curvature-aided Incremental Aggregated Gradient Method
• A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems
• Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithms
• k-SVRG: Variance Reduction for Large Scale Optimization
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Convergence analysis of stochastic higher-order majorization-minimization algorithms
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis
• SMG: A Shuffling Gradient-Based Method with Momentum
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD
• Bregman Monotone Operator Splitting
• Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
• Joint Sampling and Optimisation for Inverse Rendering
• Asynchronous Distributed Optimization with Redundancy in Cost Functions
• ErrorCompensatedX: error compensation for variance reduced algorithms
• The Minimax Complexity of Distributed Optimization
• Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization
• Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
• A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• Periodic Q-Learning
• Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
• Optimising cost vs accuracy of decentralised analytics in fog computing environments
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Exploiting the Structure via Sketched Gradient Algorithms
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback
• Convergence of variational Monte Carlo simulation and scale-invariant pre-training
• Random-reshuffled SARAH does not need a full gradient computations
• Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• Bounding the expected run-time of nonconvex optimization with early stopping
• Accelerated Variance Reduced Block Coordinate Descent
• Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• ${\bar{G}}_{mst}$:An Unbiased Stratified Statistic and a Fast Gradient Optimization Algorithm Based on It
• Fast Global Convergence via Landscape of Empirical Loss
• An Asynchronous Distributed Framework for Large-scale Learning Based on Parameter Exchanges
• A Unified Framework for Stochastic Matrix Factorization via Variance Reduction
• Adaptive Learning Rate and Momentum for Training Deep Neural Networks
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• IS-ASGD: Accelerating Asynchronous SGD using Importance Sampling
• Stochastic Primal-Dual Method for Empirical Risk Minimization with $\mathcal{O}(1)$ Per-Iteration Complexity
• Greedy Step Averaging: A parameter-free stochastic optimization method
• Projection-Free Algorithms in Statistical Estimation
• Approximate and Stochastic Greedy Optimization
• Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors
• Lightweight Stochastic Optimization for Minimizing Finite Sums with Infinite Data
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
• A Multilevel Approach to Training
• Variance Reduction in Deep Learning: More Momentum is All You Need
• Fast Nonsmooth Regularized Risk Minimization with Continuation
• Subsampled online matrix factorization with convergence guarantees
• Random gradient extrapolation for distributed and stochastic optimization
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
• Learn-and-Adapt Stochastic Dual Gradients for Network Resource Allocation
• Stochastic Doubly Robust Gradient
• SGD with Variance Reduction beyond Empirical Risk Minimization
• Scalable Peaceman-Rachford Splitting Method with Proximal Terms
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization
• Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Nonsmoothness in Machine Learning: specific structure, proximal identification, and applications
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• A Stochastic Gradient Method with Biased Estimation for Faster Nonconvex Optimization
• Accelerated Kaczmarz Algorithms using History Information
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning
• Towards Better Generalization: BP-SVRG in Training Deep Neural Networks
• Pushing on Text Readability Assessment: A Transformer Meets Handcrafted Linguistic Features
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates