PaperlayerView exact revision on arXiv

Source-linked AI summary

Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Peter Richtárik, Martin Takáč

arXiv:1107.2848v1math.OCstat.ML

TL;DR

The paper addresses iteration complexity for randomized block-coordinate descent on composite convex objectives, where large-scale problems make full-gradient methods impractical. It develops a blockwise randomized upper-bound minimization method and proves high-probability guarantees, while removing the need for objective regularization. The resulting framework also covers broad probability and norm choices in the smooth case and is demonstrated on billion-variable problems.

  • Problem

    The paper studies the limited iteration-complexity theory for randomized coordinate descent applied to a smooth convex term plus a simple nonsmooth convex block-separable term.

  • Method

    The method randomly selects a block and exactly minimizes a blockwise upper bound on the composite objective, under block-coordinate smoothness and separability assumptions.

  • Results

    The method obtains high-probability iteration guarantees without regularizing the objective, improves complexity by a factor of 4, removes ε from the logarithmic term, and supports arbitrary probabilities and general norms in the smooth case.

  • Takeaways & Limitations

    The framework extends randomized coordinate-descent complexity analysis to composite minimization and is reported to solve huge-scale ℓ1-regularized least-squares and support-vector-machine problems.

  • Takeaways & Limitations

    The analysis assumes that a minimum exists, the smooth term has block-coordinate Lipschitz gradient, and the nonsmooth term is block-separable proper closed convex.

Abstract

