Stochastic approximation is a foundation for many algorithms found in machine learning and optimization. It is in general slow to converge: the mean square error vanishes as $O(n^{-1})$. A deterministic counterpart known as quasi-stochastic approximation is a viable alternative in many applications, including gradient-free optimization and reinforcement learning. It was assumed in prior research that the optimal achievable convergence rate is $O(n^{-2})$. It is shown in this paper that through design it is possible to obtain far faster convergence, of order $O(n^{-4+\delta})$, with $\delta>0$ arbitrary. Two techniques are introduced for the first time to achieve this rate of convergence. The theory is also specialized within the context of gradient-free optimization, and tested on standard benchmarks. The main results are based on a combination of novel application of results from number theory and techniques adapted from stochastic approximation theory.

This paper concerns error bounds for recursive equations subject to Markovian disturbances. Motivating examples abound within the fields of Markov chain Monte Carlo (MCMC) and Reinforcement Learning (RL), and many of these algorithms can be interpreted as special cases of stochastic approximation (SA). It is argued that it is not possible in general to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic, such as the M/M/1 queue. This is motivation for the focus on mean square error bounds for parameter estimates. It is shown that mean square error achieves the optimal rate of $O(1/n)$, subject to conditions on the step-size sequence. Moreover, the exact constants in the rate are obtained, which is of great value in algorithm design.

Zap Q-learning is a recent class of reinforcement learning algorithms, motivated primarily as a means to accelerate convergence. Stability theory has been absent outside of two restrictive classes: the tabular setting, and optimal stopping. This paper introduces a new framework for analysis of a more general class of recursive algorithms known as stochastic approximation. Based on this general theory, it is shown that Zap Q-learning is consistent under a non-degeneracy assumption, even when the function approximation architecture is nonlinear. Zap Q-learning with neural network function approximation emerges as a special case, and is tested on examples from OpenAI Gym. Based on multiple experiments with a range of neural network sizes, it is found that the new algorithms converge quickly and are robust to choice of function approximation architecture.

This paper concerns computation of optimal policies in which the one-step reward function contains a cost term that models Kullback-Leibler divergence with respect to nominal dynamics. This technique was introduced by Todorov in 2007, where it was shown under general conditions that the solution to the average-reward optimality equations reduce to a simple eigenvector problem. Since then many authors have sought to apply this technique to control problems and models of bounded rationality in economics. A crucial assumption is that the input process is essentially unconstrained. For example, if the nominal dynamics include randomness from nature (e.g., the impact of wind on a moving vehicle), then the optimal control solution does not respect the exogenous nature of this disturbance. This paper introduces a technique to solve a more general class of action-constrained MDPs. The main idea is to solve an entire parameterized family of MDPs, in which the parameter is a scalar weighting the one-step reward function. The approach is new and practical even in the original unconstrained formulation.

The Zap Q-learning algorithm introduced in this paper is an improvement of Watkins' original algorithm and recent competitors in several respects. It is a matrix-gain algorithm designed so that its asymptotic variance is optimal. Moreover, an ODE analysis suggests that the transient behavior is a close match to a deterministic Newton-Raphson implementation. This is made possible by a two time-scale update equation for the matrix gain sequence. The analysis suggests that the approach will lead to stable and efficient computation even for non-ideal parameterized settings. Numerical experiments confirm the quick convergence, even in such non-ideal cases.

The small sample universal hypothesis testing problem is investigated in this paper, in which the number of samples$n$is smaller than the number of possible outcomes$m$. The goal of this paper is to find an appropriate criterion to analyze statistical tests in this setting. A suitable model for analysis is the high-dimensional model in which both$n$and$m$increase to infinity, and$n=o(m)$. A new performance criterion based on large deviations analysis is proposed and it generalizes the classical error exponent applicable for large sample problems (in which$m=O(n)$). This generalized error exponent criterion provides insights that are not available from asymptotic consistency or central limit theorem analysis. The following results are established for the uniform null distribution: 1) The best achievable probability of error$P_{e}$decays as$P_{e}=\exp \{-(n^{2}/m) J (1+o(1))\}$for some$J>0$. 2) A class of tests based on separable statistics, including the coincidence-based test, attains the optimal generalized error exponents. 3) Pearson's chi-square test has a zero generalized error exponent and thus its probability of error is asymptotically larger than the optimal test.

