Tamás Linder
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Tamás Linder has a total of 52 co-authors. Here are the top co-authors by number of shared publications:
- Fady Alajaji
Department of Mathematics and Statistics, Queens University, Kingston, ON, Canada
22 shared publications - Serdar Yüksel
Department of Mathematics and Statistics, Queen’s University, Kingston, Ontario K7L 3N6, Canada
21 shared publications Fady Alajaji
12 shared publications- Naci Saldi
Department of Mathematics Bilkent University C ¸ankaya 06800 Ankara TURKEY
10 shared publications - Bahman Gharesifard
Department of Mathematics and Statistics, Queens University, Kingston, ON, Canada
5 shared publications - Shahab Asoodeh
Department of Mathematics and Statistics Queen's University
5 shared publications
Latest Publications
- 3 April 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (6) , 3525-3538
Communication Complexity of Exact Sampling Under Rényi Information
We study the problem of exact sampling under an exponential communication cost, specifically Campbell’s average codeword length $\boldsymbol {L(t)}$ of order $\boldsymbol {t}$ , and Rényi’s entropy. We provide a lower bound on the Campbell cost of exact sampling that grows approximately as $\boldsymbol {D_{1/\alpha }(P||Q)}$ , the Rényi divergence of order $\boldsymbol {1/\alpha }$ , with $\boldsymbol {\alpha = 1 / 1 + t}$ . Using the Poisson functional representation of Li and El Gamal (2017), we prove an upper bound on $\boldsymbol {L(t)}$ whose leading Rényi divergence term has order within $\boldsymbol {\epsilon }$ of that of the lower bound. Our results reduce to the bounds of Harsha et al. (2010) as $\boldsymbol {\alpha \to 1}$ . We also provide numerical examples comparing the bounds in the cases of normal and Laplacian distributions, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other. Our results characterize exactly the optimal asymptotic Campbell cost $\boldsymbol {L(t)}$ per sample as the number of independent and identically distributed (i.i.d.) samples grows to infinity. We show that under the exponential cost, any causal sampler performs strictly worse asymptotically than noncausal samplers. This contrasts with the case of expected message length, where both causal and noncausal samplers have the same optimal asymptotic cost.
- 3 April 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (6) , 3525-3538
Communication Complexity of Exact Sampling Under Rényi Information
We study the problem of exact sampling under an exponential communication cost, specifically Campbell’s average codeword length $\boldsymbol {L(t)}$ of order $\boldsymbol {t}$ , and Rényi’s entropy. We provide a lower bound on the Campbell cost of exact sampling that grows approximately as $\boldsymbol {D_{1/\alpha }(P||Q)}$ , the Rényi divergence of order $\boldsymbol {1/\alpha }$ , with $\boldsymbol {\alpha = 1 / 1 + t}$ . Using the Poisson functional representation of Li and El Gamal (2017), we prove an upper bound on $\boldsymbol {L(t)}$ whose leading Rényi divergence term has order within $\boldsymbol {\epsilon }$ of that of the lower bound. Our results reduce to the bounds of Harsha et al. (2010) as $\boldsymbol {\alpha \to 1}$ . We also provide numerical examples comparing the bounds in the cases of normal and Laplacian distributions, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other. Our results characterize exactly the optimal asymptotic Campbell cost $\boldsymbol {L(t)}$ per sample as the number of independent and identically distributed (i.i.d.) samples grows to infinity. We show that under the exponential cost, any causal sampler performs strictly worse asymptotically than noncausal samplers. This contrasts with the case of expected message length, where both causal and noncausal samplers have the same optimal asymptotic cost.
- Open Access
Bounds on the Excess Minimum Risk via Generalized Information Divergence Measures
Given finite-dimensional random vectors Y, X, and Z that form a Markov chain in that order (), we derive the upper bounds on the excess minimum risk using generalized information divergence measures. Here, Y is a target vector to be estimated from an observed feature vector X or its stochastically degraded version Z. The excess minimum risk is defined as the difference between the minimum expected loss in estimating Y from X and from Z. We present a family of bounds that generalize a prior bound based on mutual information, using the Rényi and -Jensen–Shannon divergences, as well as Sibson’s mutual information. Our bounds are similar to recently developed bounds for the generalization error of learning algorithms. However, unlike these works, our bounds do not require the sub-Gaussian parameter to be constant, and therefore, apply to a broader class of joint distributions over Y, X, and Z. We also provide numerical examples under both constant and non-constant sub-Gaussianity assumptions, illustrating that our generalized divergence-based bounds can be tighter than the ones based on mutual information for certain regimes of the parameter .Open AccessBounds on the Excess Minimum Risk via Generalized Information Divergence Measures
Given finite-dimensional random vectors Y, X, and Z that form a Markov chain in that order (), we derive the upper bounds on the excess minimum risk using generalized information divergence measures. Here, Y is a target vector to be estimated from an observed feature vector X or its stochastically degraded version Z. The excess minimum risk is defined as the difference between the minimum expected loss in estimating Y from X and from Z. We present a family of bounds that generalize a prior bound based on mutual information, using the Rényi and -Jensen–Shannon divergences, as well as Sibson’s mutual information. Our bounds are similar to recently developed bounds for the generalization error of learning algorithms. However, unlike these works, our bounds do not require the sub-Gaussian parameter to be constant, and therefore, apply to a broader class of joint distributions over Y, X, and Z. We also provide numerical examples under both constant and non-constant sub-Gaussianity assumptions, illustrating that our generalized divergence-based bounds can be tighter than the ones based on mutual information for certain regimes of the parameter . - Open Access
Bounds on the Excess Minimum Risk via Generalized Information Divergence Measures
Given finite-dimensional random vectors $Y$, $X$, and $Z$ that form a Markov chain in that order (i.e., $Y \to X \to Z$), we derive upper bounds on the excess minimum risk using generalized information divergence measures. Here, $Y$ is a target vector to be estimated from an observed feature vector $X$ or its stochastically degraded version $Z$. The excess minimum risk is defined as the difference between the minimum expected loss in estimating $Y$ from $X$ and from $Z$. We present a family of bounds that generalize the mutual information based bound of Gy\"orfi et al. (2023), using the R\'enyi and $\alpha$-Jensen-Shannon divergences, as well as Sibson's mutual information. Our bounds are similar to those developed by Modak et al. (2021) and Aminian et al. (2024) for the generalization error of learning algorithms. However, unlike these works, our bounds do not require the sub-Gaussian parameter to be constant and therefore apply to a broader class of joint distributions over $Y$, $X$, and $Z$. We also provide numerical examples under both constant and non-constant sub-Gaussianity assumptions, illustrating that our generalized divergence based bounds can be tighter than the one based on mutual information for certain regimes of the parameter $\alpha$.Open AccessBounds on the Excess Minimum Risk via Generalized Information Divergence Measures
Given finite-dimensional random vectors $Y$, $X$, and $Z$ that form a Markov chain in that order (i.e., $Y \to X \to Z$), we derive upper bounds on the excess minimum risk using generalized information divergence measures. Here, $Y$ is a target vector to be estimated from an observed feature vector $X$ or its stochastically degraded version $Z$. The excess minimum risk is defined as the difference between the minimum expected loss in estimating $Y$ from $X$ and from $Z$. We present a family of bounds that generalize the mutual information based bound of Gy\"orfi et al. (2023), using the R\'enyi and $\alpha$-Jensen-Shannon divergences, as well as Sibson's mutual information. Our bounds are similar to those developed by Modak et al. (2021) and Aminian et al. (2024) for the generalization error of learning algorithms. However, unlike these works, our bounds do not require the sub-Gaussian parameter to be constant and therefore apply to a broader class of joint distributions over $Y$, $X$, and $Z$. We also provide numerical examples under both constant and non-constant sub-Gaussianity assumptions, illustrating that our generalized divergence based bounds can be tighter than the one based on mutual information for certain regimes of the parameter $\alpha$. - 26 November 2024
- Published by Springer Nature in TEST
- Vol. 34 (1) , 262-287
Distribution-free tests for lossless feature selection in classification and regression
- 26 November 2024
- Published by Springer Nature in TEST
- Vol. 34 (1) , 262-287
Distribution-free tests for lossless feature selection in classification and regression
- 8 November 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 70 (4) , 2746-2753
Distributed Optimization With Uncertain Communications
We consider a distributed optimization problem for the sum of convex functions where the underlying communication network connecting nodes at each time epoch is drawn at random from a collection of directed graphs. We propose a modified version of the subgradient-push algorithm that provably almost surely converges to an optimizer on any such sequence of random directed graphs. We also prove that the convergence rate of our proposed algorithm is upper bounded as $ O(\frac{1}{\sqrt{t}})$ , where $t$ is the time horizon
- 8 November 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 70 (4) , 2746-2753
Distributed Optimization With Uncertain Communications
We consider a distributed optimization problem for the sum of convex functions where the underlying communication network connecting nodes at each time epoch is drawn at random from a collection of directed graphs. We propose a modified version of the subgradient-push algorithm that provably almost surely converges to an optimizer on any such sequence of random directed graphs. We also prove that the convergence rate of our proposed algorithm is upper bounded as $ O(\frac{1}{\sqrt{t}})$ , where $t$ is the time horizon
- 17 June 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (11) , 8399-8413
Reinforcement Learning for Near-Optimal Design of Zero-Delay Codes for Markov Sources
In the classical lossy source coding problem, one encodes long blocks of source symbols that enables the distortion to approach the ultimate Shannon limit. Such a block-coding approach introduces large delays, which is undesirable in many delay-sensitive applications. We consider the zero-delay case, where the goal is to encode and decode a finite-alphabet Markov source without any delay. It has been shown that this problem lends itself to stochastic control techniques, which lead to existence, structural, and general structural approximation results. However, these techniques so far have only resulted in computationally prohibitive algorithmic implementations for code design. To address this problem, we present a practically implementable reinforcement learning design algorithm and rigorously prove its asymptotic optimality. In particular, we show that a quantized Q-learning algorithm can be used to obtain a near-optimal coding policy for this problem. The proof builds on recent results on quantized Q-learning for weakly Feller controlled Markov chains whose application necessitates the development of supporting technical results on regularity and stability properties, and relating the optimal solutions for discounted and average cost infinite horizon criteria problems. These theoretical results are supported by simulations.
- 17 June 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (11) , 8399-8413
Reinforcement Learning for Near-Optimal Design of Zero-Delay Codes for Markov Sources
In the classical lossy source coding problem, one encodes long blocks of source symbols that enables the distortion to approach the ultimate Shannon limit. Such a block-coding approach introduces large delays, which is undesirable in many delay-sensitive applications. We consider the zero-delay case, where the goal is to encode and decode a finite-alphabet Markov source without any delay. It has been shown that this problem lends itself to stochastic control techniques, which lead to existence, structural, and general structural approximation results. However, these techniques so far have only resulted in computationally prohibitive algorithmic implementations for code design. To address this problem, we present a practically implementable reinforcement learning design algorithm and rigorously prove its asymptotic optimality. In particular, we show that a quantized Q-learning algorithm can be used to obtain a near-optimal coding policy for this problem. The proof builds on recent results on quantized Q-learning for weakly Feller controlled Markov chains whose application necessitates the development of supporting technical results on regularity and stability properties, and relating the optimal solutions for discounted and average cost infinite horizon criteria problems. These theoretical results are supported by simulations.
- Open Access
Lossless Transformations and Excess Risk Bounds in Statistical Inference
We study the excess minimum risk in statistical inference, defined as the difference between the minimum expected loss when estimating a random variable from an observed feature vector and the minimum expected loss when estimating the same random variable from a transformation (statistic) of the feature vector. After characterizing lossless transformations, i.e., transformations for which the excess risk is zero for all loss functions, we construct a partitioning test statistic for the hypothesis that a given transformation is lossless, and we show that for i.i.d. data the test is strongly consistent. More generally, we develop information-theoretic upper bounds on the excess risk that uniformly hold over fairly general classes of loss functions. Based on these bounds, we introduce the notion of a -lossless transformation and give sufficient conditions for a given transformation to be universally -lossless. Applications to classification, nonparametric regression, portfolio strategies, information bottlenecks, and deep learning are also surveyed.Open AccessLossless Transformations and Excess Risk Bounds in Statistical Inference
We study the excess minimum risk in statistical inference, defined as the difference between the minimum expected loss when estimating a random variable from an observed feature vector and the minimum expected loss when estimating the same random variable from a transformation (statistic) of the feature vector. After characterizing lossless transformations, i.e., transformations for which the excess risk is zero for all loss functions, we construct a partitioning test statistic for the hypothesis that a given transformation is lossless, and we show that for i.i.d. data the test is strongly consistent. More generally, we develop information-theoretic upper bounds on the excess risk that uniformly hold over fairly general classes of loss functions. Based on these bounds, we introduce the notion of a -lossless transformation and give sufficient conditions for a given transformation to be universally -lossless. Applications to classification, nonparametric regression, portfolio strategies, information bottlenecks, and deep learning are also surveyed. - Open Access
Lossless Transformations and Excess Risk Bounds in Statistical Inference
We study the excess minimum risk in statistical inference, defined as the difference between the minimum expected loss in estimating a random variable from an observed feature vector and the minimum expected loss in estimating the same random variable from a transformation (statistic) of the feature vector. After characterizing lossless transformations, i.e., transformations for which the excess risk is zero for all loss functions, we construct a partitioning test statistic for the hypothesis that a given transformation is lossless and show that for i.i.d. data the test is strongly consistent. More generally, we develop information-theoretic upper bounds on the excess risk that uniformly hold over fairly general classes of loss functions. Based on these bounds, we introduce the notion of a delta-lossless transformation and give sufficient conditions for a given transformation to be universally delta-lossless. Applications to classification, nonparametric regression, portfolio strategies, information bottleneck, and deep learning, are also surveyed.
Open AccessLossless Transformations and Excess Risk Bounds in Statistical Inference
We study the excess minimum risk in statistical inference, defined as the difference between the minimum expected loss in estimating a random variable from an observed feature vector and the minimum expected loss in estimating the same random variable from a transformation (statistic) of the feature vector. After characterizing lossless transformations, i.e., transformations for which the excess risk is zero for all loss functions, we construct a partitioning test statistic for the hypothesis that a given transformation is lossless and show that for i.i.d. data the test is strongly consistent. More generally, we develop information-theoretic upper bounds on the excess risk that uniformly hold over fairly general classes of loss functions. Based on these bounds, we introduce the notion of a delta-lossless transformation and give sufficient conditions for a given transformation to be universally delta-lossless. Applications to classification, nonparametric regression, portfolio strategies, information bottleneck, and deep learning, are also surveyed.
- 19 June 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (10) , 6765-6786
An Asymptotically Optimal Two-Part Fixed-Rate Coding Scheme for Networked Control With Unbounded Noise
It is known that under fixed-rate information constraints, adaptive quantizers can be used to stabilize an open-loop-unstable linear system on Rn driven by unbounded noise. These adaptive schemes can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as boundedness of the state second moment. Although structural results and information theoretic bounds of encoders have been studied, the performance of such adaptive fixed-rate quantizers beyond stabilization has not been addressed. In this paper, we propose a two-part adaptive (fixed-rate) coding scheme that achieves state second moment convergence to the classical optimum (i.e., for the fully observed setting) under mild moment conditions on the noise process. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part ensures that the state second moment converges to the classical optimum at high rates. These results are established using an intricate analysis which uses random-time state-dependent Lyapunov stochastic drift criteria as a core tool.
- 19 June 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (10) , 6765-6786
An Asymptotically Optimal Two-Part Fixed-Rate Coding Scheme for Networked Control With Unbounded Noise
It is known that under fixed-rate information constraints, adaptive quantizers can be used to stabilize an open-loop-unstable linear system on Rn driven by unbounded noise. These adaptive schemes can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as boundedness of the state second moment. Although structural results and information theoretic bounds of encoders have been studied, the performance of such adaptive fixed-rate quantizers beyond stabilization has not been addressed. In this paper, we propose a two-part adaptive (fixed-rate) coding scheme that achieves state second moment convergence to the classical optimum (i.e., for the fully observed setting) under mild moment conditions on the noise process. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part ensures that the state second moment converges to the classical optimum at high rates. These results are established using an intricate analysis which uses random-time state-dependent Lyapunov stochastic drift criteria as a core tool.
- Open Access
An Asymptotically Optimal Two-Part Fixed-Rate Coding Scheme for Networked Control with Unbounded Noise
It is known that under fixed-rate information constraints, adaptive quantizers can be used to stabilize an open-loop-unstable linear system on $\mathbb{R}^n$ driven by unbounded noise. These adaptive schemes can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as boundedness of the state second moment. Although structural results and information theoretic bounds of encoders have been studied, the performance of such adaptive fixed-rate quantizers beyond stabilization has not been addressed. In this paper, we propose a two-part adaptive (fixed-rate) coding scheme that achieves state second moment convergence to the classical optimum (i.e., for the fully observed setting) under mild moment conditions on the noise process. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part ensures that the state second moment converges to the classical optimum at high rates. These results are established using an intricate analysis which uses random-time state-dependent Lyapunov stochastic drift criteria as a core tool.Open AccessAn Asymptotically Optimal Two-Part Fixed-Rate Coding Scheme for Networked Control with Unbounded Noise
It is known that under fixed-rate information constraints, adaptive quantizers can be used to stabilize an open-loop-unstable linear system on $\mathbb{R}^n$ driven by unbounded noise. These adaptive schemes can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as boundedness of the state second moment. Although structural results and information theoretic bounds of encoders have been studied, the performance of such adaptive fixed-rate quantizers beyond stabilization has not been addressed. In this paper, we propose a two-part adaptive (fixed-rate) coding scheme that achieves state second moment convergence to the classical optimum (i.e., for the fully observed setting) under mild moment conditions on the noise process. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part ensures that the state second moment converges to the classical optimum at high rates. These results are established using an intricate analysis which uses random-time state-dependent Lyapunov stochastic drift criteria as a core tool.