PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems

Hoi-To Wai, Jean Lafond, Anna Scaglione, Eric Moulines

arXiv:1612.01216v3math.OCcs.SYeess.SYstat.ML

TL;DR

High-dimensional constrained optimization across networked machines is challenging because projection-based decentralized methods can be computationally prohibitive. This paper develops DeFW by extending Frank-Wolfe to decentralized updates and analyzes convergence for convex and non-convex objectives. It reports convergence guarantees under stated conditions and demonstrates advantages in machine-learning applications.

  • Problem

    Projection-based decentralized methods can be computationally prohibitive for high-dimensional constrained problems, while data and measurements are distributed across networked machines.

    Source: §1 · pp. 1–2

  • Method

    The paper develops DeFW, extending Frank-Wolfe through decentralized inexact updates based on local approximations to average iterates and gradients.

    Source: §1 · p. 2, §2 · p. 4

  • Results

    DeFW is analyzed to achieve O(1/t) convergence for convex objectives, O(1/t^2) for strongly convex objectives with an interior optimum, and O(1/√t) toward stationarity for non-convex objectives.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper reports demonstrated advantages over previous state-of-the-art methods in experiments on two machine-learning problems.

    Source: §6 · p. 19

    The non-convex convergence analysis uses Assumption 3, which may be difficult to verify in practice.

    Source: §2 · p. 6

Abstract

from arXiv · show

Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high dimensional constrained problems, as the projection step becomes computationally prohibitive to compute. To address this problem, this paper adopts a projection-free optimization approach, a.k.a.~the Frank-Wolfe (FW) or conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule and letting $t$ be the iteration number, we show that the DeFW algorithm's convergence rate is ${\cal O}(1/t)$ for convex objectives; is ${\cal O}(1/t^2)$ for strongly convex objectives with the optimal solution in the interior of the constraint set; and is ${\cal O}(1/\sqrt{t})$ towards a stationary point for smooth but non-convex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. Furthermore, we demonstrate the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion and communication efficient sparse learning. Numerical results on synthetic and real data are presented to support our findings.

1 Introduction

High-dimensional decentralized optimization is motivated by dispersed data and the computational burden of projection-based methods. The paper introduces DeFW and analyzes its convergence, while the preliminaries specify the objective, constraint set, and notation used in that analysis.

1 Introduction

  • The problem models each agent's private-data loss with a continuously differentiable, possibly non-convex function and uses a closed, bounded, convex constraint set.The framework includes constraints such as sparsity or low rank and applications including system identification, matrix completion, and sparse learning.Source: §1 · p. 2
  • Projection steps in prior decentralized methods can become computationally prohibitive for high-dimensional constrained problems.The setting involves data distributed across networked machines that cooperate through near-neighbor exchanges.Source: §1 · pp. 1–2
  • DeFW extends Frank-Wolfe to near-neighbor exchanges, replacing projection with constrained linear optimization.The paper analyzes its convergence for convex and non-convex objectives and reports rates of O(1/t), O(1/t^2) under strong convexity with an interior solution, and O(1/√t) toward stationarity for non-convex objectives.Source: §1 · p. 2

1.1 Notations & Mathematical Preliminaries

  • The preliminaries define vector and matrix notation, norms, smoothness, strong convexity, and the interior-solution condition used in the analysis.They also define O(g(t)) as an upper bound by a constant multiple of g(t) for sufficiently large t.Source: §1.1 · p. 3

2 Decentralized Frank-Wolfe (DeFW)

The DeFW analysis treats decentralized updates as inexact Frank-Wolfe steps, using local approximations to the average iterate and gradient. It establishes convergence guarantees under stated conditions and illustrates how linear oracles can be efficient for common constraint sets.

