Better Mini-Batch Algorithms via Accelerated Gradient Methods

Abstract

Mini-batch algorithms have been proposed as a way to speed-up stochastic convex optimization problems. We study how such algorithms can be improved using accelerated gradient methods. We provide a novel analysis, which shows how standard gradient methods may sometimes be insufficient to obtain a significant speed-up and propose a novel accelerated gradient algorithm, which deals with this deficiency, enjoys a uniformly superior guarantee and works well in practice.

Cited by in corpus (42)

• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Communication Complexity of Distributed Convex Learning and Optimization
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Sub-Sampled Newton Methods II: Local Convergence Rates
• On perturbed proximal gradient algorithms
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• Federated Accelerated Stochastic Gradient Descent
• Indefinite Kernel Logistic Regression with Concave-inexact-convex Procedure
• Learning From An Optimization Viewpoint
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Distantly Supervised Relation Extraction via Recursive Hierarchy-Interactive Attention and Entity-Order Perception
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• Faster Learning by Reduction of Data Access Time
• A Novel Framework for Online Supervised Learning with Feature Selection
• Generalization Properties of Doubly Stochastic Learning Algorithms
• A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity
• Optimal Mini-Batch Size Selection for Fast Gradient Descent
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Matrix Factorization with Explicit Trust and Distrust Relationships
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Accelerating Mini-batch SARAH by Step Size Rules
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Never Go Full Batch (in Stochastic Convex Optimization)
• The Minimax Complexity of Distributed Optimization
• SPAN: A Stochastic Projected Approximate Newton Method
• Trajectory Normalized Gradients for Distributed Optimization
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning
• Stochastic dual averaging methods using variance reduction techniques for regularized empirical risk minimization problems
• Automatic, Dynamic, and Nearly Optimal Learning Rate Specification by Local Quadratic Approximation
• Efficient Distance Metric Learning by Adaptive Sampling and Mini-Batch Stochastic Gradient Descent (SGD)
• GWU NLP Lab at SemEval-2019 Task 3: EmoContext: Effective Contextual Information in Models for Emotion Detection in Sentence-level in a Multigenre Corpus
• Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays
• Conditions for Convergence in Regularized Machine Learning Objectives