The fidelity bandits problem is a variant of the $K$-armed bandit problem in which the reward of each arm is augmented by a fidelity reward that provides the player with an additional payoff depending on how ‘loyal’ the player has been to that arm in the past. We propose two models for fidelity. In the loyalty-points model the amount of extra reward depends on the number of times the arm has previously been played. In the subscription model the additional reward depends on the current number of consecutive draws of the arm. We consider both stochastic and adversarial problems. Since single-arm strategies are not always optimal in stochastic problems, the notion of regret in the adversarial setting needs careful adjustment. We introduce three possible notions of regret and investigate which can be bounded sublinearly. We study in detail the special cases of increasing, decreasing and coupon (where the player gets an additional reward after every $m$ plays of an arm) fidelity rewards. For the models which do not necessarily enjoy sublinear regret, we provide a worst case lower bound. For those models which exhibit sublinear regret, we provide algorithms and bound their regret.

We propose strongly consistent estimators of the$\ell _{1}$norm of the sequence of$\alpha $-mixing (respectively$\beta $-mixing) coefficients of a stationary ergodic process. We further provide strongly consistent estimators of individual$\alpha $-mixing (respectively$\beta $-mixing) coefficients for a subclass of stationary$\alpha $-mixing (respectively$\beta $-mixing) processes with summable sequences of mixing coefficients. The estimators are in turn used to develop strongly consistent goodness-of-fit hypothesis tests. In particular, we develop hypothesis tests to determine whether, under the same summability assumption, the$\alpha $-mixing (respectively$\beta $-mixing) coefficients of a process are upper bounded by a given rate function. Moreover, given a sample generated by a (not necessarily mixing) stationary ergodic process, we provide a consistent test to discern the null hypothesis that the$\ell _{1}$norm of the sequence$\boldsymbol {\alpha }$of$\alpha $-mixing coefficients of the process is bounded by a given threshold$\gamma \in [0,\infty$) from the alternative hypothesis that$\left \lVert{ \boldsymbol {\alpha }}\right \rVert > \gamma $. An analogous goodness-of-fit test is proposed for the$\ell _{1}$norm of the sequence of$\beta $-mixing coefficients of a stationary ergodic process. Moreover, the procedure gives rise to an asymptotically consistent test for independence.

Since the celebrated works of Russo and Zou (2016, 2019) and Xu and Raginsky (2017), it has been well known that the generalization error of supervised learning algorithms can be bounded in terms of the mutual information between their input and the output, given that the loss of any fixed hypothesis has a subgaussian tail. In this work, we generalize this result beyond the standard choice of Shannon’s mutual information to measure the dependence between the input and the output. Our main result shows that it is indeed possible to replace the mutual information by any strongly convex function of the joint input-output distribution, with the subgaussianity condition on the losses replaced by a bound on an appropriately chosen norm capturing the geometry of the dependence measure. This allows us to derive a range of generalization bounds that are either entirely new or strengthen previously known ones. Examples include bounds stated in terms of p-norm divergences and the Wasserstein-2 distance, which are respectively applicable for heavy-tailed loss distributions and highly smooth loss functions. Our analysis is entirely based on elementary tools from convex analysis by tracking the growth of a potential function associated with the dependence measure and the loss function.

We study the problem of recovering the structure underlying large Gaussian graphical models or, more generally, partial correlation graphs. In high-dimensional problems it is often too costly to store the entire sample covariance matrix. We propose a new input model in which one can query single entries of the covariance matrix. We prove that it is possible to recover the support of the inverse covariance matrix with low query and computational complexity. Our algorithms work in a regime when this support is represented by tree-like graphs and, more generally, for graphs of small treewidth. Our results demonstrate that for large classes of graphs, the structure of the corresponding partial correlation graphs can be determined much faster than even computing the empirical covariance matrix.

We consider an online influence maximization problem in which a decision maker selects a node among a large number of possibilities and places a piece of information at the node. The information then spreads in the network on a random set of edges. The goal of the decision maker is to reach as many nodes as possible, with the added complication that feedback is only available about the degree of the selected node. Our main result shows that such local observations can be sufficient for maximizing global influence in two broadly studied families of random graph models: stochastic block models and Chung–Lu models. With this insight, we propose a bandit algorithm that aims at maximizing local (and thus global) influence, and provide its theoretical analysis in both the subcritical and supercritical regimes of both considered models. Notably, our performance guarantees show no explicit dependence on the total number of nodes in the network, making our approach well-suited for large-scale applications.

