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