2 Decentralized Frank-Wolfe (DeFW)

  • DeFW uses local approximations to the average iterate and gradient so each agent can form an inexact Frank-Wolfe update using near-neighbor information exchanges.Agents track the average iterate with increasing accuracy and approximate the global gradient from local gradients.Source: §2 · pp. 4–5
  • For convex objectives, Theorem 1 gives an O(1/t) suboptimality guarantee; for strongly convex objectives, it gives O(1/t^2) when the optimum lies in the interior of C.The theorem uses step size γ_t = 2/(t + 1) and approximation errors proportional to 1/t.Source: §2 · p. 5
  • The non-convex convergence result is presented as novel even for centralized Frank-Wolfe, where prior cited results impose a unique-local-minimizer condition or use an adaptive step size.The paper states that its local iterates share similar convergence properties under Assumption 1.Source: §2 · p. 6
  • For an ℓ1 ball, the linear oracle selects a one-sparse direction, so each iterate is at most tN-sparse and the stated worst-case oracle cost is O(d), versus O(d log d) for projection.The paper also describes a trace-norm oracle based on top singular vectors, with O(max{m1, m2} log(1/δ)) complexity under the stated sparsity condition, versus full-SVD projection cost.Source: §2 · pp. 6–7

3 Consensus-based DeFW algorithm

The consensus-based DeFW implementation uses average consensus to produce local approximations of the average iterate and gradient with two communication rounds per iteration. Under the stated conditions, it retains DeFW’s convex and non-convex convergence guarantees, with a practical trade-off in the step-size choice.

3 Consensus-based DeFW algorithm

  • Two communication rounds per iteration suffice for the consensus-based scheme to generate local iterate and gradient approximations at the required sub-linear accuracies.The resulting consensus-based DeFW converges for both convex and non-convex problems with a constant number of communication rounds per iteration.Source: §3 · pp. 7, 9
  • The protocol uses a static, undirected communication graph and a doubly stochastic weight matrix whose second-largest eigenvalue magnitude is below one.Connectedness guarantees the existence of such a matrix; repeated average-consensus updates converge linearly to the average.Source: §3 · p. 7
  • A SAGA-inspired gradient surrogate reuses the previous gradient approximation, and its average is preserved while its approximation error decays under the step-size rule.The paper notes that a similar technique appears as gradient tracking in.Source: §3 · pp. 8–9
  • For non-convex objectives, α = 0.5 gives the best convergence rate but the slowest decay of approximation error; the authors report α = 0.75 performs well in practice.The choice of α therefore involves a trade-off between convergence rate and approximation accuracy.Source: §3 · p. 9

4 Applications

The applications illustrate DeFW for decentralized matrix completion and sparse learning, with communication and storage savings tied to the structure of its updates. The paper also presents a sparsified LASSO variant with high-probability convergence guarantees for random coordinate selection.

4.1 Example I: Decentralized Matrix Completion

  • The consensus-based DeFW algorithm applies directly to trace-norm constrained matrix completion, including a non-convex robust formulation using a smoothed ℓ0 loss for sparse-noise observations.The projection-free approach is described as yielding a low-complexity implementation.Source: §4.1 · pp. 9–10
  • Each DeFW update adds at most N rank-one singular-vector pairs, so iterates initialized at zero have rank at most tN and can be communicated using (tN)·(m1 + m2) entries instead of m1·m2.When only entries in a target subset Ξ are needed, the consensus step can instead exchange those entries.Source: §4.1 · pp. 10–11

4.2 Example II: Communication Efficient DeFW for LASSO

  • The LASSO application assumes a sparse optimal solution and uses an ℓ1-ball constraint; its sparsified DeFW variant reduces aggregation communication by exchanging selected gradient coordinates.The consensus step remains unchanged because its iterate communication is already bounded by tN.Source: §4.2 · pp. 11–12
  • With random coordinate selection, sparsified DeFW retains Theorem 1 guarantees with high probability and has communication complexity O(N · (1/δ) · log(1/δ)) for a δ-optimal solution under strong convexity and an interior optimum.The coordinate set is assembled from agent-selected subsets, and the guarantee uses a logarithmically increasing number of consensus updates.Source: §4.2 · pp. 12–13

5 Numerical Experiments

Experiments on synthetic and real data evaluate DeFW for decentralized matrix completion and sparse learning in a simulated 50-agent network.

