PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Coordinate Descent Methods for Big Data Optimization

Peter Richtárik, Martin Takáč

arXiv:1212.0873v2math.OCcs.AIstat.ML

TL;DR

The paper asks when parallel coordinate descent can accelerate optimization of partially separable composite objectives. It develops randomized parallel block methods and an expected separable overapproximation analysis, then demonstrates the approach on a billion-variable LASSO problem solved in 2 hours on 24 cores.

  • Problem

    Huge-scale convex optimization requires algorithms that can exploit parallel hardware while preserving coordinate descent's scalability.

  • Method

    The paper develops randomized parallel block coordinate descent methods for partially separable smooth convex functions plus simple separable convex regularizers, analyzed using expected separable overapproximation.

  • Results

    2 hours on 24 cores reduced a billion-variable LASSO problem's objective gap from 10^22 to 10^-14.

  • Takeaways & Limitations

    Parallel coordinate descent can accelerate objectives that are sufficiently close to separable, with speedup governed by separability and processor count.

  • Takeaways & Limitations

    For general regularizers, PCDM2 may be needed when PCDM1 monotonicity cannot be analyzed, but its safeguard introduces too much overhead.

Abstract

from arXiv · show

In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural and easily computable measure of separability of the smooth component of the objective function. In the worst case, when no degree of separability is present, there may be no speedup; in the best case, when the problem is separable, the speedup is equal to the number of processors. Our analysis also works in the mode when the number of blocks being updated at each iteration is random, which allows for modeling situations with busy or unreliable processors. We show that our algorithm is able to solve a LASSO problem involving a matrix with 20 billion nonzeros in 2 hours on a large memory node with 24 cores.

1 Introduction

The paper studies parallel coordinate descent for large convex optimization problems, asking when objective structure makes parallelization accelerate computation. It focuses on partially separable smooth terms with separable convex regularization and reports a large-scale LASSO experiment.

  • Parallelization: Parallelization is presented as necessary for truly huge-scale problems, complementing the scalability of serial coordinate descent methods.The motivation is tied to multi-core processors, GPU accelerators, and clusters.
  • Research Idea: The central question is which natural, verifiable structural assumptions on the objective guarantee acceleration from parallel coordinate descent.
  • Research Idea: The paper gives explicit speedup formulae, with acceleration increasing as the smooth objective becomes more separable.The authors state that problems close to separable are amenable to parallel acceleration.
  • Minimizing a partially separable composite objective: The objective combines a partially separable smooth convex function with a simple separable convex function that can encode constraints or structures such as sparsity.The regularizer is assumed proper and closed, and the problem is assumed to have a finite minimum.
  • Minimizing a partially separable composite objective: Partial separability measures how component functions depend on subsets of variable blocks, and the algorithms require only its degree ω rather than the underlying decomposition.The degree satisfies 1 ≤ ω ≤ n.

2 Parallel Block Coordinate Descent Methods

The paper develops two parallel block coordinate descent methods that randomly select blocks, compute separable updates, and use expected separable overapproximation to support their analysis. A regularized variant enforces monotonicity when needed, though the authors caution that its overhead can be excessive.

  • Block structure: The block structure decomposes the variables into non-overlapping blocks represented through a permutation of the identity matrix.This permits blocks formed from nonconsecutive coordinates and supports comparing multiple decompositions.
  • Algorithms: Two generic methods are developed: PCDM1 and the regularized PCDM2, with variants determined by how the block update is performed.
  • Block sampling: Each iteration randomly selects a set of blocks for parallel updating, using iid realizations of a sampling distribution.Uniform samplings give every block the same selection probability, and some subclasses receive sharper results.
  • Algorithmic update: Updates minimize a block-separable model involving the separable regularizer and parameters β and w.The resulting update can be computed block by block, with simple regularizers supporting closed-form solutions.
  • Expected Separable Overapproximation: Expected Separable Overapproximation provides the separable quadratic upper model for the expected smooth objective after a random block update.The paper introduces ESO as a principal tool for complexity analysis.
  • Algorithmic variants: PCDM2 rejects an update when it increases the objective, addressing cases where PCDM1 monotonicity cannot be established for general regularizers.The authors do not recommend implementing PCDM2 because the monotonicity safeguard can add too much overhead.

3 Smmary of Contributions

