Agreeing on the Top-k: Low-Bit Decentralized Continuous Greedy

Many selection problems are spread across machines or robots that can only talk to nearby peers. Examples include picking a small set of representative movies to recommend, placing sensors, or choosing exemplar images. These objectives are submodular: adding an item helps less the more you already have. The standard decentralized method, continuous greedy, relaxes the set to a fractional vector and runs Frank-Wolfe, a projection-free optimizer that repeatedly moves toward the best corner of the feasible region. With gradient tracking, where each node keeps a running estimate of the network-average gradient, this recovers the best possible $(1-1/e)$ guarantee in $O(1/\epsilon)$ communication rounds (Decentralized Gradient Tracking for Continuous DR-Submodular Maximization). Each of those rounds, however, sends full-precision vectors as long as the entire item catalogue. On a 0.25 Mbps robot mesh link (Communication- and Computation-Efficient Distributed Decision-Making in Multi-Robot Networks), that payload, not the number of rounds, is what limits speed.

This proposal starts from a structural fact. Under a cardinality constraint ("choose $k$ items"), the Frank-Wolfe step does not need the gradient at all. It needs only which $k$ coordinates are largest. If every node agrees on that set, every node takes the same step, and the fractional iterates stay identical without ever being exchanged. The communication a decentralized continuous greedy truly needs is therefore set by agreement on a top-$k$ ranking, not by gradient precision. We propose to build a compressed gradient-tracking method whose bit budget follows this agreement requirement. We will prove its approximation guarantee as a function of bits, not rounds. We will then test whether this ranking-aware design beats plain off-the-shelf compression at equal bits.

Core Claim

For monotone DR-submodular maximization over a cardinality or partition-matroid polytope, the chosen vertex is exactly correct whenever each node's tracked-gradient error is below half the gap between the $k$-th and $(k{+}1)$-th largest coordinates. We call this gap the ranking margin. The claim follows directly from the fact that a top-$k$ selection is unchanged by perturbations smaller than half the gap. The same reasoning bounds the damage when the margin is violated. Let $\hat g_i$ be node $i$'s tracked gradient and $g$ the true average gradient. The linear-subproblem value lost by node $i$ is at most

$$\langle g, v^\star\rangle - \langle g, v_i\rangle \le 2k\,\|\hat g_i - g\|_\infty,$$

where $v^\star$ is the correct top-$k$ indicator vertex and $v_i$ is the vertex node $i$ picks. Standard Frank-Wolfe analysis for DR-submodular functions absorbs an additive per-step error $\delta_t$ into the final gap as $\frac{1}{T}\sum_t \delta_t$. It follows that the error to control is in the $\ell_\infty$ norm, and only near the ranking boundary, not the full-vector $\ell_2$ error that generic compressors are built to shrink.

Two design consequences follow. First, the iterate channel can be removed. Iterates stay equal whenever vertices agree, so a node only needs to broadcast its $k$ selected indices. That costs $k\log_2|V|$ bits, where $|V|$ is the catalogue size, and it lets neighbors detect and repair disagreement. Second, the gradient channel can be compressed with a threshold-sparsifier. Each message carries the top-$(k{+}r)$ coordinates of the tracked-gradient difference, a coarse low-bit quantization of the rest, and error feedback, meaning unsent residuals accumulate locally and are sent later. The per-round bit budget grows only when a node's local estimate of the ranking margin shrinks.

Relation to Prior Work

The method builds on decentralized continuous greedy. Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings introduced it with neighbor averaging. DeGTFW/DeSGTFW (Decentralized Gradient Tracking for Continuous DR-Submodular Maximization) and DeSVRFW-gt (Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization) added gradient tracking and variance reduction to reach $O(1/\epsilon)$ rounds. All three send full-precision vectors. We keep their tracking recursion and change what is sent. The DeSVRFW-gp result also constrains the design: plain gossip without tracking converges only to an error neighborhood, so we do not drop tracking to save bits.

Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization is the closest work on communication cost. Its DOBGA and Mono-DMFW methods cut communication to one round per step and report 400x and 3000x speedups over DMFW on MovieLens. They reduce how often nodes talk, not how much each message carries. Our method is orthogonal to theirs and could be combined with it.

Two papers supply the compression machinery and warn about its risks. Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free shows that naively quantized Frank-Wolfe diverges and needs variance reduction. It works only in master-worker topologies and never on submodular objectives. Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization shows how to combine Choco-style compressed gossip with gradient tracking, but only for unconstrained gradient descent. We take its difference-compression-plus-tracking template and replace the unconstrained step with a margin-aware Frank-Wolfe step.

Two further lines provide contrast. GreeDi (Distributed Submodular Maximization: Identifying Representative Elements in Massive Data) partitions the data, lets each machine pick locally, and merges the picks at a coordinator. RAG (Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks) lets each robot compete only with its immediate neighbors and sends exact marginal gains. Neither compresses its messages, and GreeDi requires a hub.

Research Program

The first part is theoretical. We will prove an approximation bound of the form $(1-1/e)\mathrm{OPT} - O(\text{consensus} + \text{compression} + 1/T)$. The compression term will be expressed through the $\ell_\infty$ tracking error, and total bits will be an explicit function of the compressor. We will then state a margin-dependent refinement. If the true gradients along the trajectory keep a ranking margin $\gamma$, then a budget of roughly $\log_2(G/\gamma)$ bits per retained coordinate suffices for exact vertex agreement, where $G$ bounds the gradient magnitude. This bound comes from quantizing a range $G$ at resolution $\gamma/2$. The bound says nothing useful when margins are tiny. In that regime we fall back on the $2k\|\cdot\|_\infty$ bound and report how often it binds.