5.1 Decentralized Matrix Completion

  • On noiseless synthetic data, DeFW’s square-loss objective follows an O(1/t^2) trend, and its MSE is consistently better than DPG’s.The method in [45] achieves the best MSE in this setting, with the true rank provided.Source: Figure 1 · p. 14, §5.1 · p. 15
  • With sparse-noise contamination, negated Gaussian DeFW achieves the lowest synthetic-data MSE, while the method in [45] performs poorly.The comparison uses synthetic data with m1 = 100, m2 = 250, and rank K = 5.Source: §5.1 · p. 15, Figure 2 · p. 15
  • At rank 10 on noiseless synthetic data, DeFW achieves reasonable performance where fails to produce low test MSE.Figure 3 compares test MSE against iteration number.Source: §5.1 · p. 16, Figure 3 · p. 16
  • For noiseless synthetic matrix completion, DeFW’s average runtime per iteration is five times faster than DPG’s, which requires projection computation.The comparison evaluates objective value and test MSE against average runtime per agent.Source: §5.1 · p. 16, Figure 4 · p. 16
  • On MovieLens100k, negated Gaussian loss achieves the best MSE with sparse noise, while three consensus rounds converge faster and can outperform centralized DeFW.For noiseless observations, the tested losses reach reasonable MSE, and negated Gaussian loss converges more slowly than square loss.Source: §5.1 · pp. 16–17, Figure 5 · p. 17

5.2 Communication-efficient LASSO

  • On synthetic LASSO, DeFW and PG-EXTRA have similar iteration complexity, while random-coordinate DeFW converges fastest and DeFW is most communication-efficient at low accuracy.DeFW loses to BHT at higher accuracy; extreme-coordinate DeFW initially achieves better accuracy than random-coordinate DeFW, which overtakes it as communication cost grows.Source: §5.2 · pp. 18–19, Figure 6 · p. 18
  • On sparco7, DeFW offers the best communication-cost trade-off above ~10^-2 accuracy, while BHT performs best beyond 3 × 10^5 communication cost.The authors describe sparsified DeFW as a better balance of communication and computation complexity.Source: §5.2 · p. 19, Figure 7 · p. 19

6 Conclusions & Open Problems

The paper presents DeFW as a decentralized projection-free method for constrained optimization, with convergence analysis and empirical demonstrations.

6 Conclusions & Open Problems

  • The paper studies DeFW for constrained optimization and analyzes its convergence for convex and non-convex loss functions.Its advantages over previous state-of-the-art methods are demonstrated numerically on two machine-learning problems.Source: §6 · p. 19
  • Numerical experiments demonstrate DeFW’s efficacy on two machine-learning problems.Source: §6 · p. 19
  • Developing an asynchronous version of DeFW is identified as future work.Source: §6 · p. 19

A Proof of Theorem 1

The proof bounds the objective-gap recursion using smoothness, boundedness of the constraint set, and the linear minimization step. Convexity yields an O(1/t) rate, while strong convexity with an interior optimum gives a faster decrement.

A Proof of Theorem 1

  • The linear minimizer and smoothness and boundedness bounds are used to control the objective-gap recursion.The proof defines the gap against an optimal solution and uses a minimizer of the linear objective over C.Source: A Proof of Theorem 1 · p. 20
  • In the convex case, linear-minimizer optimality and convexity bound the linearized term by the objective gap.This bound is substituted into the recursion.Source: A Proof of Theorem 1 · p. 20
  • With γ_t = 2/(t + 1), the recurrence yields an O(1/t) bound on h_t.The passage gives h_t ≤ 2 · (4ρ̄(C_g + LC_p) + Lρ̄²)/(t + 1) for t ≥ 1.Source: A Proof of Theorem 1 · p. 21
  • When F is strongly convex and its optimum lies at distance δ > 0 inside C, a decreased h_t produces a larger decrement and faster convergence.The proof invokes the interior-optimum condition to obtain the stronger decrement.Source: A Proof of Theorem 1 · p. 21

B Proof of Theorem 2

The proof bounds the Frank-Wolfe gap through a smoothness-based one-step inequality, then sums that inequality over the second half of the iterations. It treats step-size regimes separately to obtain the stated bounds.