We present a new strategy for gap estimation in randomized algorithms for multiarmed bandits and combine it with the EXP3++ algorithm of Seldin and Slivkins (2014). In the stochastic regime the strategy reduces dependence of regret on a time horizon from $(\ln t)^3$ to $(\ln t)^2$ and eliminates an additive factor of order $∆e^1/∆^2$, where $∆$ is the minimal gap of a problem instance. In the adversarial regime regret guarantee remains unchanged.

We introduce a notion of algorithmic stability of learning algorithms—that we term hypothesis stability—that captures stability of the hypothesis output by the learning algorithm in the normed space of functions from which hypotheses are selected. The main result of the paper bounds the generalization error of any learning algorithm in terms of its hypothesis stability. The bounds are based on martingale inequalities in the Banach space to which the hypotheses belong. We apply the general bounds to bound the performance of some learning algorithms based on empirical risk minimization and stochastic gradient descent.

Boltzmann exploration is a classic strategy for sequential decision-making under uncertainty, and is one of the most standard tools in Reinforcement Learning (RL). Despite its widespread use, there is virtually no theoretical understanding about the limitations or the actual benefits of this exploration scheme. Does it drive exploration in a meaningful way? Is it prone to misidentifying the optimal actions or spending too much time exploring the suboptimal ones? What is the right tuning for the learning rate? In this paper, we address several of these questions for the classic setup of stochastic multi-armed bandits. One of our main results is showing that the Boltzmann exploration strategy with any monotone learning-rate sequence will induce suboptimal behavior. As a remedy, we offer a simple non-monotone schedule that guarantees near-optimal performance, albeit only when given prior access to key problem parameters that are typically not available in practical situations (like the time horizon $T$ and the suboptimality gap $\Delta$). More importantly, we propose a novel variant that uses different learning rates for different arms, and achieves a distribution-dependent regret bound of order $\frac{K\log^2 T}{\Delta}$ and a distribution-independent bound of order $\sqrt{KT}\log K$ without requiring such prior knowledge. To demonstrate the flexibility of our technique, we also propose a variant that guarantees the same performance bounds even if the rewards are heavy-tailed.

We study online combinatorial optimization problems that a learner is interested in minimizing its cumulative regret in the presence of switching costs. To solve such problems, we propose a version of the follow-the-perturbed-leader algorithm in which the cumulative losses are perturbed by independent symmetric random walks. In the general setting, our forecaster is shown to enjoy near-optimal guarantees on both quantities of interest, making it the best known efficient algorithm for the studied problem. In the special case of prediction with expert advice, we show that the forecaster achieves an expected regret of the optimal order O(n log N)1/2), where n is the time horizon and N is the number of experts, while guaranteeing that the predictions are switched at most O(n log N)1/2) times, in expectation.

We consider the problem of vector quantization of i.i.d. samples drawn from a density p on \mathbbR^d. It is desirable that the representatives selected by the quantization algorithm have the same distribution p as the original sample points. However, quantization algorithms based on Euclidean distance, such as k-means, do not have this property. We provide a solution to this problem that takes the unweighted k-nearest neighbor graph on the sample as input. In particular, it does not need to have access to the data points themselves. Our solution generates quantization centers that are “evenly spaced". We exploit this property to downsample geometric graphs and show that our method produces sparse downsampled graphs. Our algorithm is easy to implement, and we provide theoretical guarantees on the performance of the proposed algorithm.

The problem of detecting correlations from samples of a high-dimensional Gaussian vector has recently received a lot of attention. In most existing work, detection procedures are provided with a full sample. However, following common wisdom in experimental design, the experimenter may have the capacity to make targeted measurements in an on-line and adaptive manner. In this paper, we investigate such adaptive sensing procedures for detecting positive correlations. It is shown that, using the same number of measurements, adaptive procedures are able to detect significantly weaker correlations than their nonadaptive counterparts. We also establish minimax lower bounds that show the limitations of any procedure.

We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(\sqrtn \log N) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(\sqrtn \log N) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order.