The paper develops a general parallel coordinate descent framework for partially separable composite objectives, with complexity guarantees, sampling flexibility, and computational validation. Its analysis characterizes speedup through separability and supports both standard and unreliable parallel-update settings.

  • Problem generality: The paper gives the first complexity analysis for parallel coordinate descent methods on the full partially separable composite problem.The results provide iteration bounds for producing an approximately optimal random iterate with high probability under an Expected Separable Overapproximation condition.
  • ESO and formulas: Expected Separable Overapproximation is introduced as the main theoretical tool for analyzing the proposed methods.The framework develops deterministic and expected separable overapproximation theory and uses it to select parameters for different samplings.
  • Algorithm unification: The framework unifies known and new algorithms and continuously interpolates between serial coordinate descent and gradient methods.This interpolation is controlled by the block structure and the expected number of selected blocks per iteration.
  • Choice of blocks: The methods allow general uniform samplings, including variable update counts that model busy or unreliable processors.Doubly uniform and binomial samplings can represent processors that compute updates only with probability p_b.
  • Parallelization speedup: Theoretical speedup depends on the degree of partial separability: it is n when ω = 1 and may be absent when ω = n.For fully parallel sampling, the speedup is expressed through n and ω; increasing parallel updates lowers one complexity term while increasing β can reduce the gain.
  • Computations: A 24-core experiment solved a LASSO problem with 2 billion rows and 1 billion columns in 2 hours, achieving a 20× speedup over the serial variant.The experiment used an artificial problem under ideal conditions controlling for small ω.

4 Block Samplings

The paper formalizes randomized block samplings for parallel coordinate descent, including uniform, doubly uniform, nonoverlapping, nice, independent, binomial, serial, and fully parallel schemes. These classes determine which blocks are updated and support iteration-complexity analysis, including variable update counts and unreliable processors.

  • Sampling concepts: A sampling assigns probabilities to subsets of blocks, and properness requires every block to have positive update probability.Uniform samplings additionally select every block with the same probability.
  • Sampling classes: Doubly uniform samplings assign equal probability to all subsets of a given cardinality and are necessarily uniform.They are characterized by the probabilities q_j of selecting j blocks.
  • Sampling classes: Nonoverlapping uniform samplings assign positive probability only to sets forming a partition of all blocks.The serial and fully parallel samplings are the only nonvacuous samplings that are both doubly uniform and nonoverlapping.
  • Special samplings: A τ-nice sampling selects exactly τ blocks uniformly, while independent and binomial samplings provide alternative randomized update mechanisms.Binomial sampling models τ processors that are independently available with probability p_b, so the number of available processors varies by iteration.
  • Scope and analysis: The framework covers serial updates of one block, fully parallel updates of all blocks, and random update counts for busy or unreliable processors.Iteration-complexity results apply to proper uniform samplings, with refined results for doubly uniform and nonoverlapping subclasses.
  • Technical results: The technical results derive identities for random index sets and expected squared intersections that support the analysis of these sampling classes.For doubly uniform samplings, E[|J ∩ S_hat|^2] is expressed using E[|S_hat|] and E[|S_hat|^2].

5 Expected Separable Overapproximation

The expected separable overapproximation replaces an intractable expected update objective with a simple separable surrogate whose block updates can be computed in parallel. The resulting PCDM variants use this surrogate to obtain monotonicity in expectation, while explicit acceptance can enforce monotonicity when needed.

  • Algorithmic use: PCDM1 updates using the minimizer of the surrogate, while PCDM2 additionally accepts the update only when it does not increase the objective.The PCDM2 rule explicitly compares the candidate objective value with the current one.
  • Motivation and construction: The method constructs a simple separable overapproximation because directly minimizing the expected update bound is generally intractable.Separability makes the block updates parallelizable and simplicity allows easy or closed-form computation.
  • ESO formulation: The surrogate H_β,w(x,h) combines the smooth function, its gradient, a weighted quadratic term, and the separable regularizer.The parameters β and w define the expected separable overapproximation inequality.
  • Monotonicity: Both PCDM1 and PCDM2 are monotonic in expectation because the surrogate equals the objective at a zero update.For PCDM2, the acceptance step also gives an upper bound by the smaller of the expected candidate value and the current objective.
  • Monotonicity: A monotonic ESO guarantees F(x+h(x)[S_hat]) ≤ F(x) with probability 1 for every x in the domain.The paper distinguishes this stronger property from monotonicity in expectation.
  • Smoothness consequences: The DSO inequality generalizes block Lipschitz continuity and yields global gradient Lipschitz continuity with constant ω in the weighted norm.The constant ω is tight for some partially separable functions and cannot generally be reduced.

6 Expected Separable Overapproximation (ESO) of Partially Separable Functions

