Introduction
Coordinate Descent (CD) is a cornerstone of large-scale machine learning due to its simplicity and memory efficiency. However, a significant limitation of standard CD methods is the requirement for problem separability. In many practical applications, such as Support Vector Machines (SVMs) or fused Lasso, variables are coupled by linear constraints (e.g., $\sum x_i = 0$ or $Ax = 0$). Modifying a single variable in these cases would violate the constraints.
Historically, solving such problems with CD either restricted the scope to a single constraint or suffered from "pessimistic" iteration complexity that grew exponentially with the number of constraints. This paper introduces a novel randomized CD framework that handles non-separable linear constraints without this exponential penalty.
Methodological Framework: Pairwise Updates
The core innovation is a Randomized Block Coordinate Descent method that maintains feasibility by updating pairs of variable blocks simultaneously.
- Graph-Based Selection: The algorithm views variables as nodes in a "communication graph" $G$. At each iteration, it randomly selects an edge $(i, j)$ from this graph.
- Feasible Sub-problems: It then solves a small sub-problem to update blocks $i$ and $j$ such that the linear constraint $Ax=0$ remains satisfied.
- Versatility: The framework is analyzed across four critical scenarios: smooth objectives, composite objectives (smooth + nonsmooth separable), asynchronous parallel execution, and stochastic optimization for large-scale datasets.
Key Insights and Empirical Behavior
A major theoretical contribution of this work is proving that global iteration complexity does not depend exponentially on the number of constraints. Instead, the authors achieve an $O(1/k)$ convergence rate for smooth problems by leveraging the structure of the constraint matrix $A$.
The choice of communication graph topology significantly influences performance. While a fully connected graph (Clique) offers the fastest theoretical convergence per iteration, it may introduce high computational overhead or contention in parallel environments.
Empirical results on synthetic and LIBSVM datasets demonstrate that sparser topologies, such as "Star + Ring," provide an effective balance between information propagation and update efficiency, reaching acceptable performance with less computational overhead per update.
Parallel Performance and Scalability
In multicore settings, the proposed asynchronous variants—specifically Lock-free and Single-lock implementations—demonstrate near-linear speedup. By ensuring that updates are atomic, the system maintains feasibility ($Ax=0$) even when gradients are calculated based on slightly outdated ("stale") variable states. This allows the algorithm to scale effectively as the number of processors increases, significantly outperforming traditional double-locking synchronous methods.
Conclusion and Future Directions
This framework bridges the gap between the efficiency of coordinate descent and the complexity of linearly constrained optimization. Future work aims to extend asynchronous versions to handle nonsmooth constraints (like box constraints) more robustly, derive high-probability convergence bounds, and explore Nesterov-style acceleration to reach an $O(1/k^2)$ convergence rate.
Summary updated