The stochastic multiarmed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper, we examine the bandit problem under the weaker assumption that the distributions have moments of order$1 + \varepsilon $, for some$ \varepsilon \in (0,1]$. Surprisingly, moments of order 2 (i.e., finite variance) are sufficient to obtain regret bounds of the same order as under sub-Gaussian reward distributions. In order to achieve such regret, we define sampling strategies based on refined estimators of the mean such as the truncated empirical mean, Catoni's$M$-estimator, and the median-of-means estimator. We also derive matching lower bounds that also show that the best achievable regret deteriorates when$ \varepsilon < 1$.

In the framework of prediction with expert advice we consider prediction algorithms that compete against a class of switching strategies that can segment a given sequence into several blocks and follow the advice of a different “base” expert in each block. The performance is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight. Our goal is to construct low-complexity prediction algorithms for the case where the set of base experts is large. In particular, starting with an arbitrary prediction algorithm A designed for the base expert class, we derive a family of efficient tracking algorithms that can be implemented with time and space complexity only O(ηγIn n) times larger than that of A, where n is the time horizon and γ ≥ 0 is a parameter of the algorithm. With A properly chosen, our algorithm achieves a regret bound of optimal order for γ >; 0, and only O(ln n) times larger than the optimal order for γ = 0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters, our method achieves the optimal O(ln n) regret rate with time complexity O(n1+γIn n) for any γ ϵ (0,1).

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different “base” expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper, we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular, we provide a method that can transform any prediction algorithmAthat is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency ofAin the sense that it can be implemented with time and space complexity onlyO(nγlnn) times larger than that ofA, wherenis the time horizon and γ ≥ 0 is a parameter of the algorithm. WithAproperly chosen, our algorithm achieves a regret bound of optimal order for γ >; 0, and onlyO(lnn) times larger than the optimal order for γ = 0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimalO(lnn) regret rate with time complexityO(n1+γlnn) for any γ ∈ (0,1).

Based on randomly drawn vectors in a separable Hilbert space, one may construct a k-means clustering scheme by minimizing an empirical squared error. We investigate the risk of such a clustering scheme, defined as the expected squared distance of a random vector X from the set of cluster centers. Our main result states that, for an almost surely bounded , the expected excess clustering risk is O(¿1/n) . Since clustering in high (or even infinite)-dimensional spaces may lead to severe computational problems, we examine the properties of a dimension reduction strategy for clustering based on Johnson-Lindenstrauss-type random projections. Our results reflect a tradeoff between accuracy and computational complexity when one uses k-means clustering after random projection of the data to a low-dimensional space. We argue that random projections work better than other simplistic dimension reduction schemes.

An algorithm is presented for online prediction that allows to track the best expert efficiently even when the number of experts is exponentially large, provided that the set of experts has a certain additive structure. As an example, we work out the case where each expert is represented by a path in a directed graph and the loss of each expert is the sum of the weights over the edges in the path. These results are then used to construct universal limited-delay schemes for lossy coding of individual sequences. In particular, we consider the problem of tracking the best scalar quantizer that is adaptively matched to the source sequence with piecewise different behavior. A randomized algorithm is presented which can perform, on any source sequence, asymptotically as well as the best scalar quantization algorithm that is matched to the sequence and is allowed to change the employed quantizer for a given number of times. The complexity of the algorithm is quadratic in the sequence length, but at the price of some deterioration in performance, the complexity can be made linear. Analogous results are obtained for sequential multiresolution and multiple description scalar quantization of individual sequences.

We consider repeated games in which the player, instead of observing the action chosen by the opponent in each game round, receives a feedback generated by the combined choice of the two players. We study Hannan consistent players for these games, that is, randomized playing strategies whose per-round regret vanishes with probability one as the number of game rounds goes to infinity. We prove a general lower bound for the convergence rate of the regret, and exhibit a specific strategy that attains this rate for any game for which a Hannan consistent player exists.

The on-line shortest path problem is considered in the bandit setting. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary way, a decision maker has to pick in each round a path between two distinguished vertices, such that the weight of this path, given as the sum of the weights of its composing edges, be as small as possible. The decision maker has only limited information on how the weights of the edges are generated. In particular, the edge weights in the current round are unknown to the decision maker when it chooses a path, and after choosing a path, it learns only the weights of those edges that belong to the chosen path. An algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is proportional to 1/√n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with linear complexity in the number of rounds n and in the number of edges. This result improves earlier algorithms which have performance bounds that either depend exponentially on the number of edges or converge to zero at a slower rate than O(1/√n).

