Tomer Berg
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Tomer Berg has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Ofer Shayevitz
Tel Aviv University, Tel Aviv, Israel
5 shared publications - Or Ordentlich
School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem, Israel
4 shared publications - Lele Wang
Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, BC, Canada
1 shared publication - Young-Han Kim
Department of Electrical and Computer Engineering, University of California at San Diego, La Jolla, CA, USA
1 shared publication
Latest Publications
- 4 March 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3334-3349
Memory Complexity of Estimating Entropy and Mutual Information
We observe an infinite sequence of independent identically distributed random variables$X_{1},X_{2},\ldots $ drawn from an unknown distribution p over$[n]$ , and our goal is to estimate the entropy$H(p)=-\mathop {\mathrm {\mathbb {E}}}\nolimits [\log p(X)]$ within an$\varepsilon $ -additive error. To that end, at each time point we are allowed to update a finite-state machine with S states, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity$S^{*}$ of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least$1-\delta $ asymptotically, uniformly in p. Specifically, we show that there exist universal constants$C_{1}$ and$C_{2}$ such that$ S^{*} \leq C_{1}\cdot \frac {n (\log n)^{4}}{\varepsilon ^{2}\delta }$ for$\varepsilon $ not too small, and$S^{*} \geq C_{2} \cdot \max \left \{{{n, \frac {\log n}{\varepsilon }}}\right \}$ for$\varepsilon $ not too large. The upper bound is proved using approximate counting to estimate the logarithm of p, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.- 4 March 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3334-3349
Memory Complexity of Estimating Entropy and Mutual Information
We observe an infinite sequence of independent identically distributed random variables$X_{1},X_{2},\ldots $ drawn from an unknown distribution p over$[n]$ , and our goal is to estimate the entropy$H(p)=-\mathop {\mathrm {\mathbb {E}}}\nolimits [\log p(X)]$ within an$\varepsilon $ -additive error. To that end, at each time point we are allowed to update a finite-state machine with S states, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity$S^{*}$ of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least$1-\delta $ asymptotically, uniformly in p. Specifically, we show that there exist universal constants$C_{1}$ and$C_{2}$ such that$ S^{*} \leq C_{1}\cdot \frac {n (\log n)^{4}}{\varepsilon ^{2}\delta }$ for$\varepsilon $ not too small, and$S^{*} \geq C_{2} \cdot \max \left \{{{n, \frac {\log n}{\varepsilon }}}\right \}$ for$\varepsilon $ not too large. The upper bound is proved using approximate counting to estimate the logarithm of p, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.- 14 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 623-644
Statistical Inference With Limited Memory: A Survey
The problem of statistical inference in its various forms has been the subject of decades-long extensive research. Most of the effort has been focused on characterizing the behavior as a function of the number of available samples, with far less attention given to the effect of memory limitations on performance. Recently, this latter topic has drawn much interest in the engineering and computer science literature. In this survey paper, we attempt to review the state-of-the-art of statistical inference under memory constraints in several canonical problems, including hypothesis testing, parameter estimation, and distribution property testing/estimation. We discuss the main results in this developing field, and by identifying recurrent themes, we extract some fundamental building blocks for algorithmic construction, as well as useful techniques for lower bound derivations.
- 14 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 5, 623-644
Statistical Inference With Limited Memory: A Survey
The problem of statistical inference in its various forms has been the subject of decades-long extensive research. Most of the effort has been focused on characterizing the behavior as a function of the number of available samples, with far less attention given to the effect of memory limitations on performance. Recently, this latter topic has drawn much interest in the engineering and computer science literature. In this survey paper, we attempt to review the state-of-the-art of statistical inference under memory constraints in several canonical problems, including hypothesis testing, parameter estimation, and distribution property testing/estimation. We discuss the main results in this developing field, and by identifying recurrent themes, we extract some fundamental building blocks for algorithmic construction, as well as useful techniques for lower bound derivations.
- 28 October 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (2) , 886-901
Distributed Source Simulation With No Communication
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Un and Vn respectively, drawn from a joint distribution pUV⊗n, and wish to locally generate sequences Xn and Yn respectively with a joint distribution that is close (in KL divergence) to pXY⊗n. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains X-U-V-Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUV and pXY are doubly symmetric binary sources with parameters p,q ≤ 1/2 respectively. While it is trivial that in this case p ≤ q is both necessary and sufficient, we use Fourier analytic tools to show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.
- 28 October 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (2) , 886-901
Distributed Source Simulation With No Communication
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Un and Vn respectively, drawn from a joint distribution pUV⊗n, and wish to locally generate sequences Xn and Yn respectively with a joint distribution that is close (in KL divergence) to pXY⊗n. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains X-U-V-Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUV and pXY are doubly symmetric binary sources with parameters p,q ≤ 1/2 respectively. While it is trivial that in this case p ≤ q is both necessary and sufficient, we use Fourier analytic tools to show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.
- Open Access
- 1 June 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1259-1264
Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let X 1 , X 2 , …. be a sequence of independent identically distributed Bernoulli random variables, with expectation p under ${{\mathcal{H}}_0}$ and q under ${{\mathcal{H}}_1}$. Consider a finite-memory deterministic machine with S states that updates its state M n ∈ {1,2,…, S} at each time according to the rule M n = f(M n-1 , X n ), where f is a deterministic time-invariant function. Assume that we let the process run for a very long time (n→∞), and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability P e of any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of P e with S for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.- 1 June 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1259-1264
Open AccessBinary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let X 1 , X 2 , …. be a sequence of independent identically distributed Bernoulli random variables, with expectation p under ${{\mathcal{H}}_0}$ and q under ${{\mathcal{H}}_1}$. Consider a finite-memory deterministic machine with S states that updates its state M n ∈ {1,2,…, S} at each time according to the rule M n = f(M n-1 , X n ), where f is a deterministic time-invariant function. Assume that we let the process run for a very long time (n→∞), and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability P e of any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of P e with S for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman. - Open Access
Binary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let $X_1,X_2,\ldots$ be a sequence of independent identically distributed Bernoulli random variables, with expectation $p$ under $\mathcal{H}_0$ and $q$ under $\mathcal{H}_1$. Consider a finite-memory deterministic machine with $S$ states that updates its state $M_n \in \{1,2,\ldots,S\}$ at each time according to the rule $M_n = f(M_{n-1},X_n)$, where $f$ is a deterministic time-invariant function. Assume that we let the process run for a very long time ($n\rightarrow \infty)$, and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability $P_e$ of any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of $P_e$ with $S$ for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.Open AccessBinary Hypothesis Testing with Deterministic Finite-Memory Decision Rules
In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let $X_1,X_2,\ldots$ be a sequence of independent identically distributed Bernoulli random variables, with expectation $p$ under $\mathcal{H}_0$ and $q$ under $\mathcal{H}_1$. Consider a finite-memory deterministic machine with $S$ states that updates its state $M_n \in \{1,2,\ldots,S\}$ at each time according to the rule $M_n = f(M_{n-1},X_n)$, where $f$ is a deterministic time-invariant function. Assume that we let the process run for a very long time ($n\rightarrow \infty)$, and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability $P_e$ of any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of $P_e$ with $S$ for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.