Technical Summary: Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems

Problem Formulation

This paper addresses the challenge of solving constrained optimization problems in a decentralized network setting, specifically targeting high-dimensional scenarios where traditional projection-based methods become computationally intractable. The problem is defined as minimizing a global objective function $F(\theta)$ composed of the average of local functions $f_i(\theta)$ held by $N$ agents, subject to the constraint that the solution $\theta$ lies within a closed, bounded, convex set $C$:

$$\min_{\theta \in \mathbb{R}^d} F(\theta) := \frac{1}{N} \sum_{i=1}^N f_i(\theta) \quad \text{s.t.} \quad \theta \in C$$

The agents communicate over a graph $G=(V, E)$ where $V$ represents the agents and $E$ defines the connectivity. The primary difficulty addressed is that conventional decentralized algorithms based on Projected Gradient Descent (PGD) require a projection step onto $C$ at every iteration. For high-dimensional problems (e.g., matrix completion or sparse learning), this projection step is often computationally prohibitive (e.g., requiring full Singular Value Decomposition or sorting operations).

Methodology: The Decentralized Frank-Wolfe (DeFW) Algorithm

To overcome the computational bottleneck of projection, the authors propose the Decentralized Frank-Wolfe (DeFW) algorithm. This approach extends the classical Frank-Wolfe (FW) or Conditional Gradient algorithm to a decentralized setting. The core innovation is replacing the costly projection step with a constrained linear optimization (LO) step, which is often computationally efficient for specific constraint sets (e.g., $\ell_1$-balls or trace-norm balls).

Algorithmic Structure

The DeFW algorithm operates in iterations $t$. At each step, agents perform three main actions:

1. Consensus (Iterate Approximation): Agents approximate the global average iterate $\bar{\theta}_t$ using a near-neighbor information exchange (Average Consensus). Let $\bar{\theta}_i^t$ denote agent $i$'s local approximation.
2. Aggregation (Gradient Approximation): Agents approximate the global gradient $\nabla F(\bar{\theta}_t)$. Since agents only have access to local gradients $\nabla f_i(\bar{\theta}_i^t)$, they compute a local gradient approximation $\nabla_i^t F$. To achieve this efficiently without multiple communication rounds, the authors employ a gradient tracking mechanism (inspired by SAGA). Agents maintain a surrogate gradient $\nabla_i^t F$ updated via:
   $$\nabla_i^t F = \nabla_i^{t-1} F + \nabla f_i(\bar{\theta}_i^t) - \nabla f_i(\bar{\theta}_i^{t-1})$$
   This surrogate is then averaged across the network using a single round of consensus.
3. Frank-Wolfe Step: Each agent solves a linear optimization problem over $C$ using its local gradient approximation to find a direction $a_i^t$:
   $$a_i^t \in \arg\min_{a \in C} \langle \nabla_i^t F, a \rangle$$
   The iterate is then updated as a convex combination:
   $$\theta_i^{t+1} = (1 - \gamma_t)\bar{\theta}_i^t + \gamma_t a_i^t$$
   where $\gamma_t$ is a diminishing step size.

Convergence Analysis Framework

The authors analyze the convergence of DeFW by viewing it as an inexact FW algorithm. They establish two key assumptions regarding the accuracy of the local approximations:

• Assumption 1: The consensus error on iterates decays as $\max_i \|\bar{\theta}_i^t - \bar{\theta}_t\| \leq \Delta_{p,t}$.
• Assumption 2: The consensus error on gradients decays as $\max_i \|\nabla_i^t F - \nabla_t F\| \leq \Delta_{d,t}$.

The paper demonstrates that a consensus-based implementation using a fixed number of communication rounds (specifically, one round for iterates and one round for gradient surrogates) satisfies these assumptions with $\Delta_{p,t}, \Delta_{d,t} = O(1/t^\alpha)$.

Key Contributions and Theoretical Results

1. Convergence Rates

The paper provides rigorous convergence guarantees for DeFW under different objective function properties:

• Convex Objectives: With a step size $\gamma_t = 2/(t+1)$, the sub-optimality of the objective value converges at a rate of $O(1/t)$.
• Strongly Convex Objectives: If the optimal solution lies in the interior of the constraint set $C$, the convergence rate improves to $O(1/t^2)$.
• Non-Convex Objectives: For smooth but non-convex objectives, the algorithm converges to a stationary point. The FW gap (a measure of stationarity) decays at a rate of $O(1/\sqrt{t})$ when the step size is set to $\gamma_t = 1/\sqrt{t}$. The authors note that this rate is comparable to centralized projected gradient methods for non-convex problems.

2. Consensus-Based Implementation

A significant contribution is the demonstration that these theoretical guarantees can be achieved with a constant number of communication rounds per iteration (specifically, two rounds: one for iterates and one for gradient surrogates). This is achieved through the specific gradient tracking update rule, which avoids the need for logarithmic communication rounds often required to achieve high-precision consensus in decentralized settings.

3. Sparsified DeFW for Communication Efficiency

For applications like LASSO where communication bandwidth is a bottleneck, the authors propose a sparsified DeFW variant. In this version, agents exchange only a subset of coordinates (either randomly selected or the largest magnitude coordinates) of the gradient surrogate. Theoretical analysis shows that with appropriate selection of the number of coordinates, the algorithm maintains the convergence guarantees of the standard DeFW while significantly reducing communication costs.

Applications and Numerical Results

The paper validates the DeFW algorithm on two specific applications:

1. Decentralized Matrix Completion:

   • Problem: Recovering a low-rank matrix from incomplete, noisy observations distributed across agents.
   • Constraint: Trace-norm ball (promoting low rank).
   • Results: DeFW successfully recovers the matrix with convergence rates matching theoretical predictions. It outperforms decentralized projected gradient (DPG) methods in terms of computational time per iteration because it avoids full SVD projections. The algorithm also demonstrates robustness to sparse noise when using a non-convex negated Gaussian loss function.

2. Communication-Efficient Sparse Learning (LASSO):

   • Problem: Distributed sparse linear regression with $\ell_1$ constraints.
   • Constraint: $\ell_1$-ball (promoting sparsity).
   • Results: The sparsified DeFW algorithm achieves a favorable trade-off between communication cost and accuracy. In experiments, it outperforms DPG and PG-EXTRA in low-accuracy regimes regarding communication efficiency and matches the performance of Iterative Hard Thresholding (BHT) while offering a better balance between communication and computational complexity.

Significance and Claims

The paper claims to present the first decentralized Frank-Wolfe algorithm. Its significance lies in:

• Scalability: By eliminating the projection step, DeFW makes decentralized optimization feasible for high-dimensional problems where projection is too expensive (e.g., large-scale matrix completion or high-dimensional sparse learning).
• Non-Convex Guarantees: It provides one of the first convergence analyses for decentralized projection-free methods on non-convex objectives, establishing a convergence rate to stationary points comparable to centralized methods.
• Communication Efficiency: The consensus-based implementation achieves these guarantees with a minimal, constant number of communication rounds, making it suitable for bandwidth-constrained networks.
• Practical Utility: Numerical experiments on synthetic and real-world data (MovieLens) confirm that the algorithm is not only theoretically sound but also practically efficient, often outperforming state-of-the-art decentralized gradient methods in terms of runtime and robustness.

The authors conclude that while the current work focuses on synchronous, static networks, future directions include developing asynchronous versions of the DeFW algorithm.