This paper considers the problem of feature selection for composite hypothesis testing: The goal is to select, from m candidate features, r relevant ones for distinguishing the null hypothesis from the composite alternative hypothesis; the training data are given as L sequences of observations, of which each is an n-sample sequence coming from one distribution in the alternative hypothesis. What is the fundamental limit for successful feature selection? Are there any algorithms that achieve this limit? We investigate this problem in a small-sample high-dimensional setting, with n = o(m), and obtain a tight pair of achievability and converse results: (i) There exists a function f(L, n, r,m) such that if f(L, n, r,m) ↓ 0, then no asymptotically consistent feature selection algorithm exists; (ii) We propose a feature selection algorithm that is asymptotically consistent whenever f(L, n, r,m) ↑ ∞.

We consider the small sample composite hypothesis testing problem, where the number of samples n is smaller than the size of the alphabet m. A suitable model for analysis is the high-dimensional model in which both n and m tend to infinity, and n = o(m). We propose a new performance criterion based on large deviation analysis, which generalizes the classical error exponent applicable for large sample problems (in which m = O(n)). The results are: (i) The best achievable probability of error Pe decays as -log(Pe) = (n2/m)(1 + o(1))J for some J >; 0, shown by upper and lower bounds. (ii) A coincidence-based test has non-zero generalized error exponent J, and is optimal in the generalized error exponent of missed detection. (iii) The widely-used Pearson's chi-square test has a zero generalized error exponent. (iv) The contributions (i)-(iii) are established under the assumption that the null hypothesis is uniform. For the non-uniform case, we propose a new test with nonzero generalized error exponent.

The task of the binary classification problem is to determine which of two distributions has generated a length-n test sequence. The two distributions are unknown; two training sequences of length N, one from each distribution, are observed. The distributions share an alphabet of size m, which is significantly larger than n and N. How does N,n,m affect the probability of classification error? We characterize the achievable error rate in a high-dimensional setting in which N,n,m all tend to infinity, under the assumption that probability of any symbol is O(m-1). The results are: 1) There exists an asymptotically consistent classifier if and only if m = o(min{N2, Nn}). This extends the previous consistency result in [1] to the case N ≠ n. 2) For the sparse sample case where max{n, N} = o(m), finer results are obtained: The best achievable probability of error decays as - log(Pe) = J min {N2, Nn}(1 +o(1))/m with J >; 0. 3) A weighted coincidence-based classifier has non-zero generalized error exponent J. 4) The ℓ2-norm based classifier has J = 0.

For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of Kullback-Leibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of distributions characterized by a finite-dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance for applications involving large alphabet distributions. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis.

The popular criteria of optimality for quickest change detection procedures are the Lorden criterion, the Pollak criterion, and the Bayesian criterion. In this paper, a robust version of these quickest change detection problems is considered when the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. For uncertainty classes that satisfy a specific condition, it is shown that one can identify least favorable distributions (LFDs) from the uncertainty classes, such that the detection rule designed for the LFDs is optimal for the robust problem in a minimax sense. The condition is similar to that required for the identification of LFDs for the robust hypothesis testing problem originally studied by Huber. An upper bound on the delay incurred by the robust test is also obtained in the asymptotic setting under the Lorden criterion of optimality. This bound quantifies the delay penalty incurred to guarantee robustness. When the LFDs can be identified, the proposed test is easier to implement than the CUSUM test based on the Generalized Likelihood Ratio (GLR) statistic which is a popular approach for such robust change detection problems. The proposed test is also shown to give better performance than the GLR test in simulations for some parameter values.

This paper concerns the construction of tests for universal hypothesis testing problems, in which the alternate hypothesis is poorly modeled and the observation space is large. The mismatched universal test is a feature-based technique for this purpose. In prior work it is shown that its finite-observation performance can be much better than the (optimal) Hoeffding test, and good performance depends crucially on the choice of features. The contributions of this paper include: (i) We obtain bounds on the number of ε-distinguishable distributions in an exponential family. (ii) This motivates a new framework for feature extraction, cast as a rank-constrained optimization problem. (iii) We obtain a gradient-based algorithm to solve the rank-constrained optimization problem and prove its local convergence.

Goodness-of-fit tests are statistical procedures used to test the hypothesis H0that a set of observations were drawn according to some given probability distribution. Decision thresholds used in goodness-of-fit tests are typically set for guaranteeing a target false-alarm probability. In many popular testing procedures results on the weak convergence of the test statistics are used for setting approximate thresholds when exact computation is infeasible. In this work, we study robust procedures for goodness-of-fit where accurate models are not available for the distribution of the observations under hypothesis H0. We develop procedures for setting thresholds in two specific examples - a robust version of the Kolmogorov-Smirnov test for continuous alphabets and a robust version of the Hoeffding test for finite alphabets.

