It has been shown by earlier results that for fixed rate multiresolution scalar quantizers and for mean squared error distortion measure, codecell convexity precludes optimality for certain discrete sources. However it was unknown whether the same phenomenon can occur for any continuous source. In this paper, examples of continuous sources (even with bounded continuous densities) are presented for which optimal fixed rate multiresolution scalar quantizers cannot have only convex codecells, proving that codecell convexity precludes optimality also for such regular sources.

We consider online learning in finite stochastic Markovian environments where in each time step a new reward function is chosen by an oblivious adversary. The goal of the learning agent is to compete with the best stationary policy in terms of the total reward received. In each time step the agent observes the current state and the reward associated with the last transition, however, the agent does not observe the rewards associated with other state-action pairs. The agent is assumed to know the transition probabilities. The state of the art result for this setting is a no-regret algorithm. In this paper we propose a new learning algorithm and assuming that stationary policies mix uniformly fast, we show that after T time steps, the expected regret of the new algorithm is O(T^{2/3} (ln T)^{1/3}), giving the first rigorously proved convergence rate result for the problem.

We consider continuous state, continuous action batch reinforcement learning where the goal is to learn a good policy from a sufficiently rich trajectory generated by another policy. We study a variant of fitted Q-iteration, where the greedy action selection is replaced by searching for a policy in a restricted set of candidate policies by maximizing the average action values. We provide a rigorous theoretical analysis of this algorithm, proving what we believe is the first finite-time bounds for value-function based algorithms for continuous state- and action-space problems.

It has been shown by earlier results that the minimax expected (test) distortion redundancy of empirical vector quantizers with three or more levels designed from n independent and identically distributed (i.i.d.) data points is at least Omega(1/radicn) for the class of distributions on a bounded set. In this correspondence, a much simpler construction and proof for this are given with much better constants. There are similar bounds for the training distortion of the empirically optimal vector quantizer with three or more levels. These rates, however, do not hold for a one-level quantizer. Here, the two-level quantizer case is clarified, showing that it already shares the behavior of the general case. Given that the minimax bounds are proved using a construction that involves discrete distributions, one suspects that for the class of distributions with uniformly bounded continuous densities, the expected distortion redundancy might decrease as o(1/radicn) uniformly. It is shown as well that this is not so, proving that the lower bound for the expected test distortion remains true for these subclasses

We consider the rate of convergence of the expected distortion redundancy of empirically optimal vector quantizers. Earlier results show that the mean-squared distortion of an empirically optimal quantizer designed from n independent and identically distributed (i.i.d.) source samples converges uniformly to the optimum at a rate of O(1//spl radic/n), and that this rate is sharp in the minimax sense. We prove that for any fixed distribution supported on a given finite set the convergence rate is O(1/n) (faster than the minimax lower bound), where the corresponding constant depends on the source distribution. For more general source distributions we provide conditions implying a little bit worse O(logn/n) rate of convergence. Although these conditions, in general, are hard to verify, we show that sources with continuous densities satisfying certain regularity properties (similar to the ones of Pollard that were used to prove a central limit theorem for the code points of the empirically optimal quantizers) are included in the scope of this result. In particular, scalar distributions with strictly log-concave densities with bounded support (such as the truncated Gaussian distribution) satisfy these conditions.

We consider the rate of convergence of the expected distortion redundancy of empirically optimal vector quantizers. Earlier results show that the mean-squared distortion of an empirically optimal quantizer designed from n independent and identically distributed source samples converges uniformly to the optimum at a rate O(1/radicn), and that this rate is sharp in the minimax sense. We prove that for any fixed source distribution supported on a given finite set, the convergence rate is O(1/n) (faster than the minimax lower bound), where the corresponding constant depends on the distribution. For more general source distributions, we provide conditions implying a little bit worse O(log n/n) rate of convergence. In particular, scalar distributions having strictly log-concave densities with bounded support (such as the truncated Gaussian distribution) satisfy these conditions

We give a short proof of the following result. Let (X,Y) be any distribution on N/spl times/{0,1}, and let (X/sub 1/,Y/sub 1/),...,(X/sub n/,Y/sub n/) be an i.i.d. sample drawn from this distribution. In discrimination, the Bayes error L*=inf/sub g/P{g(X)/spl ne/Y} is of crucial importance. Here we show that without further conditions on the distribution of (X,Y), no rate-of-convergence results can be obtained. Let /spl phi//sub n/(X/sub 1/,Y/sub 1/,...,X/sub n/,Y/sub n/) be an estimate of the Bayes error, and let {/spl phi//sub n/(.)} be a sequence of such estimates. For any sequence {a/sub n/} of positive numbers converging to zero, a distribution of (X,Y) may be found such that E{|L*-/spl phi//sub n/(X/sub 1/,Y/sub 1/,...,X/sub n/,Y/sub n/)|}/spl ges/a/sub n/ often converges infinitely.

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.