Wireless schedulers decide, slot by slot, which links transmit and at what power. The classic recipe, called Max-Weight, picks the transmission pattern that maximizes the sum of each link's queue length times its rate. It provably keeps queues bounded even when an adversary controls packet arrivals and channel quality. The proof assumes the scheduler solves that per-slot problem to within a fixed fraction of the true best answer, every slot. In practice, once power is a continuous variable, the per-slot problem is non-convex. Deployed solvers such as WMMSE (weighted minimum mean-square error, an iterative power and beamforming method) only promise a stationary point, a place where the gradient vanishes. That point may be a mediocre local optimum. Nobody has checked whether this mismatch is harmless or dangerous. Under the harmless reading, the network simply loses a few percent of capacity. Under the dangerous reading, an adversary steers the queues into states where the solver is stuck badly, and backlogs grow without bound at loads the network should easily carry.
This note proposes to settle that question empirically and then to fix the failure if it exists. We will build an adversarial stress-testing harness: a search procedure that hunts for injection and channel sequences that maximize backlog growth for a given scheduler, while respecting the leaky-bucket rate limits of adversarial queueing theory. We will test the conjecture that the per-slot approximation requirement is the wrong target and that what matters is the scheduler's weighted-rate shortfall accumulated over windows of slots. If so, a cheap modification restores stability without global solvers: warm-start the solver, keep the previous slot's schedule whenever it scores better under the new queue weights, and spend one randomized restart per slot.
Core Claim
Stability of the Max-Weight Protocol in Adversarial Wireless Networks proves that exact Max-Weight, and any $\hat\epsilon$-approximate version with $\hat\epsilon<\epsilon$, stays stable against an adversary that keeps injections at least an $\epsilon$ margin inside capacity. The paper uses a potential argument instead of standard drift analysis, and its only numerical evidence is a small synthetic grid. In that result the approximation must hold in every slot.
Two papers say continuous solvers miss that bar. MAPEL computes exact global optima of non-convex weighted throughput maximization via polyblock approximation. It reports that a distributed heuristic (ADP) found the global optimum only 0.6% of the time in 10-link networks, with about 10% average loss. A centralized heuristic (SPC) did better, finding the optimum 65–80% of the time with about 2% loss. On Convergence Rates of Quadratic Transform and WMMSE Methods proves that WMMSE reaches a stationary point at rate $O(1/k)$ and accelerates this to $O(1/k^2)$. It gives no guarantee of global quality.
Our claim has two parts. The first is empirical and falsifiable. A state-aware adversary can destabilize Max-Weight run with a warm-started stationary-point solver at loads strictly inside the solver's average-case capacity loss. The danger is that the adversary keeps the queue-weight vector parked near a bad stationary point, which is worse than a uniform capacity shrink. The second part is algorithmic. Let $Q(t)$ be the queue vector and $r(t)$ the chosen rate vector. Let $W^*(t)=\max_{r\in\mathcal R(t)}\sum_e Q_e(t)r_e$ be the best achievable queue-weighted rate in slot $t$. Define the windowed shortfall over a window of $T$ slots as
$$ \Delta_T(t)=\frac{\sum_{s=t}^{t+T-1}\big(W^*(s)-\sum_e Q_e(s)r_e(s)\big)}{\sum_{s=t}^{t+T-1}W^*(s)} . $$
We conjecture that stability holds whenever $\Delta_T\le\hat\epsilon<\epsilon$ for all windows, for some finite $T$ that depends on the adversary's burst size. This would extend the potential argument of Lim et al. The intuition is that queues move by at most a bounded amount per slot, so a few bad slots can be paid back within a window. The keep-and-restart scheduler is designed to drive $\Delta_T$ down. Keeping the previous schedule never lowers the weighted rate below last slot's choice, adjusted for slow queue drift. Each randomized restart gives an independent chance of escaping a bad basin, and an adversary that cannot see the scheduler's coins cannot block it.
Research Program
The first component is the harness. Networks are interference-limited ad hoc topologies in the style of the MAPEL setup at 5–10 links, where MAPEL can still compute exact $W^*(s)$. Multi-hop grids in the style of Lim et al. extend this to longer paths. The adversary has two controls: per-link injections obeying $\text{Arrivals}(I)\le\rho|I|+\sigma$, and bounded perturbations of channel gains within the $A(\omega,\epsilon)$ model. It observes the queues and the scheduler's last decision but not its random seeds. Its strategy is found by black-box search over short-horizon injection plans (receding-horizon random search and evolution strategies), with backlog growth as the objective. Because MAPEL's polyblock method is too slow per slot at larger sizes, we use it offline to label shortfalls on small instances. At larger sizes we use best-of-many-restarts as a lower bound on $W^*$ and report results as bounds rather than exact values.
The second component is analysis. We will attempt the windowed version of the potential proof of Lim et al., aiming for an explicit $T$ as a function of $\sigma$ and the maximum per-slot rate. We will also check empirically whether $\Delta_T$, measured on the harness, predicts instability better than the per-slot ratio does.
The third component is the scheduler itself: warm-started WMMSE or the accelerated quadratic transform of Shen et al., the keep-if-better comparison, and one random restart per slot, with an optional cap on restart frequency. We will also probe whether landscape conditions make stationary points safe. The Polyak-Łojasiewicz inequality, which Karimi, Nutini and Schmidt show forces every stationary point to be global, would serve as a diagnostic: we will estimate on which queue-weight regions the per-slot landscape behaves this way. The goal is to describe where the adversary must push to hurt the scheduler. We do not assume the condition holds.
Baselines
The naive reference is Max-Weight restricted to on/off link activation at full power, solved greedily. It has no local-optimum problem in the power variables, but it discards the capacity that continuous power control buys. The proposal must beat it in sustainable load to justify continuous solvers at all.
The practical incumbent is Max-Weight with warm-started WMMSE, using the accelerated quadratic transform of Shen et al.. This is what an engineer would deploy, so it is the system our harness is designed to break. Shen et al. report convergence in about 0.02 seconds on a 128-antenna setup. That figure sets a realistic per-slot budget, and we give every method the same wall-clock allowance per slot.
The quality ceiling is Max-Weight with the exact MAPEL solution on small networks, the setting covered by Theorem 1 of Lim et al. No reported result on Lacuna gives this system's queue backlog or capacity margin under adversarial injection; Lim et al. report only a small synthetic grid simulation. Beating the incumbent means sustaining a load margin $\epsilon$ that the oracle sustains and the incumbent does not, under the same searched adversary and the same per-slot compute budget.
A strong brute-force competitor is warm-started WMMSE with $K$ restarts per slot, swept over $K$, as a compute-matched check.
Ablations isolate the key ingredient by removing, one at a time, the keep-if-better step, the restart, and the warm start.
As a sanity anchor, we reproduce the single-server non-stationary setup of When Lyapunov Drift Based Queue Scheduling Meets Adversarial Bandit Learning. That paper reports that plain MaxWeight with noisy estimates shows linear queue growth, while its SoftMW scheduler stays near the oracle. Reproducing this qualitative pattern confirms the harness can detect instability.
Why not just…?
Why not just run many random restarts every slot? This is the real threat. If a modest number of restarts within the 0.02-second budget keeps $\Delta_T$ small against the searched adversary, then the contribution shrinks to the diagnosis plus the windowed analysis. The $K$-sweep at matched compute settles this directly. We report the smallest $K$ that keeps the network stable at each load margin, and the proposal only claims an algorithmic win if keep-and-restart reaches that stability at lower compute.
Why not just convexify with the high-SINR geometric-programming approximation? MAPEL shows this approximation breaks down under strong interference, because good solutions there often mute links entirely and the approximation cannot represent muting. Dense interference is exactly the regime where Max-Weight weights favor muting. We include the approximation as an extra baseline on the dense topologies to confirm this.
Why not accept the capacity loss and run the local solver below it? This is the harmless-reading hypothesis, and the first decisive experiment tests it. If the searched adversary cannot destabilize the incumbent at margins larger than its average shortfall (about 10% for ADP-like solvers per MAPEL), the danger claim is false. We would then publish that negative result together with the harness as an evaluation tool.
Why not use bandit-coupled schedulers such as SoftMW? SoftMW and SSMW handle unknown rates, but only for one server choosing among $K$ discrete queues. They do not optimize continuous power over interfering links. They address a different failure, unknown information, while our failure is a non-convex search problem.
Decisive Experiments
On 5–10-link MAPEL-style networks and 4×4 to 6×6 multi-hop grids, we sweep the load margin $\epsilon$ and the burst size $\sigma$. For each scheduler we record three quantities: the growth slope of total backlog over $10^5$ slots, the largest $\epsilon$ for which the backlog stays bounded, and the measured per-slot and windowed shortfalls against exact MAPEL or the restart-based bound.
The first check asks whether the searched adversary destabilizes warm-started WMMSE at margins where random leaky-bucket traffic does not, and where the oracle remains stable. A yes supports the danger claim; a no supports the harmless reading. The second check asks whether windowed shortfall $\Delta_T$ separates stable runs from unstable ones better than the worst per-slot ratio does. The third check asks whether keep-and-restart matches the oracle's sustainable margin at incumbent compute, and whether the ablations show that the keep step and the restart are both necessary.
Results are reported over independent seeds for both the adversary search and the scheduler. The harness, with its adversaries and topologies, is released as a benchmark, which addresses the field's reliance on proofs and benign synthetic traffic.
References
- Stability of the Max-Weight Protocol in Adversarial Wireless Networks
- MAPEL: Achieving global optimality for a non-convex wireless power control problem
- Accelerating Quadratic Transform and WMMSE
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
- When Lyapunov Drift Based Queue Scheduling Meets Adversarial Bandit Learning
- Queue Scheduling with Adversarial Bandit Learning