The focus of this work is on the analysis of transmit beamforming schemes with a low-rate feedback link in wireless sensor/relay networks, where nodes in the network need to implement beamforming in a distributed manner. Specifically, the problem of distributed phase alignment is considered, where neither the transmitters nor the receiver has perfect channel state information, but there is a low-rate feedback link from the receiver to the transmitters. In this setting, a framework is proposed for systematically analyzing the performance of distributed beamforming schemes. To illustrate the advantage of this framework, a simple adaptive distributed beamforming scheme that was recently proposed by Mudambai et al. is studied. Two important properties of the received signal magnitude function are derived. Using these properties and the systematic framework, it is shown that the adaptive distributed beamforming scheme converges both in probability and in mean. Furthermore, it is established that the time required for the adaptive scheme to converge in mean scales linearly with respect to the number of sensor/relay nodes.

Information theory--a field at the intersection of applied mathematics and electrical engineering--was primarily developed for the purpose of addressing problems arising in data storage and data transmission over (noisy) communication media. Consequently, information theory provides the formal basis for much of today’s storage and communication infrastructure.

We study the problem of robust quickest change detection where the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. Both Bayesian and minimax versions of the quickest change detection problem are considered. When the uncertainty classes satisfy some specific conditions, we identify least favorable distributions (LFD's) from the uncertainty classes, and show that the detection rule designed for the LFD's is optimal in a minimax sense. The condition is similar to that required for the existence of LFD's for the robust hypothesis testing problem studied by Huber.

The support vector machine (SVM) has emerged as one of the most popular approaches to classification and supervised learning. It is a flexible approach for solving the problems posed in these areas, but the approach is not easily adapted to noisy data in which absolute discrimination is not possible. We address this issue in this paper by returning to the statistical setting. The main contribution is the introduction of a statistical support vector machine (SSVM) that captures all of the desirable features of the SVM, along with desirable statistical features of the classical likelihood ratio test. In particular, we establish the following: (i) The SSVM can be designed so that it forms a continuous function of the data, yet also approximates the potentially discontinuous log likelihood ratio test. (ii) Extension to universal detection is developed, in which only one hypothesis is labeled (a semi-supervised learning problem). (iii) The SSVM generalizes the robust hypothesis testing problem based on a moment class. Motivation for the approach and analysis are each based on ideas from information theory. A detailed performance analysis is provided in the special case of i.i.d. observations. This research was partially supported by NSF under grant CCF 07-29031, by UTRC, Motorola, and by the DARPA ITMANET program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF, UTRC, Motorola, or DARPA.

We address the problem of computing the optimal Q-function in Markov decision problems with infinite state-space. We analyze the convergence properties of several variations of Q-learning when combined with function approximation, extending the analysis of TD-learning in (Tsitsiklis & Van Roy, 1996a) to stochastic control settings. We identify conditions under which such approximate methods converge with probability 1. We conclude with a brief discussion on the general applicability of our results and compare them with several related works.

This paper concerns error exponents and the structure of input distributions maximizing the random coding exponent for a stochastic channel model. The following conclusions are obtained under general assumptions on the channel statistics. 1) The optimal distribution has a finite number of mass points, or in the case of a complex channel, the amplitude has finite support. 2) A new class of algorithms is introduced based on the cutting-plane method to construct an optimal input distribution. The algorithm constructs a sequence of discrete distributions, along with upper and lower bounds on the random coding exponent at each iteration. 3) In some numerical example considered, the resulting code significantly outperforms traditional signal constellation schemes such as quadrature amplitude modulation and phase-shift keying for all rates below the capacity.

This paper presents models, algorithms and analysis for measurement-based admission control in network applications in which there is high uncertainty concerning source statistics. In the process it extends and unifies several recent approaches to admission control. A new class of algorithms is introduced based on results concerning Markov's canonical distributions. In addition, a new model is developed for the evolution of the number of flows in the admission control system. Performance evaluation is done through both analysis and simulation. Results show that the proposed algorithms minimize buffer-overflow probability among the class of all moment-consistent algorithms

We develop explicit, general bounds for the probability that the normalized partial sums of a function of a Markov chain on a general alphabet would exceed the steady-state mean of that function by a given amount. Our bounds combine simple information-theoretic ideas together with techniques from optimization and some fairly elementary tools from analysis. In one direction, we obtain a general bound for the important class of Doeblin chains; this bound is optimal, in the sense that in the special case of independent and identically distributed random variables it essentially reduces to the classical Hoeffding bound. In another direction, motivated by important problems in simulation, we develop a series of bounds in a form which is particularly suited to these problems, and which apply to the more general class of "geometrically ergodic" Markov chains

