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

2014/07/01 by Aaron Defazio, Francis Bach, Defazio, Aaron +3 · 63 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1407.0202

openalex publication_date 2014/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning

Cited by

• A Convex Loss Function for Set Prediction with Optimal Trade-offs Between Size and Conditional Coverage
• FedOAED: Federated On-Device Autoencoder Denoiser for Heterogeneous Data under Limited Client Availability
• An Additively Preconditioned Trust Region Strategy for Machine Learning
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• Learning to Generate Cross-Task Unexploitable Examples
• OLR-WAA: Adaptive and Drift-Resilient Online Regression with Dynamic Weighted Averaging
• Non-Convex Federated Optimization under Cost-Aware Client Selection
• Variance Matters: Improving Domain Adaptation via Stratified Sampling
• Beyond Scaffold: A Unified Spatio-Temporal Gradient Tracking Method
• SVRG and Beyond via Posterior Correction
• Accelerated Distributional Temporal Difference Learning with Linear Function Approximation
• Sampling and Loss Weights in Multi-Domain Training
• Unified Theory of Adaptive Variance Reduction
• Structured Matrix Scaling for Multi-Class Calibration
• Large-scale empirical tuning and comparison of default optimizers for variational inference
• Nonlinear forward-backward-half forward splitting with momentum for monotone inclusions
• OEUVRE: OnlinE Unbiased Variance-Reduced loss Estimation
• Convergence Analysis of SGD under Expected Smoothness
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization
• MARS-M: When Variance Reduction Meets Matrices
• Bregman Stochastic Proximal Point Algorithm with Variance Reduction
• Personalized Collaborative Learning with Affinity-Based Variance Reduction
• Non-Asymptotic Analysis of Efficiency in Conformalized Regression
• H+: An Efficient Similarity-Aware Aggregation for Byzantine Resilient Federated Learning
• CYCLADES: Conflict-free Asynchronous Machine Learning
• SPRINT: Stochastic Performative Prediction With Variance Reduction
• Do Activation Verbalization Methods Convey Privileged Information?
• Stochastic Gradient Descent with Strategic Querying
• A Multi-Batch L-BFGS Method for Machine Learning
• Polyak Steps for Adaptive Fast Gradient Method
• Improved Rates for Stochastic Variance-Reduced Difference-of-Convex Algorithms
• A Proximal Stochastic Gradient Method with Adaptive Step Size and Variance Reduction for Convex Composite Optimization
• Fast Global Convergence via Landscape of Empirical Loss
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• An Alternative View: When Does SGD Escape Local Minima?
• History-Gradient Aided Batch Size Adaptation for Variance Reduced\n Algorithms
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved\n Complexity
• Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees
• GENO -- GENeric Optimization for Classical Machine Learning
• A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks
• Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
• Jointly Computation- and Communication-Efficient Distributed Learning
• Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs
• Natural Compression for Distributed Deep Learning
• A Universal Catalyst for First-Order Optimization
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization
• An Approximate Shapley-Folkman Theorem
• Decentralized Composite Optimization with Compression
• Detecting COPD Through Speech Analysis: A Dataset of Danish Speech and Machine Learning Approach
• Stochastic Reweighted Gradient Descent
• A Trainable Optimizer
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical\n Risk Minimization via Accumulating Sample Strategy
• EMA Without the Lag: Bias-Corrected Iterate Averaging Schemes
• Decentralized online stochastic generalized Nash Equilibrium seeking for multi-cluster games: A Byzantine-resilient algorithm
• A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
• Stochastic gradient with least-squares control variates
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• A Unified Framework for Stochastic Matrix Factorization via Variance Reduction
• Barzilai-Borwein Step Size for Stochastic Gradient Descent
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Leveraging Sparse Linear Layers for Debuggable Deep Networks
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration

Related

• Fast Incremental Method for Nonconvex Optimization
• SAGA and Restricted Strong Convexity
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• FLAG n' FLARE: Fast Linearly-Coupled Adaptive Gradient Methods
• On the SAGA algorithm with decreasing step