This paper addresses the covariate shift problem in the context of nonparametric regression within reproducing kernel Hilbert spaces (RKHSs). Covariate shift arises in supervised learning when the input distributions of the training and test data differ, presenting additional challenges for learning. Although kernel methods have optimal statistical properties, their high computational demands in terms of time and, particularly, memory, limit their scalability to large datasets. To address this limitation, the main focus of this paper is to explore the trade-off between computational efficiency and statistical accuracy under covariate shift. We investigate the use of random projections where the hypothesis space consists of a random subspace within a given RKHS. Our results show that, even in the presence of covariate shift, significant computational savings can be achieved without compromising learning performance.

In this work we consider the problem of numerical integration, i.e., approximating integrals with respect to a target probability measure using only pointwise evaluations of the integrand. We focus on the setting in which the target distribution is only accessible through a set of $n$ i.i.d. observations, and the integrand belongs to a reproducing kernel Hilbert space. We propose an efficient procedure which exploits a small i.i.d. random subset of $m \lt n$ samples drawn either uniformly or using approximate leverage scores from the initial observations. Our main result is an upper bound on the approximation error of this procedure for both sampling strategies. It yields sufficient conditions on the subsample size to recover the standard (optimal) $n^{-1/2}$ rate while reducing drastically the number of functions evaluations---and thus the overall computational cost. Moreover, we obtain rates with respect to the number $m$ of evaluations of the integrand which adapt to its smoothness, and match known optimal rates for instance for Sobolev spaces. We illustrate our theoretical findings with numerical experiments on real datasets, which highlight the attractive efficiency-accuracy tradeoff of our method compared to existing randomized and greedy quadrature methods. We note that, the problem of numerical integration in RKHS amounts to designing a discrete approximation of the kernel mean embedding of the target distribution. As a consequence, direct applications of our results also include the efficient computation of maximum mean discrepancies between distributions and the design of efficient kernel-based tests.

We investigate an extension of classical empirical risk minimization, where the hypothesis space consists of a random subspace within a given Hilbert space. Specifically, we examine the Nyström method where the subspaces are defined by a random subset of the data. This approach recovers Nyström approximations used in kernel methods as a specific case. Using random subspaces naturally leads to computational advantages, but a key question is whether it compromises the learning accuracy. Recently, the tradeoffs between statistics and computation have been explored for the square loss and self-concordant losses, such as the logistic loss. In this paper, we extend these analyses to general convex Lipschitz losses, which may lack smoothness, such as the hinge loss used in support vector machines. Our main results show the existence of various scenarios where computational gains can be achieved without sacrificing learning performance. When specialized to smooth loss functions, our analysis recovers most previous results. Moreover, it allows to consider classification problems and translate the surrogate risk bounds into classification error bounds. Indeed, this gives the opportunity to compare the effect of Nyström approximations when combined with different loss functions such as the hinge or the square loss.

Compressive learning is an approach to efficient large scale learning based on sketching an entire dataset to a single mean embedding (the sketch), i.e. a vector of generalized moments. The learning task is then approximately solved as an inverse problem using an adapted parametric model. Previous works in this context have focused on sketches obtained by averaging random features, that while universal can be poorly adapted to the problem at hand. In this paper, we propose and study the idea of performing sketching based on data-dependent Nyström approximation. From a theoretical perspective we prove that the excess risk can be controlled under a geometric assumption relating the parametric model used to learn from the sketch and the covariance operator associated to the task at hand. Empirically, we show for k-means clustering and Gaussian modeling that for a fixed sketch size, Nyström sketches indeed outperform those built with random features.

Kernel methods provide a principled approach to nonparametric learning. While their basic implementations scale poorly to large problems, recent advances showed that approximate solvers can efficiently handle massive datasets. A shortcoming of these solutions is that hyperparameter tuning is not taken care of, and left for the user to perform. Hyperparameters are crucial in practice and the lack of automated tuning greatly hinders efficiency and usability. In this paper, we work to fill in this gap focusing on kernel ridge regression based on the Nyström approximation. After reviewing and contrasting a number of hyperparameter tuning strategies, we propose a complexity regularization criterion based on a data dependent penalty, and discuss its efficient optimization. Then, we proceed to a careful and extensive empirical evaluation highlighting strengths and weaknesses of the different tuning strategies. Our analysis shows the benefit of the proposed approach, that we hence incorporate in a library for large scale kernel methods to derive adaptively tuned solutions.

