Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems

Abstract

Recent advances in optimization theory have shown that smooth strongly convex finite sums can be minimized faster than by treating them as a black box "batch" problem. In this work we introduce a new method in this class with a theoretical convergence rate four times faster than existing methods, for sums with sufficiently many terms. This method is also amendable to a sampling without replacement scheme that in practice gives further speed-ups. We give empirical results showing state of the art performance.

References in corpus (4)

• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Optimization with First-Order Surrogate Functions
• Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (54)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• A Universal Catalyst for First-Order Optimization
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Variance Reduction for Faster Non-Convex Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Fixed Point Strategies in Data Science
• A Simple Practical Accelerated Method for Finite Sums
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• SDCA without Duality, Regularization, and Individual Convexity
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• A Generic Acceleration Framework for Stochastic Composite Optimization
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Starting Small -- Learning with Adaptive Sample Sizes
• On the Ineffectiveness of Variance Reduced Optimization for Deep Learning
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Variance-Reduced Stochastic Learning under Random Reshuffling
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• On Biased Stochastic Gradient Estimation
• Trading-off variance and complexity in stochastic gradient descent
• Advances in Asynchronous Parallel and Distributed Optimization
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• Stochastic Subspace Descent
• Random Shuffling Beats SGD after Finite Epochs
• Variance Reduction for Distributed Stochastic Gradient Descent
• MISO is Making a Comeback With Better Proofs and Rates
• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• Federated Stochastic Gradient Langevin Dynamics
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
• A Unifying Framework for Variance Reduction Algorithms for Finding Zeroes of Monotone Operators
• Reducing Runtime by Recycling Samples
• Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
• Dynamic Average Diffusion with randomized Coordinate Updates
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Stochastic Dykstra Algorithms for Metric Learning on Positive Semi-Definite Cone
• A Randomized Nonlinear Rescaling Method in Large-Scale Constrained Convex Optimization
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• Learning with Smooth Hinge Losses
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Lightweight Stochastic Optimization for Minimizing Finite Sums with Infinite Data
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning