Adaptive Decentralized Composite Optimization via Three-Operator Splitting

1. Problem Formulation

The paper addresses decentralized composite optimization over a network of $m$ agents. The goal is to minimize a global objective function $u(x)$ defined as the sum of local smooth losses and local nonsmooth regularizers:
$$\min_{x \in \mathbb{R}^d} u(x) := \sum_{i=1}^m f_i(x) + \sum_{i=1}^m r_i(x)$$
Key Characteristics:

• Smoothness: The local loss functions $f_i$ are assumed to be (strongly) convex but only locally smooth (Lipschitz continuous gradients locally, not necessarily globally).
• Nonsmoothness: The regularizers $r_i$ are convex, proper, extended-value functions (e.g., indicator functions of sets, $\ell_1$ norms) and are private to each agent.
• Network: Agents communicate over a fixed, undirected, connected graph without a central server.
• Limitation of Existing Methods: Current decentralized algorithms typically require:
  1. Global smoothness of $f_i$.
  2. Identical regularizers ($r_i = r$) or specific structures.
  3. Global problem parameters (e.g., global Lipschitz constants, spectral gap of the graph) to set conservative, fixed stepsizes. This leads to manual tuning, poor performance, and failure in locally smooth scenarios.

2. Methodology

The authors propose DATOS (Decentralized Adaptive Three-Operator Splitting), a family of algorithms that adaptively adjust stepsizes using only local information and neighbor-to-neighbor communication.

A. Algorithmic Framework

The method is built upon a Davis-Yin Three-Operator Splitting applied to a specific reformulation of the problem:

1. BCV Reformulation: The problem is reformulated using the Bertsekas–O'Connor–Vandenberghe (BCV) technique. This introduces local copies $x_i$ and slack variables $\tilde{x}_i$, enforcing consensus via a linear constraint $LX = 0$.
2. BCV Preconditioning: A crucial innovation is the introduction of a specific metric matrix $M$ (the BCV metric) in the reformulation. This metric allows the proximal operator of the consensus constraint to be computed locally by agents, avoiding the need for global matrix inversions or transmissions of high-dimensional vectors.
3. Primal-Dual Structure: The algorithm operates as a primal-dual scheme, tracking primal variables ($X$), dual variables ($S$), and auxiliary tracking variables ($D, T$).

B. Adaptive Stepsize Strategy

The core novelty is the adaptive stepsize selection via local backtracking:

• Merit Function: A Lyapunov function (merit function) is constructed based on the distance to the saddle point of the Lagrangian.
• Local Backtracking: Each agent $i$ performs a local line search to find the largest stepsize $\alpha_i$ satisfying a descent condition on its local loss $f_i$.
• Consensus on Stepsize: To ensure global convergence, agents must agree on a common stepsize. The paper proposes two implementations:
  1. Global Min-Consensus (Algorithm 2.1): Agents broadcast their local stepsizes, and the network computes the global minimum ($\alpha_k = \min_i \alpha_{k,i}$). This can be implemented efficiently in modern wireless mesh networks (e.g., using LoRa for scalar broadcasting).
  2. Local Min-Consensus (Algorithm 4.1): Agents only exchange stepsizes with immediate neighbors. The algorithm proves that under mild conditions, the local stepsizes eventually synchronize to a uniform value, recovering the convergence properties of the global version.
• No Global Knowledge: The method requires no prior knowledge of global Lipschitz constants, network topology (spectral gap), or problem parameters.

3. Key Contributions

1. First Parameter-Free Decentralized Composite Solver: The proposed algorithms are the first to solve composite problems with locally smooth losses and private nonsmooth terms using only neighbor communications, without requiring global network or problem constants.
2. Novel BCV Metric Design: The design of the BCV metric $M$ enables a fully decentralized implementation of the three-operator splitting, specifically allowing the computation of the consensus proximal step locally.
3. Robust Convergence Guarantees:
   • Sublinear Rate: Under mere convexity, the algorithms converge with a rate of $O(1/k)$.
   • Linear Rate: Under local strong convexity of $f_i$ and partial smoothness of $r_i$ (a broad class including $\ell_1$ norms and polyhedral constraints), the algorithms achieve linear convergence.
   • Finite-Time Identification: The algorithm identifies the active manifold (where the nonsmooth function behaves smoothly) in finite time, after which it enters the linear convergence regime.
4. Adaptive Three-Operator Splitting: As a byproduct, the authors derive a new adaptive three-operator splitting algorithm for centralized/federated settings, which is also parameter-free and converges linearly under strong convexity.

4. Results

The paper validates the theory through extensive numerical experiments on three tasks:

1. Logistic Regression with $\ell_1$-regularization:
   • DATOS (both global and local variants) significantly outperformed non-adaptive baselines (SONATA, PG-EXTRA) and the adaptive centralized method adapted to decentralized settings (adaPDM).
   • DATOS required no manual tuning, whereas baselines required grid-searching for optimal stepsizes.
2. Maximum Likelihood Estimation of Covariance Matrix:
   • A case where $f_i$ is only locally smooth.
   • Non-adaptive methods (SONATA, PG-EXTRA) failed to converge or required extremely conservative stepsizes. DATOS converged robustly and rapidly.
3. Linear Regression with Elastic Net:
   • Demonstrated linear convergence behavior in the strongly convex setting.
   • The observed convergence slopes matched the theoretical predictions, showing superior performance on sparse graphs compared to baselines.

Key Finding: The performance gap between the "Global Min-Consensus" and "Local Min-Consensus" variants was negligible, especially on well-connected graphs, validating the efficiency of the purely local communication approach.

5. Significance

This work bridges a critical gap in decentralized optimization:

• Practicality: It removes the reliance on "global knowledge" (Lipschitz constants, graph spectral gaps) which is often unavailable in real-world distributed systems (e.g., sensor networks, IoT).
• Robustness: By handling local smoothness, the method applies to a wider class of problems (like covariance estimation) where global smoothness assumptions fail.
• Efficiency: The adaptive stepsize strategy automatically adjusts to the local geometry of the problem, often leading to faster convergence than manually tuned, conservative fixed-stepsize methods.
• Theoretical Depth: The proof of linear convergence under partial smoothness and local strong convexity provides a rigorous foundation for the observed empirical speedups, establishing that adaptivity does not come at the cost of convergence guarantees.

In summary, the paper presents a theoretically sound, parameter-free, and highly efficient framework for solving complex decentralized optimization problems in realistic, information-constrained network environments.