Large-scale randomized-coordinate descent methods with non-separable linear constraints

Sashank J. Reddi, Ahmed Hefny, Carlton Downey, Avinava Dubey, Suvrit Sra

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.

Comparison of the proposed framework with existing literature across different optimization properties.

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.

Convergence of objective value over iterations for different communication graph topologies.

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

Abstract

We develop randomized (block) coordinate descent (CD) methods for linearly\nconstrained convex optimization. Unlike most CD methods, we do not assume the\nconstraints to be separable, but let them be coupled linearly. To our\nknowledge, ours is the first CD method that allows linear coupling constraints,\nwithout making the global iteration complexity have an exponential dependence\non the number of constraints. We present algorithms and analysis for four key\nproblem scenarios: (i) smooth; (ii) smooth + nonsmooth separable; (iii)\nasynchronous parallel; and (iv) stochastic. We illustrate empirical behavior of\nour algorithms by simulation experiments.\n
BibTeX
@inproceedings{reddi2015large,
  author = {Sashank J. Reddi and Ahmed Hefny and Carlton Downey and Avinava Dubey and Suvrit Sra},
  title = {{Large-scale randomized-coordinate descent methods with non-separable linear constraints}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=FfValN8phgZ},
}
Figure