CS Paper Radar

Estimation with Quantized Parameter Side-Information

Mathis Wetterwald, Ofer Shayevitz, Michèle Wigger

cs.IT ·submitted 2026-10-08 13:42 UTC · v1
published

Abstract

This paper presents upper and lower bounds on the minimax risk of a parameter estimation problem where the estimator not only observes independent and identically distributed observations but also a quantized version of the parameter, where the quantization has a limitation on the number of levels, but can be optimized otherwise. Our upper and lower bounds have similar decay rates for large number of observation samples and quantization levels.

Comment
5 pages, conference paper
Journal ref
2026 IEEE International Symposium on Information Theory (ISIT)
DOI
10.1109/ISIT62367.2026.11653704

Closest papers

Nearest neighbours by meaning across the whole index.

Minimax Quantile Bounds via Information Measures

cs.IT math.ST ·2026-08-21 ·Amedeo Roberto Esposito
similarity 0.61
Abstract

We develop a unified information-theoretic framework for lower bounding minimax quantiles. The starting point is a loss-adapted Neyman--Pearson metaconverse that bounds the minimax success probability at every loss threshold and confidence level. The bound separates the small-ball behaviour of the prior under the loss from the statistical distinguishability of the observation model, and is optimised over an auxiliary output distribution. Different relaxations of this Neyman--Pearson bound yield converses based on \(f\)-informativity, Sibson mutual information \(I_α\), Maximal Leakage, and Amemiya norms. Classical Fano and Le Cam lower bounds are recovered as special cases. The framework also clarifies why different information measures are suited to different recovery criteria. Maximal Leakage is exact for a class of symmetric exact-recovery problems. We use this identity to derive finite-sample bounds on the full minimax exact-recovery risk in the balanced Gaussian weighted stochastic block model, as well as two-sided finite-sample minimax-quantile bounds for low-rank matrix estimation under isotropic bounded-energy noise. For approximate Hamming recovery, we exhibit a heterogeneous binary model in which an optimised finite Sibson order yields a strong converse while the Maximal Leakage specialisation is trivial. Finally, for one-coordinate Poisson localisation, a Bennett-type Young function used through its Amemiya norm recovers the exact success-probability scale, whereas classical Fano and fixed-power relaxations are strictly weaker. These results show that sharp converses for minimax quantiles require adapting the information measure to the recovery resolution, whether exact or approximate, and to the tail behaviour of the likelihood ratio.

0.45

Quickest Change Detection in Parametric Models With 1-Bit Measurements

cs.IT math.ST ·2026-08-18 ·Liyan Xie, Martina Cardone
similarity 0.57
Abstract · Accepted to IEEE Information Theory Workshop (ITW) 2026

We consider the quickest change detection from 1-bit quantized observations, where the post-change distribution is a parametric model with unknown parameters and the quantization thresholds are jointly chosen with the detection statistic. We propose an Adaptive-Quantization-Threshold CUSUM (AQuTeCUSUM) algorithm, which estimates the post-change parameter online and adaptively selects the quantization threshold to maximize the induced Kullback-Leibler divergence. Under suitable regularity conditions, we characterize the average run length and worst-case average detection delay of the AQuTe-CUSUM procedure, and show that it is asymptotically optimal in first-order as the average run length goes to infinity. Finally, we assess the performance of AQuTe-CUSUM for two distributions, namely the Gaussian and Poisson.

0.28

Optimal random quantisers for spherically symmetric distributions

cs.LG math.STstat.ML ·2026-10-08 ·Luc Pronzato, Anatoly Zhigljavsky
theory similarity 0.56
Abstract

Zador's celebrated theorem is a cornerstone of optimal quantisation: it establishes both the weak limit of the empirical distribution of an optimal $n$-point quantiser in $R^d$ and the decay rate of the associated $L_s$-mean quantisation error. In large dimension, however, observing this asymptotic behaviour requires an astronomically large sample size. We prove that, for spherically symmetric target distributions, optimisation over all spherically symmetric distributions is a convex problem and derive an equivalence theorem that both characterises global optimality and yields a constructive algorithm. We show that, for moderate $n$, random quantisers uniformly distributed on a sphere of suitably chosen radius $R$ perform exceptionally well and, over a broad range of values of $n$, are numerically certified to be optimal among all random quantisers. Their expected distortion has an explicit integral representation that can be evaluated to arbitrary precision, and we prove concentration across random quantisers: the distortion variance tends to zero as $n\to\infty$ for fixed $d$. For $s=2$, both the optimal radius and the associated minimum expected distortion admit exact expressions. For general $s$, the optimal radius can be determined efficiently, and extreme-value theory provides useful approximations when $n$ grows with $d$. Depending on this growth rate, $R$ either converges to zero or approaches a positive limit that is independent of $s$.

0.35

Universal Quantizer Design for Identification of Systems with Memory

eess.SY ·2026-11-16 ·Yibo Shi, Ying Wang, Karl H. Johansson, Cristian R. Rojas
similarity 0.55
Abstract · 8 pages

In system identification from quantized observations, the quantizer determines how much information about the parameters the observations retain, and hence the achievable estimation accuracy. Quantizer design can be guided by the Fisher information matrix (FIM), which assesses the parameter information retained by candidate quantizers. Existing methods, however, typically rely on closed-form expressions of the FIM. This paper proposes a universal quantizer design method for general systems with memory. Its core is a universal FIM estimator that evaluates the information per bit from simulated trajectories, and the thresholds are designed by maximizing the estimated criterion under a bit budget. For unknown parameters, the design is implemented through a two-stage procedure. Numerical studies on a quantized ARX system yield designs close to the reference optimum, while a nonlinear cascaded-tanks example reduces the identification error by about 50% relative to a single median threshold.

