RSG: Beating Subgradient Method without Smoothness and Strong Convexity

Tianbao Yang, Qihang LinJMLR 2018

TL;DR

This paper introduces a "Restarted SubGradient" (RSG) method that significantly speeds up optimization for non-smooth, non-strongly convex problems. RSG achieves this by periodically restarting the standard subgradient method with a geometrically decreasing step size, leading to lower iteration complexity than traditional methods, especially for problems with specific "local error bound" properties.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly in machine learning, involve objective functions that are not smooth (they have sharp corners or kinks) and not strongly convex (meaning the minimum might not be unique or the function might be relatively flat around the minimum). The standard "subgradient method" (SG) is a common tool for these problems, but it can be very slow, requiring a number of iterations that grows quadratically with the initial distance to the optimal solution. While some methods offer improvements for specific cases (like smooth or strongly convex functions), there's a need for faster general-purpose methods that can handle the more challenging non-smooth, non-strongly convex scenarios. This paper aims to bridge that gap by developing a faster algorithm that still works for a broad class of these difficult problems.

Methods

The core innovation is the Restarted SubGradient (RSG) method. Instead of running the standard subgradient method continuously, RSG breaks the optimization process into stages. At the end of each stage, the algorithm "restarts" with a new, smaller step size, effectively resetting some of the convergence dependencies. This restart strategy, combined with a geometric decrease in step size across stages, allows RSG to achieve better theoretical convergence guarantees.

The analysis of RSG's effectiveness relies heavily on a concept called a "local error bound condition." This condition essentially quantifies how quickly the objective function value approaches its minimum as you get closer to the optimal solution. By exploiting this condition, the authors can derive tighter bounds on the number of iterations needed. They also introduce a variant called R2SG that can be implemented without knowing certain parameters of the local error bound, making it more practical.

Datasets

The paper uses standard machine learning datasets for evaluation, including:

  • Housing data: Used for robust regression.
  • Space-ga data: Used for robust regression.
  • DNA data: Used for SVM classification.
  • MovieLens 100k data: Used for matrix completion.

These are publicly available datasets commonly used in machine learning benchmarks.

Key Insights and Ideas

  • Restarting is powerful, even without strong convexity: The paper demonstrates that the simple idea of restarting an algorithm can yield significant improvements even when the objective function lacks strong convexity, a common assumption for fast convergence.
  • Local error bounds are key: The theoretical improvements of RSG are deeply tied to the "local error bound condition." This highlights the importance of understanding the local geometry of the objective function near the optimum, not just its global properties.
  • Bridging the gap between theory and practice: The development of R2SG, which doesn't require knowing specific parameters of the local error bound, is a crucial step towards making these theoretical advances practically applicable.
  • RSG's convergence depends on the "distance to the e-level set," not the initial point: A significant theoretical insight is that RSG's iteration complexity depends on the distance from the current iterate to the e-level set (the set of points with objective value close to the optimum), rather than the distance from the initial solution to the optimum. This is a much smaller and more relevant quantity for convergence.

Key Results

  • Improved Iteration Complexity: For general convex problems, RSG achieves an iteration complexity of $O(\log(1/\epsilon))$, which is a significant improvement over the standard SG method's $O(1/\epsilon^2)$.
  • Linear Convergence for Polyhedral Problems: When the problem's epigraph is a polyhedron, RSG achieves linear convergence, $O(\log(1/\epsilon))$.
  • Faster Convergence under Specific Conditions: RSG demonstrates improved convergence rates (e.g., $O(\log(1/\epsilon))$) for problems satisfying local quadratic growth or a local Kurdyka-Łojasiewicz property.
  • Empirical Validation: Experiments on robust regression, SVM classification, and matrix completion show that RSG and its variants (like R2SG) consistently outperform the standard SG method in terms of convergence speed and accuracy, especially when dealing with challenging datasets. R2SG also shows less sensitivity to initial solutions compared to SG.

Limitations and Future Work

  • Parameter Sensitivity: While RSG offers theoretical improvements, its practical performance can depend on tuning parameters like the number of iterations per stage ($t$). The R2SG variant addresses the need to know parameters related to the local error bound, but some tuning might still be necessary.
  • "Local" vs. "Global" Error Bounds: The analysis primarily relies on local error bounds. Extending these results to global error bounds would be a valuable future direction.
  • Specific Problem Classes: While RSG is general, its most significant improvements are seen under specific conditions (like local error bounds). Exploring its performance on a wider range of non-smooth, non-strongly convex problems is an ongoing area.
  • Comparison with Other Advanced Methods: The paper compares RSG to SG and a few other methods. Further comparisons with state-of-the-art algorithms for specific problem types could provide more context.
  • Stochastic Variants: The paper focuses on deterministic subgradient methods. Extending RSG to stochastic settings (where gradients are estimated from data) is a natural and important next step.

Summary updated

BibTeX
@article{yang2018rsg,
  author = {Tianbao Yang and Qihang Lin},
  title = {{RSG: Beating Subgradient Method without Smoothness and Strong Convexity}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
}
Figure