This paper concerns the structure of capacity-achieving input distributions for stochastic channel models, and a renewed look at their computational aspects. The following conclusions are obtained under general assumptions on the channel statistics. i) The capacity-achieving input distribution is binary for low signal-to-noise ratio (SNR). The proof is obtained on comparing the optimization equations that determine channel capacity with a linear program over the space of probability measures. ii) Simple discrete approximations can nearly reach capacity even in cases where the optimal distribution is known to be absolutely continuous with respect to Lebesgue measure. iii) A new class of algorithms is introduced based on the cutting-plane method to iteratively construct discrete distributions, along with upper and lower bounds on channel capacity. It is shown that the bounds converge to the true channel capacity, and that the distributions converge weakly to a capacity-achieving distribution.

We consider the optimization of the random coding error exponent of a class of memoryless channels where the input is subject to a peak and average-power constraints. The capacity-achieving input is shown to be typically discrete and an algorithm is developed for computing these optimal distributions. As one application, we propose a new signal constellation design which out-performs QAM and PSK for certain channels.

A robust hypothesis testing framework is introduced in which candidate hypotheses are characterized by moment classes. It is shown that there exists a test sequence that is asymptotically optimal in the min-max sense, and that it is expressed as a comparison of a log-linear combination of the constraint functions to a predetermined threshold.

Many problems in information theory can be distilled to an optimization problem over a space of probability distributions. The most important examples are in communication theory, where it is necessary to maximize mutual information in order to compute channel capacity, and the classical hypothesis testing problem in which an optimal test is based on the maximization of divergence. Two general classes of optimization problems are considered in this paper: convex and linear programs, where the constraint set is defined by a finite number of moment constraints.

We study different notions of capacity for time-slotted ALOHA systems. In these systems, multiple users synchronously send packets in a bursty manner over a common additive white Gaussian noise (AWGN) channel. The users do not coordinate their transmissions, which may collide at the receiver. For such a system, we define both single-slot capacity and multiple-slot capacity. We then construct a coding and decoding scheme for single-slot capacity that achieves any rate within this capacity region. This coding and decoding scheme for a single time slot combines aspects of multiple access rate splitting and of broadcast codes for degraded AWGN channels. This design allows some bits to be reliably received even when collisions occur and more bits to be reliably received in the absence of collisions. The exact number of bits reliably received under both of these scenarios is part of the code design process, which we optimize to maximize the expected rate in each slot. Next, we examine the behavior of the system asymptotically over multiple slots. We show that there exist coding and decoding strategies such that regardless of the burstiness of the traffic, the system is stable as long as the average rate of the users is within the multiple access capacity region of the channel. In other words, we show that bursty traffic does not decrease the Cover-Wyner capacity region of the multiple access channel. A vast family of codes, which includes the type of codes we introduce for the single-slot transmission, achieve the capacity region, in a sense we define, for multiple-slot transmissions. These codes are stabilizing, using only local information at each of the individual queues. The use of information regarding other queues or the use of scheduling does not improve the multiple-slot capacity region.

We consider decentralized congestion control algorithms for low-loss operation of the Internet using the ECN bit. There has been much analysis of such algorithms, but with a few exceptions, these typically ignore the effect of feedback delays in the network on stability. We study a single node with many flows passing through it, with each flow (possibly) having a different round-trip delay. Using a fluid model for the flows, we show that even with delays, the total data rate at the router is bounded; and this bound shows that the (peak) total rate grows linearly with increase in system size, i.e., the fraction of overprovisioning required is constant with respect to N, the number of flows in the system. Further, for typical user data rates and delays seen in the Internet today, the bound is very close to the data rate at the router without delays. Earlier results by Johari and Tan have given conditions for a linearized model of the network to be (locally) stable. We show that even when the linearized model is not stable, the nonlinear model is upper bounded, i.e., the total rate at the bottleneck link is upper bounded, and the upper bound is close to the equilibrium rate for TCP.

The estimation of the statistics of buffer overflows in networks of queues by means of simulation is inherently costly, simply because of the rarity of these events. An alternative analytic approach is presented, with very low computational cost, for calculating the recurrence time of buffer overflows for Jackson networks in which the recurrence times of buffer overflows in a network are expressed in terms of the recurrence times for overflows of individual buffers, isolated from the network. This result is applied to the buffer allocation problem for queueing networks, providing extensions and further justification for a previously derived heuristic approach to this problem.>