B Proof of Theorem 2

  • Smoothness bounds each iterate's objective change using the gap, step size, and approximation errors.The displayed bound includes the descent term and terms involving Δd_t and Δp_t.Source: §B.1 · p. 21
  • The Frank-Wolfe gap is nonnegative, enabling lower bounds when the one-step inequality is summed over iterations.The proof sums from T/2 + 1 through T.Source: §B.1 · pp. 21–22
  • For γ_t = t^-α, the proof bounds the summed inequality separately for α ≥ 0.5 and α < 0.5, then divides by the sum of step sizes.This produces the bounds identified as (16) and (17).Source: §B.1 · p. 22

B.2 Convergence to stationary point of (1)

The proof applies a sufficient-condition theorem for sequences in a compact set to establish that DeFW limit points belong to the stationary-point set. It verifies the conditions using descent and boundedness arguments.

B.2 Convergence to stationary point of (1)

  • The sufficient-condition theorem concludes that limit points lie in the stationary set when its sequence conditions hold.The proof checks those conditions for the DeFW iterates.Source: §B.2 · p. 23
  • A limit point outside the stationary set would imply persistent strict descent, contradicting boundedness of F over C.The proof uses the linear minimizer and compactness of C in this contradiction argument.Source: §B.2 · pp. 23–24
  • The proof also verifies the remaining condition by showing iterates must move away from a nonstationary limit point within finite time.It uses the positive accumulated step size and the vanishing error term to complete the stationary-point conclusion.Source: §B.2 · p. 24

C Proof of Lemma 1

The proof establishes the claimed iterate bound by induction, using boundedness of C and the update rule. The induction yields the relation used to complete Lemma 1.

C Proof of Lemma 1

  • Boundedness of C supplies the initial bound for the induction.The proof uses that the diameter of C is bounded by ρ̄.Source: C Proof of Lemma 1 · p. 25
  • The update expresses the next iterate as a convex combination, and boundedness of C controls the induction step.The proof also uses norm equivalence and the induction hypothesis to bound the relevant terms.Source: C Proof of Lemma 1 · p. 25
  • The induction establishes the bound that implies relation (25), completing Lemma 1.The proof identifies this implication as the final step.Source: C Proof of Lemma 1 · p. 25

D Proof of Lemma 2

The proof establishes the stated conditions by induction, using bounds on the recursion and the gradient-averaging error. It also invokes doubly stochasticity and smoothness in bounding that error.

D Proof of Lemma 2

  • Condition (29) is proved by induction, with the base case established through evaluating the recursion and the later step using the induction hypothesis.The proof notes that a term vanishes by the induction hypothesis.Source: D Proof of Lemma 2 · pp. 26–28
  • To prove the second condition, the argument defines gradient-related matrices and derives a recursion for t ≥ 2.The proof uses the equivalence stated for that recursion.Source: D Proof of Lemma 2 · p. 26
  • The gradient-error bound uses the spectral norm bound involving |λ2(W)| and the L-smoothness of fi.The proof also invokes convexity of the ℓ2 norm, the update rule, and Lemma 1 in bounding intermediate terms.Source: D Proof of Lemma 2 · pp. 26–27
  • The induction step bounds the right-hand side of (95) by C2 g/(t + 1)^2α, then takes square roots to complete the step.The passage says this implies (30) from (87).Source: D Proof of Lemma 2 · p. 28

E Proof of Lemma 3

The proof bounds an error vector using consensus updates and concentration arguments for sparsified gradients. It combines a union bound with a bounded-gradient assumption to establish its stated probability guarantee.

E Proof of Lemma 3

  • The proof obtains ∇i tF by applying AC updates to sparsified local gradients for ℓt rounds, with the round count depending on |λ−1 2(W)|.It applies Fact 1 to these updates.Source: E Proof of Lemma 3 · p. 28
  • The concentration argument uses Hoeffding’s inequality and a union bound for the ℓ∞ norm, assuming the gradients are bounded.The passages also state that E[1Ωt] = ξt1 and refer to the probability that a coordinate is included.Source: E Proof of Lemma 3 · pp. 28–29
  • With probability at least 1 − (π²ϵ/6), a stated bound holds for all t ≥ 1 after applying another union bound.The passage gives the bound in terms of (log(2dt2) − log ϵ)/2.Source: E Proof of Lemma 3 · p. 29
Loading 1612.01216v3…