Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization

Yi Zhou, Zhe Wang, Kaiyi Ji, Yingbin Liang, Vahid TarokharXiv 2019 · DOI · arXiv

TL;DR

This paper introduces novel momentum-accelerated algorithms for nonconvex composite optimization, specifically enhancing the SPIDER variance-reduction technique. The proposed methods achieve near-optimal theoretical convergence rates and demonstrate superior practical performance compared to existing algorithms, particularly in challenging nonsmooth and online optimization settings.

What Problem Does This Paper Address?

Many real-world machine learning problems involve optimizing complex, non-convex functions that also include non-smooth regularization terms. While recent algorithms like SPIDER offer theoretical guarantees for finding "good enough" solutions (first-order stationary points) in these scenarios, their practical performance often doesn't significantly outperform older methods like SVRG. This gap suggests that simply having a theoretically optimal gradient estimator isn't enough for practical speedup. The challenge is to effectively combine these advanced variance-reduction techniques with acceleration methods like momentum, which have historically been designed for simpler, convex problems and don't directly translate to the nonconvex, non-smooth setting. Furthermore, existing momentum schemes often require specific properties of the regularizer (like being bounded), limiting their applicability.

Methods

The core contribution is the development of Proximal SPIDER-M, a new algorithm that integrates momentum into the SPIDER framework for nonconvex composite optimization. Key aspects include:

  • Novel Momentum Scheme: The authors design a flexible momentum scheme that is compatible with SPIDER's variance reduction and works for arbitrary convex regularizers (including non-smooth ones with unbounded domains). This is a significant departure from prior work that was restricted to bounded regularizers.
  • Coupled Updates: The algorithm features a coupled update for its internal variables, which is more computationally efficient than separate updates in some existing momentum methods.
  • Generalized Gradient: To handle non-smooth regularizers, the paper uses a generalized notion of gradient based on proximal mappings.
  • Variants for Flexibility: Two specific momentum scheduling strategies are proposed:
  • Epochwise-diminishing Momentum: The momentum coefficient decreases gradually over epochs, allowing for more consistent acceleration.
  • Epochwise-restart Momentum: The momentum is reset at the beginning of each epoch, injecting periodic acceleration.
  • Online Extension: The framework is extended to handle online optimization problems, where data is processed sequentially and the objective is based on an underlying data distribution rather than a fixed finite set.

Datasets

The paper uses standard datasets for evaluation:

  • LIBSVM datasets: a9a and w8a for logistic regression and robust linear regression tasks.

Key Insights and Ideas

  • Momentum is Crucial for Practical SPIDER: While SPIDER offers theoretical advantages, momentum is shown to be essential for unlocking its practical performance benefits in nonconvex settings.
  • Bridging Convex and Nonconvex Momentum: The paper successfully adapts momentum techniques, traditionally used for convex optimization, to the more challenging nonconvex composite optimization landscape, overcoming prior limitations.
  • Regularizer Flexibility is Key: The proposed momentum scheme's ability to handle arbitrary convex regularizers (including non-smooth and unbounded ones) significantly broadens its applicability in real-world machine learning.
  • Momentum Scheduling Matters: Different momentum scheduling strategies (iteration-wise, epoch-wise diminishing, epoch-wise restart) have a tangible impact on performance, with epoch-wise diminishing momentum showing particular promise.
  • Online Optimization Benefits: The extension to online settings demonstrates that momentum can also accelerate SPIDER in scenarios with streaming data, achieving state-of-the-art oracle complexity.

Key Results

  • Theoretical Guarantees: Proximal SPIDER-M achieves a generalized first-order stationary condition with near-optimal stochastic gradient oracle complexity of $O(n + \sqrt{n}\epsilon^{-2})$ for finite-sum problems and $O(\epsilon^{-3})$ for online problems, matching state-of-the-art bounds.
  • Experimental Performance: Extensive experiments show that the proposed Proximal SPIDER-M algorithms (especially with epochwise-diminishing momentum) significantly outperform other variance-reduced algorithms (SVRG, SARAH variants, Katyushas, ASVRG, etc.) in terms of convergence speed on both un-regularized and regularized nonconvex problems.
  • Efficiency: The coupled update in the momentum scheme leads to reduced computational overhead.

Limitations and Future Work

  • Convex Optimization: The authors suggest exploring whether their algorithm can achieve the best possible convergence rate in convex optimization.
  • Advanced Momentum Schemes: They anticipate their design will inspire further development of more advanced momentum acceleration schemes for stochastic nonconvex optimization.
  • Manifold Optimization: While mentioned in the related work, the current paper focuses on Euclidean space. Extending these momentum schemes to optimization on manifolds for nonconvex problems could be a future direction.

Summary updated

Abstract

Two new stochastic variance-reduced algorithms named SARAH and SPIDER have been recently proposed, and SPIDER has been shown to achieve a near-optimal gradient oracle complexity for nonconvex optimization. However, the theoretical advantage of SPIDER does not lead to substantial improvement of practical performance over SVRG. To address this issue, momentum technique can be a good candidate to improve the performance of SPIDER. However, existing momentum schemes used in variance-reduced algorithms are designed specifically for convex optimization, and are not applicable to nonconvex scenarios. In this paper, we develop novel momentum schemes with flexible coefficient settings to accelerate SPIDER for nonconvex and nonsmooth composite optimization, and show that the resulting algorithms achieve the near-optimal gradient oracle complexity for achieving a generalized first-order stationary condition. Furthermore, we generalize our algorithm to online nonconvex and nonsmooth optimization, and establish an oracle complexity result that matches the state-of-the-art. Our extensive experiments demonstrate the superior performance of our proposed algorithm over other stochastic variance-reduced algorithms.
BibTeX
@misc{zhou2019momentum,
  author = {Yi Zhou and Zhe Wang and Kaiyi Ji and Yingbin Liang and Vahid Tarokh},
  title = {{Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization}},
  year = {2019},
  eprint = {1902.02715},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.02715},
}
Figure