Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter

Yi Xu, Qihang Lin, Tianbao YangNeurIPS 2017 · OpenReview

Introduction

Stochastic Variance Reduced Gradient (SVRG) methods have become a cornerstone of finite-sum optimization, which is the foundational engine for training most machine learning models. By periodically computing a full gradient to reduce the variance of stochastic updates, SVRG achieves remarkably fast convergence. However, its most desirable property—linear convergence, where the optimization error decays exponentially—traditionally requires the objective function to be strictly "strongly convex."

Unfortunately, many ubiquitous real-world machine learning formulations, such as LASSO or unregularized logistic regression, are convex but lack strong convexity. While these problems often satisfy a relaxed geometric property known as a Quadratic Error Bound (QEB), exploiting this property with SVRG requires knowing a specific, highly elusive "growth parameter." This paper introduces a novel suite of adaptive SVRG algorithms that achieve linear convergence under QEB without requiring prior knowledge of this parameter, effectively solving optimization in the "dark setting."

The Challenge of the "Dark Setting"

In optimization, an Error Bound relates the distance from the current parameters to the optimal solution directly to the current sub-optimality of the objective function. For many non-strongly convex problems, a Quadratic Error Bound (QEB) or a more general Hölderian Error Bound (HEB) holds true.

Theoretical frameworks dictate that SVRG can still achieve linear convergence under QEB, but there is a significant operational catch: the algorithm's inner loop length must be precisely calibrated using the problem's growth parameter ($c$). In practice, this parameter is unknown and computationally prohibitive to estimate. Practitioners are typically forced to rely on sub-optimal heuristics, which can cause the algorithm to stall or converge slowly. The authors refer to this scenario—optimizing under an error bound with an unknown growth parameter—as the "dark setting."

Methodology: The Probabilistic Certificate

To navigate the dark setting, the authors propose adaptive SVRG variants that search for the unknown growth parameter on the fly. The core innovation is a mechanism called the Probabilistic Certificate.

Instead of attempting to directly estimate the growth parameter, the algorithm operates on a simple principle: verification is cheaper than estimation.

  • For QEB ($\theta = 1/2$): The algorithm occasionally performs a full proximal gradient update at a reference point. The norm of this update acts as a "gauge" or certificate. Because SVRG already computes a full gradient at the start of each epoch, this check adds virtually no computational overhead. If the certificate indicates insufficient progress, the algorithm "restarts" and scales up its estimate of the growth parameter.
  • For HEB ($\theta < 1/2$): The authors employ a restarting strategy that geometrically increases the number of inner iterations, ensuring steady progress even under more relaxed error bounds.

Crucially, rigorous theoretical analysis proves that this adaptive searching process only adds a logarithmic factor to the total computational complexity. In other words, the adaptive algorithm is nearly as fast as an "oracle" algorithm that perfectly knows the growth parameter in advance.

Empirical Validation

The authors evaluated their adaptive algorithms (such as SVRG-QEB-RS) against state-of-the-art baselines like SAGA and SVRG++ using standard benchmark datasets from the LIBSVM library, including Adult, YearPredictionMSD, and E2006-tfidf. The tasks spanned $\ell_1$-regularized squared hinge loss, logistic loss, Huber loss, and $\ell_p$ regression.

Key Results: * True Linear Convergence: SVRG-QEB-RS successfully achieved linear convergence on QEB problems without any prior knowledge of the growth parameter. * Robustness and Efficiency: The adaptive method proved highly robust to initialization. Unlike standard SVRG, which stalls if the inner loop is too short, the adaptive version automatically corrects itself. The total number of stochastic gradient computations remained remarkably close to the theoretical minimum. * Superior Performance: The proposed adaptive methods consistently outperformed established baselines across the tested datasets. Furthermore, for the more general HEB case, the adaptive method yielded intermediate convergence rates significantly faster than standard sublinear rates.

Limitations and Future Directions

While the introduction of the probabilistic certificate marks a significant step forward, the authors note a few limitations that pave the way for future research:

  1. Compactness Assumption: The current theoretical analysis assumes optimization occurs over a compact set. While adding a large bounding constraint serves as a practical workaround, extending the proofs to unbounded domains would strengthen the theoretical foundation.
  2. Probabilistic Nature: The certificate is inherently probabilistic, meaning there is a marginal chance it could fail to trigger a necessary parameter increase. Developing deterministic certificates remains an open challenge.
  3. Broader Application: The current framework is tailored to SVRG. Extending this certificate-based adaptive search to other variance-reduction techniques, such as SARAH or Katyusha, could yield a new family of highly robust optimization algorithms.

Conclusion

By demonstrating that the elusive growth parameter can be efficiently bounded on the fly, this research bridges a critical gap between optimization theory and machine learning practice. The proposed adaptive SVRG methods allow practitioners to enjoy the rapid, linear convergence of variance-reduced gradients on a much broader class of real-world problems, all without the burden of manual hyperparameter tuning.

Summary updated

Abstract

Error bound, an inherent property of an optimization problem, has recently revived in the development of algorithms with improved global convergence without strong convexity. The most studied error bound is the quadratic error bound, which generalizes strong convexity and is satisfied by a large family of machine learning problems. Quadratic error bound have been leveraged to achieve linear convergence in many first-order methods including the stochastic variance reduced gradient (SVRG) method, which is one of the most important stochastic optimization methods in machine learning. However, the studies along this direction face the critical issue that the algorithms must depend on an unknown growth parameter (a generalization of strong convexity modulus) in the error bound. This parameter is difficult to estimate exactly and the algorithms choosing this parameter heuristically do not have theoretical convergence guarantee. To address this issue, we propose novel SVRG methods that automatically search for this unknown parameter on the fly of optimization while still obtain almost the same convergence rate as when this parameter is known. We also analyze the convergence property of SVRG methods under H\"{o}lderian error bound, which generalizes the quadratic error bound.
BibTeX
@inproceedings{xu2017adaptive,
  author = {Yi Xu and Qihang Lin and Tianbao Yang},
  title = {{Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=HkW7TOWd-H},
}
Figure