We study the behavior of error bounds for multiclass classification under suitable margin conditions. For a wide variety of methods we prove that the classification error under a hard-margin condition decreases exponentially fast without any bias-variance trade-off. Different convergence rates can be obtained in correspondence of different margin assumptions. With a self-contained and instructive analysis we are able to generalize known results from the binary to the multiclass setting.

We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nyström approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to ex- tend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector ma- chines. This extension requires developing new proofs, that use different technical tools. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance. Theoretical results are illustrated with simple numerical experiments.

In this work, we consider the linear inverse problem $y=Ax+\varepsilon$, where $A\colon X\to Y$ is a known linear operator between the separable Hilbert spaces $X$ and $Y$, $x$ is a random variable in $X$ and $\epsilon$ is a zero-mean random process in $Y$. This setting covers several inverse problems in imaging including denoising, deblurring, and X-ray tomography. Within the classical framework of regularization, we focus on the case where the regularization functional is not given a priori, but learned from data. Our first result is a characterization of the optimal generalized Tikhonov regularizer, with respect to the mean squared error. We find that it is completely independent of the forward operator $A$ and depends only on the mean and covariance of $x$.Then, we consider the problem of learning the regularizer from a finite training set in two different frameworks: one supervised, based on samples of both $x$ and $y$, and one unsupervised, based only on samples of $x$. In both cases, we prove generalization bounds, under some weak assumptions on the distribution of $x$ and $\varepsilon$, including the case of sub-Gaussian variables. Our bounds hold in infinite-dimensional spaces, thereby showing that finer and finer discretizations do not make this learning problem harder. The results are validated through numerical simulations.

Shearlets are a relatively new directional multi-scale framework for signal analysis, which have been shown effective to enhance signal discontinuities, such as edges and corners at multiple scales even in the presence of a large quantity of noise. In this paper, we consider blob-like features in the shearlets framework. We derive a measure, which is very effective for blob detection, and, based on this measure, we propose a blob detector and a keypoint description, whose combination outperforms the state-of-the-art algorithms with noisy and compressed images. We also demonstrate that the measure satisfies the perfect scale invariance property in the continuous case. We evaluate the robustness of our algorithm to different types of noise, including blur, compression artifacts, and Gaussian noise. Furthermore, we carry on a comparative analysis on benchmark data, referring, in particular, to tolerance to noise and image compression.

Shearlets are a relatively new and very effective multi-scale framework for signal analysis. Contrary to the traditional wavelets, shearlets are capable to efficiently capture the anisotropic information in multivariate problem classes. Therefore, shearlets can be seen as the valid choice for multi-scale analysis and detection of directional sensitive visual features like edges and corners. In this paper, we start by reviewing the main properties of shearlets that are important for edge and corner detection. Then, we study algorithms for multi-scale edge and corner detection based on the shearlet representation. We provide an extensive experimental assessment on benchmark data sets which empirically confirms the potential of shearlets feature detection.

In this paper we consider the problem of learning from data the support of a probability distribution when the distribution {\em does not} have a density (with respect to some reference measure). We propose a new class of regularized spectral estimators based on a new notion of reproducing kernel Hilbert space, which we call {\em ``completely regular''}. Completely regular kernels allow to capture the relevant geometric and topological properties of an arbitrary probability space. In particular, they are the key ingredient to prove the universal consistency of the spectral estimators and in this respect they are the analogue of universal kernels for supervised problems. Numerical experiments show that spectral estimators compare favorably to state of the art machine learning algorithms for density support estimation.

We discuss how a large class of regularization methods, collectively known as spectral regularization and originally designed for solving ill-posed inverse problems, gives rise to regularized learning algorithms. All of these algorithms are consistent kernel methods that can be easily implemented. The intuition behind their derivation is that the same principle allowing for the numerical stabilization of a matrix inversion problem is crucial to avoid overfitting. The various methods have a common derivation but different computational and theoretical properties. We describe examples of such algorithms, analyze their classification performance on several data sets and discuss their applicability to real-world problems.

