PaperlayerView exact revision on arXiv

Source-linked AI summary

A Class of Randomized Primal-Dual Algorithms for Distributed Optimization

Jean-Christophe Pesquet, Audrey Repetti

arXiv:1406.6404v3math.OC

TL;DR

Primal-dual formulations can avoid inverting linear operators, a potential computational advantage for large-scale problems. This paper develops randomized block-coordinate primal-dual methods for monotone inclusions, convex variational problems, and asynchronous multi-agent settings. The reported results include almost-sure weak convergence for the convex and distributed formulations under stated assumptions.

  • Problem

    Primal-dual methods can avoid inverting involved linear operators, a potential computational advantage in large-scale problems, while the paper seeks to make such methods more flexible through restricted operator activation.

    Source: §1 · p. 2

  • Method

    The paper derives randomized block-coordinate primal-dual algorithms for monotone inclusions and convex variational problems, and develops asynchronous distributed versions for multi-agent settings.

    Source: §1 · p. 2, §4.1 · p. 8, §6 · p. 24

  • Results

    The convex and distributed formulations have iterates that converge weakly almost surely to solution-valued random variables under their stated assumptions.

    Source: §5 · p. 21, Remark 6.6 · p. 34

  • Takeaways & Limitations

    The resulting implementations may reduce computational complexity and memory requirements, and the approach applies to asynchronous multi-agent algorithms.

    Source: §1 · p. 2, §6 · p. 24

    In the distributed scheme, each iteration requires updating all variables belonging to the randomly activated neighborhoods.

    Source: Remark 6.6 · p. 31

Abstract

from arXiv · show

Based on a preconditioned version of the randomized block-coordinate forward-backward algorithm recently proposed in [Combettes,Pesquet,2014], several variants of block-coordinate primal-dual algorithms are designed in order to solve a wide array of monotone inclusion problems. These methods rely on a sweep of blocks of variables which are activated at each iteration according to a random rule, and they allow stochastic errors in the evaluation of the involved operators. Then, this framework is employed to derive block-coordinate primal-dual proximal algorithms for solving composite convex variational problems. The resulting algorithm implementations may be useful for reducing computational complexity and memory requirements. Furthermore, we show that the proposed approach can be used to develop novel asynchronous distributed primal-dual algorithms in a multi-agent context.

1 Introduction

Primal-dual methods can split problems into operators handled individually, but this paper seeks greater flexibility by activating only a random subset at each iteration. It develops block-coordinate methods for monotone inclusions, convex optimization, and asynchronous multi-agent settings, while allowing summable stochastic errors.

1 Introduction

  • Joint primal-dual formulations can avoid inverting involved linear operators, which may reduce computational complexity in large-scale problems.The cited motivation concerns formulations with various linear operators.Source: §1 · p. 2
  • The paper focuses on primal-dual algorithms based on forward-backward iteration, which can use resolvents or cocoercive operators and, in variational problems, proximity operators or gradients.Gradients may be preferable for complexity reasons when the function is smooth.Source: §1 · p. 2
  • Random sweeping restricts each iteration to a subset of operators and yields methods tolerant of stochastic errors satisfying a summability condition.The framework is applied to block-coordinate primal-dual methods for monotone inclusions and composite convex optimization.Source: §1 · p. 2
  • The paper develops block-coordinate versions of two forward-backward-based primal-dual algorithms for monotone inclusion and convex variational problems.In multi-agent settings, updates can be limited to neighborhoods of a small number of agents and performed asynchronously.Source: §1 · p. 2
  • The paper proceeds from monotone-operator and convex-analysis background to randomized block-coordinate methods, then to primal-dual, variational, and distributed algorithms.The distributed algorithms address both monotone inclusion and convex variational problems.Source: §1 · p. 3

2 Notation

The notation section establishes the probability and Hilbert-space setting, then defines the operator and convex-analysis objects used to express the algorithms and optimization problems.

