Splitting One Error Budget Across Solver, Chip, and Radio

When several edge devices jointly solve an optimization problem, such as fitting a shared sparse regression model, each round has three places where a device can cut corners. It can stop its local solver early. It can run the solver at lower arithmetic precision on its accelerator. It can send a coarser, more heavily quantized message over the radio. Each shortcut saves energy, and each adds error to the shared iterate. Today these choices are made by three separate communities. Optimization theorists schedule how loosely inner subproblems may be solved. Hardware designers choose bit-widths and parallelism to save area and bandwidth. Wireless researchers trade transmit power against CPU clock speed.

The opportunity comes from a result in inexact optimization. An outer algorithm still converges at its optimal rate as long as the total error injected each round stays under a shrinking tolerance. That tolerance is one budget, and it does not matter which of the three shortcuts spends it. This proposal builds a per-round controller that splits the budget across early stopping, datapath precision, and message quantization, choosing whichever mix is cheapest given the current channel and the measured energy costs of a parameterized accelerator. The bet is simple: when the channel is good, spend the budget on cheap compute; when it fades, spend it on coarse messages and buy accuracy back on the chip. A controller that sees all three sources of error should reach a target accuracy with less energy than one that sees only one or two of them.

Core Claim

Consider distributed consensus ADMM, an algorithm that alternates local solves on each device with a network averaging step. Let $\varepsilon_k$ be the error tolerance at outer round $k$, decaying fast enough that $\sum_k \varepsilon_k < \infty$. Error bounds of this summable kind preserve convergence in the analyses of Duan et al. and, with tolerances tied to the outer convergence rate, preserve optimal rates in Rasch & Chambolle. At each round, device $i$ picks three things: an inner stopping certificate $s$, a datapath precision mode $q$, and a message bit-width plus transmit power $(b, p)$. It does so by solving

$$\min_{s,q,b,p}\; E^{\text{chip}}_i(s,q) + E^{\text{radio}}_i(b,p;h_{i,k}) \quad \text{s.t.}\quad e^{\text{stop}}(s)+e^{\text{prec}}(q)+e^{\text{quant}}(b)\le \varepsilon_k,\;\; T^{\text{chip}}_i+T^{\text{radio}}_i\le T_{\max}.$$

Here $E^{\text{chip}}$ and $T^{\text{chip}}$ are the energy and time of the inner solve, read from a measured table for the generated accelerator rather than from the usual $f^3$ CPU model. $h_{i,k}$ is the channel gain. $E^{\text{radio}}$ and $T^{\text{radio}}$ follow a standard rate–power model. $T_{\max}$ is the per-round deadline. Each error term must be a computable upper bound, not an unknowable distance to the true minimizer.

What is new is the shared constraint. Earlier work splits error among at most two sources, or ignores the hardware entirely. The proposal also tests a specific risk raised in the literature: a fixed low-precision datapath has a noise floor that does not shrink, so precision error can break summability. The controller must therefore raise precision as rounds progress. Whether that requirement erases the savings from low precision is an empirical question this work answers.

Relation to Prior Work

Three works already couple algorithmic inexactness with communication–computation trade-offs, and they motivate this proposal.

  • Local ADA treats $K$ local SGD steps as an inexact gradient of a dual function and reaches near-optimal communication complexity. It counts steps abstractly and models the network only as a mixing parameter.
  • Gao et al. jointly choose transmit power, CPU frequency, and local accuracy $\theta$. They identify $\theta$ as the main lever, but tune it with a Harmony Search heuristic rather than a convergence-certified budget, and model computation as a 0–2 GHz CPU.
  • The Lyapunov adaptive FL work adapts quantization bits, participation, power, and CPU frequency slot by slot. Its inexactness is limited to gradient quantization, and its accuracy model is a fitted sigmoid surrogate.

All three represent compute as a scalar clock. None has a precision term.

Two hardware works supply the compute side.

  • Callipepla is a stream-instruction conjugate gradient (CG) accelerator. Its FP32-matrix/FP64-vector mixed precision is exactly the kind of precision knob this proposal exposes. It runs CG to a fixed exact tolerance, with no outer error envelope, and its precision choice carries no convergence guarantee.
  • Kao et al. show that tiling and parallelism flexibility costs under 1% area. That result supports making parallelism a generator parameter as well.

Cocco co-explores on-chip memory against off-chip traffic. Its "communication" is the memory bus, not a radio. It is the closest hardware analogue of a joint search, and the inspiration for searching hardware and mapping together rather than in sequence.

Two works constrain the design.

  • GeNI-ADMM proves that cheap randomized inner solves keep ADMM's rates. This lets the inner solver be approximate, but it also warns that some cheap solvers, such as sketch-and-solve, need correction terms to stay stable.
  • Rasch & Chambolle define "Type-2" errors, which are certified by the inner problem's duality gap. That supplies the computable certificate $e^{\text{stop}}$.

SCCD-ADMM lets nodes trade computation against how many neighbors they contact. It assumes constant unit costs and exact local solves, both of which this proposal drops.

Research Program

Hardware. A parameterized CG and Newton-CG engine in the style of Callipepla is generated at a few parallelism widths. Each variant has a runtime-selectable storage precision with three modes: FP16, FP32, and FP64 matrix storage, all with FP64 accumulation for the residual. This addresses the open problem that generators are compiled statically. Precision and inner-iteration count become runtime registers rather than bitstream choices, while parallelism stays a synthesis-time choice made per device class.

Avoiding pipeline drain. A known tension is that stopping a deep pipeline at an unpredictable point drains it and wastes cycles. The engine therefore checks its duality-gap certificate only at fixed chunk boundaries, every $m$ inner iterations. This trades a little slack in the error budget for full pipeline utilization. We will measure that slack directly.

