Abstract. We consider the problem of embedding a subset of [Formula: see text] into a low-dimensional Hamming cube in an almost isometric way. We construct a simple, data-oblivious, and computationally efficient map that achieves this task with high probability; we first apply a specific structured random matrix, which we call the double circulant matrix; using that a matrix requires linear storage and matrix-vector multiplication that can be performed in near-linear time. We then binarize each vector by comparing each of its entries to a random threshold, selected uniformly at random from a well-chosen interval. We estimate the number of bits required for this encoding scheme in terms of two natural geometric complexity parameters of the set: its Euclidean covering numbers and its localized Gaussian complexity. The estimate we derive turns out to be the best that one can hope for, up to logarithmic terms. The key to the proof is a phenomenon of independent interest: we show that the double circulant matrix mimics the behavior of the Gaussian matrix in two important ways. First, it maps an arbitrary set in [Formula: see text] into a set of well-spread vectors. Second, it yields a fast near-isometric embedding of any finite subset of [Formula: see text] into [Formula: see text]. This embedding achieves the same dimension reduction as the Gaussian matrix in near-linear time, under an optimal condition—up to logarithmic factors—on the number of points to be embedded. This improves a well-known construction due to Ailon and Chazelle.

We study learning problems in which the underlying class is a bounded subset of Lpand the target Y belongs to Lp. Previously, minimax sample complexity estimates were known under such boundedness assumptions only when p=∞. We present a sharp sample complexity estimate that holds for any p > 4; it is based on a learning procedure that is suited for heavy-tailed problems.

We study learning problems involving arbitrary classes of functions F , underlying measures μ, and targets Y . Because proper learning procedures, i.e., procedures that are only allowed to select functions in F , tend to perform poorly unless the problem satisfies some additional structural property (e.g., that F is convex), we consider unrestricted learning procedures that are free to choose functions outside the given class. We present a new unrestricted procedure whose sample complexity is almost the best that one can hope for and holds for (almost) any problem, including heavy-tailed situations. Moreover, the sample complexity coincides with what one could expect if F were convex, even when F is not. And if F is convex, then the unrestricted procedure turns out to be proper.

We study estimation properties of regularized procedures of the form $\hat f \in\arg\min_{f\in F}\Big(\frac{1}{N}\sum_{i=1}^N\big(Y_i-f(X_i)\big)^2+\lambda \Psi(f)\Big)$ for a convex class of functions $F$, regularization function $\Psi(\cdot)$ and some well chosen regularization parameter $\lambda$, where the given data is an independent sample $(X_i, Y_i)_{i=1}^N$. We obtain bounds on the $L_2$ estimation error rate that depend on the complexity of the true model $F^*:=\{f\in F: \Psi(f)\leq\Psi(f^*)\}$, where $f^*\in\arg\min_{f\in F}\mathbb{E}(Y-f(X))^2$ and the $(X_i,Y_i)$'s are independent and distributed as $(X,Y)$. Our estimate holds under weak stochastic assumptions -- one of which being a small-ball condition satisfied by $F$ -- and for rather flexible choices of regularization functions $\Psi(\cdot)$. Moreover, the result holds in the learning theory framework: we do not assume any a-priori connection between the output $Y$ and the input $X$. As a proof of concept, we apply our general estimation bound to various choices of $\Psi$, for example, the $\ell_p$ and $S_p$-norms (for $p\geq1$), weak-$\ell_p$, atomic norms, max- norm and SLOPE. In many cases, the estimation rate almost coincides with the minimax rate in the class $F^*$.

We obtain sharp bounds on the estimation error of the Empirical Risk Minimization procedure, performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used here relies on a “small-ball” assumption and thus holds for classes consisting of heavy-tailed functions and for heavy-tailed targets. The resulting estimates scale correctly with the “noise level” of the problem, and when applied to the classical, bounded scenario, always improve the known bounds.

We obtain sharp bounds on the convergence rate of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without any boundedness assumptions on class members or on the target. Rather than resorting to a concentration-based argument, the method relies on a ‘small-ball’ assumption and thus holds for heavy-tailed sampling and heavy-tailed targets. Moreover, the resulting estimates scale correctly with the ‘noise level’ of the problem. When applied to the classical, bounded scenario, the method always improves the known estimates.

In this correspondence, we present a simple argument that proves that under mild geometric assumptions on the classFand the set of target functionsT, the empirical minimization algorithm cannot yield a uniform error rate that is faster than 1/radic(k)in the function learning setup. This result holds for various loss functionals and the target functions fromTthat cause the slow uniform error rate are clearly exhibited.

We introduce a new parameter which may replace the fat-shattering dimension. Using this parameter we are able to provide improved complexity estimates for the agnostic learning problem with respect to any L/sub p/ norm. Moreover, we show that if fat/sub /spl epsi//(F) = O(/spl epsi//sup -p/) then F displays a clear phase transition which occurs at p=2. The phase transition appears in the sample complexity estimates, covering numbers estimates, and in the growth rate of the Rademacher averages associated with the class. As a part of our discussion, we prove the best known estimates on the covering numbers of a class when considered as a subset of L/sub p/ spaces. We also estimate the fat-shattering dimension of the convex hull of a given class. Both these estimates are given in terms of the fat-shattering dimension of the original class.

We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L/sub 2/ spaces (e.g. log-covering numbers which are polynomial with exponent p<2). We present several examples of relevant classes which have a "small" fat-shattering dimension, and hence fit our setup, the most important of which are kernel machines.

We introduce a new supervised learning model that is a nonhomogeneous Markov process and investigate its properties. We are interested in conditions that ensure that the process converges to a "correct state," which means that the system agrees with the teacher on every "question." We prove a sufficient condition for almost sure convergence to a correct state and give several applications to the convergence theorem. In particular, we prove several convergence results for well-known learning rules in neural networks.

The goal of most learning processes is to bring a machine into a set of "correct" states. In practice, however, it may be difficult to show that the process enters this target set. We present a condition that ensures that the process visits the target set infinitely often almost surely. This condition is easy to verify and is true for many well-known learning rules. To demonstrate the utility of this method, we apply it to four types of learning processes: the perceptron, learning rules governed by continuous energy functions, the Kohonen rule, and the committee machine.