In this paper we consider zero delay lossy coding schemes for individual sequences, and address the problem of tracking the best scalar quantizer which is adaptively matched to the sequence. The problem is an individual-sequence version of the problem of scalar quantization of piecewise stationary sources. A randomized algorithm is presented which can perform, on any source sequence, asymptotically as well as the best scalar quantization algorithm matched to the sequence which is allowed to change the employed quantizer from time to time. The complexity of the algorithm is quadratic in the sequence length. At the price of a slight deterioration of performance, the complexity can be made linear in the sequence length

We investigate label efficient prediction, a variant, proposed by Helmbold and Panizza, of the problem of prediction with expert advice. In this variant, the forecaster, after guessing the next element of the sequence to be predicted, does not observe its true value unless he asks for it, which he cannot do too often. We determine matching upper and lower bounds for the best possible excess prediction error, with respect to the best possible constant predictor, when the number of allowed queries is fixed. We also prove that Hannan consistency, a fundamental property in game-theoretic prediction models, can be achieved by a forecaster issuing a number of queries growing to infinity at a rate just slightly faster than logarithmic in the number of prediction rounds.

Zero-delay sequential lossy source coding schemes are considered for both individual sequences and random sources. Performance is measured by the distortion redundancy, defined as the difference between the normalized cumulative distortion of the scheme and that of the best scalar quantizer matched to the entire sequence to be encoded. Weiss-man and Merhav [2001] constructed a randomized scheme which, for any bounded individual sequence of length n, achieves a distortion redundancy O(n/sup -1/3/ logn). However, this scheme has prohibitive complexity. Here we present an algorithm with encoding complexity O(n/sup 4/3/ logn) and distortion redundancy O(n/sup -1/3/ logn). The complexity can be made linear in the sequence length n at the price of increasing the distortion redundancy to O(n/sup -1/4/logn/sup 1/2/). We also show that for the class of bounded memoryless sources, the minimax expected distortion redundancy in zero-delay lossy coding is upper and lower bounded by (constant multiples of) n/sup -1/2/.

We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of k nominal densities is the true density closest to, under the total variation (L/sub 1/) distance. We obtain a density-free uniform exponential bound for the probability of false detection.

We consider adaptive sequential lossy coding of bounded individual sequences when the performance is measured by the sequentially accumulated mean-squared distortion. The encoder and the decoder are connected via a noiseless channel of capacity R and both are assumed to have zero delay. No probabilistic assumptions are made on how the sequence to be encoded is generated. For any bounded sequence of length n, the distortion redundancy is defined as the normalized cumulative distortion of the sequential scheme minus the normalized cumulative distortion of the best scalar quantizer of rate R which is matched to this particular sequence. We demonstrate the existence of a zero-delay sequential scheme which uses common randomization in the encoder and the decoder such that the normalized maximum distortion redundancy converges to zero at a rate n/sup -1/5/ log n as the length of the encoded sequence n increases without bound.

We study sequential strategies for assigning probabilities to the elements that may appear next in a sequence of data. The goal is to minimize the regret under log loss over the worst possible sequence. That is, to minimize the worst-case drop in the log-likelihood of the final sequence when measured under the assigned probabilities, as opposed to being measured under the best assignment in a given class of strategies (or experts). Using tools from empirical process theory, we prove a general upper bound on the best possible (minimax) regret that depends on the metric properties of the class of experts. This extends previous results by Opper and Haussler. In the special case of parametric experts, we obtain nonasymptotical versions of results proven by Rissanen and others under much stronger conditions on the expert class. Finally, we point out a suboptimal behavior of the popular Bayesian weighted average algorithm.

We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from previous developments of the theory of the prediction of individual sequences. We show that if the sequence is a realization of a stationary and ergodic random process then the average number of mistakes converges, almost surely, to that of the optimum, given by the Bayes predictor. The desirable finite-sample properties of the predictor are illustrated by its performance for Markov processes. In such cases the predictor exhibits near-optimal behavior even without knowing the order of the Markov process. Prediction with side information is also considered.

