Source-linked AI summary
On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
Zhaosong Lu, Lin Xiao
TL;DR
The paper analyzes randomized block-coordinate methods for minimizing a smooth convex function plus a block-separable convex function. It extends existing techniques and introduces randomized estimate sequences, obtaining sharper expected-value convergence rates and improved high-probability complexity bounds.
Problem
Existing analyses of randomized block-coordinate methods did not provide the sharper convergence guarantees sought for general composite minimization and accelerated methods.
Method
The paper extends Nesterov’s technique to composite RBCD and develops randomized estimate sequences for Nesterov’s ARCD method when Ψ ≡ 0.
Results
The analyses establish sharper expected-value convergence rates, improve high-probability iteration complexity by at least O(n/ε), and match the optimal accelerated full-gradient rate when n = 1.
Takeaways & Limitations
The paper provides stronger convergence and complexity guarantees for the studied RBCD methods, including an optimal-rate match in the single-block unconstrained case.
Takeaways & Limitations
The results assume block-wise Lipschitz continuity of the partial gradients and a block-separable convex regularizer.
Abstract
from arXiv · showhide
In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in [8,11] for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov's technique developed in [8] for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general problem and obtain a sharper expected-value type of convergence rate than the one implied in [11]. Also, we obtain a better high-probability type of iteration complexity, which improves upon the one in [11] by at least the amount $O(n/ε)$, where $ε$ is the target solution accuracy and $n$ is the number of problem blocks. In addition, for unconstrained smooth convex minimization, we develop a new technique called {\it randomized estimate sequence} to analyze the accelerated RBCD method proposed by Nesterov [11] and establish a sharper expected-value type of convergence rate than the one given in [11].
1 Introduction
The paper studies randomized block-coordinate methods for composite convex minimization and develops sharper convergence analyses for both RBCD and accelerated RBCD.
- 1 Introduction: RBCD methods randomly select coordinate blocks instead of using a deterministic cyclic order, supporting large-scale optimization applications.Each iteration updates one block while keeping the others fixed.
- 1 Introduction: The target problem minimizes a differentiable convex function plus a block-separable convex function.The variables are partitioned into blocks, and each regularizer Ψi is closed and convex.
- 1 Introduction: At each iteration, the RBCD method uniformly samples one block and solves a block-wise proximal subproblem, then updates only that block.The other blocks remain unchanged; Li denotes the Lipschitz constant of the corresponding partial gradient.
- 1 Introduction: Nesterov’s earlier ARCD analysis left open whether a sharper rate could match the optimal accelerated full-gradient rate when n = 1.The issue arises for strongly convex objectives, where the rate in was worse than the known optimal rate.
- 1 Introduction: The paper extends Nesterov’s technique to the general composite setting and improves both expected convergence rates and high-probability iteration complexity.The high-probability improvement is at least O(n/ε), while randomized estimate sequences sharpen the unconstrained ARCD rate.
- 1 Introduction: The paper develops technical preliminaries, analyzes general RBCD in Section 3, and analyzes unconstrained ARCD using randomized estimate sequences in Section 4.The Section 4 technique is applied when Ψ ≡ 0.
2 Technical preliminaries
The preliminaries establish assumptions, block-coordinate notation, norms, composite gradient mappings, and expectation inequalities used in the convergence analyses.
- 2 Technical preliminaries: The analysis assumes that problem (1) has a finite minimum and a nonempty set of optimal solutions.The minimum is denoted F⋆ and the optimal set X∗.
- 2 Technical preliminaries: The variables are represented through a block partition and an associated permutation matrix that embeds each block into the full space.The matrix is written U = [U1 ··· Un].
- 2 Technical preliminaries: The partial gradient of f with respect to each block is assumed Lipschitz continuous with constant Li.The assumption bounds changes in ∇if after perturbing only block i.
- 2 Technical preliminaries: The paper uses Euclidean norms on block subspaces and defines paired whole-space norms satisfying the Cauchy-Schwarz inequality.These norms follow the block Lipschitz constants Li.
- 2 Technical preliminaries: Convexity parameters quantify curvature relative to the weighted norm, and the composite objective’s parameter is at least the sum of the parameters of f and Ψ.The framework identifies strong convexity with a positive convexity parameter and implies µf ≤ 1 under the stated assumptions.
- 2 Technical preliminaries: A uniformly sampled block yields expectation identities and inequalities for block-separable functions and coordinate updates.These results include the equivalent form used later in convergence analysis.
- 2 Technical preliminaries: The block-wise composite gradient mapping extends Nesterov’s full-gradient concept and provides lower bounds on F(y) from information at x.It is derived from the block proximal subproblem’s optimality conditions and is used in subsequent convergence analysis.
3 Randomized block-coordinate descent
The paper extends RBCD convergence analysis to general block-separable convex composite minimization and derives sharper expected-value and high-probability guarantees. It also compares these guarantees with prior bounds and identifies improvements under strong convexity and multiple independent runs.
- Expected-value convergence: The analysis extends Nesterov’s technique from block-separable constraints to general block-separable convex functions.The extension uses block-wise composite gradient mapping machinery.
- Expected-value convergence: Theorem 1 establishes an expected-value convergence rate for the uniformly randomized block-coordinate method.The sequence is generated by repeatedly choosing a block uniformly and updating it through the RBCD method.
- Expected-value convergence: A factor of 4/3 asymptotic improvement is obtained over the implied prior expected-value rate, with potentially larger gains when the initial comparison quantity is larger.The stated improvement applies when the iteration count is sufficiently large.
- Expected-value convergence: Under strong convexity, the proposed convergence rate is much sharper than the comparison rate for sufficiently large iteration counts.The condition is µf + µΨ > 0, meaning at least one of f and Ψ is strongly convex.
- High-probability complexity: Theorem 2 gives a sharper single-run high-probability iteration complexity for obtaining an ε-optimal solution.The bound applies for target accuracy ε and failure parameter ρ.
- High-probability complexity: When ρ or ε is sufficiently small, the proposed single-run complexity can be substantially smaller than the prior bound.This follows because R0 can be much smaller than the comparison quantity R̄0.
- Multiple-run complexity: A multiple-run strategy uses r = ⌈log(1/ρ)⌉ independent runs, each initialized at x0 and performed for the same iteration count.The final guarantee is obtained by selecting among the independently generated outputs.
- Multiple-run complexity: For the multiple-run strategy, the total iteration complexity can be substantially smaller than the prior bound when ρ or ε is sufficiently small.The comparison uses the fact that R̄0 can be much larger than R0.
4 Accelerated randomized coordinate descent
This section develops and analyzes an accelerated randomized coordinate descent method for unconstrained smooth convex minimization. Its randomized estimate-sequence analysis yields a sharper expected-value convergence rate, matching deterministic accelerated full-gradient complexity when n = 1.
- Method: The ARCD method targets smooth convex minimization with convexity parameter µ = µf ≥ 0 and samples one of n blocks uniformly at each iteration.The method initializes v0 = x0 and updates its iterates using randomly selected block indices.
- Method: Each iteration generates yk, xk+1, and vk+1, with xk+1 and vk+1 depending on the current random realization and yk depending on ξk−1.This dependence structure motivates the randomized analysis.
- Convergence results: Theorem 4 establishes a sharper expected-value convergence rate than the rate given in.The comparison considers both µ > 0 and µ = 0; for sufficiently large k, the paper concludes that its rate is much tighter or sharper under the stated conditions.
- Convergence results: When n = 1, ARCD becomes deterministic accelerated full gradient descent, and the paper’s iteration-complexity result coincides with the corresponding result in [6, (2.2.8)].This provides the stated deterministic full-gradient specialization of the randomized method.
- Randomized estimate sequence: The paper extends estimate sequences to randomized block-coordinate descent through a new randomized estimate sequence technique for analyzing ARCD.The construction uses random functions depending on prior block selections and deterministic weights independent of the current random variable.
- Randomized estimate sequence: The constructed sequence preserves a canonical quadratic form and supports a stronger condition used to establish the ARCD convergence bound.The proof proceeds by induction using convexity, block-diagonal curvature, and the recursive sequence definitions.