Source-linked AI summary
Windowed and Quantized Group-Based ADMM for Distributed Optimization in Heterogeneous Edge Networks
Gaiguo Wei, Qingying Zhang, Heqiang Wang, Yu Zhang, Xiaoxiong Zhong
TL;DR
Heterogeneous client resources and limited activation capacity make it challenging to coordinate group updates and model exchanges in edge-network optimization. WQ-GADMM schedules fixed groups in windows, quantizes downlink and uplink exchanges, and allows bounded staleness and inexact local updates. On MNIST and CIFAR-10, its 12-bit configuration reduces communication volume while maintaining comparable accuracy and lower simulated time than full precision.
Problem
Heterogeneous computing and communication conditions create unequal group-update completion times, while limited activation capacity can require multiple rounds to collect every group’s update.
Source: §I · p. 1Method
WQ-GADMM groups clients by estimated computation time, schedules one update per group within activation windows, quantizes downlink and uplink exchanges, and allows bounded staleness and inexact local updates.
Source: §I · pp. 1–2Results
On MNIST and CIFAR-10, Q12 reduced communication volume by 62.5% versus FP32 while maintaining comparable final accuracy and lower simulated wall-clock time.
Source: D. Overall Performance · p. 11Takeaways & Limitations
Q12 maintained complete group coverage and achieved shorter group inter-completion gaps than the evaluated baselines.
Source: §I · p. 2
Abstract
from arXiv · showhide
Distributed optimization in edge networks is constrained by heterogeneous client computing capabilities and limited communication resources. We propose the Windowed and Quantized Group-Based Alternating Direction Method of Multipliers (WQ-GADMM) to coordinate group updates under limited activation capacity and reduce communication costs. Clients are grouped by estimated computation time. Each window activates a limited number of groups per round, and the cloud updates the global model after all groups have updated once. The method quantizes both downlink and uplink model exchanges to reduce communication costs and allows bounded model staleness and inexact proximal local updates. For smooth nonconvex objectives, we establish an average squared Karush-Kuhn-Tucker residual bound under the stated assumptions and parameter conditions. The bound consists of a term that decreases with the iteration count and a quantization-dependent error term. Experiments on MNIST and CIFAR-10 show that 12-bit communication reduces communication volume and simulated wall-clock time while maintaining test accuracy comparable to full precision. The 12-bit configuration also maintains complete group coverage and achieves shorter mean group inter-completion gaps than the evaluated baselines.
I. INTRODUCTION
Heterogeneous client resources and limited group-activation capacity complicate the coordination of distributed optimization in edge networks. WQ-GADMM combines fixed computation-aware groups, windowed scheduling, and bidirectional quantization, and the paper frames it alongside prior work on distributed optimization, inexact ADMM, and quantized group methods.
I. INTRODUCTION
- Heterogeneous computing, data volumes, and communication conditions produce unequal update completion times, while limited activation capacity can require multiple rounds to collect every group’s contribution.The cloud-edge-client hierarchy coordinates groups but still requires decisions about group participation, model exchange, and global updates.Source: §I · p. 1
- WQ-GADMM schedules fixed computation-aware groups in activation windows, updates the cloud model after every group contributes, and quantizes downlink references and uplink models.The method also allows bounded model staleness and inexact local updates.Source: §I · pp. 1–2
A. Distributed Optimization in Edge Networks
- Prior edge-optimization work addresses heterogeneity through distributed optimization, client grouping, hierarchy, and selection, including approaches such as FedProx and Oort.The cited discussion describes these as complementary ways of handling resource, data, or participation differences.Source: A. Distributed Optimization in Edge… · p. 2
B. ADMM and Inexact Local Optimization
- Inexact local solutions reduce the need for exact subproblem solves, while asynchronous ADMM approaches use partial barriers or bounded delay to coordinate updates.The cited work studies convergence conditions for these settings, including conditions depending on maximum network delay.Source: B. ADMM and Inexact Local Optimization · p. 2
C. Quantized and Group-Based ADMM
- Quantized optimization methods study communication errors and compression, while group-based ADMM methods coordinate local updates; WQ-GADMM combines both in a hierarchical network with limited per-round activation.It uses fixed groups and windows so every group updates once before the cloud updates the global model.Source: C. Quantized and Group-Based ADMM · p. 3
A. Client Model and Fixed Group Partition
- The client model assigns each client a local dataset and empirical loss, then partitions clients into fixed, disjoint groups using estimated computation times.The group objective preserves sample weights in the global objective.Source: A. Client Model and Fixed Group… · p. 3
B. Group Consensus Formulation
The formulation links each group model to a shared cloud model through consensus constraints and associated dual variables. The method constructs computation-time-based groups, schedules their updates within capacity-limited windows, and updates the cloud after all groups contribute.
B. Group Consensus Formulation
- Consensus constraints require every group model to agree with the cloud’s global model, and each constraint has an associated scaled dual variable.The formulation uses an ADMM penalty parameter to define the scaled dual variable.Source: B. Group Consensus Formulation · p. 3
- First-order stationarity is characterized by the stated group-gradient and consensus conditions, which provide the basis for the paper’s KKT residual.The passage identifies these conditions as the basis for the residual used in the convergence analysis.Source: B. Group Consensus Formulation · p. 3
IV. WINDOWED AND QUANTIZED GROUP-BASED ADMM
- Within each window, activated groups receive quantized references, approximately solve proximal subproblems, and upload quantized models; the global model and dual variables remain fixed until all groups contribute.The cloud then updates the global model and dual variables.Source: §IV · p. 3, Figure 2 · p. 4
A. Computation-Aware Grouping
- Clients are partitioned before training into fixed groups according to estimated computation times, so group membership remains unchanged during training.The construction is described as grouping clients with similar estimated computation times.Source: A. Computation-Aware Grouping · p. 4
B. Windowed Group Scheduling
- Each physical round activates at most Ma groups, and a window ends only after every group has completed one update.Completed groups are excluded from later rounds in the same window; when activated updates finish, a window contains ⌈G/Ma⌉ physical rounds.Source: B. Windowed Group Scheduling · pp. 4–5
- Eligible groups accumulate waiting counts when not selected, and groups with the largest counts receive priority once the activation threshold is reached.Waiting counters reset at each window; ties are resolved in ascending group-index order.Source: B. Windowed Group Scheduling · p. 4
- Before the activation threshold is reached, eligible groups are ranked by normalized model disagreement when its weight is positive.The waiting-count term does not affect ranking because eligible groups have the same waiting count; the score also has a stabilizer that prevents division by zero.Source: B. Windowed Group Scheduling · p. 4
- A logical iteration spans the physical rounds from the first round of its window until the first round of the next window.The window closes when all groups have completed their updates.Source: B. Windowed Group Scheduling · p. 5
C. Quantized Local Updates with Bounded Staleness
WQ-GADMM uses cached global-model references for group updates and refreshes caches according to a bounded-staleness rule. Groups approximately solve proximal subproblems and exchange quantized models with the cloud.
C. Quantized Local Updates with Bounded Staleness
- Groups use cached global-model references, with the cache retaining both the model and its logical-iteration index from the previous iteration.The method checks cache age and refreshes the cached model when its staleness condition is met.Source: C. Quantized Local Updates with… · p. 5
- The cloud forms a downlink reference and sends its quantized version to the activated group.The quantization introduces a downlink quantization error.Source: C. Quantized Local Updates with… · p. 5
- Using the received reference, each group approximately minimizes a proximal local objective and performs gradient updates.The local objective includes a proximal parameter.Source: C. Quantized Local Updates with… · p. 5
- The local update uses a stepsize constrained by the group objective’s Lipschitz constant and the selected penalty and proximal parameters.The stated condition also requires the sum of the penalty and proximal parameters to exceed the Lipschitz constant.Source: C. Quantized Local Updates with… · p. 5
- A tolerance-based stopping criterion determines when the local iterations end, after which the group uploads its quantized model.The stopping rule is defined through a local optimality residual, and the upload has an associated quantization error.Source: C. Quantized Local Updates with… · p. 5
D. Cloud Update and Overall Algorithm
After every group completes its update in a window, the cloud updates the global model and scaled dual variables. The algorithm repeats this process across logical iterations and returns the final global model.
D. Cloud Update and Overall Algorithm
- After all groups complete their updates within a window, the cloud computes the global-model update and updates the scaled dual variables.The procedure also defines a group consensus residual and dual increments.Source: D. Cloud Update and Overall Algorithm · p. 5
- Algorithm 1 initializes the model, parameters, and fixed computation-time-based groups, then retains cached models and resets completed-group sets and waiting counters at each iteration.The stated inputs include activation, staleness, scheduling, quantization, and local-update parameters.Source: D. Cloud Update and Overall Algorithm · p. 6
- Within each window, the algorithm selects active groups, refreshes cached references when needed, sends references, runs local updates, and collects uploaded models.It records completed groups and updates waiting counters until every group has contributed.Source: D. Cloud Update and Overall Algorithm · p. 6
- Once the window closes, the algorithm updates the global model and dual variables, repeats for the specified iteration limit, and returns wK.The algorithm summary identifies the global and dual updates as the end-of-window steps.Source: D. Cloud Update and Overall Algorithm · pp. 5–6
V. CONVERGENCE ANALYSIS
The analysis establishes an average squared KKT residual bound for WQ-GADMM on smooth nonconvex objectives, under assumptions on the objectives, quantization errors, and iterates. It specifies parameter and cache conditions for the convergence analysis.
A. Assumptions and Notation
- The analysis considers Algorithm 1 with its window updates and cache refresh rule, and local solves satisfying the stated stopping criterion.The parameters are positive, the cache threshold is finite, and each step size obeys the stated upper bound.Source: A. Assumptions and Notation · p. 6
- The convergence analysis targets smooth, possibly nonconvex group objectives whose sum is bounded below.The stacked objective is assumed to have a Lipschitz-continuous gradient.Source: A. Assumptions and Notation · p. 6
- The bound analysis assumes quantization errors with history-conditioned second-moment controls and finite second moments for model and dual variables.The quantization-error bounds use constants that do not depend on the iteration.Source: A. Assumptions and Notation · p. 6
B. Auxiliary Lemmas
The auxiliary lemmas establish finite local-solver termination, relationships among group and cloud iterates, and bounds used to analyze the algorithm’s potential. They also establish shared-cache behavior and a bound on cache age.
B. Auxiliary Lemmas
- When ρ + η > L, every local gradient loop in Algorithm 1 terminates after finitely many steps.The termination argument uses the local solver’s stopping criterion and smoothness.Source: B. Auxiliary Lemmas · pp. 6–7
- The prescribed gradient step and parameter conditions support the finite-termination argument for local updates.The stated sufficient parameter choice implies the condition ρ + η > L.Source: B. Auxiliary Lemmas · pp. 6, 8
- After refresh checks, all groups use a shared unquantized cache, whose age is bounded by the cache threshold.The shared-cache statement follows by induction from common initialization and the common refresh threshold.Source: B. Auxiliary Lemmas · p. 7
- The local-update lemma defines a combined local and quantization error and establishes identities and bounds for the local updates.The argument uses the local stopping criterion and smoothness, then sums over groups and takes expectations.Source: B. Auxiliary Lemmas · p. 7
- The potential-function analysis accounts for cache differences and group-model changes while deriving a potential decrease and lower bound.The analysis defines the potential from the augmented Lagrangian and cache-related terms.Source: B. Auxiliary Lemmas · pp. 7–8
C. Average KKT Residual Bound
Under the stated assumptions and parameter conditions, the theorem bounds WQ-GADMM’s average squared KKT residual. The bound has a decreasing iteration-dependent term and a quantization-dependent limiting term.
C. Average KKT Residual Bound
- The theorem bounds the average squared KKT residual for every integer K ≥ 1 under Assumptions 1–3 and the stated parameter conditions.The theorem sets H = τmax + 1 and defines finite constants independent of K.Source: C. Average KKT Residual Bound · pp. 8–9
- The bound combines a term that decreases with iteration count and a quantization-dependent error term.For fixed algorithm parameters, the limiting average squared residual is bounded in proportion to quantization.Source: C. Average KKT Residual Bound · p. 9
- With persistent quantization errors, the result bounds average residual but does not guarantee convergence of the full model sequence or global optimality.The residual includes stationarity and consensus errors; the remaining KKT condition holds exactly by Lemma 2.Source: C. Average KKT Residual Bound · pp. 8–9
VI. EXPERIMENTS
The experiments evaluate WQ-GADMM on a smooth nonconvex test problem and MNIST and CIFAR-10. They examine residual behavior, quantization precision, learning performance, group participation, and resource efficiency against baselines.
VI. EXPERIMENTS
- The evaluation includes a smooth nonconvex test problem and the MNIST and CIFAR-10 datasets.The section proceeds from experimental settings to residual behavior, quantization precision, and comparisons with baseline methods.Source: §VI · p. 9
- The experiments examine residual behavior and quantization precision before comparing learning performance, group participation, and resource efficiency.The supplied section passage describes the evaluation plan but does not report the comparison outcomes.Source: §VI · p. 9
A. Experimental Setup
The experiments compare four methods on MNIST and CIFAR-10 under shared data, model, and computation settings. They measure accuracy, communication, simulated time, fairness, group coverage, and completion gaps.
Platform and datasets
- Experiments used 50 clients in five fixed groups, CNNs, Dirichlet-partitioned data (α = 0.1), and three seeds with shared initialization, partitions, grouping, and computation profiles.The workstation used an RTX 4090, Python 3.10, PyTorch 2.10.0, and CUDA 13.0.Source: A. Experimental Setup · p. 9
Training settings
- Training workloads were 25,000 client-gradient evaluations for MNIST and 1,500,000 for CIFAR-10, with batch size 64, at most two SGD steps, two active groups, and staleness at most 1.The passage also specifies method-specific optimization and scheduling parameters.Source: A. Experimental Setup · p. 9
Compared methods
- The comparison included P-GADMM [5], P-GADMM-Sync, WQ-GADMM-FP32, and WQ-GADMM-Q12.P-GADMM-Sync used a round-robin 2 + 2 + 1 schedule; both WQ configurations used that activation pattern and completed one update per group per window.Source: A. Experimental Setup · pp. 9–10
- P-GADMM activated at most two group tasks concurrently and updated the global model after two group results, retaining previous models for other groups.P-GADMM used local SGD followed by model averaging within each group.Source: A. Experimental Setup · p. 9
- WQ-GADMM-FP32 and WQ-GADMM-Q12 shared optimization parameters and group-update sequences; Q12 used 12-bit symmetric stochastic quantization on both communication directions, versus FP32’s 32-bit exchanges.P-GADMM-Sync retained P-GADMM’s local updates, optimization parameters, and 32-bit communication.Source: A. Experimental Setup · p. 10
Metrics and simulation settings
- Metrics included test accuracy, communication volume, simulated wall-clock time, Jain fairness, full-group coverage, and mean inter-completion gaps.Communication volume excluded client-to-edge traffic; simulated time included computation, transmission, and waiting, under Pareto-distributed client computation and fixed 5 Mbit/s downlink and 2 Mbit/s uplink rates.Source: A. Experimental Setup · p. 10
B. Residual Behavior on a Smooth Nonconvex Problem
On a smooth nonconvex test problem, the residual results show lower residual levels with finer quantization than with Q8, while cumulative averages decline across configurations. The experiment evaluates the residual bound’s quantization-dependent behavior.
Test problem
- The test problem had five groups and a 12-dimensional model, with objectives bounded below and globally Lipschitz-continuous gradients; the Hessian was negative definite at w = π1.The stated Hessian property confirms nonconvexity for this experiment.Source: B. Residual Behavior on a Smooth… · p. 10
Experimental conditions
- The comparison used FP32, Q12, and Q8 for 1,000 logical iterations over three seeds, with shared initial models and zero-initialized dual variables.Q12 and Q8 used stochastic rounding on 212 and 28 uniformly spaced levels over [−2, 2], respectively, in both communication directions.Source: B. Residual Behavior on a Smooth… · p. 10
- The experiment set ρ = 12, η = 0.2, and θg = 0.1, with at most two active groups, activation window Tact = 2, and maximum staleness τmax = 2.Local updates used full gradients, stepsize ζg = (Lg + ρ + η)^−1, and the stopping criterion in (40).Source: B. Residual Behavior on a Smooth… · p. 10
Residual results
- FP32 residuals decreased to a low numerical level, while Q12 and Q8 fluctuated at higher levels in the per-iteration results.The cumulative-average traces declined for all configurations.Source: B. Residual Behavior on a Smooth… · p. 10
- Over the final 200 iterations, Q12’s mean residual was approximately 1/247 of Q8’s; Fig. 3 reports per-iteration and cumulative average squared KKT residuals.The cumulative average declined for all configurations, and FP32 and Q12 nearly overlapped because early iterations dominated their averages.Source: Figure 3 · p. 10, B. Residual Behavior on a Smooth… · p. 10
C. Effect of Quantization Precision
WQ-GADMM-Q12 reduces communication and simulated time while maintaining comparable accuracy, and preserves full group coverage with shorter inter-completion gaps than the evaluated baselines. The paper also establishes a quantization-dependent KKT residual bound for smooth nonconvex objectives under stated assumptions and parameter conditions.
C. Effect of Quantization Precision
- Q16, Q12, and Q8 retained final accuracies close to FP32, but Q8 had larger consensus residuals than Q12, particularly on CIFAR-10, and Q2 diverged on both datasets.Q12 was selected for the remaining comparisons.Source: C. Effect of Quantization Precision · p. 10
D. Overall Performance
- WQ-GADMM-Q12 achieved higher accuracy than the baselines on MNIST and similar final accuracy on CIFAR-10, with the lowest communication volume and shortest simulated wall-clock time on both datasets.Compared with WQ-GADMM-FP32, it reduced communication volume by 62.5% while maintaining comparable final accuracy.Source: D. Overall Performance · pp. 10–11, Table II · p. 11
E. Group Participation and Inter-Completion Gaps
- WQ-GADMM-Q12 and P-GADMM-Sync both achieved Jain fairness indices and full-group coverage ratios of 1.000, while Q12 reduced mean inter-completion gaps versus P-GADMM-Sync by 52.9% on MNIST and 59.6% on CIFAR-10.P-GADMM achieved Jain fairness indices above 0.96 but covered all groups in only about half of observation intervals.Source: Figure 8 · p. 11, E. Group Participation and… · p. 12, Table III · p. 12
F. Resource Efficiency
- Under a fixed training workload, Q12 used 37.5% of FP32 communication volume, with simulated wall-clock time at 47.4% of FP32 on MNIST and 40.5% on CIFAR-10.Under a common communication budget, Q12 achieved higher accuracy than FP32 because quantization allowed more model updates.Source: F. Resource Efficiency · p. 12, Table IV · p. 12
VII. CONCLUSION
- For smooth nonconvex objectives, the paper establishes an average squared KKT residual bound with an O(1/K) term and a quantization-dependent error term; future work will address time-varying resources and physical edge platforms.The bound holds under the stated assumptions and parameter conditions.Source: §VII · p. 12