Article Free Access Share on On sequential prediction of individual sequences relative to a set of experts Authors: Nicolò Cesa-Bianchi Department of Information Sciences, University of Milan, Via Comelico 39, 20135 Milano, Italy Department of Information Sciences, University of Milan, Via Comelico 39, 20135 Milano, ItalyView Profile , Gábor Lugosi Department of Economics, Pompeu Fabra University, Ramon Trias Fargas 25-27, 08005 Barcelona, Spain Department of Economics, Pompeu Fabra University, Ramon Trias Fargas 25-27, 08005 Barcelona, SpainView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 1–11https://doi.org/10.1145/279943.279946Published:24 July 1998Publication History 2citation279DownloadsMetricsTotal Citations2Total Downloads279Last 12 Months48Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean-squared distortion of a vector quantizer designed from n independent and identically distributed (i.i.d.) data points using any design algorithm is at least /spl Omega/(n/sup -1/2/) away from the optimal distortion for some distribution on a bounded subset of /spl Rscr//sup d/. Together with existing upper bounds this result shows that the minimax distortion redundancy for empirical quantizer design, as a function of the size of the training data, is asymptotically on the order of n/sup -1/2/. We also derive a new upper bound for the performance of the empirically optimal quantizer.

Classical and recent results in statistical pattern recognition and learning theory are reviewed in a two-class pattern classification setting. This basic model best illustrates intuition and analysis techniques while still containing the essential features and serving as a prototype for many applications. Topics discussed include nearest neighbor, kernel, and histogram methods, Vapnik-Chervonenkis theory, and neural networks. The presentation and the large (though nonexhaustive) list of references is geared to provide a useful overview of this field for both specialists and nonspecialists.

The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean independent and identically distributed (i.i.d.) training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided.

Minimax lower bounds for concept learning state, for example, that for each sample size $n$ and learning rule $g_n$, there exists a distribution of the observation $X$ and a concept $C$ to be learnt such that the expected error of $g_n$ is at least a constant times $V/n$, where $V$ is the VC dimension of the concept class. However, these bounds do not tell anything about the rate of decrease of the error for a {\sl fixed} distribution--concept pair.\\ In this paper we investigate minimax lower bounds in such a--stronger--sense. We show that for several natural $k$--parameter concept classes, including the class of linear halfspaces, the class of balls, the class of polyhedra with a certain number of faces, and a class of neural networks, for any {\sl sequence} of learning rules $\{g_n\}$, there exists a fixed distribution of $X$ and a fixed concept $C$ such that the expected error is larger than a constant times $k/n$ for {\sl infinitely many n}. We also obtain such strong minimax lower bounds for the tail distribution of the probability of error, which extend the corresponding minimax lower bounds.

Article A data-dependent skeleton estimate for learning Share on Authors: Gábor Lugosi Department of Mathematics and Computer Science, Faculty of Electrical Engineering, Technical University of Budapest, 1521 Stoczek u. 2, Budapest, Hungary Department of Mathematics and Computer Science, Faculty of Electrical Engineering, Technical University of Budapest, 1521 Stoczek u. 2, Budapest, HungaryView Profile , Márta Pintér Department of Mathematics and Computer Science, Faculty of Electrical Engineering, Technical University of Budapest, 1521 Stoczek u. 2, Budapest, Hungary Department of Mathematics and Computer Science, Faculty of Electrical Engineering, Technical University of Budapest, 1521 Stoczek u. 2, Budapest, HungaryView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 51–56https://doi.org/10.1145/238061.238068Online:01 January 1996Publication History 7citation158DownloadsMetricsTotal Citations7Total Downloads158Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean i.i.d. training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided.

In pattern recognition or, as it has also been called, concept learning, the value of a { 0,1}-valued random variable Y is to be predicted based upon observing an R/sup d/-valued random variable X. We apply the method of complexity regularization to learn concepts from large concept classes. The method is shown to automatically find a good balance between the approximation error and the estimation error. In particular, the error probability of the obtained classifier is shown to decrease as O(/spl radic/(logn/n)) to the achievable optimum, for large nonparametric classes of distributions, as the sample size n grows. We also show that if the Bayes error probability is zero and the Bayes rule is in a known family of decision rules, the error probability is O(logn/n) for many large families, possibly with infinite VC dimension.

Studies convergence properties of radial basis function (RBF) networks for a large class of basis functions, and reviews the methods and results related to this topic. The authors obtain the network parameters through empirical risk minimization. The authors show the optimal nets to be consistent in the problem of nonlinear function approximation and in nonparametric classification. For the classification problem the authors consider two approaches: the selection of the RBF classifier via nonlinear function estimation and the direct method of minimizing the empirical error probability. The tools used in the analysis include distribution-free nonasymptotic probability inequalities and covering numbers for classes of functions.

