Introduction
Coordinate Descent (CD) is a cornerstone of large-scale machine learning due to its simplicity and scalability. However, its application is traditionally limited to problems with separable constraints. When variables are coupled by linear constraints (e.g., $\sum x_i = 0$), standard CD fails because updating a single coordinate violates feasibility. This paper introduces a novel randomized CD framework that handles non-separable linear constraints without the exponential complexity seen in prior attempts.
Problem Statement
The core challenge addressed is the "Achilles' heel" of CD: handling constraints like $Ax=0$. Previous solutions often required expensive projections or suffered from theoretical complexity that grew exponentially with the number of constraints ($m$). This work aims to provide a scalable, $O(1/k)$ convergent CD method for constrained optimization.
Proposed Framework: Randomized Block Coordinate Descent
The authors propose updating pairs of blocks $(i, j)$ simultaneously. By selecting pairs based on a communication graph $G$, the algorithm ensures that updates satisfy $A_i d_i + A_j d_j = 0$, maintaining feasibility throughout the optimization process.
The framework is highly versatile, supporting smooth, composite (e.g., $L_1$ regularized), asynchronous parallel, and stochastic optimization variants. As shown in the comparison below, this approach is the first to simultaneously address linear constraints (LC), proximal steps (Prox), parallelization, and stochasticity.
Theoretical Insights
A key contribution is breaking the "exponential curse." The authors prove a global iteration complexity of $O(1/k)$, removing the dependence on $O(b^m/\epsilon)$. Furthermore, they establish a link between the convergence rate and the spectral gap of the communication graph's Laplacian. Denser graphs like a "Clique" converge in fewer iterations, though they may introduce hardware contention in parallel environments.
Experimental Results
Evaluation on synthetic quadratic problems and LIBSVM datasets (a7a, w8a) confirms the theoretical findings.
Graph Topology and Convergence
Experiments show that the choice of communication graph significantly impacts convergence speed. While a Clique topology is the fastest per iteration, sparser configurations like "Star + Ring" offer a robust balance between convergence and computational overhead.
Parallel Performance
In SVM training tasks, the asynchronous "Lock-free" and "Single-lock" versions achieved near-linear speedups. These methods significantly outperformed traditional "Double-locking" approaches, which are prone to thread contention as the number of processors increases.
Conclusion and Future Work
This framework provides a scalable solution for constrained CD. Future directions include extending asynchronous analysis to non-smooth problems, deriving high-probability convergence bounds, and incorporating Nesterov-style acceleration to reach $O(1/k^2)$ convergence rates.
Summary updated