Browsing by Author "Morris, Joel M."
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Improvements to Sanov and PAC Sublevel-set Bounds for Discrete Random Variables(IEEE, 2021-04-19) Tope, Michael A.; Morris, Joel M.We derive an improvement for probably approximately correct (PAC) sublevel-set bounds for the multinomial distributed discrete random variables. Previous bounds (including Sanov's Theorem) show that the Kullback Leibler (KL) divergence between the empirical probability mass function (pmf) and the true PMF converges with rate O(log(N)/N), where N is the number of independent and identically distributed (i.i.d.) samples used to compute the empirical pmf. We interpret the KL divergence as bounding the probability that a multinomial distributed random variable (RV) deviates into a halfspace and construct improved uniform PAC sublevel-set bounds that converge with rates O (log (log (N)) / N). These results bound the worst case performance for a number of machine learning algorithms. Finally, the ‘halfspace bound’ methodology suggests further improvements are possible for non-uniform bounds. In this paper, we derive an improvement (on the convergence rate) for various Probably Approximately Correct (PAC) bounds (including Sanov's Theorem) for multinomially distributed discrete random variables.Item Near-optimal Sampling to Optimize Communication Over Discrete Memoryless Channels(IEEE, 2023-04-10) Tope, Michael A.; Morris, Joel M.This paper develops a strategy to minimize the number of channel probes required to recover the components of the channel law and maximize the reliable communication rate across a discrete memoryless channel (DMC). Based on the aggregate set of observed input-output pairs over time, the algorithm sequentially probes subsets of channel input values. We leverage a non-asymptotic probably approximately correct (PAC) bounds to establish the rate of convergence towards channel capacity as O(√log(log(N)) log(N)/N), where N is the number of channel probes. For a discrete channel with |X| input values and |Y| output values, the sampling strategy may reduce the sample complexity by a factor of nearly min (|X|/|Y|,1) relative to previous methods.Item On the Limits of Learning a Discrete Memoryless Communication Channel(IEEE, 2023-01-24) Tope, Michael A.; Morris, Joel M.This paper explores bounds on the minimum number of channel probes required to learn sufficient information to establish reliable communication at a given communication rate (below channel capacity) for a discrete memoryless channel. Given a set of discrete channel input-output sample pairs (where for each discrete input value, the associated aggregate set of discrete output values observations is multinomially distributed), we leverage a non-asymptotic probably approximately correct (PAC) bound on the mutual information (channel capacity) between the label (discrete) random variable (RV) and the observation RV to establish a convergence rate for the worst case channel. Previous bounds (such as those based on Sanov’s Theorem) provide high probability (i.e. PAC) bounds on the true mutual information that converge with rate O(log(N)/ √ N), where N is the number of independent and identically distributed (i.i.d.) samples used to compute the empirical probability mass functions. Using an improved PAC sublevel-set bound, we sharpen the rate of convergence to O( p log(log(N)) log(N)/N).Item A PAC-bound on the Channel Capacity of an Observed Discrete Memoryless Channel(IEEE, 2021-04-19) Tope, Michael A.; Morris, Joel M.This paper presents a method to compute the channel capacity of an observed (partially known) discrete memoryless channel (DMC) using a probably approximately correct (PAC) bound. Given N independently and identically distributed (i.i.d.) input-output sample pairs, we define a compound DMC with convex sublevel-sets to constrain the channel output uncertainty with high probability. Then we numerically solve an ‘K-way’ convex optimization to determine an achievable information rate RL(N) across the channel that holds with a specified high probability. Our approach provides the non-asymptotic ‘worst-case’ convergence RL(N) to channel capacity C at the rate of O(√log(log(N))/N) .