AI Research Portal

This paper investigates non-smooth stochastic decentralized optimization problems over time-varying networks, where objective functions are distributed across nodes and network connections can change intermittently. The core idea is to extend existing theory, which primarily focused on smooth settings or time-invariant networks, to this more general non-smooth and stochastic setting, including both convex minimization and convex-concave saddle point problems. The authors propose an algorithm that reformulates these problems into a monotone inclusion problem and establishes upper bounds on the number of stochastic oracle calls and communication rounds, which are claimed to match known lower bounds, thus achieving optimal convergence rates.

The paper addresses several bottlenecks in decentralized optimization:

Non-smoothness and Stochasticity: Prior works have primarily focused on smooth settings or deterministic scenarios, or time-invariant networks. The paper aims to extend the theory to the more general non-smooth and stochastic settings.

First Optimal Convergence Rates for Stochastic Decentralized Non-Smooth Convex Problems: The paper establishes the first optimal convergence rates for stochastic decentralized non-smooth convex problems over time-varying graphs (Theorems 2, 3).
First Optimal Convergence Rates for Stochastic Decentralized Non-Smooth Saddle Point Problems: The paper establishes the first optimal convergence rates for stochastic decentralized non-smooth saddle point problems over time-varying graphs (Theorems 2, 3).
Optimal Convergence Rates for Deterministic Non-Smooth Saddle Point Problems: The paper also establishes optimal convergence rates for deterministic decentralized non-smooth saddle point problems over time-varying graphs (Corollary of Theorems 2, 3).
Generalization of Deterministic Algorithm: The deterministic algorithm from Kovalev et al. (2024) is generalized to handle arbitrary stochastic monotone operators, making it applicable to a broader class of real-world problems.

The method addresses stochastic decentralized optimization problems by reformulating them into a monotone inclusion problem and solving it using an accelerated Forward-Backward Algorithm.

Problem Reformulation: The paper considers two main problem types:

Stochastic decentralized (strongly) convex non-smooth optimization: min p(x) = (1/n) ∑_{i=1}^n fi(x) + (r/2)||x||²
Stochastic decentralized (strongly) convex-(strongly) concave non-smooth optimization: min max p(ξ, ζ) = (1/n) ∑_{i=1}^n fi(ξ, ζ) + (r/2)||ξ||² - (r/2)||ζ||²

These problems are unified by defining an associated operator Ti(x). For problem (1), Ti(x) = ∂fi(x). For problem (2), Ti(x) = [∂ξ fi(ξ, ζ), -∂ζ fi(ξ, ζ)], where x = (ξ, ζ). The decentralized optimization problem is then reformulated as a monotone inclusion problem: find u ∈ E such that 0 ∈ A(u) + B(u), where A(u) and B(u) are operators derived from the problem structure and network communication.

Time-Varying Network Model: The communication network is represented as a time-varying graph G(t) = (V, E(τ)), where E(τ) denotes the time-varying set of edges. Node interaction is modeled through a gossip matrix W(τ) : R+ → R^(n×n), which satisfies specific properties (Assumption 5) related to network structure and convergence to the average. A condition number κ ≥ 1 quantifies network connectivity (Assumption 6).

Stochastic Oracle: A stochastic decentralized oracle returns a random vector ği(x) for an operator Ti(x) such that:

E[ği(x)] = gi ∈ Ti
E[||ği(x) - gi||²] ≤ σ² where σ > 0 is a bound on the variance.

Algorithm: The proposed Algorithm 1 is an iterative method that combines Nesterov's acceleration for the operator A (which corresponds to the gradient of a smooth function) with updates for operator B (which incorporates the non-smooth operator T). It introduces an additional input variable m for an error-feedback mechanism. The algorithm involves K outer iterations and T inner iterations.

Decentralized communication: Steps 7 and 8 involve updates using the gossip matrix W(τ) and parameters γk, ηk, θk.
Stochastic oracle call: Step 12 involves calling the stochastic oracle ğk,t.
Nesterov's acceleration: The y and z updates are accelerated using Nesterov's method.