0.31

Occupancy-based Quantile Risk Control

cs.LG stat.ML ·2026-09-02 ·Zihao Shi, Huajun Xi, Bingyi Jing, Hongxin Wei
theory similarity 0.55
Abstract

Conformal risk control is an emerging framework for the safe deployment of machine learning models with finite-sample guarantees. To accommodate a broader class of risk notions, quantile risk control extends this framework to quantile-based risk measures. However, existing methods either suffer from excessive conservatism or lack rigorous finite-sample guarantees. To address these limitations, we introduce Occupancy-based Quantile Risk Control (OQRC), a novel method that provides tight risk control bounds with finite-sample validity. Our key idea is to formulate risk control as a finite-occupancy problem by partitioning the loss space with the ordered calibration losses. Specifically, we estimate the distribution of test losses across the resulting bins and upper-bound the risk by the maximum loss attained within each bin. We then select the parameter $λ$ such that this upper bound does not exceed a predefined threshold $α$ with high probability $1-δ$. Theoretically, we establish a finite-sample guarantee showing that OQRC yields tight risk control bounds that converge to the optimal bounds at a provable rate of $\mathcal{O}_ p(n^{-1/2})$. Extensive experiments demonstrate the effectiveness of our method, reducing the risk gap by up to 78.64\% on common benchmarks.

0.16

Deterministic Causal Quantization with Bounded Error: Adaptive Reconstruction and Entropy bounds

cs.IT math.PR ·2026-10-20 ·Rama Cont, Massoud Heidari
theory similarity 0.55
Abstract · 41 pages

We study compression of real-valued stationary sources under a deterministic error bound: every sample must be reconstructed within a prescribed tolerance $\varepsilon$ on every input sequence. Reconstructions are causal, depending only on present and past inputs. Rates are measured by the entropy of the quantizer output, which block entropy coding can approach, and compared with the minimum rate of unrestricted block quantization under the same error constraint. A uniform scalar quantizer with cells of width $2\varepsilon$ is within one bit per sample of this minimum whenever finite-entropy scalar quantization is possible, without density, independence, or mixing assumptions. Under entropy and Sobolev regularity conditions, the gap is at most $2\mathcal{J}\varepsilon^2/(π^2\ln 2)$, where $\mathcal{J}$ is the asymptotic Fisher information per sample. Thus the cost of causal reconstruction vanishes at a quadratic rate as the tolerance decreases. A uniform grid, however, cannot adapt to the source. We construct an adaptive quantizer whose encoder and decoder maintain a common finite set of reconstruction values, updated from the transmitted symbols alone; suitable initialization reproduces any uniform grid. When its initial values are at least $\varepsilon$ apart, its rate is within two bits per sample of the minimum for every such source. For sources uniform within separated intervals of width $2\varepsilon$, storing the interval centers attains the minimum and its Shannon lower bound. Such configurations can outperform every uniform grid of the same cell width: over sources with well-separated intervals, the best uniform grid's worst-case excess rate is $1/(2\ln 2)\approx 0.72$ bit per sample.

0.27

Maximal correlation under cardinality constraints

cs.IT ·2026-08-17 ·Dror Drach, Tomer Berg, Or Ordentlich, Ofer Shayevitz
theory similarity 0.55
Abstract

In this paper, we define and analyze the quantized maximal correlation, an extension of the notion of maximal correlation restricted to functions taking values in sets of bounded cardinality. We derive an upper bound on the quantized maximal correlation by showing that the correlation between any quantized functions of $X$ and $Y$ is related to the MMSE distortion in quantization of a particular linear combination of random variables. Following this, we leverage rate-distortion techniques and anti-concentration inequalities to further bound this MMSE, which results in explicit bounds on the quantized maximal correlation. Unlike the quantized maximal correlation itself, which does not generally tensorize, our bounds on the mean squared error do tensorize, resulting in a dimension-free upper bound on the quantized maximal correlation for product distributions. Our results also lead to improved bounds on the isoperimetric constants of reversible Markov chains and product chains, strengthening classical results such as those by Alon and Milman.

0.31

Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions

cs.LG stat.ML ·2026-09-22 ·Yicheng Li, Huifu Xu
similarity 0.54
Abstract

We study preference elicitation under the Bradley-Terry-Luce (BTL) model where the true partworth vector is unknown and has to be estimated as a parameter with elicited preference information. The set of selected pairwise queries is non-uniform, deterministic, and arbitrary over a collection of alternatives, provided that it satisfies a joint identifiability condition. We focus on understanding when the canonical maximum likelihood estimator (MLE) is finite and admits sharp error bounds without explicit compactness constraints on the feasible set or external regularizers. To this end, we derive minimax lower bounds under the standard bounded dynamic range condition, and find that the same Fisher-information geometry in the classic Cramér-Rao lower bounds underpins the finite-sample difficulty of the estimation problem. By combining a non-asymptotic expansion of the likelihood score equation with a fixed-point localization argument, we identify a design-dependent sample size threshold above which the unconstrained canonical MLE exists and is unique with high probability. The same expansion yields a decomposition of the estimation error into a linear stochastic term, an explicit second-order bias, and a higher-order remainder. A refined analysis gives sufficient sample size conditions under which the canonical MLE attains the minimax rates up to logarithmic and constant factors. These results provide a unified non-asymptotic theory for parametric utility elicitation and reveal when the inference is determined by response data alone rather than by external regularization. Preliminary numerical results are consistent with the theoretical findings.

0.44