This section derives expected separable overapproximations for partially separable smooth functions under several uniform sampling schemes. The resulting parameters control update bounds and monotonicity, with sharper β values available for specialized samplings such as τ-nice sampling.

  • General framework: The analysis derives ESO inequalities for proper uniform samplings and refined bounds for nonoverlapping, nice, and doubly uniform samplings.Properness ensures every block has a positive chance of being updated.
  • Uniform samplings: For arbitrary proper uniform samplings, β and w can be computed to form the expected separable overapproximation used by PCDM.The paper presents the general result in Theorem 12 and specializes it to several sampling subclasses.
  • Uniform samplings: For τ-uniform samplings, the conservative choice β = min{ω, τ} yields a monotonic ESO.The corresponding PCDM1 update is monotonic, so PCDM1 and PCDM2 coincide in this setting.
  • Nonoverlapping samplings: Nonoverlapping uniform samplings also admit monotonic ESOs, with parameters determined by how sampled blocks intersect the partially separable components.Serial sampling has γ_i = 1, whereas fully parallel sampling has γ_i = ω.
  • Doubly uniform samplings: The doubly uniform ESO reduces to the nice-sampling result for nice samplings and matches the serial and fully parallel results in those special cases.This establishes consistency among the specialized sampling analyses.

7 Iteration Complexity

The paper establishes high-probability iteration-complexity guarantees for parallel coordinate descent in both convex and strongly convex settings, then derives speedup factors from those bounds. Speedup depends on sampling, parallelism, and partial separability, reaching the number of blocks under fully parallel sampling and approaching the average number of updated blocks in strongly convex regimes with large µΩ(w).

  • Iteration-complexity theorems: Two iteration-complexity theorems cover non-strongly-convex and strongly convex objectives, with PCDM1 or PCDM2 selected according to ESO monotonicity requirements.The convex theorem covers PCDM2 generally and PCDM1 with a monotonic ESO; the strongly convex theorem covers PCDM1 without monotonicity restrictions.
  • Convex case: O(βThe convex-case iteration complexity is stated as O(β
  • Convex case: 1/ε) is the convex-case iteration-complexity form, while the serial method has α = 1.The cited passage reports the complexity dependence and identifies α = 1 for serial sampling.
  • Convex-case speedup: n is the fully parallel speedup, whereas serial sampling has speedup 1 relative to itself.The maximum is obtained when all blocks are updated at each iteration.
  • Convex-case speedup: s(r) = τ / (1 + r(τ − 1)) expresses τ-nice-sampling speedup using normalized partial separability r.For small r, the speedup can be large, including as much as the number of processors in the separable case; in many applications r is small when the problem dimension is huge.
  • Strongly convex case: For strongly convex objectives, the speedup approaches αn = E[| ˆS|] as µΩ(w) becomes large and is independent of µf.The strongly convex result provides high-probability convergence guarantees under µf(w) + µΩ(w) > 0 and an ESO assumption.

8 Numerical Experiments

The experiments evaluate PCDM1 on huge-scale LASSO and controlled partially separable problems, showing substantial practical speedups and close agreement between predicted and observed parallelization speedup. Additional classification experiments examine processor scaling and regularization effects.

  • 8.1 A LASSO problem with 1 billion variables: 24 cores solve a LASSO problem with 10^9 variables in 2 hours, compared with 41 hours on one core.The problem description required around 350GB of memory.
  • 8.1 A LASSO problem with 1 billion variables: PCDM1 pushes the LASSO optimality gap below 10^-13 after 34n to 37n coordinate updates for every tested processor count.Rows compare configurations after the same normalized number of coordinate updates.
  • 8.1 A LASSO problem with 1 billion variables: Doubling the number of cores roughly halves wall time, and parallelization speedup is essentially equal to the number of cores.The experiments attribute this behavior to small partial-separability degree relative to the problem dimension.
  • 8.2 Tightness of speedup estimates: Theoretical and empirical speedup factors match remarkably closely on carefully constructed problems with ω = 5, 10, 50, and 100.The comparison measures iterations needed to reach ϵ = 10^-6 across processor counts from 1 to 1000.
  • 8.4 L2-regularized logistic regression with good data for PCDM: With τ = 16, PCDM is about 2.5× faster than τ = 1, while theory predicts a parallelization speedup of 2.15.The result is below linear speedup but agrees with the theoretical prediction based on β = 7.46.

A Notation glossary

Table 8 presents the paper's main notation.

  • Table 8 is a reference table for the main notation used throughout the paper.
  • The glossary is intended to support interpretation of the paper's mathematical symbols and terminology.
  • No individual notation definitions are specified in the supplied table caption.
Loading 1212.0873v2…