from arXiv · show

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $ε$-accurate solution with probability at least $1-ρ$ in at most $O(\tfrac{n}ε \log \tfrac{1}ρ)$ iterations, where $n$ is the number of blocks. For strongly convex functions the method converges linearly. This extends recent results of Nesterov [Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper #2010/2], which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $ε$ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving true iteration complexity bounds. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale $\ell_1$-regularized least squares and support vector machine problems with a billion variables.

1 Introduction

The paper targets very large or distributed structured convex problems where full gradients, complete data, or conventional iterations are impractical. It develops randomized block-coordinate methods for composite minimization and extends prior complexity results with broader settings and sharper guarantees.

  • Motivation: Large problem dimensions can make a single function-value or gradient computation prohibitive, while memory and iteration time independently constrain standard gradient methods.These constraints motivate methods that provide intermediate progress without processing every variable at once.
  • Block-coordinate descent: Block-coordinate descent partitions variables into manageable blocks and updates one block while fixing the others.The strategy is also known as alternating minimization, coordinate relaxation, and related methods.
  • Randomization: Randomized block selection avoids potentially expensive greedy selection and is suitable when data availability varies across blocks.The paper also studies nonuniform probabilities to improve speed or model different data-availability frequencies.
  • Problem and contribution: The paper analyzes randomized coordinate descent for a smooth convex term plus a simple nonsmooth convex block-separable term, extending iteration-complexity results beyond previously covered special cases.Earlier randomized complexity analyses mainly addressed quadratic, smooth, box-constrained, or ℓ1-regularized settings.
  • Problem and contribution: The method provides high-probability iteration guarantees without regularizing the objective, improves complexity by a factor of 4, removes ε from the logarithmic term, and supports arbitrary probabilities and general norms in the smooth case.The paper focuses on simple methods because accelerated methods may impose excessive per-iteration work on huge sparse problems.

2 Assumptions and the Algorithm

The generic randomized method models variables as blocks, assumes block-coordinate smoothness and separable convex nonsmooth terms, and exactly minimizes a blockwise upper bound after sampling a block. Its analysis converts per-iteration decrease into expected and high-probability complexity results.

  • Block structure: The variable space is decomposed into n block subspaces, with coordinate-selection matrices embedding each block into the full space.The block representation permits vectors to be written from their component coordinates.
  • Assumptions: The smooth term has uniformly block-coordinate Lipschitz gradients, while the nonsmooth term is proper, closed, convex, and block separable.Each block contribution to the nonsmooth term is convex and closed.
  • Algorithm: At each iteration, the algorithm samples block i with probability p_i and exactly minimizes an upper bound on the composite objective over that block.For convex quadratic smooth terms, the actual block-restricted objective may sometimes be minimized directly.
  • Analysis: The analysis uses weighted norms and matrices based on block Lipschitz constants and sampling probabilities, together with a finite initial level-set-size measure.The generic analysis tracks objective decrease through the random iterates and objective values.
  • Complexity analysis: The one-shot approach avoids the repeated objective evaluations required by restarting, and the resulting bounds are tight on simple examples.Restarting repeats the random process for ⌈log 1/ρ⌉ runs to reduce failure probability.

3 Coordinate Descent for Composite Functions

The section analyzes uniform randomized coordinate descent for composite convex objectives, establishing high-probability complexity bounds and linear convergence under strong convexity. It also examines regularization for non-strongly-convex objectives and notes that its parameter depends on quantities unknown in advance.

  • Algorithm 2: Uniform Coordinate Descent for Composite Functions selects one coordinate uniformly and updates it by minimizing the corresponding coordinate model.The method is named UCDC and defines each coordinate update through T^(i)(xk).
  • Algorithmic analysis: The coordinate-update vector T(x) minimizes the central function H(x, ·), which supports the method’s decrease analysis.
  • Convex objective: High-probability iteration bounds are derived for reaching ε accuracy, with confidence ρ appearing under a logarithm.The theorem statements parameterize the target accuracy and confidence, while the text emphasizes the logarithmic dependence on ρ.
  • Strongly convex objective: For strongly convex objectives, the expected objective gap converges linearly, and the high-probability bound places both accuracy and confidence parameters under logarithms.The linear convergence result is stated through a factor involving γµ.
  • A Regularization Technique: Regularizing the objective makes it strongly convex and can yield an approximate solution to the original problem, but the regularization depends on quantities not known in advance.The regularized analysis replaces one distance bound by another that may be significantly smaller, while requiring an unavailable scaling quantity.

4 Coordinate Descent for Smooth Functions

The smooth-function analysis simplifies coordinate descent by allowing arbitrary, possibly non-Euclidean block norms and by making the coordinate step explicit. It then derives objective-decrease and complexity results, including a strongly convex case.

  • General norms: The smooth-case treatment explicitly extends the analysis to arbitrary, possibly non-Euclidean block norms.The discussion defines dual norms and emphasizes that the analysis is not restricted to Euclidean geometry.
  • General norms: In non-Euclidean norms, Lemma 10 characterizes the solution of the coordinate subproblem sufficiently for the subsequent analysis.The solution need not have a closed form for every norm, but its structure yields the needed bounds.
  • Algorithm 3: The smooth method selects coordinate i with probability pi and updates xk using the coordinate gradient and its Lipschitz parameter.
  • Iteration analysis: Lemma 10 enables an explicit bound on the objective decrease during one iteration, in a form analogous to the Euclidean case.
  • Strong convexity: For strongly convex smooth objectives, the method’s expected objective gap decreases linearly, with corresponding high-probability efficiency estimates.The strongly convex statements use a convexity parameter µ and the norm induced by the block geometry.

5 Comparison of CD Methods with Complexity Guarantees

The paper compares its randomized coordinate-descent complexity bounds with prior methods, reporting a factor-of-4 improvement and broader guarantees for probabilities, norms, and direct application to the original objective.

  • Smooth case (Ψ = 0): 4x: The paper improves the relevant complexity bound over Nesterov’s result in the non-strongly convex smooth case.The comparison concerns achieving P(F(x_k) − F* ≤ ε) ≥ 1 − ρ.
  • Smooth case (Ψ = 0): Arbitrary probability vector p is covered, extending beyond uniform probabilities and probabilities proportional to L_i.This permits fine-tuning p to minimize R^2 in suitable situations.
  • Smooth case (Ψ = 0): ε is removed from the logarithmic factor in the paper’s complexity results.
  • Smooth case (Ψ = 0): General norms are allowed by the paper’s results.
  • Smooth case (Ψ = 0): The algorithms can be applied directly to F without adding a quadratic regularization term with an unknown constant.The paper identifies this as necessary for obtaining true iteration complexity results.
  • Nonsmooth case (Ψ ≠ 0): Individual coordinate Lipschitz constants L_i give the best complexity among the compared approaches, while randomized updates can be implemented cheaply for large problems.

6 Numerical Experiments

The numerical study evaluates randomized coordinate descent on sparse regression/Lasso and linear support vector machine instances, with experiments designed to assess scalability.

  • Experimental scope: The experiments study two problem classes: Sparse Regression/Lasso and Linear Support Vector Machines.The paper reserves a separate report for the (Sparse) Group Lasso problem.
  • Experimental setup: The scalability experiments were run on a PC with 480GB RAM, and all algorithms were written in C.

6.1 Sparse Regression / Lasso

The sparse regression experiments specialize RCDC to ℓ1-regularized least squares, using soft-thresholding updates and UCDC with uniform coordinate probabilities. Across million- and billion-variable instances, UCDC achieves substantial residual reduction, while adaptive probabilities and shrinking improve practical performance.

  • Algorithm: RCDC solves sparse regression by applying soft-thresholding to each selected coordinate update.Uniform coordinate probabilities define UCDC; experiments also allow probabilities to change during iterations without a theoretical justification.
  • Computational cost: The time for one block of n UCDC iterations increases roughly linearly with ∥A∥0 and does not depend on ∥x∗∥0.For ∥A∥0 values of 10^7, 10^8, and 10^9, the reported times are about 0.9 seconds, 4–6 seconds, and 46 seconds, respectively.
  • Huge-scale instances: 35×n iterations reduce the initial residual by 10^18 on a million-variable instance, taking about a minute and a half.The iterate’s support stabilizes at 160,000 nonzeros, matching the optimum’s support size.
  • Huge-scale instances: A billion-variable instance with 20 billion matrix nonzeros reaches a tenfold residual reduction in n iterations and a 1000-fold reduction in less than a day.The tenfold reduction takes less than an hour and a half.
  • Fat matrices: When m < n, UCDC needs many more iterations for global reduction, but the residual can decrease from 10^2 to 10^-3 in 15×n iterations.On the reported fat-matrix instance, the initial reduction by a factor of 10^+ takes 5,010×n iterations and less than 19 minutes.
  • Probability choices: Choosing probabilities proportional to larger Lipschitz constants accelerates moderate-accuracy convergence, but switching toward uniform probabilities improves high-accuracy convergence.With extreme Lipschitz imbalance, α = 1 stalls near 10^-4, whereas α = 0 continues toward higher accuracy; shrinking can improve this further.
  • Speedup by shrinking: The shrinking experiments show that correct nonzeros reach the optimal support level around 3n iterations, while the full iterate support reaches it around 30n.A 0.9-shrinking strategy saves nearly 70% relative to 0-shrinking when obtaining residual 10^-14.
  • Initialization: Starting UCDC from xLS rather than zero gives a 4× speedup for reducing the residual below 10^-5.This comparison uses the same λ = 1 sparse regression instance as the shrinking experiments.

6.2 Linear Support Vector Machines

The paper applies UCDC to L1-regularized linear SVMs using smooth losses with cheaply updated coordinate derivatives. On the kdd2010 dataset, it obtains good solutions after 10×n iterations and trains models with nearly 30 million features in seconds to minutes.

  • Problem setup: The linear-classification formulation combines a convex loss with either L1 or L2 regularization, while the experiments use the L1 setup.Because the method requires a continuously differentiable smooth term, the experiments consider L2-SVM and LG losses.
  • Method: UCDC uses coordinate-specific Lipschitz constants and derivatives for the L2-SVM and LG losses.These quantities are listed for the two losses to support the coordinate updates.
  • Implementation: Updating one feature coordinate requires work proportional to the number of observations in which that feature appears.The implementation updates partial derivatives incrementally after each coordinate step.
  • Results: UCDC finds a good solution after 10×n iterations, requiring less than half a second on the reported data.The experiment excludes a bias term and does not scale the data.
  • Results: On kdd2010, which has 29,890,095 features, training takes approximately 70 seconds with L2-SVM loss and 112 seconds with LG loss.The reported runs use the entire training set and run UCDC for n iterations.
Loading 1107.2848v1…