A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization

Abstract

We introduce a new approach to develop stochastic optimization algorithms for a class of stochastic composite and possibly nonconvex optimization problems. The main idea is to combine two stochastic estimators to create a new hybrid one. We first introduce our hybrid estimator and then investigate its fundamental properties to form a foundational theory for algorithmic development. Next, we apply our theory to develop several variants of stochastic gradient methods to solve both expectation and finite-sum composite optimization problems. Our first algorithm can be viewed as a variant of proximal stochastic gradient methods with a single-loop, but can achieve $\mathcal{O}({\sigma }^3{\epsilon }^{-1}+\sigma {\epsilon }^{-3})$-oracle complexity bound, matching the best-known ones from state-of-the-art double-loop algorithms in the literature, where $\sigma >0$ is the variance and $\epsilon$ is a desired accuracy. Then, we consider two different variants of our method: adaptive step-size and restarting schemes that have similar theoretical guarantees as in our first algorithm. We also study two mini-batch variants of the proposed methods. In all cases, we achieve the best-known complexity bounds under standard assumptions. We test our methods on several numerical examples with real datasets and compare them with state-of-the-arts. Our numerical experiments show that the new methods are comparable and, in many cases, outperform their competitors.

arXiv comment49 pages, 2 tables, 9 figures

References in corpus (25)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• A Universal Catalyst for First-Order Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Convergence rates of sub-sampled Newton methods
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Neon2: Finding Local Minima via First-Order Oracles
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• A Lower Bound for the Optimization of Finite Sums
• SEGA: Variance Reduction via Gradient Sketching
• Escaping Saddle Points in Constrained Optimization
• Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• When Does Stochastic Gradient Algorithm Work Well?
• Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization
• On Biased Stochastic Gradient Estimation
• Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization

Cited by in corpus (6)

• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization