CS Paper Radar

Distributed Nash Equilibrium Seeking with Logarithmic Bit Rates over Digital Channels

Zihao Ren, Chengyang Jiang, Lei Wang, Yang Liu, Kemi Ding

eess.SY ·submitted 2026-08-12 12:58 UTC · v1
theory

Abstract

This paper introduces quantization techniques to reduce the communication complexity in the distributed Nash equilibrium (NE) seeking problem, achieving an exponential reduction in bit rates over digital channels. The goal of distributed NE seeking algorithms is to coordinate agents in a network game toward equilibrium through iterative message exchanges among them via a communication network. The computational complexity of this distributed algorithm critically depends on network communication overhead in the digital channel, motivating the development of communication reduction mechanism. Regarding this, we proposed some quantizers based on sparsification and uniform quantization through a general class of ultimate-boundedness-based quantizers. Based on this, we propose a Passivity-Based NE seeking Algorithm with Time-varying scaling Error state Quantization (PBA-TEQ), and show that the linear convergence can be achieved under a sufficient condition. Moreover, when employing either the scalarization quantizer or the greedy quantizer, both belonging to the ultimate-boundedness-based quantizers, within the PBA-TEQ framework, we establish a lower bound on communication complexity of $\log_2(\mathcal{O}(nd))$ bit rates per transmission to achieve unbiased linear convergence, with $n$ being the number of agents and $d$ being the dimension of the decision state of the network game. Numerical simulation examples are provided to validate our theoretical results.

Closest papers

Nearest neighbours by meaning across the whole index.

Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels

cs.LG ·2026-11-09 ·Sreejeet Maity, Aritra Mitra
theory similarity 0.63
Abstract

Motivated by reinforcement learning subject to communication constraints, we study a policy evaluation problem with linear function approximation over a rate-limited channel. In our setup, an agent interacting with an unknown environment (modeled as a Markov Decision Process) transmits quantized estimates of a temporal-difference (TD) learning update direction to a server over a finite-capacity channel. Our goal is to investigate to what extent one can preserve the statistical convergence rates achievable when the channel has infinite capacity. To that end, we propose a new algorithm called Batched Adaptively Quantized TD (BAQ-TD), which uses batching to reduce the variance of the transmitted information, and adaptive quantization to encode innovations. We prove a high-probability finite-time error bound for BAQ-TD, and show that, above a certain finite channel capacity, BAQ-TD preserves the convergence rate of unquantized TD up to logarithmic factors. Specifically, for a $d$-dimensional value function parameter, we establish that transmitting a total of $\mathcal{O}(d \log(T))$ bits over a horizon of length $T$ suffices to achieve the order-optimal rate of $\tilde{\mathcal{O}}(1/T)$, marking an exponential improvement in communication-complexity over prior work.

0.25

A Quantization Problem Posed by Adaptive Streaming

cs.IT ·2026-09-03 ·Yuriy A. Reznik
similarity 0.59
Abstract

In adaptive bitrate (ABR) streaming, the delivery technology behind most Internet video, each title is encoded at several bitrates, forming an \emph{encoding ladder} of \emph{renditions}. Each client plays the highest rendition that its network bandwidth can sustain. We show that choosing the ladder is a problem of \emph{scalar quantization} of the bandwidth distribution. However, this quantization problem is of an unusual kind: the client's logic pins each quantization cell's reproduction value to the cell's \emph{left edge}, and the distortion measure is a one-sided quality loss rather than a squared error. The constraint reshapes the classical theory. The \emph{quality gap} of a ladder is the distance between its average delivered quality and the \emph{quality limit} that infinitely many renditions would attain. For optimal $n$-rendition ladders the gap $\mathcal{G}_n^*$ decays as $Θ(1/n)$, not the textbook $Θ(1/n^2)$. Moreover, with large $n$, $n\,\mathcal{G}_n^*\to C_w=\frac{1}{2}(\int\!\sqrt{p\,Q'}\,\,d B)^2$, with the limit attained when the ladder's rates follow the density $\sqrt{p\,Q'}$, which replaces Panter--Dite's $p^{1/3}$; here $p$ is the bandwidth density and $Q$ the quality--rate curve of the content. The law yields closed-form design rules: quantile rung placement, the rendition count $n(\varepsilon)\approx C_w/\varepsilon$ needed to reach tolerance $\varepsilon$, and the economic ladder size $n^*=\sqrt{λC_w/κ}$ when a rendition costs $κ$ to operate and the quality gap is priced at $λ$. The same analysis extends to the design of ladders employing different video resolutions, codecs, perceptual quality metrics, and the two-dimensional adaptation logic of modern web players.