Many works related learning from examples to regularization techniques for inverse problems, emphasizing the strong algorithmic and conceptual analogy of certain learning algorithms with regularization algorithms. In particular it is well known that regularization schemes such as Tikhonov regularization can be effectively used in the context of learning and are closely related to algorithms such as support vector machines. Nevertheless the connection with inverse problem was considered only for the discrete (finite sample) problem and the probabilistic aspects of learning from examples were not taken into account. In this paper we provide a natural extension of such analysis to the continuous (population) case and study the interplay between the discrete and continuous problems. From a theoretical point of view, this allows to draw a clear connection between the consistency approach in learning theory and the stability convergence property in ill-posed inverse problems. The main mathematical result of the paper is a new probabilistic bound for the regularized least-squares algorithm. By means of standard results on the approximation term, the consistency of the algorithm easily follows.

Many works have shown that strong connections relate learning from ex- amples to regularization techniques for ill-posed inverse problems. Nev- ertheless by now there was no formal evidence neither that learning from examples could be seen as an inverse problem nor that theoretical results in learning theory could be independently derived using tools from reg- ularization theory. In this paper we provide a positive answer to both questions. Indeed, considering the square loss, we translate the learning problem in the language of regularization theory and show that consis- tency results and optimal regularization parameter choice can be derived by the discretization of the corresponding inverse problem. 1 Introduction The main goal of learning from examples is to infer an estimator, given a finite sample of data drawn according to a fixed but unknown probabilistic input-output relation. The desired property of the selected estimator is to perform well on new data, i.e. it should gen- eralize. The fundamental works of Vapnik and further developments [16], [8], [5], show that the key to obtain a meaningful solution to the above problem is to control the complex- ity of the solution space. Interestingly, as noted by [12], [8], [2], this is the idea underlying regularization techniques for ill-posed inverse problems [15], [7]. In such a context to avoid undesired oscillating behavior of the solution we have to restrict the solution space. Not surprisingly the form of the algorithms proposed in both theories is strikingly similar. Anyway a careful analysis shows that a rigorous connection between learning and regular- ization for inverse problem is not straightforward. In this paper we consider the square loss and show that the problem of learning can be translated into a convenient inverse problem and consistency results can be derived in a general setting. When a generic loss is consid- ered the analysis becomes immediately more complicated. Some previous works on this subject considered the special case in which the elements of the input space are fixed and not probabilistically drawn [11], [9]. Some weaker results in the same spirit of those presented in this paper can be found in [13] where anyway the connections with inverse problems is not discussed. Finally, our analysis is close to the idea of stochastic inverse problems discussed in [16]. It follows the plan of the paper. Af- ter recalling the main concepts and notation of learning and inverse problems, in section 4 we develop a formal connection between the two theories. In section 5 the main results are stated and discussed. Finally in section 6 we conclude with some remarks and open problems. 2 Learning from examples We briefly recall some basic concepts of learning theory [16], [8]. In the framework of learning, there are two sets of variables: the input space X, compact subset of Rn, and the output space Y , compact subset of R. The relation between the input x X and the output y Y is described by a probability distribution (x, y) = (x)(y|x) on X Y . The distribution is known only through a sample z = (x, y) = ((x1, y1), . . . , (x , y )), called training set, drawn i.i.d. according to . The goal of learning is, given the sample z, to find a function fz : X R such that fz(x) is an estimate of the output y when the new input x is given. The function fz is called estimator and the rule that, given a sample z, provides us with fz is called learning algorithm. Given a measurable function f : X R, the ability of f to describe the distribution is measured by its expected risk defined as I[f ] = (f (x) - y)2 d(x,y). XY The regression function g(x) = y d(y|x), Y is the minimizer of the expected risk over the set of all measurable functions and always exists since Y is compact. Usually, the regression function cannot be reconstructed exactly since we are given only a finite, possibly small, set of examples z. To overcome this problem, in the regularized least squares algorithm an hypothesis space H is fixed, and, given > 0, an estimator f z is defined as the solution of the regularized least squares problem, 1 min{ (f (xi) - yi)2 + f 2H}. (1) f H i=1 The regularization parameter has to be chosen depending on the available data, = ( , z), in such a way that, for every > 0 lim P I[f ( ,z) z ] - inf I[f] = 0. (2) + f H We note that in general inffH I[f ] is larger that I[g] and represents a sort of irreducible error associated with the choice of the space H. The above convergence in probability is usually called consistency of the algorithm [16] [14]. 3 Ill-Posed Inverse Problems and Regularization In this section we give a very brief account of linear inverse problems and regularization theory [15], [7]. Let H and K be two Hilbert spaces and A : H K a linear bounded operator. Consider the equation Af = g (3) where g, g K and g - g K . Here g represents the exact, unknown data and g the available, noisy data. Finding the function f satisfying the above equation, given A and g, is the linear inverse problem associated to Eq. (3). The above problem is, in general, ill- posed, that is, the Uniqueness can be restored introducing the Moore-Penrose generalized inverse f = Ag defined as the minimum norm solution of the problem min Af - g 2 . (4) K f H However the operator A is usually not bounded so, in order to ensure a continuous de- pendence of the solution on the data, the following Tikhonov regularization scheme can be considered1 min{ Af - g 2 + f 2 K H}, (5) f H whose unique minimizer is given by f = (AA + I )-1Ag , (6) where A denotes the adjoint of A. A crucial step in the above algorithm is the choice of the regularization parameter = (, g), as a function of the noise level and the data g, in such a way that lim f (,g) = 0, (7) - f 0 H that is, the regularized solution f (,g) converges to the generalized solution f = Ag (f exists if and only if P g Range(A), where P is the projection on the closure of the range of A and, in that case, Af = P g) when the noise goes to zero. The similarity between regularized least squares algorithm (1) and Tikhonov regulariza- tion (5) is apparent. However, several difficulties emerge. First, to treat the problem of learning in the setting of ill-posed inverse problems we have to define a direct problem by means of a suitable operator A. Second, in the context of learning, it is not clear the nature of the noise . Finally we have to clarify the relation between consistency (2) and the kind of convergence expressed by (7). In the following sections we will show a possible way to tackle these problems. 4 Learning as an Inverse Problem We can now show how the problem of learning can be rephrased in a framework close to the one presented in the previous section. We assume that hypothesis space H is a reproducing kernel Hilbert space [1] with a contin- uous kernel K : X X R. If x X, we let Kx(s) = K(s, x), and, if is the marginal distribution of on X, we define the bounded linear operator A : H L2(X, ) as (Af )(x) = f, Kx = f (x), H 1In the framework of inverse problems, many other regularization procedures are introduced [7]. For simplicity we only treat the Tikhonov regularization. that is, A is the canonical injection of H in L2(X, ). In particular, for all f H, the expected risk becomes, I[f ] = Af - g 2 + I[g], L2(X,) where g is the regression function [2]. The above equation clarifies that if the expected risk admits a minimizer fH on the hypothesis space H, then it is exactly the generalized solution2 f = Ag of the problem Af = g. (8) Moreover, given a training set z = (x, y), we get a discretized version Ax : H E of A, that is (Axf)i = f, Kx = f (x i H i), where E = R is the finite dimensional euclidean space endowed with the scalar product 1 y, y = y E iyi. i=1 It is straightforward to check that 1 (f (xi) - yi)2 = Axf - y 2 , E i=1 so that the estimator f z given by the regularized least squares algorithm is the regularized solution of the discrete problem Axf = y. (9) At this point it is useful to remark the following two facts. First, in learning from examples we are not interested into finding an approximation of the generalized solution of the dis- cretized problem (9), but we want to find a stable approximation of the solution of the exact problem (8) (compare with [9]). Second, we notice that in learning theory the consistency property (2) involves the control of the quantity I[f z ] - inf I[f] = Af - g 2 Af . (10) L2(X,) - inf - g 2L2(X,) f H f H If P is the projection on the closure of the range of A, the definition of P gives 2 I[f z ] - inf I[f] = Afz - P g (11) f H L2(X,) (the above equality stronlgy depends on the fact that the loss function is the square loss). In the inverse problem setting, the square root of the above quantity is called the residue of the solution f z . Hence, consistency is controlled by the residue of the estimator, instead of the reconstruction error f z - f (as in inverse problems). In particular, consistency H is a weaker condition than the one required by (7) and does not require the existence of the generalized solution fH. 5 Regularization, Stochastic Noise and Consistency To apply the framework of ill-posed inverse problems of Section 3 to the formulation of learning proposed above, we note that the operator Ax in the discretized problem (9) differs from the operator A in the exact problem (8) and a measure of the difference between Ax and A is required. Moreover, the noisy data y E and the exact data g L2(X, ) belong to different spaces, so that the notion of noise has to be modified. Given the above premise our derivation of consistency results is developed in two steps: we first study the residue of the solution by means of a measure of the noise due to discretization and then we show a possible way to give a probabilistic evaluation of the noise previously introduced. 2The fact that fH is the minimal norm solution of (4) is ensured by the assumption that the support of the measure is X, since in this case the operator A is injective. 5.1 Bounding the Residue of the Regularized Solution We recall that the regularized solutions of problems (9) and (8) are given by f = (A A y, z x x + I )-1A x f = (AA + I)-1Ag. The above equations show that f and f depend only on A A z x x and AA which are operators from H into H and on Ay and Ag which are elements of x H, so that the space E disappears. This observation suggests that noise levels could be A A x x - AA L(H) and A y , where is the uniform operator norm. To this purpose, for x - Ag H L(H) every = (1, 2) R2+ we define the collection of training sets. U = {z (X Y ) | Ay A x - Ag H 1, Ax x - AA L(H) 2, N} and we let M = sup{|y| | y Y }. The next theorem is the central result of the paper. Theorem 1 If > 0, the following inequalities hold 1. for any training set z U M Af 2 + 1 z - P g L2(X,) - Af - P g L2(X,) 4 2 2. if P g Range(A), for any training set z U, M f 2 + 1 z - f H - f - f H 3 2 2 Moreover if we choose = (, z) in such a way that lim0 sup (,z) = 0 zU 2 lim 1 0 sup = 0 zU (12) (,z) then lim 2 0 sup = 0 zU (,z) lim sup Af (,z) = 0. (13) z - Pg 0 zU L2(X,) We omit the complete proof and refer to [3]. Briefly, the idea is to note that Af z - P g L2(X,) - Af - P g L2(X,) 1 Af = (AA) 2 (f z - Af L2(X,) z - f) H where the last equation follows by polar decomposition of the operator A. Moreover a simple algebraic computation gives f A A y+(AA+I)-1(A y z -f = (AA+I)-1(AA-Ax x)(Ax x+I)-1Ax x -Ag) where the relevant quantities for definition of the noise appear. The first item in the above proposition quantifies the difference between the residues of the regularized solutions of the exact and discretized problems in terms of the noise level = (1, 2). As mentioned before this is exactly the kind of result needed to derive consistency. On the other hand the last part of the proposition gives sufficient conditions on the parameter to ensure convergence of the residue to zero as the level noise decreases. The above results were obtained introducing the collection U of training sets compatible with a certain noise level . It is left to quantify the noise level corresponding to a training set of cardinality . This will be achieved in a probabilistic setting in the next section. 5.2 Stochastic Evaluation of the Noise In this section we estimate the discretization noise = (1, 2). Theorem 2 Let 1, 2 > 0 and = supxX K(x, x), then M 2 P Ag - A x y A H + 1, AA - Ax x L(H) + 2 2 2 1 2 1 - e-22M2 - e-24 (14) The proof is given in [3] and it is based on McDiarmid inequality [10] applied to the random variables F (z) = A x y - Ag G(z) = A A . H x x - AA L(H) Other estimates of the noise can be given using, for example, union bounds and Hoeffd- ing's inequality. Anyway rather then providing a tight analysis our concern was to find an natural, explicit and easy to prove estimate of . 5.3 Consistency and Regularization Parameter Choice Combining Theorems 1 and 2, we easily derive the following corollary. Corollary 1 Given 0 < < 1, with probability greater that 1 - , Af z - Pg - Af - Pg L2(X,) L2(X,) M 1 4 + 1 + log (15) 2 2

In this letter, we investigate the impact of choosing different loss functions from the viewpoint of statistical learning theory. We introduce a convexity assumption, which is met by all loss functions commonly used in the literature, and study how the bound on the estimation error changes with the loss. We also derive a general result on the minimizer of the expected risk for a convex loss function in the case of classification. The main outcome of our analysis is that for classification, the hinge loss appears to be the loss of choice. Other things being equal, the hinge loss leads to a convergence rate practically indistinguishable from the logistic loss rate and much better than the square loss rate. Furthermore, if the hypothesis space is sufficiently rich, the bounds obtained for the hinge loss are not loosened by the thresholding stage.