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:
a9aandw8afor 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