0.21

Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation

cs.IT cs.DScs.LG ·2026-10-17 ·Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
theory similarity 0.58
Abstract · 66 pages

We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds, with asymptotic normalized error at most $(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$. At fixed $R$, this error vanishes as storage grows, giving an unbounded advantage over query-independent reading. We also prove a finite-dimensional lower bound for arbitrary encoders, decoders, and fully branching readers. In the doubly sparse regime $W/R\to\infty$ and $R\log(W/R)\to0$, it gives normalized error at least $(1-o(1))/[2R\log(W/R)]$. Thus, our protocol is optimal within a factor of $π/2$ in the leading constant.

0.19

Entropy-Constrained Adaptive Stochastic Quantization

cs.LG cs.AIcs.DScs.IT ·2026-08-10 ·Ran Ben Basat, Yaniv Ben-Itzhak, Michael Mitzenmacher, Shay Vargaftik
similarity 0.58
Abstract

Adaptive stochastic quantization (ASQ) is a recently introduced quantization approach that optimizes the Mean Squared Error (MSE) for a given input while preserving unbiasedness. It is designed to alleviate the communication and memory bottlenecks of modern data and machine learning workloads, including model, gradient, and KV-cache compression and nearest-neighbor search. Further, practical systems can then compress quantized data with a lossless entropy encoder. However, existing unbiased methods, including ASQ, choose their quantization values without considering this later encoding stage, leaving accuracy on the table. We formulate the Entropy Constrained Adaptive Stochastic Quantization (ECASQ) problem, which jointly selects adaptive quantization values to minimize MSE under an entropy budget and an unbiasedness constraint. We give an optimal dynamic program with $O(sd^2)$ time and $O(d^2)$ space for a length-d vector and at most s quantization values, and a GPU-friendly approximate dynamic program with $O(sd^2)$ time and $O(d)$ space. The approximation guarantees that the solution has an MSE no larger than the optimal solution that uses one fewer bit of entropy per entry. We also provide an iterative refinement procedure for the approximation solution that, in our experiments, yields near-optimal results while retaining a substantial speed advantage over our solver for the optimal solution.

0.34

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

cs.IT stat.MLcs.LGmath.ST ·2026-09-08 ·Ivan Lau, Jonathan Scarlett
similarity 0.57
Abstract

We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query $Q: \mathbb{R}\to\{0,1\}$ chosen by a central learner. The distribution has mean in $[-λ,λ]$ and $k$-th central moment at most $σ^k$, for a fixed $k>1$. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every $k>1$, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set $Q^{-1}(1)$ is restricted to a union of at most $s$ intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order $(λσ/(s\varepsilon^2))\log(1/δ)$, giving the full tradeoff between sample complexity and interval complexity to within $k$-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.

0.40

The Exact Communication Threshold for Parallel Repetition

cs.CC ·2026-10-31 ·Daiki Suruga
theory similarity 0.56
Abstract

The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all $n$ independent instances of a finite two-player game decays exponentially in $n$, provided that the game has no perfect strategy. The classical theorem assumes that the players cannot communicate, raising the question of how much communication can be allowed while preserving this exponential decay. For every finite total relation $g$ and arbitrary input distribution $μ$, we prove exponential decay at every fixed communication rate below a quantity called zero-error internal information complexity, denoted by $\mathrm{IC}_μ(g,0)$. Together with known results showing that $n\,\mathrm{IC}_μ(g,0)+o(n)$ bits of communication suffice to solve all $n$ instances with success probability tending to one, our bound determines the exact communication threshold. As a by-product, we obtain exact characterizations of amortized distributional and randomized communication complexity under the global-error criterion.

0.17

Regret Bounds for Quantum Linear Bandits

cs.LG ·2026-11-11 ·Maoli Liu, Zhuohua Li, John C. S. Lui
theory similarity 0.55
Abstract · 26 pages

We study $d$-dimensional quantum linear bandits with bounded rewards, where the learner selects an action and queries its quantum reward oracle or its inverse in each round. For general action sets, existing algorithms achieve regret $O(d^{3/2}\operatorname{polylog}(T))$ over $T$ rounds. Prior work established a lower bound of $Ω(d\log(1+T/d))$, leaving open whether the $d^{3/2}$ dependence in the upper bound is necessary. We resolve this question by proving a minimax lower bound of $Ω(d^{3/2}\log(1+T/d^{3/2}))$. To prove this result, we construct a family of hard instances in which the reward gap of each action is proportional to its squared distance from the optimal action. We establish a posterior Fisher information bound for adaptive quantum queries with quantum memory, relating the information acquired about the optimal direction to the regret incurred. Viewing each selected action as an estimate of the optimal direction, we use a matrix Cramér--Rao argument to derive a lower bound on expected regret. When the action set is fixed and has size $K$, we propose two phased elimination algorithms, Soft-G-Elim and QG-Elim. We adapt quantum phase estimation to construct SoftQME, a mean estimator with small bias and controlled tails. Soft-G-Elim estimates the mean reward of every surviving action from independent SoftQME outputs on the support of an experimental design. Controlling the bias and fluctuations of these estimates yields regret $O(d\log T\log(dT)\sqrt{\log(KT)})$, reducing the $\log(KT)\log\log(dT)$ factor in the previous regret bound to $\sqrt{\log(KT)}$. QG-Elim further reduces this factor to $\min\{\sqrt{\log(KT)},\sqrt d\}$.

0.14

Information Potential: A Variational Approach to Quantum Information Complexity

cs.CC quant-ph ·2026-09-30 ·Penghui Yao, Yifan Zhou
theory similarity 0.55
Abstract

Quantum information complexity (QIC), introduced by Touchette [Touchette, STOC 2015], has been shown to be one of the most powerful methods for proving quantum communication complexity and has also been shown to be equal to amortized quantum communication complexity. Unfortunately, QIC is generally hard to analyze because it is a sum of quantum conditional mutual information terms, which are difficult to estimate. In this work, we introduce a new variational approach, the information potential, for analyzing QIC and proving quantum communication lower bounds inspired by the resolvent representation for quantum relative entropy. This approach connects the QIC of individual messages to a quadratic form, making it more amenable and thus enables us to bound the cumulative positive increments of the potential throughout an interactive quantum protocol by its QIC. Lower bounds on the growth of the potential therefore translate into lower bounds on both QIC and quantum communication complexity. As an application, we give an optimal $Ω(1/r)$ lower bound on the QIC of the two-bit $\mathsf{AND}$ function as well as an optimal $Ω(n/r)$ lower bound on the quantum communication complexity of $r$-round Set-Disjointness, answering an open problem in~[Braverman, Garg, Ko, Mao, Touchette FOCS 2015]. Moreover, we further prove a direct-sum theorem for bounded-round quantum communication complexity of Set Disjointness. With the tight bound on the QIC of $\mathsf{AND}$ function, we further establish a nearly tight tradeoff for the asymmetric quantum communication complexity of $\mathsf{Set} \mathsf{Disjointness}$: $(q_A+1)(q_B+1)=Ω(n)$, where $q_A$ and $q_B$ denote the total numbers of qubits sent by Alice and Bob, respectively.

0.26