Technical Summary: Distributed Online Convex Optimization with Efficient Communication

1. Problem Formulation

The paper investigates Distributed Online Convex Optimization (D-OCO) under the constraint of compressed communication. In this setting, $n$ learners are connected via an undirected graph $G = ([n], E)$. In each round $t \in [T]$, each learner $i$ selects a decision $x_i(t)$ from a convex set $X \subseteq \mathbb{R}^d$ and suffers a local loss $f_{t,i}(x_i(t))$. The collective goal is to minimize the cumulative global loss defined as $f_t(x) = \sum_{j=1}^n f_{t,j}(x)$.

The primary challenge addressed is the communication bottleneck. Transmitting full gradients or decision vectors between learners is costly when $n$ is large. To mitigate this, learners communicate compressed data using a compression operator $C(\cdot)$. The quality of compression is characterized by a factor $\omega \in (0, 1]$, where $\omega=1$ implies no compression and smaller $\omega$ indicates higher compression (and potentially higher error). The communication network is characterized by a doubly stochastic matrix $P$ with a spectral gap $\rho = 1 - \sigma_2(P) \in (0, 1]$.

The performance metric is the regret:
$$R(T, i) = \sum_{t=1}^T \sum_{j=1}^n f_{t,j}(x_i(t)) - \min_{x \in X} \sum_{t=1}^T \sum_{j=1}^n f_{t,j}(x)$$

Prior work (specifically Tu et al., 2022) established regret bounds of $\tilde{O}(\max\{\omega^{-2}\rho^{-4}n^{1/2}, \omega^{-4}\rho^{-8}\}n\sqrt{T})$ for convex functions. The authors identify that these bounds suffer from a quadratic or quartic dependence on $\omega^{-1}$ and a super-linear dependence on $n$, which are undesirable for large-scale, highly compressed systems.

2. Methodology: Top-DOGD

The authors propose a novel algorithm termed Two-level Compressed Decentralized Online Gradient Descent (Top-DOGD). The core technical contribution is a two-level blocking update framework that integrates two specific strategies to control consensus error, compression error, and projection error.

2.1. The Two-Level Blocking Framework

Instead of updating decisions every round, the total $T$ rounds are partitioned into blocks of size $L = L_1 + L_2$. Within each block, the decision $x_i(b)$ remains constant, and updates occur only at the end of the block. This structure allows the algorithm to distribute multiple communication rounds across the rounds within a block, satisfying the constraint of one communication per round while enabling more sophisticated error correction.

2.2. Strategy 1: Online Compressed Gossip ($L_1$ rounds)

To address consensus error (divergence among learners) and compression error, the algorithm employs a multi-step gossip protocol within the first $L_1$ rounds of each block.

• Learners perform multiple steps of the Choco-gossip protocol (Koloskova et al., 2019), which uses difference compression to track the state of neighbors.
• By setting $L_1 = \lceil 2 \ln(14n) / (\gamma \rho) \rceil$, the algorithm ensures that the consensus and compression errors decay exponentially, achieving a tighter bound than single-step gossip.

2.3. Strategy 2: Projection Error Compensation ($L_2$ rounds)

In D-OCO, learners must project their decisions onto the feasible domain $X$ at each step. This projection introduces a projection error that, in previous methods, led to an $O(n)$ dependence in the regret bound.

• The authors propose a projection error compensation scheme. Learners recursively compress the residual of the projection error ($r_i = \Pi_X(y) - y$) and transmit these residuals to neighbors.
• By utilizing a repeated compressor (Huang et al., 2022) over $L_2 = \lceil \ln(8n) / \omega \rceil$ rounds, the compression error of the projection residual is reduced to $O(1/n)$.
• This effectively eliminates the linear dependence on $n$ caused by projection errors, a key limitation in prior work.

3. Key Contributions and Results

3.1. Improved Regret Bounds

The paper establishes significantly improved regret bounds for both convex and strongly convex loss functions, demonstrating a superior dependence on the compression ratio $\omega$, spectral gap $\rho$, and number of learners $n$.

• Convex Functions:
  • Previous (Tu et al., 2022): $O(\max\{\omega^{-2}\rho^{-4}n^{1/2}, \omega^{-4}\rho^{-8}\}n\sqrt{T})$
  • This Work: $\tilde{O}(\omega^{-1/2}\rho^{-1}n\sqrt{T})$
• Strongly Convex Functions:
  • Previous (Tu et al., 2022): $O(\max\{\omega^{-2}\rho^{-4}n^{1/2}, \omega^{-4}\rho^{-8}\}n \ln T)$
  • This Work: $\tilde{O}(\omega^{-1}\rho^{-2}n \ln T)$

The notation $\tilde{O}$ hides constant factors and polylogarithmic factors in $n$. The improvement is particularly notable in the reduction of the $\omega$ dependence from quadratic/quartic to square-root/linear, and the reduction of the $n$ dependence.

3.2. Lower Bounds

The authors establish the first lower bounds for D-OCO with compressed communication, justifying the near-optimality of their results:

• Convex: $\Omega(\omega^{-1/2}\rho^{-1/4}n\sqrt{T})$
• Strongly Convex: $\Omega(\omega^{-1}\rho^{-1/2}n \ln T)$

These lower bounds match the upper bounds of Top-DOGD up to factors of $\rho$ and polylogarithmic terms in $n$, confirming that the algorithm's dependence on $\omega$ and $T$ is essentially optimal.

3.3. Extension to Bandit Feedback

The method is extended to bandit feedback settings (where only loss values, not gradients, are available) using classic gradient estimators:

• One-point feedback: Achieves $\tilde{O}(\omega^{-1/4}\rho^{-1/2}d^{1/2}n T^{3/4})$ for convex and $\tilde{O}(\omega^{-1/3}\rho^{-2/3}d^{2/3}n T^{2/3}(\ln T)^{1/3})$ for strongly convex functions.
• Two-point feedback: Achieves $\tilde{O}(\omega^{-1/2}\rho^{-1}dn\sqrt{T})$ for convex and $\tilde{O}(\omega^{-1}\rho^{-2}d^2n \ln T)$ for strongly convex functions.
  These results improve upon existing bounds in the bandit setting as well.

4. Significance and Claims

The paper claims that the proposed Top-DOGD algorithm overcomes the limitations of prior communication-efficient methods by explicitly addressing the interplay between decentralization, compression, and projection.

• Optimality: The establishment of lower bounds provides a theoretical justification that the improved dependence on $\omega$ and $T$ cannot be significantly further improved without changing the problem setting.
• Scalability: The reduction in the dependence on $n$ and $\omega$ makes the algorithm more suitable for large-scale distributed systems where communication bandwidth is limited and the number of agents is large.
• Unified Framework: The two-level blocking update structure is presented as a unified framework that successfully integrates online compressed gossip and error compensation, resolving the dilemma of requiring multiple communication rounds per update while maintaining a single communication per round in the overall timeline.

The authors emphasize that their results represent a step forward in the theoretical understanding of distributed online learning under communication constraints, providing a foundation for more efficient distributed algorithms in streaming data environments.