2 Notation

  • The paper works on a probability space and uses measurable Hilbert-space-valued random variables, generated sigma-algebras, and expectation.The notation for inner products and norms is shared across the Hilbert spaces considered.Source: §2 · p. 3
  • Bounded linear operators, adjoints, strongly positive self-adjoint operators, and their inverses are specified for the Hilbert spaces.The identity operator is denoted by Id.Source: §2 · p. 3
  • The section defines zeros and inverses of set-valued operators, along with monotonicity, strong monotonicity, cocoercivity, and resolvents.For maximally monotone operators, the resolvent is firmly nonexpansive.Source: §2 · pp. 3–4
  • For convex analysis, it introduces proper lower-semicontinuous convex functions, subdifferentials, conjugates, metric proximity operators, and Hilbert direct-sum spaces.The proximity operator is defined relative to a strongly positive metric operator; the standard version is recovered when that operator is Id.Source: §2 · p. 4

3 A preconditioned random block-coordinate forward-backward algorithm

The section extends forward-backward iteration to preconditioned randomized block updates in a changed metric. Under its stated assumptions, the iterates converge weakly almost surely, and the framework accommodates summable stochastic errors.

3 A preconditioned random block-coordinate forward-backward algorithm

  • A metric change incorporates preconditioning, allowing the resolvent of Q and the forward step for cocoercive R to form the iteration.The algorithm updates selected coordinates through randomized activation, with error terms in the operator evaluations.Source: §3 · pp. 5–6
  • The randomized preconditioned block-coordinate forward-backward iteration converges weakly almost surely to a zero of Q + R under the proposition's assumptions.The assumptions include nonempty zeros, bounded step sizes below 2ϑ, relaxation bounded away from zero, independent block activations, and positive activation probability for each block.Source: §3 · p. 5

Remark 3.2

  • When R factors as L* Rtilde L, the cocoercivity requirement holds for strongly positive V satisfying ϑ∥LVL*∥ = eϑ.This supplies a sufficient condition for choosing the preconditioner.Source: Remark 3.2 · p. 6
  • Summable stochastic errors are allowed in both the forward-operator and resolvent evaluations, offering more freedom than summable deterministic-error assumptions.The two error terms correspond respectively to applying R and JγnVQ.Source: Remark 3.2 · p. 6

4 Block-coordinate primal-dual algorithms for composite monotone inclusion problems

The section develops randomized block-coordinate primal-dual algorithms for composite monotone inclusion problems in primal and dual variables, including a second subclass for the case A = 0. Under stated assumptions, the first subclass converges to primal-dual solutions, while the second subclass’s primal and dual iterates converge weakly almost surely.

4.1 Problem

  • The primal-dual solution pair is equivalent to a zero of a sum of maximally monotone operators and a cocoercive operator, enabling a block-coordinate forward-backward approach.The problem seeks random variables valued in the primal and dual solution sets.Source: §4.1 · pp. 7–8

4.2 First algorithm subclass

  • If W1/2CW1/2 is μ-cocoercive with μ ∈ (0,∞) and U1/2D−1U1/2 is ν-cocoercive with ν ∈ (0,∞), then for every α ∈ (0,∞), V1/2RV1/2 is ϑα-cocoercive.V′ is strongly positive and is an isomorphism; its inverse is strongly positive and self-adjoint.Source: §4.2 · pp. 8–9

Remark 4.4

  • The first block-coordinate primal-dual algorithm converges almost surely to primal and dual solutions under its stated step-size, activation, independence, and error assumptions.The iterates are also shown to converge weakly almost surely to random variables in the respective solution sets.Source: Remark 4.4 · pp. 11, 12, 14

Remark 4.7

  • Boolean activation variables avoid updating inactive blocks, while stochastic terms model errors in operator evaluations; the algorithm extends deterministic methods and admits a symmetric primal-dual form.The symmetric algorithm also converges weakly almost surely to primal and dual solutions under its stated assumptions.Source: Remark 4.7 · pp. 14–15