Error bounds. The analysis reuses the inexact-ADMM machinery of Frangella et al. and adds the precision and quantization terms, each with its own bound:

  • $e^{\text{stop}}$ is the on-chip duality gap.
  • $e^{\text{prec}}$ is bounded by the difference between the residual computed in FP64 and the solver's working-precision residual. This is the same split Callipepla already computes.
  • $e^{\text{quant}}$ follows from the quantizer's step size.

Controller. The constraint is separable and the knob sets are small. At each round, the controller enumerates the chip choices $(s,q)$ from the measured table and solves the remaining power/bit subproblem in closed form, much as Gao et al. handle $(p, f)$ through Lagrangian duality. The result is exact per-round allocation, not a heuristic.

Theory. We will prove that the outer algorithm keeps the $O(1/t)$ ergodic rate of Frangella et al., and the linear rate under strong convexity, whenever the controller's choices satisfy the constraint. We will also characterize when a non-decaying precision floor forces precision to escalate.

Baselines

Naive reference. Every device solves its subproblem exactly in FP64, sends full-precision messages, and transmits at fixed maximum power, running the same consensus ADMM. Every other method is reported as a ratio against this.

Strongest existing method. The Lyapunov adaptive FL controller of Lyapunov-Based Optimization of Edge Resources is the only cited system that adapts quantization, power, and compute online without prior channel statistics. Its reported result is "roughly 30–50%" energy savings over static allocation at a fixed latency target. We port its drift-plus-penalty allocator to consensus ADMM. Its compute variable becomes the accelerator's iteration count at fixed FP64, and it receives the same channel traces and deadline. Its virtual-queue weights get the same hyperparameter search budget as our controller.

Joint accuracy-tuning baseline. Gao et al. is run with $\theta$ mapped to the inner duality-gap tolerance. The file reports no energy-savings number for it; it reports only that alternating minimization "converges within 5 iterations."

Algorithmic baselines. Local ADA with tuned $K$ and momentum (no reported numerical error floor found on Lacuna for w8a or YearPredictionMSD), and NysADMM from GeNI-ADMM (no numerical accuracy reported on Lacuna for realsim). Both run on the same accelerator at FP64.

Ablations. Two ablations isolate the key ingredient.

  • Precision frozen: our controller with precision fixed at FP64, so the budget is split only between stopping and quantization. If this matches the full controller, the hardware precision knob is not worth having.
  • Clock model only: our controller with the measured chip table replaced by the standard $\kappa f^2 C$ CPU model. This tests whether accurate hardware costs change the decisions.

What counts as winning. The full controller must reach the target relative suboptimality with less total device energy than the ported Lyapunov allocator, by a margin outside the seed-to-seed spread across channel traces. It must also meet the same deadline-violation rate and show no divergence. The precision-frozen ablation must lose by a comparable margin, or the precision dimension is not supported.

Why not just…?

Why not just use DVFS (scaling clock frequency and voltage) on an off-the-shelf processor, as the joint-allocation literature already does? A clock change cannot change dataflow or memory traffic. The flexibility study of Kao et al. reports an 11.8× geomean runtime gain from architectural knobs alone. Callipepla's 25% bandwidth cut comes from precision, not frequency. Still, the relevant question here is narrower. Does adding a precision knob to an accelerator beat running the same accelerator at a lower clock? We add an accelerator-DVFS baseline that varies only the clock at fixed FP64. The clock-model ablation then shows whether the $f^2$ model even ranks configurations correctly.

Why not just solve inner problems exactly, since the accelerator is fast anyway? This is the most serious threat. If Callipepla-class engines make compute energy negligible next to radio energy, the joint problem collapses to communication-only optimization, and SCCD-ADMM's assumption that communication dominates would hold. We take this seriously. We measure the chip-to-radio energy ratio per round across matrix sizes, and we report the crossover subproblem size below which our controller adds nothing. The claim is limited to the regime where the two energies are comparable. Results outside that regime are reported as a negative finding, not hidden.

Why not just adapt only the inner tolerance, like Gao et al.'s $\theta$, and leave precision alone? Gao et al. show that local accuracy is the main lever. Precision might add little once stopping is tuned, especially if raising precision late in the run cancels the early savings. The precision-frozen ablation answers exactly this question. If it ties the full controller, we drop the precision knob and report a simpler stop-plus-quantization controller with hardware-measured costs as the contribution.

Proposed Experiments

Workloads. Distributed Lasso and ℓ1-logistic regression on the 10,000-sample realsim subset used by GeNI-ADMM, and on heterogeneously partitioned w8a and YearPredictionMSD as in Local ADA. Least-squares subproblems use CG; logistic subproblems use Newton-CG. To test the accelerator cost tables on varied sparsity and conditioning, each device's subproblem matrix is also drawn from the 36 SuiteSparse matrices used by Callipepla.

Hardware and network. Energy per inner chunk is measured on a U280-class FPGA for each precision and parallelism variant. Edge-class devices are modeled by scaling the measured values with the post-synthesis power reports of the smaller variants. Networks follow SCCD-ADMM's Erdős–Rényi setup (10–100 nodes) with IEEE 802.11 rate models. Channel fading traces include abrupt drops, to probe the mobility weakness noted for existing frameworks.

Metrics. Total energy to reach $10^{-6}$ relative suboptimality, deadline-violation rate, number of rounds, and divergence count.

Decisive checks. Four results decide the outcome:

  • the full controller beats the ported Lyapunov allocator on energy at equal deadline compliance;
  • the precision-frozen ablation loses, establishing that the shared budget across chip and radio matters;
  • precision escalation keeps the measured error sum bounded, with no stall at the FP16 floor;
  • the measured compute-to-radio energy crossover shows a non-trivial regime where joint allocation pays off.