The second part is algorithmic. We will build three pieces:

  • a threshold-sparsifier with error feedback on the tracked-gradient channel;
  • index-only messages on the iterate channel, with a repair step that averages full iterates only when neighbors' index sets disagree;
  • local rules that estimate the ranking margin and set each node's bit budget, which needs neighbor-free estimates.

We will cover cardinality constraints and partition-matroid constraints. For the partition matroid, the Frank-Wolfe step is a per-block top-$k$ selection, so the same argument applies block by block. After the final step, the fractional solution is rounded to a set, and nodes agree on the rounding by sharing a random seed.

Baselines

The naive reference point is uncompressed DeGTFW (Decentralized Gradient Tracking for Continuous DR-Submodular Maximization) sending 32-bit vectors. We run it for the same number of rounds, and it defines 100% objective value for the continuous methods. The file gives only communication complexities and curves for it on MovieLens and non-convex quadratic programs; no reported result found on Lacuna for its numeric MovieLens objective value, so we will re-run it ourselves.

The strongest competitor is generic compressed gradient tracking. We will run the Choco-gossip difference-compression recipe of Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization inside DeGTFW. In one variant it uses the $s$-level $L_\infty$ quantizer and SPIDER variance reduction from QFW; in another it uses top-$k$ sparsification. It is the strongest because it is exactly what a practitioner would try first, and it may well work. For bit reduction on a Frank-Wolfe method, the only reported figure in the file is QFW's $3\times10^8$ bits versus $3.8\times10^9$ bits for unquantized Frank-Wolfe on MNIST logistic regression. That is a different task, so we cite it only as the expected order of magnitude.

For fairness, every method gets the same partitioned data and communication graph. Each gets the same tuning budget: a fixed grid over step sizes, quantization levels, and sparsity levels, the same number of configurations for each method, selected on a held-out seed. Methods are compared at matched total bits. Our method "beats" this baseline if it reaches 99% of uncompressed DeGTFW's objective with at least 3x fewer total bits across both MovieLens scales. A tie at matched bits counts as a negative result for the ranking-aware ingredients.

We add GreeDi as the coordinator-based discrete reference and count all transmitted items as bits. Its reported quality is 98% of centralized greedy on Tiny Images and 97% on Yahoo! Front Page (Distributed Submodular Maximization: Identifying Representative Elements in Massive Data, Distributed Submodular Maximization).

Two ablations isolate the key ingredients. The first keeps our compressor but restores full iterate exchange; this measures what index-only iterates save. The second keeps index-only iterates but uses a fixed-rate compressor with no margin adaptation; this measures what margin awareness adds.

Why not just…?

Why not just run GreeDi with a coordinator? When a hub exists and the number of machines $m$ is moderate, GreeDi is cheap and strong: it keeps 90–98% of centralized quality in two rounds. We will report its bit count honestly. Our claim is limited to settings with no hub, such as mesh networks and robot swarms. It also covers settings with large $m$, where GreeDi's worst-case $1/\min(m,k)$ bound and coordinator memory become problems. The experiment sweeps $m$ from 8 to 100 on MovieLens-1M and records where, if anywhere, GreeDi's quality drops below the decentralized methods at matched bits.

Why not just use off-the-shelf compressed gradient tracking with error feedback? This is the real threat. Error feedback may already keep the $\ell_\infty$ error small enough that vertices agree almost every round, which would make margin awareness redundant. QFW's divergence result argues that naive compression fails for Frank-Wolfe, but that result concerns unmitigated quantization, not error feedback. The second ablation settles the question directly. We will also log the per-round vertex-disagreement rate for both methods. If the generic method already agrees over 99% of the time at low bits, we will drop the margin-adaptive component and present the result as a proof and study of generic compression for this problem.

Why not just communicate less often, as in DOBGA or a single late merge? Fewer rounds and smaller messages attack different factors of total bits, so they can be combined. The single-merge result of On The Surprising Effectiveness of a Single Global Merging in Decentralized Learning was shown for neural network weights. For Frank-Wolfe, a wrong early vertex is permanently added into the iterate, which suggests merging late may not transfer. We test this with a late-burst schedule at matched bits and with DOBGA with and without our compressor.

Proposed Experiments

The benchmarks follow the file.

  • MovieLens-1M facility location: 100 nodes, as in the original decentralized continuous greedy paper, on ring, grid, and Erdős–Rényi graphs.
  • MovieLens-10M: tests scaling, since the catalogue size $|V|$ makes full-vector messages expensive.
  • Synthetic non-convex quadratic programs: we control the ranking margin by planting near-ties.
  • Tiny Images exemplar clustering subset: head-to-head against GreeDi.

The metrics are:

  • objective value after rounding, as a fraction of centralized greedy, plotted against total bits;
  • bits needed to reach 95% and 99% of uncompressed DeGTFW;
  • per-round vertex-disagreement rate;
  • wall-clock time under a simulated 0.25 Mbps link.

The decisive check is the quadratic-program margin sweep. If the method's bit savings do not shrink as the planted margin shrinks, the claimed mechanism is wrong, even if the method still performs well on MovieLens.