A fixed-rate universal lossy coding scheme is introduced for independent and identically distributed (i.i.d.) sources. It is shown for finite alphabet sources and arbitrary single letter distortion measures that as the sample size n grows the expected distortion obtained using this universal scheme converges to Shannon's distortion rate function D(R) at a rate O(log n/n). The scheme can be extended to universal quantization of real i.i.d sources subject to a squared error criterion. It is shown in this case that the per-letter distortion converges to D(R) at a rate O(/spl radic/(log n/n)) both in expectation and almost surely for any real-valued bounded i.i.d. source.>

A general notion of universal consistency of nonparametric estimators is introduced that applies to regression estimation, conditional median estimation, curve fitting, pattern recognition, and learning concepts. General methods for proving consistency of estimators based on minimizing the empirical error are shown. In particular, distribution-free almost sure consistency of neural network estimates and generalized linear estimators is established.>

In the paper convergence properties of radial basis function (RBF) networks are studied for a large class of basis functions. The universal approximation property of the nets is shown. Parameters of RBF nets are learned through empirical risk minimization. The optimal nets are shown to be consistent in nonparametric classification. The tools used in the analysis include Vapnik-Chervonenkis (VC) dimension and the covering numbers.

Rate of convergence results are established for vector quantization. Convergence rates are given for an increasing vector dimension and/or an increasing training set size. In particular, the following results are shown for memoryless real-valued sources with bounded support at transmission rate R. (1) If a vector quantizer with fixed dimension k is designed to minimize the empirical mean-square error (MSE) with respect to m training vectors, then its MSE for the true source converges in expectation and almost surely to the minimum possible MSE as O(/spl radic/(log m/m)). (2) The MSE of an optimal k-dimensional vector quantizer for the true source converges, as the dimension grows, to the distortion-rate function D(R) as O(/spl radic/(log k/k)). (3) There exists a fixed-rate universal lossy source coding scheme whose per-letter MSE on a real-valued source samples converges in expectation and almost surely to the distortion-rate function D(R) as O((/spl radic/(loglog n/log n)). (4) Consider a training set of n real-valued source samples blocked into vectors of dimension k, and a k-dimension vector quantizer designed to minimize the empirical MSE with respect to the m=[n/k] training vectors. Then the per-letter MSE of this quantizer for the true source converges in expectation and almost surely to the distortion-rate function D(R) as O(/spl radic/(log log n/log n))), if one chooses k=[(1/R)(1-/spl epsiv/)log n] for any /spl epsiv//spl isin/(0.1).>

The posterior-probability estimate of the classification error rate of some nonparametric classification rules is studied. The variance of the estimator is shown to have same remarkable distribution-free properties for the k-nearest neighbor, kernel, and histogram rules. We also investigate the bias of the estimate and establish its consistency and upper bounds. The version of the estimate calculated from an independent set of unclassified patterns is also considered.>

The authors show that without knowing anything about the statistics of a bounded real-valued memoryless source, it is possible to construct a sequence of codes, of rate not exceeding a fixed number R>0, such that the per-letter sample distortion converges to the distortion-rate function D(R) with probability one as the length of the message approaches infinity. It is proven that the distortion converges to D(R) as square root log log n/log n almost surely, where n is the length of the data to be transmitted.>

A fast nearest-neighbor algorithm is presented. It works in general spaces in which the known cell techniques cannot be implemented for various reasons, such as the absence of coordinate structure or high dimensionality. The central idea has already appeared several times in the literature with extensive computer simulation results. An exact probabilistic analysis of this family of algorithms that proves its O(1) asymptotic average complexity measured in the number of dissimilarity calculations is presented.>

In statistical pattern recognition, a classifier is called universally consistent if its error probability converges to the Bayes-risk as the size of the training data grows for all possible distributions of the random variable pair of the observation vector and its class. It is proven that if a one-layered neural network with properly chosen number of nodes is trained to minimize the empirical risk on the training data, then a universally consistent classifier results. It is shown that the exponent in the rate of convergence does not depend on the dimension if certain smoothness conditions on the distribution are satisfied. That is, this class of universally consistent classifiers does not suffer from the curse of dimensionality. A training algorithm is presented that finds the optimal set of parameters in polynomial time if the number of nodes and the space dimension is fixed and the amount of training data grows.>