Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization

Sudeep Salgia, Qing Zhao, Sattar Vakili

Overview

This paper introduces Progressive Coordinate Minimization (PCM), a novel framework that brings the efficiency of coordinate minimization to the noisy world of stochastic optimization. By carefully controlling the precision of each coordinate-wise search—increasing it as the algorithm progresses—the authors achieve order-optimal regret while maintaining the low communication overhead that makes coordinate methods highly attractive for large-scale distributed systems.

The Challenge of Stochastic Optimization

In large-scale machine learning, we frequently deal with "stochastic" optimization: we don't have access to the true objective function $f(x)$, but rather noisy snapshots of it (such as the loss from a single data point).

Two common approaches to solve this are Stochastic Gradient Descent (SGD) and Stochastic Coordinate Descent (SCD). SCD is particularly popular for its scalability; it picks one direction (coordinate) at a time and takes a small step. However, in deterministic optimization, there is a more powerful alternative called Coordinate Minimization (CM). Instead of taking one tiny step, CM stays on a single coordinate until it finds the absolute minimum for that direction before moving to the next.

The catch? In a stochastic setting, finding the "exact" minimum along a coordinate is impossible due to inherent noise. If an algorithm spends too much time on one coordinate, it wastes resources fitting to noise; if it spends too little, it fails to converge. This paper directly addresses this "how long should I stay here?" dilemma.

Progressive Coordinate Minimization (PCM)

To solve this, the authors propose the PCM framework, which consists of three main components:

  1. A Low-Dimensional Routine ($v$): An algorithm (like SGD) used to solve the optimization problem along a single coordinate.
  2. A Termination Rule ($\tau$): A "stop" signal that dictates when the algorithm has reached a specific precision level for that coordinate.
  3. Progressive Precision ($\epsilon_k$): The core innovation. Instead of aiming for the same accuracy every time, the algorithm demands higher precision ($\epsilon_k$) as the iteration count ($k$) increases.

The most significant theoretical contribution of the paper is the Universal Optimal Precision Control. The authors prove that setting the precision to decay geometrically ($\epsilon_k = \epsilon_0 \gamma^k$) is optimal. Remarkably, this specific decay rate is universally effective, regardless of which low-dimensional solver is used under the hood.

Key Insights

  • The "Aha" Moment on Precision: Because the optimal progression of precision across iterations is independent of the specific low-dimensional routine employed, practitioners can swap out the internal solver (e.g., using a robust Random Walk on a Tree instead of SGD) without redesigning the high-level precision schedule.
  • Minimization vs. Descent: The paper highlights a crucial distinction for distributed computing. Coordinate Descent (CD) switches coordinates after every step, leading to high "message exchange" costs. PCM (based on Minimization) switches coordinates sublinearly, making it vastly more efficient for distributed architectures where communication is a bottleneck.
  • Robustness via RWT: By plugging in a "Random Walk on a Tree" (RWT) routine as the solver, the framework becomes self-adaptive to unknown function characteristics (like the exact degree of smoothness), a scenario where standard SGD often struggles without heavy hyperparameter tuning.

Experimental Results

The authors evaluated their framework using the MNIST dataset, framing the task as a binary "one-vs-rest" classification problem with a regularized hinge loss.

Theoretical Optimality: The authors prove that PCM achieves "order-optimal" regret. For strongly convex functions, it hits a regret order of $O(\log T)$, which is the gold standard for these types of optimization problems.

Empirical Superiority: In the MNIST experiments, PCM significantly outperformed the standard online version of Stochastic Coordinate Descent (SCD).

Regret vs. Time for PCM and SCD across different MNIST digit classifications.

As demonstrated in the plots above, PCM achieves lower cumulative regret much faster than SCD across various digit classifications. Because PCM stays on a coordinate for multiple steps to reach its precision target, it requires fewer "switches" between coordinates, confirming its empirical and communication efficiency.

Limitations and Future Work

Currently, the PCM framework is specifically tailored for strongly convex and separably non-smooth functions (where the non-smooth part can be broken down coordinate-by-coordinate, such as with $L_1$ regularization).

Extending this framework to general convex functions or non-convex landscapes remains an open challenge. The optimal design of the precision sequence for these broader classes of functions is not yet known and forms a primary direction for ongoing research. Additionally, while the paper establishes strong theoretical and empirical foundations, a full-scale implementation on a massive distributed cluster would be the next logical step to prove its real-world engineering impact.

Summary updated

Abstract

A framework based on iterative coordinate minimization (CM) is developed for stochastic convex optimization. Given that exact coordinate minimization is impossible due to the unknown stochastic nat...
BibTeX
@inproceedings{salgia2020stochastic,
  author = {Sudeep Salgia and Qing Zhao and Sattar Vakili},
  title = {{Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=e0VQCA_qQJl},
}
Figure