Problem Formulations:
- Convex: min_{x∈R^d} p(x) = (1/n) ∑_{i=1}^n fi(x) + (r/2)||x||²
- Saddle Point: min_{ξ∈R^de} max_{ζ∈R^ds} p(ξ, ζ) = (1/n) ∑_{i=1}^n fi(ξ, ζ) + (r/2)||ξ||² - (r/2)||ζ||²
- Asymmetric Saddle Point: p(ξ, ζ) = (1/n) ∑_{i=1}^n fi(ξ, ζ) + (r_ξ/2)||ξ||² - (r_ζ/2)||ζ||²
Assumptions:
- Assumption 1: fi(x) is convex in x for problem (1).
- Assumption 2: fi(ξ, ζ) is convex in ξ for fixed ζ, and concave in ζ for fixed ξ for problem (2).
- Assumption 3: Existence of a solution x* with ||x*|| ≤ R.
- Assumption 4: Bounded operators, ||gi|| ≤ M for gi ∈ Ti(x).
- Assumption 5: Gossip matrix W(τ) properties (W(τ)ij = 0 if i ≠ j and (j,i) ∉ E(τ); W(τ)1n = 0 and W(τ)T1n = 0).
- Assumption 6: Network connectivity constant κ ≥ 1 such that ||W(τ)x - (1/n)1n1n^T x||² ≤ (1 - 1/κ)||x - (1/n)1n1n^T x||² for all x ∈ R^n: ∑_{i=1}^n xi = 0.
Stochastic Oracle: Definition 4, with E[ği(x)] = gi ∈ Ti and E[||ği(x) - gi||²] ≤ σ².
Gap Functions:
- Gcvx(x) = p(x_0) - p(x*) for problem (1).
- GSPP(x) = p(ξ_0, ζ*) - p(ξ*, ζ_0) for problem (2).
Algorithm 1 Parameters: K, T ∈ {1, 2, ...}, and sequences {(αk, βk, γk, σk, λk)} for k = 0, ..., K-1. Specific values for these parameters are not stated in the paper.
Output: The algorithm outputs an average of iterates x_o^K = (1/K) ∑_{k=1}^K x_o^k.
Experimental Setup:
- Graph Type: Synthetic random graphs constructed using the Erdős-Rényi model.
- Network Scenarios: Time-static (graph fixed) and time-varying (edges randomly removed/added at each iteration).
- Test Problem: Non-smooth saddle-point problem: min max p(ξ, ζ) = ∑_{i=1}^n fi(ξ, ζ) + (r/2)||ξ||₁ - (r/2)||ζ||₁, where r = 10⁻³ and fi(ξ, ζ) = ||ξ - c_ξ,i||₁ - ||ζ - c_ζ,i||₁.
- Constants: c_ξ,i and c_ζ,i are fixed constants.
- Iterations: K ∈ {1, ..., 30}, fixed parameter T = 10.

Datasets: Not stated in the paper. Experiments are conducted on synthetic random graphs.
Metrics:
- Euclidean distance to the objective: ||x_o^K - x*||
- Saddle point residual: f(ξ^K, ζ*) - f(ξ*, ζ^K)
Baselines: Not stated in the paper.
Numeric Results: No specific numeric results are reported. Performance is shown qualitatively through plots.
- Time-Varying Graphs (Figure 3): The Euclidean distance and saddle-point residual generally decrease over iterations (K), but exhibit some fluctuations due to the randomness in the graph structure.
- Time-Static Graphs (Figure 4): Both metrics show a more stable and monotonic decrease in error across iterations compared to the time-varying scenario.
Runtime/Training Cost:
- Strongly Monotone Case (r > 0):
  - Decentralized communications: O(√(κM / (rε)))
  - Oracle calls: O(((M + σ)² / (rε)))
- Monotone Case (r = 0):
  - Decentralized communications: O(κMR / ε²)
  - Oracle calls: O(((M + σ)²R² / ε²))
- Asymmetric Saddle Point (r_ξ > 0, r_ζ > 0):
  - Decentralized communications: O(√(κM / ε) * √(1/r_ξ + 1/r_ζ))
  - Oracle calls: O(((M + σ)² / ε) * (1/r_ξ + 1/r_ζ))
- The algorithm requires K decentralized communication rounds and K × T stochastic oracle calls.

Asymmetric Oracle Cost: A possible future direction is studying the case of asymmetric oracle cost in saddle point problems, where the computational cost of querying the convex (primal) and concave (dual) oracles may differ (e.g., in GANs). Extending the current analysis could result in a better convergence rate with this assumption.

Method evidence: "We follow this reformulation, extending the analysis to stochastic primal settings and saddle-point problems." (section: 3 Stochastic Decentralized Setting)
Result evidence: "Figure 3 presents the performance of the method under the time-varying graph setting. As observed, the randomness in the graph structure introduces some fluctuations in both performance metrics. Conversely, Figure 4 illustrates the results under the time-static setting, where the graph remains fixed. In this case, we observe a more stable and monotonic decrease in error across iterations." (section: 6 Experiments)
Limitation evidence: "A possible future direction may be studying the case of asymmetric oracle cost. In saddle point problems, the computational cost of querying the convex (primal) and concave (dual) oracles may differ (e.g., in GANs). Extending our analysis could result in a better convergence rate with this assumption." (section: 7 Conclusion)

Stochastic Decentralized Optimization of Non-Smooth Convex and Convex-Concave Problems over Time-Varying Networks

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures