CS Paper Radar

New Contraction Bounds for Multidimensional Asymptotic Consensus in Dynamic Networks

Zeremonienmeister Berber Aab, Darya Melnyk, Stefan Schmid

cs.DC ·submitted 2026-10-08 12:12 UTC · v1
theory

Abstract

This work studies the multidimensional asymptotic agreement problem in dynamic networks. We assume that nodes have $d$-dimensional inputs and need to converge arbitrarily close to each other's inputs while their vectors stay inside the convex hull of all inputs. We present a new upper bound of $\sqrt{2d/(3d+1)}$ on the contraction rate of asymptotic agreement in the non-split network model, where $d$ is the dimension of the input and $\sqrt{2d/(3d+1)}\rightarrow \sqrt{2/3}\approx 0.816$ for $d\rightarrow\infty$. To this end, we adapt the BallMidpoint algorithm (Melnyk, 2026) recently introduced for the all-to-all communication model. This algorithm lets the nodes choose the midpoint of the smallest enclosing ball of the received vectors. This bound is strictly worse than the $\sqrt{1/2}\approx 0.707$ contraction rate for fault-tolerant approximate agreement in all-to-all communication networks because the convex hulls of the nodes do not have a common intersection, and only intersect pairwise. Our bound improves over the previously best-known contraction rate of $\sqrt{7/8}\approx 0.935$ for dynamic networks via the MidExtremes algorithm (Függer and Nowak, 2018). We present the first multi-dimensional lower bound of $2/3$ for the contraction of coordinate-free memoryless anonymous deterministic algorithms in non-split networks, for $d\ge 8$. This result shows that the previously best-known lower bound of $1/2$ on the contraction rate for $n\ge 3$ and $d=1$ is not tight in higher dimensions. If $n$ is infinite, we extend this lower bound to $\sqrt{1/2\cdot d/(d+1)}$, which converges to $\sqrt{1/2}$ for $d\rightarrow \infty$. We further show that for a single round, the one-round contraction is at least $\sqrt{\frac{2d-2}{3d+7}}$, which converges to $\sqrt{2/3}$ for $d\rightarrow\infty$, showing that the BallMidpoint strategy is asymptotically optimal for one round.

Comment
21 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Faster Convergence of Multidimensional Approximate Agreement via Smallest Enclosing Balls

cs.DC ·2026-09-01 ·Darya Melnyk
theory similarity 0.77
Abstract

This work considers the multidimensional approximate agreement problem. In this problem, $n$ parties in a distributed system, up to $t$ of which may be corrupted by a Byzantine adversary, need to output vectors that are close to each other and that lie inside the convex hull of all non-corrupted input vectors. We assume that nodes communicate in a fully-connected authenticated network and analyze synchronous and asynchronous communication models. The focus of this work is on the contraction factor of approximate agreement protocols. The first multidimensional approximate agreement protocols had a contraction rate of $1-1/n$(VG, PODC'13) and $\sqrt[d]{1/2}$(MH, STOC'13). While a rate below $1$ is sufficient for convergence, it is not sufficient for practical applications. To date, the best known convergence rate of approximate agreement algorithms is $\sqrt{7/8}\approx0.935$ (FN, DISC'18), which is achieved through the MidExtremes protocol. This stands in contrast to the lower bound on the convergence rate in the $1$-dimensional setting, which is $1/2$. In this work, we propose BallMidpoint - a novel approximate agreement protocol with a contraction rate of $1/\sqrt{2}\approx 0.707$ in the synchronous and the asynchronous communication models. This algorithm satisfies the optimal resilience under convex validity. The presented contraction rate is achieved by choosing the midpoint of the smallest enclosing ball of the so-called local safe areas, and it is tight for the presented algorithms. Similar to (FN, DISC'18), our algorithm is coordinate-free, and the point inside the safe area can be computed efficiently. This work presents the first multidimensional approximate agreement protocol where the convergence rate is closer to the best known lower bound rather than the upper bound of $1$.

0.39

Fast Multidimensional Approximate Agreement with Optimal Resilience Using Ball Validity

cs.DC ·2026-09-07 ·Tijana Milentijević, Stefan Schmid
theory similarity 0.70
Abstract

Multidimensional approximate agreement requires $n$ processes with inputs in $\mathbb{R}^d$ to output vectors close to each other, despite up to $t$ Byzantine faults. Under convex validity, outputs must lie in the convex hull of the correct inputs, which leads to resilience thresholds that grow with the dimension. We instead study Minimum Enclosing Ball (MEB) validity and its multiplicative relaxation $c$-MEB validity. Our first contribution is Adaptive MEB Contraction, a coordinate-free algorithm that, in the synchronous model with $n>(d+1)t$ contracts the correct MEB radius by $1/\sqrt2$ per round for $α=1$ while satisfying $\sqrt2$-MEB validity. We also give an example showing that this bound is tight for our analysis. Our main technical contribution is a dimension-free inflation theorem: if every $β$ balls in a finite family of Euclidean balls have a common point, then inflating each radius by $\sqrt{β/(β-1)}$ guarantees a common intersection. Applying the theorem to the candidate balls defining the local MEB-safe areas results in a synchronous algorithm with optimal resilience $n>3t$, contraction factor $\sqrt3/2$ and $\sqrt6$-MEB validity. To the best of our knowledge, this is the first multidimensional approximate agreement algorithm with optimal resilience, constant $c$-MEB validity and coordinate-free contraction. We further extend the approach to the asynchronous setting. Without inflation we obtain resilience $n>(d+2)t$, contraction factor $\sqrt{2/3}$ and $\sqrt6$-MEB validity, whereas with inflation for $n>4t$ we get the contraction factor $\sqrt{15}/4$ and $2\sqrt{10}$-MEB validity. Finally, we compare our guarantees with existing algorithms, including Minimum-Diameter Averaging (MDA), for which we derive MEB-validity guarantees. Our algorithms achieve strictly better resilience while providing substantially stronger MEB-validity guarantees than MDA.

0.45

The threshold for online balancing of i.i.d. binary vectors

cs.DS math.PRmath.CO ·2026-09-14 ·Dylan J. Altschuler, Konstantin Tikhomirov
theory similarity 0.60
Abstract · Supersedes and replaces arxiv.org/abs/2509.02432, which has the same lower bound, but only has an upper bound for the ultra-sparse regime

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^tσ_i X_i\right\|_\infty$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $Θ(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $Θ(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.

0.44

Multivalued Consensus: General Adversaries Require More Communication

cs.DC cs.CRcs.IT ·2026-08-18 ·Mose Mizrahi, Roger Wattenhofer
theory similarity 0.60
Abstract · 33 pages, 1 figure, full version of a DISC 2026 paper

We study $n$-party fault-tolerant consensus against general (non-threshold) adversaries. We describe an infinite family $Z_\mathsf{proj}^{n,d}$ of $Q^d$-satisfying $n$-party adversary structures based on finite projective geometry which cause error-free $R$-round protocols for interactive consistency on $L$-bit inputs to require $Ω(Ln^{2+1/d})$ bits of expected communication. Likewise, $Z_\mathsf{proj}^{n,d}$ causes error-free byzantine agreement and broadcast to cost $Ω(Ln^{1+1/d})$ bits. In every case, the lower bound is $Ω(L_{\mathsf{out}} \cdot n^{1+1/d})$ bits, where $L_{\mathsf{out}}$ is the output length. The family $Z_\mathsf{proj}^{n,d}$ also causes reliable broadcast and byzantine agreement to cost $Ω(Ln^{1+1/d})$ bits of expected communication in asynchronous networks. Moreover, there exists a related family $Z_\mathsf{2\textsf-proj}^{n,d}$ of $Q^d$-satisfying adversary structures that make core set agreement cost $Ω(Ln^{2+1/d})$ bits. These asynchronous lower bounds hold against send-omission adversaries, even if the protocol uses cryptography. Their basis is that if a quorum of non-faulty parties agree on an output and terminate, then the messages they sent before terminating must suffice for the parties outside the quorum to also terminate with the same output. Surprisingly, if we do not require the parties to terminate (stop sending messages) after they output, then these bounds no longer hold. We show this by designing a non-terminating omission-tolerant reliable broadcast protocol that can for any parameter $δ> 1$ be tuned to cost $(1 + \frac{1}{δ- 1})Ln + O(δn^2\log(δn))$ bits, which is of independent interest. Lastly, we show how to get termination with $O(Ln^{1+1/d} + n^2\log n)$ bits (assuming the $Q^d$ condition), and thus prove our asynchronous lower bounds tight.

0.35

Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

cs.LG math.OC ·2026-10-05 ·Yuanyu Wan, Lan Xue, Haomin Bai, Tong Wei, Mingli Song
hot direction similarity 0.60
Abstract

We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of $n$ nodes, with the goal of finding an $(δ,ε)$-Goldstein stationary point. The best existing algorithm achieves $O(δ^{-1}(ε^{-3}+dε^{-1}))$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))$ communication complexity, where $d$ is the problem dimension and $γ$ is the spectral gap of the communication matrix. However, the polynomial dependence on $d$ can be a major bottleneck in high-dimensional regimes. In this paper, we propose a novel algorithm that achieves $O(δ^{-1}ε^{-3})$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}ε^{-3})$ communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on $d$ can be removed with only logarithmic additional communication.

0.33

Optimal Lower Bounds for Networked Information Aggregation

cs.LG cs.AIstat.ML ·2026-08-16 ·Ambar Pal
theory similarity 0.58
Abstract

The problem of networked information aggregation, studied in Kearns et al. (2026), involves a group of learners situated on the vertices of a directed acyclic graph $G$, each learning a linear predictor $\widehat Y$ for a fixed random variable $Y$ given access to a local feature, as well as the predictors learnt by its parents. Learning proceeds iteratively, with learners ordered according to a topological sort of $G$. The main quantity of interest is the error incurred by the current learner, constrained to this flow of information, with respect to the best linear predictor using all the features seen so far. When the studied error is the MSE, i.e., $\mathbb{E} (\widehat Y - Y)^2$, Kearns et al. (2026) show that the error is at most $O(1/\sqrt{D})$ along a path of length $D$. They also obtain a hard instance where the MSE is lower bounded by $Ω(1/D)$, leaving the correct order open. In this work, we resolve this central open problem, and obtain a family of worst case problem instances with a MSE lower bound of $Ω(1/\sqrt{D})$. By exploiting invariances in the structure of the learnt predictors, our analysis generalizes to all convex loss functions $\ell(\widehat Y, Y)$ satisfying regularity conditions which include strong convexity in a ball around the origin, and that the ideal predictor minimizing the population loss is positively correlated with the label. We show that networked information aggregation on a gaussian instance in our worst case family incurs an $\ell$-error lower bounded by $Ω(1/\sqrt{D})$ with respect to this ideal predictor. We demonstrate that a variety of common losses satisfy these regularity conditions. In particular, the logistic loss satisfies them, and hence our analysis also closes the gap between the upper and lower bounds in Bateni et al. (2026).

0.04

Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks

cs.LG ·2026-11-05 ·Ye Su, Yong Liu
theory similarity 0.58
Abstract

Schoots et al.~\citep{schoots2025relating} (AISTATS 2025) established a generally loose upper bound on the number of linear regions of continuous piecewise-linear (CPWL) Kolmogorov--Arnold networks (KANs), without providing a lower bound. We consider a $T$-layer network with width vector $\mathbf n=(n_0,\ldots,n_T)$, input dimension $n_0=d$, output width $n_T=1$, and at most $k\geq2$ affine segments per edge. Our matching upper and lower bounds determine the tight growth order $Θ_{\mathbf n}(k^{\sum_{\ell=1}^{T}ρ_{\ell-1}})$ in $k$, where $ρ_{\ell-1}:=\min_{0\leq s\leq\ell-1}n_s$. When every hidden width is at least $d$, the tight order simplifies to $Θ_{\mathbf n}(k^{dT})$. The upper bound of \citep{schoots2025relating} is $k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell}$. Our upper bound improves it by a factor of $Θ_{\mathbf n}\!\left(k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell-\sum_{\ell=1}^{T}ρ_{\ell-1}} \right)$, with strict asymptotic improvement whenever a hidden layer has width greater than one. We further compare CPWL KANs with rectified linear unit (ReLU) networks using dense parameterizations with at most $Λ$ parameters per model and the same fixed nonlinear depth $T$. Counting trainable knot locations and optimizing the widths and $k$, we prove that the maximum region count of CPWL KANs divided by that of ReLU networks is $Θ_{d,T}(Λ^{d\lfloor T/2\rfloor})$ as $Λ\to\infty$, yielding a polynomial advantage for KANs when $T\geq2$. These tight bounds characterize the attainable geometric complexity of CPWL KANs, providing a foundation for understanding their expressive power and guiding architectural design.

0.32

Attracting Rotations Obstruct Almost-Global Consensus on Spheres over Strongly Connected Graphs

eess.SY math.OC ·2026-10-20 ·Galina Sidorenko, Johan Thunberg
similarity 0.57
Abstract · 21 pages including appendices, 2 figures

We study discrete-time consensus on the Euclidean unit sphere, where weighted combinations of neighboring states are normalized to unit length. For symmetric weights on connected undirected graphs and ambient dimension $d\ge3$, earlier results establish instability of non-consensus fixed points under suitable weight conditions. For directed graphs on the unit circle, earlier results show that fixed points other than consensus and antipodal configurations occur only for a measure-zero set of weights. We show that these conclusions do not extend directly to general strongly connected directed graphs in higher dimensions. First, we construct full-rank non-consensus fixed points whose tangent eigenvalues all equal one, showing that strict linear instability need not hold. In a separate construction, for every $d\ge3$, we present a sparse strongly connected graph admitting full-rank fixed points on an open set of its permitted weights. Our main result establishes robust counterexamples to almost-global consensus: attracting rotating motions exist for $d=2$ with every $n\ge3$ and for $d=3$ with every $n\ge6$. These motions are locally asymptotically stable modulo common rotations and have asymptotic phase. They persist on open sets of strictly positive weight matrices. For each such matrix, an open set of initial configurations approaches neither consensus nor any fixed configuration. Thus the absence of full-rank non-consensus fixed points does not ensure almost-global convergence to consensus.

0.26