4.3 Second algorithm subclass

  • For the diagonal form of V, if W^1/2CW^1/2 is μ-cocoercive with μ ∈ ]0, +∞[ and U^1/2D^-1U^1/2 is ν-cocoercive with ν ∈ ]0, +∞[, then V^1/2RV^1/2 is ϑ-cocoercive.Source: §4.3 · p. 16
  • The second subclass yields a block-coordinate primal-dual algorithm for Problem 4.1 in the case A = 0.Source: §4.3 · p. 17
  • When all Aj = 0, the primal and dual sequences converge weakly almost surely to solutions under the stated conditions.The result assumes Conditions (ii)–(iii) in Proposition 4.8.Source: §4.3 · p. 18
  • The necessary condition for (4.58) is described as less restrictive than condition (4.48).Source: §4.3 · p. 19

5 Block-coordinate primal-dual proximal algorithms for convex optimization problems

Section 5 specializes the block-coordinate framework into primal-dual proximal algorithms for convex optimization and gives convergence guarantees under stated assumptions. It also relates the algorithms to earlier deterministic and randomized methods.

5 Block-coordinate primal-dual proximal algorithms for convex optimization problems

  • The algorithms address composite convex problems with convex terms, Lipschitz-differentiable terms, and linear couplings.Problem 5.1 specifies these components through f_j, h_j, g_k, l_k, and L_k,j.Source: §5 · p. 20
  • Under Proposition 5.3’s assumptions, the first algorithm’s primal and dual iterates converge weakly almost surely to their respective solution sets.The result identifies the limits as belonging to the primal and dual solution sets.Source: §5 · p. 21
  • Assuming Conditions (i) of Proposition 4.11 and (ii)–(iii) of Proposition 4.8, when every f_j = 0, (x_n) and (v_n) converge weakly P-a.s. to eF- and eF*-valued random variables, respectively.Source: §5 · p. 22

Remark 5.5

  • Algorithm (5.10) extends algorithms [16, 37], developed deterministically without errors, to p = q = 1, finite-dimensional H1 and G1, specified operators, and no or constant relaxation.The conditions specify l1 = ι{0}, W1 = τId, U1 = ρId, and either no relaxation (λn ≡ 1) or constant relaxation (λn ≡ λ0 < 1).Source: Remark 5.5 · p. 23
  • Unlike the randomized Douglas–Rachford method [23], Algorithms (5.4) and (5.10) do not require inversion of Id + LL* or Id + L*L.Source: Remark 5.5 · p. 23

6 Asynchronous distributed algorithms

This section reformulates coupled agent problems using overlapping subsets of agents and derives randomized asynchronous distributed primal-dual algorithms. It covers their almost-sure weak convergence under stated assumptions, an alternative distributed convex optimization scheme, and a variational-problem specialization.

6 Asynchronous distributed algorithms

  • The distributed coupling is split across overlapping agent subsets V_ℓ; when these subsets are hyperedges, Assumption 6.2 requires their hypergraph to be connected.The text also gives the full-agent set and consecutive-agent pairs as examples satisfying the assumption.Source: §6 · p. 24
  • Proposition 6.3 represents the distributed problem as a product-space inclusion with a normal-cone term enforcing the split linear constraints.The equivalence uses N_Λm = S* N_Λ S under the stated closed-subspace condition.Source: §6 · pp. 25–26
  • Under Assumption 6.2, for every agent i and set-level index ℓ, the iterates x_{i,n} and x_{ℓ,n} converge weakly P-almost surely to a bF-valued random variable bx.Source: §6 · pp. 27, 29

Remark 6.6

  • When all B_i are zero, computations of u_i,n and v_i,n become unnecessary; another variant updates all x_i,n variables corresponding to sets V_l that are randomly activated at each iteration n.Source: Remark 6.6 · p. 31
  • Under Assumption 6.2, Conditions (ii)–(iii) in Proposition 6.5, and Ai = 0 for every i in Problem 6.1, each (xi,n)n∈N converges weakly P-a.s. to a bF-valued random variable bx.Source: Remark 6.6 · p. 32
  • The section begins a variational specialization for sums of convex functions and smooth terms, and introduces a proximal algorithm derived from Proposition 6.5.Problem 6.9 includes strongly convex functions composed through the operators M_i.Source: Remark 6.6 · p. 33
  • Under the stated conditions and Assumption 6.2, each agent’s iterate converges weakly almost surely to a random variable valued in ˇF.The proof also establishes that the solution set bF is nonempty and contained in ˇF.Source: Remark 6.6 · p. 34

Remark 6.11

  • Under gi = 0, li = ι{0}, κℓ = 2, and (6.39), Algorithm (6.53) reduces to the displayed scheme; its specified Euclidean-space case appears similar to [7].That comparison specifies λn = 1, common θℓ, Wi = τiId with τi ∈ ]0, +∞[, and no error term. The sets Vℓ can be viewed as edges of a connected undirected graph whose nodes are indexed by i.Source: Remark 6.11 · p. 35
Loading 1406.6404v3…