A Distributionally Robust Optimization Method for Adversarial Multiple Kernel Learning
Masoud Badiei Khuzani Hongyi Ren Md Tauhidul Islam Lei Xing

	
	A Robust Optimization Method for Adversarial Multiple Kernel Learning]A Distributionally Robust Optimization Method for Adversarial Multiple Kernel Learning  
	
	
	
	
	
	
	
	
	
	
	
	
	Masoud Badiei Khuzani, et al.]Masoud Badiei Khuzani^†, Hongyi Ren^, MD Tauhidul Islam^, Lei Xing^

	
	
	Stanford University, 450 Serra Mall, Stanford, CA 94305

		
	
	
	
	mbadieik,hongyi,devan,tauhid,lei@stanford.edu
	
	
	

	
			^†Department of Management Science, 	Stanford University, CA 94043, USA.

			^Department of Radiation Oncology, Stanford University, CA 94043, USA.

			Revised paper. Current Revision: April 2021, Last Edition: December 2018.
			

		

	




We propose a novel data-driven method to learn a mixture of multiple kernels with random features that is certifiabaly robust against adverserial inputs. Specifically, we consider a distributionally robust optimization of the kernel-target alignment with respect to the distribution of training samples over a distributional ball defined by the Kullback-Leibler (KL) divergence. The distributionally robust optimization problem can be recast as a min-max optimization whose objective function includes a log-sum term. We develop a mini-batch biased stochastic primal-dual proximal method to solve the min-max optimization. To debias the minibatch algorithm, we use the Gumbel perturbation technique to estimate the log-sum term. We establish theoretical guarantees for the performance of the proposed multiple kernel learning method. In particular, we prove the consistency, asymptotic normality, stochastic equicontinuity, and the minimax rate of the empirical estimators.  In addition, based on the notion of Rademacher and Gaussian complexities, we establish distributionally robust generalization bounds that are tighter than previous known bounds. More specifically, we leverage matrix concentration inequalities to establish distributionally robust generalization bounds. We validate our kernel learning approach for classification with the kernel SVMs on synthetic dataset generated by sampling multvariate Gaussian distributions with differernt variance structures. We also apply our kernel learning approach to the MNIST data-set and evaluate its robustness to perturbation of input images under different adversarial models. More specifically, we examine the robustness of the proposed kernel model selection technique against FGSM, PGM, C&W, and DDN adversarial perturbations, and compare its performance with alternative state-of-the-art multiple kernel learning paradigms. 

	[
    [
    December 30, 2023
=====================

plain



§ INTRODUCTION



Kernel methods are a class of statistical machine learning algorithms that capture the non-linear relationship between the representations of input data and class labels. The kernel methods circumvent explicit feature mapping that is required to learn a non-linear function or decision boundary in linear learning algorithms. Instead, these methods only rely on the inner product of feature maps in the feature space, which is often known as the “kernel trick" in machine learning literatures. In the kernel methods, the underlying kernel function must be specified by the user which poses a model selection problem. In practice, good representations of data are unknown a priori, and it is thus unclear how to select a good kernel function. In particular, choosing a good kernel often entails some domain knowledge about the underlying learning application. Multiple kernel learning (MKL) methods aim to address this model selection issue by learning a mixture model of a set of user-defined base kernels.

While MKL techniques in conjunction with the kernel SVMs often yield a good accuracy in experiments with standard test (out-of-sample) data, they are susceptible to perturbed inputs commonly referred to as adversarial examples <cit.>. For instance, in imaging applications, it has been observed that a certain hardly perceptible perturbation to the input image, which is found by maximizing the classifer’s prediction error, causes the machine learning model to mis-classify an image that is conveniently recognizable by human.  Nevertheless, such adversarial examples are primarily devised to showcase the vulnerabilities of the deep neural networks to adversarial inputs rather than the kernel SVMs. As a result, methodologies that are developed in the literature to mitigate the impact of such adversarial examples on the prediction accuracy of deep neural networks are inadequate for the kernel SVMs.

To ensure the robustness of the kernel SVM models against adversarial inputs, we propose a novel MKL procedure. In particular, we propose a novel kernel learning algorithm based on a distributionally robust optimization procedure with respect to a distribution ball measured by the KL divergence, and centered at the distribution of training data. We show that such distributional optimization procedure can be characterized as the standard min-max optimization problem that can be solved efficiently via the primal-dual proximal algorithms in conjunction with the Monte-Carlo sample average approximation. We provide theoretical guarantees for the consistency and the asymptotic normlality of the proposed optimization procedure. We also establish novel distributionally robust generalization bounds based on the notions of Rademacher and Gaussian complexities of function classes.



 §.§ Related works

We situate our results in the connection to the multiple kernel learning, adversarial training, and distributionally robust optimization problem.


  §.§.§ Multiple kernel learning
 Multiple kernel learning for classification problems using kernel SVMs has been studied extensively over the past decade. Cortes, et al. <cit.> studied a kernel learning procedure from the class of mixture of base kernels.  They have also studied the generalization bounds of the proposed methods. The same authors have also studied a two-stage kernel learning in <cit.> based on a notion of alignment. The first stage of this technique consists of learning a kernel that is a convex combination of a set of base kernels. The second stage consists of using the learned kernel with a standard kernel-based learning algorithm such as SVMs to select a prediction hypothesis.  In <cit.>, the authors have proposed a semi-definite programming for the kernel-target alignment problem. An alternative approach to kernel learning is to sample random features from an arbitrary distribution (without tuning its hyper-parameters) and then apply a supervised feature screening method to distill random features with high discriminative power from redundant random features.

The current paper is also closely related to the multiple kernel learning of Yang, et al. <cit.> and Sinha and Duchi <cit.>. In <cit.>, a primal-dual proximal algorithm for the multiple kernel learning from training data with noisy class labels is proposed. More specifically, the work of <cit.> proposes a chance constraint optimization problem to deal with data-sets in which binary class labels are noisy. Our multiple kernel learning framework generalizes <cit.> by providing robustness against perturbations of both class labels and input features. The work of Sinha and Duchi <cit.> proposes a distributionally robust optimization with respect to χ^2-divergence for the weights of the mixture model in multiple kernel learning. In contrast, in this paper, we consider a distributionally robust optimization with respect to KL divergence of the training data distribution. Therefore, while the work of Sinha and Duchi <cit.> can be considered as a form of robust feature selection for the Rahimi and Recht random features <cit.>, our work can be viewed through the lense of adverserial robustness against the perturbation of the input features and their class labels.




  §.§.§ Distributionally robust optimization
 There are different paradigms in the distributional robust optimization literature corresponding to different methodologies that are used to characterize the uncertainty distribution set, such as constraint sets for moments, support, or directional deviations  <cit.>, distributional balls with respect to the f-divergences <cit.>, and  with respect to the Wasserstein distance <cit.>.  In this paper, we leverage a distributionally robust optimization with respect to the KL divergence distributional ball. Such distributional optimization procedure is closely related to the notion of the tilted empirical risk minimization (TERM) <cit.>. Specifically, TERM is a generalization of the standard empirical risk minimization, where the empirical loss function is parameterized with “tilt".  In the work of <cit.>, the tilt parameter can take any real values, and its value is determined by a grid search over some set of candidate values.  In our framework, the tilt is a non-negative value that emerges as a dual variable in the primal-dual characterisation of the distributionally robust optimization. Therefore, the value of the tilt in our framework can be determined in a principled manner from an optimization problem.



  §.§.§ Adversarial training
  In the past few years, several empirical defenses have been proposed for training classifiers to be robust against adversarial perturbations <cit.>. These robust classifiers are devised to mitigate a particular adversarial model, and as such, they can still be vulnerable against alternative adversarial examples <cit.>. To overhaul the dichotomy between defenses and attacks, certified defenses have been popularized, where the objective is to train classifiers whose predictions are provably robust; see, e.g., <cit.> for a non-exhasutive list.  Another line of defense work focuses on randomized smoothing where the prediction is robust within some region around the input with a user-defined probability <cit.>. All the aforementioned methods, however, are primarily concerned with deep neural networks training, and cannot be applied to kernel SVMs.



 §.§ Paper outline
 The rest of this paper is organized as follows:


	
  * Empirical Risk Minimization in Reproducing Kernel Hilbert Spaces: In Section <ref>, we review some preliminaries regarding the empirical risk minimization in reproducing kernel Hilbert spaces. We also provide the notion of the kernel-target alignment for optimizing the kernel in support vector machines (SVMs). We then characterize a distributionally robust optimization problem for multiple kernel learning. 
	
	
  * Primal-Dual Method for Distributionally Robust Optimization: In Section <ref>,  we describe a procedure to transform the distributionally robust optimization into a min-max optimization problem. We then apply a Gumbel perturbation in conjunction with SAA to devise a stochastic primal-dual method.
	
	
  * Consistency, Min-Max Rate, and Robust Generalization Bounds: In Section <ref>, we provide the theoretical guarantees for the kernel learning algorithm. In particular, we establish the non-asymptotic consistency of the finite sample approximations. 
	
	
  * Empirical Evaluation on Synthetic and Benchmark Data-Sets: In Section <ref>, we evaluate the performance of  
    our proposed kernel learning model on synthetic and benchmark data-sets. 	
    





§ PRELIMINARIES AND THE OPTIMIZATION PROBLEM FOR KERNEL LEARNING

 


In this section, we review preliminaries of kernel methods in classification and regression problems. 



 §.§ Reproducing kernel Hilbert spaces (RKHS)


Let 𝒳 be a metric space. A Mercer kernel on 𝒳 is a continuous and symmetric function K:𝒳×𝒳→ such that for any finite set of points {x_1,⋯,x_N}⊂𝒳, the kernel matrix (K(x_i,x_j))_1≤ i,j≤ N is positive semi-definite.  The reproducing kernel Hilbert space (RKHS) ℋ_K associated with the kernel K is  the completion of the linear span of the set of functions {K_x K(x,·), x∈𝒳} with the inner product structure ⟨·,·⟩_ℋ_K defined by ⟨ K_x_i,K_x_j⟩_ℋ_K=K(x_i,x_j). That is 

    ⟨∑_i=1^Nα_iK_x_i,∑_j=1^Nβ_jK_x_j⟩_ℋ_K=∑_i,j=1^Nα_iβ_jK(x_i,x_j).

The reproducing property takes the following form

    ⟨ K_x,f⟩_ℋ_K=f(x),   ∀x∈𝒳, f∈ℋ_K.
 


In this paper, we focus on the supervised learning of classifiers from RKHS. In the classical supervised learning settings, we are given n feature vectors and their corresponding univariate class labels  (x_1,y_1),⋯,(x_n,y_n)∼_i.i.d. P^0_X,Y,  (x_i,y_i)∈𝒵𝒳×𝒴⊂^d×. For the binary classification and regression tasks, the target spaces are given by 𝒴={-1,1} and 𝒴=, respectively. Given a loss function ℓ:𝒴×→, a classifier f is learned from the function class ℱ by minimizing the empirical risk with a quadratic regularization term,

    inf_f∈ℱR[f]1n∑_i=1^nℓ(y_i,f(x_i))+λ2f_ℱ^2,

where ·_ℱ is a function norm, and λ>0 is the parameter of the regularization.  In the adversarial learning models, the out-of-sample (test) data distribution z_i=(y_i,x_i)∼ P P_X,Y deviate from the in sample data distribution Q P_X^0,Y^0, and there is a “cost" c:𝒵×𝒵→_+∪{+∞} associated with such a perturbation.  In the adversarial learning litearture,  the quadratic norm c(z_i,z_i^0)=z_i-z_i^0_p^2 with p=∞ or p=2 is typically imposed on the actual test samples z_i^0∼ Q and their corresponding perturbations z_i∼ P <cit.>. However, such a cost function is oblivious of the underlying generative distribution of samples. Alternatively, the cost function can penalize the shift of the joint distribution of the test samples c(z,z^0)=D_f(P||Q) for all realizations of the samples and their perturbations z,z^0∈𝒵×𝒵, where D_f(·||·) is the f-divergence. In the sequel, we focus on the Kullback-Leibler divergence  D_KL(·||·) between two distributions P and Q, namely

    D_KL(P||Q)∫_𝒳×𝒴log(dPdQ)dP,

when P is absolutely continuous with respect to Q (denoted by P≪ Q), and +∞ otherwise.  Now, consider a Reproducing Kernel Hilbert Space (RKHS) ℋ_K with the kernel function K:𝒳×𝒳→, and suppose ℱ=ℋ_K⊕ 1. Then, using the expansion f(x)=ω_0+∑_i=1^n-1ω_iK(x,x_i), and optimizing the kernel over the kernel class 𝒦 yields the following penalized primal population optimization
	
    min_ω∈^nmin_K∈𝒦_P[ℓ(y,ω_0+∑_i=1^n-1ω_iK(x,x_i) )+λ2ω_2^2]- ρ D_KL(P||Q),

where the risk function is caliberated with the cost function c(z,z^0)=D_KL(P(z)||Q(z^0)) associated with the perturbations. The risk minimization in Eq. (<ref>) is the Lagrangian form of the following distributionally robust optimization problem
	
    min_ω∈^nmin_K∈𝒦inf_P∈𝒫_P[ℓ(y,ω_0+∑_i=1^n-1ω_iK(x,x_i) )+λ2ω_2^2],

where 𝒫{P∈ℳ(𝒵): D_KL(P||Q)≤ r, P≪ Q } is a distributional ball centered at Q. In the particular case of the soft margin SVM classifier ℓ(y,z)=[1-yz]_+max{0,1-yz}, the primal and dual empirical risk optimizations can be written as follows

	
	
    Primal:min_ω∈^nmin_K∈𝒦inf_P^n∈𝒫^n_P^n[1-ω_0y+∑_i=1^n-1ω_iyK(x,x_i)]_++λ2ω_2^2,    
       Dual:max_α∈^nmin_γ_0,γ,γ̃min_K∈𝒦inf_P^n∈𝒫^n F(α,y,γ,γ̃,γ_0) -12Tr(K(α⊙y)(α⊙y)^T),


where ⊙ is Hadamard's (element-wise) product,  and F(α,y,γ,γ̃,γ_0)⟨α,1⟩-γ_0⟨α,y⟩-γ(C1-α)^T+γ̃α^T, where γ_0∈_+,γ∈_+^n, and γ̃∈_+^n. In Equation (<ref>), P^n=1 n∑_i=1^nδ_x_i,y_i(x,y) is the empirical measure associated with the observed (training) samples, and 𝒫^n{P^n∈ℳ(𝒵): D_KL(P^n||Q^n)≤ r, P^n≪Q^n} is the empirical distribution ball centered at the empirical measure Q^n. 



 §.§ MKL as the importance sampling of the random features

The form of the dual optimization in Eq. (<ref>) suggests that for a fixed dual vector α∈^n and a tuple of Lagrange multipliers (γ_0,γ,γ̃)∈_+×_+^n×_+^n, the optimal kernel can be computed by optimizing the following unbiased statistics known as the kernel-target alignment, i.e.

    max_K∈𝒦min_P^n∈𝒫^n_P^n^⊗ 2[yỹK(x̃,x)]=2n(n-1)∑_1≤ i≤ j≤ ny_iy_jK(x_i,x_j).

The empirical optimization problem in Eq. (<ref>) is a unbiased estimator of the following population value

    max_K∈𝒦inf_P∈𝒫_P^⊗ 2[yỹK(x,x̃)],

Now, consider the class of the mixture kernels 

    𝒦_m{K:𝒳×𝒳→:K(x,x')=∑_i=1^mω_iK_i(x,x'),ω∈S^+_m},

where K_i,i=1,2,⋯,m are the set of known base kernels (e.g. Gaussian kernels with different bandwidth parameters), and S_m^+{ω∈^m:⟨ω,1⟩=1,ω≽0} is the simplex of the probability distribution. To establish the connection between the multiple kernel learning and the importance sampling of the random feature distribution, we require the following two definitions:

(Bochner's Representation of the Shift Invariant Kernels)
	
A kernel K:𝒳→𝒳→ is translation invariant if there exists a symmetric positive definite function, ψ such that K(x,y)=ψ(x-y) for all x,y∈^d. Bochner's theorem <cit.> provides a complete characterization of a
positive definite function ψ:^d→. A continuous function ψ:^d→ is positive definite if it admits the integral representation

    ψ(x)=1(2π)^d/2∫_^de^-i⟨ξ,x⟩μ(dξ),   ∀x∈^d, μ∈ℬ_+(^d),

where ℬ_+(^d) is the set of all finite  non-negative
Borel measures on ^d.


(Schönberg's representation of the Radial Kernels)
			
A translation invariant kernel K:𝒳×𝒳→ is a radial kernel if there exists a function ψ:^d→ such that K(x,y)=ψ(x-y_2). The Schönberg's representation theorem <cit.> provides a complete characterization of a
positive definite RBF kernel ψ:→. A radial basis function ψ:→ is positive definite if it admits the integral representation

    ψ(x_2)=∫__+e^-sx_2^2ν(ds),   ∀x∈^d, ν∈ℬ_+(_+).



We consider a kernel optimization scheme in conjunction with the random features model of Rahimi and Recht <cit.> for the translation invariant kernels. Specifically, let φ: ^d×^D→ [-1, 1] denotes the explicit feature maps and μ∈ℳ(^D) denotes a probability measure from the space of probability measures ℳ(^D) on ^D. The kernel function is characterized via the random feature maps using Bochner's theorem (cf. <cit.>)

    K_μ(x,x̃)   =∫_Ξφ(x;ξ)φ(x̃;ξ)μ(dξ),   ∀x,x̃∈𝒳⊂^d.

For RBF kernels in Definition <ref> with the spectral density ν, it can be shown that 

	

    ξ   =(ζ,b)∈Ξ=^d× [-π,π], 
    ξ   ∼μ(dξ)=π(ζ)⊗Uniform[-π,π],
    φ(x,ξ)   =cos(⟨ (x,1),(ζ,b)⟩),


where π(dζ)∫_0^∞π_s(dζ)ν(ds), and π_s(dζ)=1 (4π s)^d 2exp(-ζ_2^2 4s)dζ. Let μ_1,⋯,μ_m denotes the distribution of random features corresponding to the kernels K_1,⋯,K_m, i.e., K_i=K_μ_i,i=1,2,⋯,m. Then, we can recast the multiple kernel learning in terms of the distribution of random features random features

    max_ω∈S_m^+inf_P∈𝒫_P^⊗ 2[yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)].

where the optimization in Eq. (<ref>) corresponds to the importance sampling of the random feature distribution μ_ω(ξ)∑_i=1^mω_iμ_i(ξ).




 §.§ Connections to the maximum mean discrepancy (MMD)


The distributionally robust optimization in Eq. (<ref>) can also be interpreted as the problem of finding a kernel that maximizes the distance between the marginal distributions of the features given their class labels in the settings that the marginals are adversarially chosen to minimize their distance. To provide a more precise description, in the following definition we formalize the notion of discrepancy between two distributions:
(Maximum Mean Discrepancy <cit.>)
	
	Let (𝒵,d) be a metric space, ℱ be a class of functions f:𝒵→, and P,Q∈ℳ(𝒵) be two probability measures from the set of all Borel probability measures ℳ(𝒵) on 𝒵. The maximum mean discrepancy (MMD) between the distributions P and Q with respect to the function class ℱ is defined below
	
    MMD_ℱ[P,Q]sup_f∈ℱ∫_𝒵 f(z)(P-Q)(dz).



When the function class ℱ is restricted to a RKHS norm ball ℱ{f∈ℋ_K:f_ℋ_K≤ 1}, the kernel MMD can be rewritten as follows

    MMD_K[P,Q]   =sup_f:f_ℋ_K≤ 1_P[f]-_Q[f] 
       =μ_P-μ_Q_ℋ_K
       =(_P^⊗ 2[K(z,z')]+_Q^⊗ 2[K(s,s')]-2_P,Q[K(z,s)])^1 2,

where μ_P,μ_Q∈ℋ_K are the kernel mean embeddings of the distributions P and Q, i.e.,


    μ_P∫_𝒳K(·,x)dP(x),  μ_Q∫_𝒳K(·,x) dQ(x).


Hence, _P[f]=⟨ f,μ_P⟩_ℋ_K, and _Q[f]=⟨ f,μ_Q⟩_ℋ_K, for all  functions f:𝒳→. Let 𝒵=𝒳×𝒴 and P∈ℳ(𝒵). Furthermore, consider the conditional distributions P_+ P_x|y=+1 and P_- P_x|y=1. Then, using the Rahimi and Recht random feature model <cit.>, K_μ_ω(x,x̃)=∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ), the following equality holds

    MMD^2_K_ω[P_+, P_-]=_P^⊗ 2[∫_Ξyỹφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)].

Furthermore, for the joint distributions P,Q∈ℳ(𝒵) with the marginals P(y) and Q(y), respectively, we obtain that

    D_KL(P(x,y)|| Q(x,y))=D_KL(P(y)||Q(y))+_P(y)[D_KL(P(x|y)||Q(x|y))].

Suppose the restriction P(y)=Q(y) applies to the marginals so that  D_KL(P(y)||Q(y))=0. Under this restriction, the class labels in the training data-set are the ground truths and only the input features are adverserially perturbed. Furthermore, consider a balanced training data-set Q(y=+1)=Q(y=-1)=1 2. Then, the KL divergence admits the following decomposition

    D_KL(P(x,y)|| Q(x,y))   =12D_KL(P(x|y=+1)||Q(x|y=+1))
       +12D_KL(P(x|y=-1)||Q(x|y=-1))
       =12D_KL(P_+⊗ P_-||Q_+⊗ Q_-).

where Q_+ Q_x|y=+1, Q_- Q_x|y=-1, and P_+⊗ P_- and Q_+⊗ Q_- denotes the tensor product of the distributions. Now, define the following distribution ball on the product space ℳ(𝒳)×ℳ(𝒳) of the marginal distributions:

    𝒫_±{(P_+,P_-)∈ℳ(𝒳)×ℳ(𝒳): D_KL(P_+⊗ P_-||Q_+⊗ Q_-)≤ 2r}.

Due to  the identity (<ref>), P∈𝒫 implies (P_+,P_-)∈𝒫_± and vice versa. Consequently, in the case of the balanced data-set and under the restriction that the class labels are not adverserially chosen P(y)=Q(y), the kernel-target alignment in Eq. (<ref>) can be recast as the following MMD optimization problem

    max_ω∈S_+^mmin_(P_+,P_-)∈𝒫_±MMD^2_K_ω[P_+,P_-].

In words, Equation (<ref>) says that the best mixture of base kernels is the one that increases the distance between the conditional distributions of features of each class label, as measured by the kernel MMD, when such conditional distributions are chosen adverserially to minimize the discrepancy. 




§ BIASED AND UNBIASED STOCHASTIC PRIMAL-DUAL METHOD TO SOLVE THE DISTRIBUTIONALLY ROBUST OPTIMIZATION PROBLEM



The distributional optimization problem in Eq. (<ref>) is intractable. To derive a solvabale optimization problem, we consider three main approximation steps in the sequel: (i) a change of measure techniques due to <cit.>, (ii) a Monte-Carlo sample average approximation with respect to the random feature samples and data-samples, and (iii)  a Gumbel perturbation technique for the log-sum approximation. Each step is described in the sequel.



 §.§ Change of measure


Define the Radon-Nikodym derivative L=d^2P^⊗ 2/d^2Q^⊗ 2. Then, we observe that L(x,y)≥ 0, ∀x,y∈𝒳×𝒴, and _Q^⊗ 2[L]=1. Moreover, the KL divergence can be rewritten as follows

    D_KL(P^⊗ 2||Q^⊗ 2)   =∫_𝒳×𝒴log(dP^⊗ 2dQ^⊗ 2)dP^⊗ 2dQ^⊗ 2dQ^⊗ 2
       =_Q^⊗ 2[Llog(L)].

The objective function in Eq. (<ref>) can also be rewritten in terms of L, as follows

    _P^⊗ 2[yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)]   =∫_𝒳×𝒴yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)dP^⊗ 2
       =∫_𝒳×𝒴yỹ∫_Ξφ(x_0;ξ)φ(x_1;ξ)μ_ω(dξ)dP^⊗ 2dQ^⊗ 2dQ^⊗ 2
       =_Q^⊗ 2[Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)].

Using Eqs. (<ref>)-(<ref>), the distributional  optimization in Eq. (<ref>) can be cast as a convex functional optimization

	
	
    max_ω∈S^+_mmin_L∈𝕃(Q)_Q^⊗ 2[Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)]
       s.t.:_Q^⊗ 2[Llog L]≤ r/2,
       _Q^⊗ 2[L]=1, L≥ 0,
 

where 𝕃(Q) is the set of such functionals, and in writing the constraint in Eq. (<ref>), we used the tensorization property of the KL divergence 

    D_KL(P^⊗ 2||Q^⊗ 2)=2D_KL(P||Q).

In the sequel, let 𝕃(Q)={L∈𝕃(Q):_Q^⊗ 2[Llog L]≤ r/2, _Q^⊗ 2[L]=1,L≥ 0 }. The following lemma provides a method to solve the functional optimization problem in Eq. (<ref>) via the standard primal-dual optimization methods:
(Saddle Point Characterization of Functional Optimization)
	
Consider the function H(λ;ω) defined below

    H(λ;ω)λlog_Q^⊗ 2[exp(-yỹλ_μ_ω[φ(x;ξ)φ(x̃;ξ)])]+λ r 2.
		
Then, the inner functional optimization problem in Eq. (<ref>) can be recast as a minimization of the function H(λ,ω), namely

    min_L∈𝕃(Q)_Q^⊗ 2[Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)]=-min_λ∈ΛH(λ;ω),   ∀ω∈S_m^+.

Consequently, the inner distributional optimization in Eq. (<ref>) can be recast as a minimization of the function H(λ,ω), namely

    inf_P∈𝒫_P^⊗ 2[yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ) ]=-min_λ∈ΛH(λ;ω),  ∀ω∈S_m^+.
		

The proof is provided in Section <ref> of the Supplementary.




 §.§ Biased stochastic primal-dual (SPD) method


To solve the optimization problem in Eq. (<ref>), we consider Monte-Carlo  sample average approximation (SAA) of the expectations with respect to the data distribution Q, and the random features distribution μ. 



  * Monte-Carlo SAA of random features: Consider the samples ξ_i^1,⋯,ξ_i^N∼_i.i.d.μ_i for each distribution associated with the base kernel K_i, i=1,2,⋯,m. Then, we define the empirical measure 

    μ_ω^N(ξ)=1N∑_k=1^N∑_i=1^mω_iδ_ξ_i^k(ξ),

and consider the following SAA

    ∫_Ξφ(x_i;ξ)φ(x_j;ξ)μ^N_ω(dξ)=1N⟨φ_ω(x_i),φ_ω(x_j)  ⟩,

where φ_ω(x)vec(diag^1 2(ω)Φ(x))∈^mN is defined via the concatenation of random features associated with each base kernel. Here, ω (ω_1,⋯,ω_m), Φ(x)=[φ(x;ξ_i^k)]_i∈ [m],k∈ [N]∈^m× N, and vec(·) is the vectorization of the matrix by stacking its rows.




  * Monte-Carlo SAA of data samples:
The second sample average approximation is due to sampling the training data (x_i,y_i)_1≤ i≤ n∼_i.i.d.Q=P_X,Y. Then, we define the empirical measure associated with the observed training samples as follows

    Q^n(x,y)=1n∑_i=1^nδ_(x_i,y_i)(x,y).

Using the empirical measure defined above, the SAA with respect to the training data is given by 

    _Q^n,⊗ 2[exp(-yỹλ_μ^N_ω[φ(x;ξ)φ(x̃;ξ)])]
       =2n(n-1)∑_1≤ i<j≤ nexp(-1Nλ⟨ y_iφ_ω(x_i),y_jφ_ω(x_j)  ⟩),

where in writing the product measure Q^n,⊗ 2, we ignored the diagonal elements, and as a result Equation (<ref>) is an unbiased estimator of the population value.


Now, combining Eqs. (<ref>)-(<ref>) and  the sample average approximations from  the following unbiased estimator of the population optimization problem 

    H_n,N(λ;ω)=1 2λ r+λlog2n(n-1)∑_1≤ i<j≤ nexp(-1 Nλ⟨ y_iφ_ω(x_i),y_jφ_ω(x_j)  ⟩).

Let us make a few remarks regarding the form of the objective of Eq. (<ref>) in Lemma <ref>. To solve the min-max optimization, we consider a mini-batch stochastic primal-dual method (SPD). In particular, consider a batch size of B∈ such that B≥ 2. Let π:{1,2,⋯,B}→{1,2,⋯,n} denotes the stochastic sampling function. Define the mini-batch objective function

    H^π_B,N(λ;ω)12λ r+λlog2B(B-1)∑_1≤ i<j≤ Bexp(-1 Nλ⟨ y_π(i)φ_ω(x_π(i)),y_π(j)φ_ω(x_π(j)) ⟩).

Then, we define the stochastic gradients as follows
for all ℓ=1,2,⋯,m. In Algorithm <ref>, we describe a stochastic primal-dual method to solve the minimax optimization of the objective function in Eq. (<ref>). The proposed stochastic primal-dual algorithm is biased. In particular, the expected value of the gradient estimators _π[𝖦_ω^π(λ;ω)] and _π[𝖦_λ^π(λ;ω)] deviate from their deterministic counterparts ∇_ωH_n,N(λ,ω) and ∇_λH_n,N(λ,ω), respectively. Nevertheless, for a large batch size B, the biased estimators are good approximations of the deterministic gradients. The exponentiation step in Equation (<ref>) of Algorithm <ref> is equivalent to the following proximal optimization step

    ω←Prox^β_𝖦^π_ω(λ;·)(ω),

where the proximal operator Prox_f:^d→𝒳 for a lower semi-continuous function f:𝒳→ with the gradient estimator [𝖦_f(x)]=∇ f(x) is defined as follows

    Prox^β_𝖦_f(x)min_y∈𝒳{⟨𝖦_f(x),y-x⟩ +1βD_ϕ(y||x)},

 for all x∈𝒳. In the previous display, D_ϕ(y||x)ϕ(y)-ϕ(x)-⟨y-x,∇ϕ(x) ⟩ is the Bregman divergence corresponding to the Legendre function ϕ. The proximal optimization step in Equations (<ref>) is adapted to the geometry of the simplex S_m^+, using the Bregman divergence corresponding to the negative entropy function ϕ(x)=∑_i=1^dx_ilog(x_i). In particular, it is a projection-free step for the convex optimization over the simplex. See the excellent monograph of Parikh and Boyd <cit.> for a treatise on the proximal algorithms.





 §.§ Debiasing via the Gumbel max perturbation scheme


Due to the logarithmic term,  constructing unbiased estimators with
proper variance for the deterministic gradients ∇_ω H(ω,λ) and ∇_λ H(ω,λ) based on the uniform sampling of the training data is challenging. To debiase the stochastic optimization algorithm, in the sequel we leverage the Gumble max perturbation technique to estimate the log-partition function. Specifically, let {ζ(z)}_z∈𝒵 denotes a collection of the independent random variables ζ(z) indexed by z∈𝒵, each
following the Gumbel distribution whose cumulative
distribution function  is F(ζ) = exp(-exp(-(ζ + γ))),
where γ≈ 0.577 is the Euler-Mascheroni constant. Then the random variable max_z∈𝒵{ϕ(z)+ζ(z)} is distributed according to
the Gumbel distribution and its expected value is the
logarithm of the partition function (see <cit.>)

    log∑_z∈𝒵exp(ϕ(z))=_ν[max_z∈𝒵{ϕ(z)+ζ(z)}],
	
where ν=dF/dζ is the Lebesgue density.
The Gumbel distribution can be sampled efficiently using the inverse transform sampling technique. Specifically, let U∼Uniform[0,1], and ζ=-γ-ln(-ln(U)). Then, ζ∼Gumbel(-γ,1) with the desired cumulative
distribution function F(ζ).  We employ the identity in Eq. (<ref>) to replace the log-sum term in Eq. (<ref>) with the Gumbel max formulation tain

    H_n,N(λ;ω)=   1 2λ r+λlog(2 n(n-1))
       +λ_ν[ max_1≤ i<j≤ n{-1 Nλ⟨ y_iφ_ω(x_i),y_jφ_ω(x_j)  ⟩+ζ_ij}],

where ζ_ij∼ν are i.i.d. for all 1≤ i<j≤ n. Using SAA for the expectation with respect to the Gumbel distribution yields

    H^D_n,N(λ;ω)=   1 2λ r+λlog(2 n(n-1))
       +1D∑_s=1^Dmax_1≤ i<j≤ n{-1N⟨ y_iφ_ω(x_i),y_jφ_ω(x_j) ⟩+λζ^s_ij}.


We now apply a penalty function to evaluate the maximum in Eq. (<ref>). In particular, the maximum of the real-valued functions (g_i(x))_1≤ i≤ n,g_i:→ can be computed as max_1≤ i≤ ng_i(x)=min_α∈α+ρ∑_i=1^n[g_i(x)-α]_+^2,
provided that the penalty factor ρ is sufficiently large.[More precisely, suppose ρ^∗_1,⋯,ρ^∗_n are the optimal Lagrange multipliers of the constrained optimization problem min_α∈α subject to g_i(x)≤α, i=1,2,⋯,n. Then, letting ρ=max_1≤ i≤ nρ^∗_i guarantees the equality.
] Therefore,


    H^D_n,N(λ;ω)=min_α∈^DG_n,N^D(λ,α;ω),

where G_n,N^D(λ,α;ω) is defined below

    G_n,N^D(λ,α;ω)   1 2λ r+λlog(2 n(n-1))+1D∑_s=1^Dα_s
       +ρD∑_s=1^D∑_1≤ i<j≤ n[λζ_ij^s-y_iy_jN⟨φ_ω(x_i),φ_ω(x_j) ⟩ -α_s]_+^2.

We now consider the following saddle point optimization problem

    min_ω∈S^+_mmin _(λ,α)∈_+×^DG_n,N^D(λ,α;ω).

We devise a stochastic primal-dual proximal method to solve the min-max optimization in Eq. (<ref>). In particular, we consider the following unbiased estimators of the deterministic gradients with the batch size B≥ 2:
 
			

    [𝖰^π_ω(λ,α;ω)]_ℓ   =∑_s=1^D∑_1≤ i<j≤ Bρδ_ℓ(π(i),π(j))[λζ_π(i)π(j)^s+⟨ω,δ(π(i),π(j)) ⟩ -α_s]_+, 
    [𝖰^π_α(λ,α;ω)]_s   =1D-∑_1≤ i<j≤ Bρ[λζ_π(i)π(j) ^s+⟨ω,δ(π(i),π(j)) ⟩-α_s]_+,
    𝖰^π_λ(λ,α;ω)   =12r+log(2n(n-1))
       +∑_s=1^D∑_1≤ i<j≤ Bρ[λζ^s_π(i)π(j)+⟨ω,δ(π(i),π(j)) ⟩ -α_s]_+,

for all  ℓ=1,2,⋯,m and s=1,2,⋯,D. In Eqs. (<ref>), ρ2n(n-1)ρ DB(B-1) is the normalized penalty factor, and the vector δ(π(i),π(j)) (δ_ℓ(π(i),π(j)))_1≤ℓ≤  m has the following elements

    δ_ℓ(π(i),π(j))1N∑_k=1^Ny_π(i)y_π(j)φ(x_π(i);ξ^k_ℓ)φ(x_π(j);ξ^k_ℓ),

and the features (y,x) and (ỹ,x̃) are sampled uniformly from the training data. Using the unbiased estimators of the sub-gradients, we provide a stochastic primal-dual (SPD) optimization procedure in Algorithm <ref>.







§ THEORETICAL RESULTS



In this section, we state our main theoretical results regarding the performance guarantees of the proposed kernel learning procedure. The proofs of theoretical results are presented in Appendix. Before we delve into the theoretical results, we state the main assumptions underlying our results. 

	
	The random feature maps are bounded, i.e., sup_x∈𝒳|φ_i(x,ξ)|≤ L, for all i=1,2,⋯,m.



	
	The base kernels are shift invariant, i.e., K_i(x,y)=K_i(x-y) for all i=1,2,⋯,m.



	
	The feature space 𝒳⊂^d has a finite diameter, i.e., diam(𝒳)sup_x,y∈𝒳x-y_2<∞.



































 §.§ Asymptotic normality and stochastic equicontinuity


In this part, we establish a few properties of the underlying U-statistics in this paper:

(Asymptotic Normality) 
	
Consider the i.i.d. random vectors z_i (y_i,x_i)∈𝒵=𝒳×𝒴, where z_1:n (z_1,⋯,z_n), (z_i)_1≤ i≤ n∼_i.i.d. P∈ℳ(𝒵), and define the following U-statistics

    U_λ(ψ_N,z_1:n)2n(n-1)∑_1≤ i<j≤ nexp(1λψ_N(z_i,z_j)),

where ψ_N(z_i,z_j)1 N⟨ y_iφ_ω(x_i), y_jφ_ω(x_j) ⟩. Let Ψ_N(z)_z̃∼ P[exp(1λψ_N(z,z̃))]. Then,

    √(n)(λlog  U_λ(ψ_N,z_1:n)-λlog_P^⊗ 2[U_λ])2Var^1 2[Ψ_N]d𝖭(0,λ^2_P^⊗ 2[U_λ]),

where d denotes the convergence in the distribution.


	The proof follows from <cit.> and subsequently applying the standard δ-method to λlog U_λ. For completeness, the proof is provided in Appendix <ref>. 


The next result is concerned with the stochastic equicontinuity of the U-statistics in Eq. (<ref>) which is formally defined below:

(Stochastic Equicontinuity)  	
Let {Q_n(θ):θ∈Θ,n∈} denotes a family of real-valued functions indexed by n, where (Θ,d) is any normed metric space. Then {Q_n}_n∈ is stochastically equicontinuous if for every ϵ>0, and η>0, there is a δ>0 such that

    limsup_n→∞(sup_θ∈Θsup_θ∈_δ(θ)|Q_n(θ)-Q_n(θ)|>ϵ)<η,

where _δ(θ){θ∈Θ: d(θ,θ)≤δ} is the ball of the radius δ.

The stochastic equicontinuity is a useful property as it can yield weak convergence. Moreover, the stochastic equicontinuity together with the pointwise convergence implies uniform convergence in probability to equicontinuous functions on a compact set. The following result establishes the stochastic equicontinuity of the U-statistic  in Eq. (<ref>) of Theorem <ref>:

(Stochastic Equicontinuity of the Kernel U-statistic) 
	
Suppose Assumptions <ref>-<ref> are satisfied. Consider the U-statistic U_λ(ψ_N,z_1:n) defined in Eq. (<ref>) of Theorem <ref>. Furthermore, consider the composite function class

    𝒢_m,N{ψ_N:𝒵×𝒵→:(z,z̃)↦ψ_N(z,z̃)=exp(1 N⟨φ_ω(z), φ_ω(z̃) ⟩), ω∈S_+^m,φ∈ℱ},
	
where z=(y,x), z̃=(ỹ,x̃), and φ_ω(z) (√(ω_i)yφ(x;ξ_i^k))_i=1,2,⋯,m^k=1,2,⋯,N. Moreover, ℱ is the following function class

    ℱ={φ:𝒳→: x↦φ_0(⟨x,ξ⟩+b ), ξ∈Ξ, b∈, φ_0∈Lip(1)},

where Lip(1) is the class of 1-Lipschitz functions. Then, with the probability of 1-δ, we have

    sup_g∈𝒢_m,N|U_λ(g,Z_1:n)-_P[exp(1λg(Z_1:n))]|=4√(⌈ n/2 ⌉)1δ∫_0^η√(2N(d+2)log(S(ϵ,λ)))dϵ,

where ηexp(L^2/λ), S(ϵ,λ)Klog (K/(λγ(ϵ) exp(-L^2/λ))^2) (λγ(ϵ) exp(-L^2/λ))^2, γ(ϵ)λ (ϵ)^1 r 2mexp(L^2/λ)L, and K=3e^2/(e-1)≈ 12.9008.


The proof is presented in Appendix <ref>.



We remark that the function class in Eq. (<ref>) of Theorem <ref> includes the random Fourier feature model of Rahimi and Recht <cit.> as a special case when φ_0(x)=cos(x). The stochastic equicontinutiy of Theorem <ref> makes no assumptions on the underlying distributions of variables ξ and b in the random feature model of Eq. (<ref>). Thus, it can be applied to base kernels whose distributions have with finite or infinite supports. In particular, the proof techniques of Theorem <ref> is based on empirical process theory and the Vapnik–Chervonenkis theory of function classes.



 §.§ Non-asymptotic consistency and the minimax rate


Recall the definition of the finite sample estimator H_n,N(λ;ω) from Equation (<ref>). Then, we observe that H_n,N(λ;ω)=λlog U_λ+λ r 2. Therefore, the asymptotic normality in Eq. (<ref>) of Lemma <ref> holds for H_n,N(λ;ω). In the next lemma, we provide the non-asymptotic consistency of the sample average approximations (SAAs). To describe the consistency of SAAs, we define


    T_ω(P)   _P^⊗ 2_μ_ω[y
    ỹφ(x;ξ)φ(x̃;ξ)]
    T_ω(P)   1N_P^⊗ 2[yỹ⟨φ_ω(x), φ_ω(x̃) ⟩].


From Lemma <ref>, we recall the following identities


    sup_ω∈S_+^mmin_λ∈_+H(λ;ω)   = sup_ω∈S_+^minf_P∈𝒫T_ω(P)
    sup_ω∈S_+^mmin_λ∈_+H_n,N(λ;ω)   =sup_ω∈S_+^minf_P^n∈𝒫^nT_ω(P^n),


Now, the following consistency result can be established:
(Non-Asymptotic Consistency of the Monte Carlo Samplings)	
	Suppose Assumptions <ref>-<ref> hold. Let 
	
    (ω_∗,P_∗^n)sup_ω∈S_+^minf_P^n∈𝒫^nT_ω(P^n),

 denotes the saddle point of the finite sample max-min optimization problem. Then, with the probability of (at least) 1-3ρ we have
 
    |sup_ω∈S_+^minf_P∈𝒫T_ω(P)-T_ω_∗(P_∗^n)|   ≤2KLn√(log(2× (16Ln)^mρ× K^m))+C^3K^2n^2
       +4√(2N(r+2ln(2)) L^4log(2× (16L^4)^mρ (2N(r+2ln(2))^m 2) )).
     


	The proof is presented in Section <ref> of the supplementary materials.


In the next theorem, we establish the minimax estimation rate of the weights of the mixture model in Eq. (<ref>). Formally, let K_1^m=(K_1,⋯,K_m) denotes the set of base kernels. Given a distribution from the distributional ball P∈𝒫, we  consider estimating the optimal weights ω given the i.i.d. training samples (y_i,x_i)_1≤ i≤ n∼_i.i.d. P. That is, we wish to estimate the map ω:𝒫→S_+^m defined by

	

    P   ↦ω(P)=max_ω∈S_m^+∑_i=1^mω_i_P^⊗ 2[yỹK_i(x,x̃)].
 

Given the training samples (y_i,x_i)_1≤ i≤ n, we denote an empirical estimator of the coefficients of the mixture model by ω_nω((y_i,x_i)_1≤ i≤ n). Recall the definition of the total variation (TV) metric d_TV:S_+^m×S_+^m→_+, (ω,ω_n)↦ d_TV(ω,ω_n)1 2ω-ω_n_1. The minmax rate or minimax rate of the empirical estimators is defined as the minimum TV distance between the best empirical estimator and the population estimator of Eq. (<ref>) over the worst case data distribution that is drawn from the distribution ball 𝒫, i.e.,

    R_n(𝒫)inf_ω∈S_m^+sup_P∈𝒫_P[d_TV(ω_n,ω)],

where the infimum is taken with respect to all admissible estimators ω_n.  In the following theorem, we characterize the minmax estimation rate of ω(P) in Eq. (<ref>) for the special case of the RBF kernels:
(The Minimax Estimation Rate) 
	
Suppose the base kernels are RBF, i.e., K_i=ψ_i(x-y_2) with the corresponding Schönberg measure ν_i for all i∈ [M]{1,2,⋯,M}, (cf. Definition <ref>). Furthermore, consider the restriction P(y)=Q(y) for the marginals, and assume that the distribution ball of the marginals 𝒫_± in Eq. (<ref>) contains the following normal distributions

	
    P_+   =𝖭(μ_+^P,σ^2I_d× d),      P_-=𝖭(μ_-^P,σ^2I_d× d),
    
    		Q_+   =𝖭(μ_+^Q,σ^2I_d× d),    Q_-=𝖭(μ_-^Q,σ^2I_d× d),


where Q_+⊗ Q_- is the center of the distribution ball 𝒫_± with the radius 2r. Furthermore, for some i,j∈ [M], suppose the inequalities J_k,d(∞)≤1 2J_i,d(τ_P) and J_ℓ,d(∞)≤1 2J_j,d(τ_Q) hold for all k∈ [M]\{i} and ℓ∈ [M]\{j}, respectively, where

    J_k,d(τ)   ∫_0^τt(1+4tσ^2)^(d+2)/2ν_k(dt),
and τ_Q1μ_+^Q-μ_-^Q_2^2-4σ^2 and τ_P1μ_+^P-μ_-^P_2^2-4σ^2. Then, the minimax rate of the empirical estimatiors is given by

    R_n(𝒫)≥18e^-nD_KL(P_+⊗ P_-||Q_+⊗ Q_-)≥18e^-nr.



	The proof is presented in Appendix <ref>.



Let us make a remark about the restrictions J_k,d(τ_P)≤1 2J_i,d(∞) and J_ℓ,d(τ_Q)≤1 2J_j,d(∞) in Theorem <ref> are sufficient conditions for the minimax inequality in Eq. (<ref>) of Theorem <ref>. Alternatively, we can obtain less obsecure conditions by obtaining a lower bound and an upper bound on the integral formula of Eq. (<ref>). To attain this objective, notice that the function t↦t (1+4tσ^2)^(d+2)/2 monotonically increases on the interval [0,1 2dσ^2] and then decreases on (1 2dσ^2, ∞), thus attaining its maximum at t=1 2dσ^2. Hence,

    J_k,d(∞)   ≤12dσ^2(1+(2/d))^(d+2)/2,    ∀ k∈{1,2,⋯,d}.

Similarly, a lower bound can be obtained as follows


    J_k,d(τ_P)   ≥sup_τ∈ (0,τ_P]ν_k([τ,τ_P]) τe(1-2 2+d)
       ≥ν_k([τ_P/2,τ_P]) τ_P2e(1-2 2+d),    ∀ k∈{1,2,⋯,d}.


where  ν_i([τ_0,τ_1])∫_τ_0^τ_1ν_i(ds). The sufficient condition J_i,d(∞)≤1 2 J_i,d(τ_P) for the minimax lower bound of Eq. (<ref>) now can be restated as follows


    ν_i([τ_P/2,τ_P])   ≥eτ_P(1-2 2+d)^-1·1dσ^2(1+(2/d))^(d+2)/2.
A similar inequality can be stated for J_j,d(∞)≤1 2 J_j,d(τ_Q).



 §.§ Distributionally robust generalization bounds


To obtain an out-of-sample generalization bound, we require the following notions of complexities of a function class:

(Rademacher and Gaussian Complexities)
	
	Given a finite-sample set S=(x_1,⋯,x_n), and function class ℱ consider the following random variable
	
    ℜ^n_S(ℱ)_P_ε[sup_f∈ℱ1n∑_i=1^nε_i f(x_i)|x_1,⋯,x_n].

	where ε (ε_1,⋯,ε_n) are i.i.d. Rademacher random variables, i.e., (ε_1,⋯,ε_n)_ ∼_i.i.d.P_ε=Uniform{-1, 1}, and P_ε=P_ε^⊗ n. The Rademacher complexity is then defined as the expected value of ℜ^n_S(ℱ) with respect to the observed samples, i.e., 
	
    ℜ^n(ℱ)_P_X[ℜ_S^n(ℱ)].

	Similarly, the Gaussian complexities 𝔊_S^n(ℱ) and 𝔊^n(ℱ) are defined by letting P_ε=𝖭(0,1) in Eqs. (<ref>)-(<ref>), respectively.



In the following proposition, we establish novel  upper bounds on the Rademacher and Gaussian complexities of the class of functions based on the mixture of random features:

(Upper Bounds on the Function Class Complexities)
	
	Consider the class of functions ℱ_m(R) defined as follows
	
    ℱ_m(R){f:^d→:x↦ f(x)=1√(N)β^Tφ_ω(x):β∈^2_r(0),ω∈S_m^+},

	where ^2_r(0)⊂^mN is the Euclidean ℓ_2-norm ball of radius r=R√(mN) centered at the origin, and φ_ω∈^mN is the concatenated random feature vector. Moreover, define the row matrix of the random feature maps as Φ(ω) (φ_ω(x_i))_1≤ i≤ n∈^n× mN. Then, the Rademacher complexity of the class ℱ_m(R) is 
	
    ℜ^n(ℱ_m(R))≤RnN√(192π m)Φ(ω)_2𝒬(-√(192 min{mN,n})),

	and the Gaussian complexity of the class ℱ_m(R) is 
    
    𝔊^n(ℱ_m(R))≤RnN√(π 2m)Φ(ω)_F𝒬(-√(n 4)),

	where 𝒬(x)1√(2π)∫_x^∞e^-x^2 2dx is the complementary error function.


	The proof is presented in Section <ref> of the supplementary material. 

Let us make some remarks about the implications of Proposition <ref>.

The proof techniques we used to establish the upper bound on the Rademacher complexity are novel and based on concentration inequalities for the quadratic forms. In particular, the proof does not rely on the Khintchin-Kahane type inequality which is a typical tool in the computation of the upper bounds on the Rademacher complexity; see, e.g.,  <cit.>,<cit.>. As shown in Appendix <ref>, the Khintchin-Kahane type inequality yields the following upper bound on the Rademacher complexity:

    ℜ^n(ℱ_m(R))≤RnN√(2344m)Φ(ω)_F.

Since 0<erfc(x)≤ 2 for all x∈, and Φ(ω)_2≤Φ(ω)_F for any feature matrix Φ(ω)∈^n× mN, the upper bound we established in Eq. (<ref>) is sharper than that of Eq. (<ref>). Similarly, the proof of the upper bound on the Gaussian complexity is based on the concentration of measure for χ^2 random variables.

To compute explicit bounds from the Rademacher and Gaussian complexities, we require upper and lower bounds on the matrix norms of the feature matrix Φ(ω). The following lemma provides a first step to characterize such a result:
(Uniform Concentration of the Spectra of Feature Matrices)
	
	Suppose Assumptions <ref>-<ref> holds. Consider the feature matrix Φ(ω)=(	φ_ω(x_i)))_1≤ i≤ n and the associated kernel matrix K(ω) (K_ω(x_i,x_j))_1≤ i,j≤ n. Then, the following concentration inequality holds
	
    (sup_ω∈S_m^+| K(ω) _2-1NΦΦ^T(ω)_2|≥δ)
       ≤  2^14(m^2n^2L^2δ^2)exp(6nlog 3 m+2)·exp(-cNδ^2 2n^2m(m+2)L^2),

where c>0 is a universal constant. In particular, 

    limsup_N→∞(sup_ω∈S_m^+| K(ω) _2-1NΦΦ^T(ω)_2|≥δ)=0.



	The proof is presented in Section <ref> of the supplementary materials.


Lemma <ref> suggests that the spectra of the feature matrix 1 NΦΦ^T(ω) uniformly concentrates around that of  the kernel matrix K(ω) at the rate of 𝒪(N^-1 2log(N)) as the number of random feature samples N tends to infinity. Consequently, to establish the spectral bound Φ(ω)_2, it suffices to establish the spectral bound for the kernel matrix. The asymptotic analysis of the  spectrum of the (radial) kernel matrices has been studied extensively in the random matrix literature; see, e.g., <cit.> for locally smooth kernel functions, and <cit.> for the non-smooth kernel functions. Those asymptotic results are universal and consequently do not impose any conditions on the distribution of feature vectors. In the sequel, we are concerned with the non-asymptotic results for the spectrum of the Gram matrices of the mixture kernels:

(Spectral Norm of the Translation Invariant Kernels)
	
	Suppose Assumptions <ref>-<ref> holds. Suppose the base kernels are centered and translation invariant in the sense that  K_i(x,x)=ψ_i(x-x)-ψ_i(0)1_{x=x} for all i=1,2,⋯,m. Then, with the probability of at least 1-ρ, we have that

    K(ω)_2≤ 2n√(1-1 n)+4√(ln4× 3^2nρ),

for all ω∈S_+^m.



	The proof is deferred to Section <ref> of the supplementary materials.

We remark that our non-asymptotic analysis of the spectrum of kernel matrices in Lemma <ref>  generalizes those of <cit.> that are established for the special cases of the Gaussian and polynomial kernels. Moreover, the spectral bounds in <cit.> are stated under the assumption that the features (x_i)_1≤ i≤ n are i.i.d. sub-Gaussian random variables. More specifically, the proof we present employs the decoupling technique from the random matrix theory <cit.> as well as a concentration of measure for Lipschitz functions of the Gaussian random variables. 































We now are in position to state the main result of this section which is a generalization bound for the risk function based on the Rademacher complexity of the class of function ℱ_m(R) defined by Eq. (<ref>):
(Distributionally Robust Generalization Bound)
	
	 Consider the function class ℱ_m(R) defined in Eq. (<ref>) mapping from 𝒳 to 𝒵. Let (x_i,y_i)_1≤ i≤ n∼_i.i.d. Q  denote the training data sampled from the joint probability distribution Q∈ℳ(𝒵). Suppose there exists a dominating  loss function in the sense that
	 
    ℓ(y,f(x))≤ℓ̃(y,f(x)),

	for all z=(y,x)∈𝒵=𝒴×𝒳, and all f∈ℱ_m(R) such that  ℓ̃(y,·):𝒳→𝒵 is L_ψ-Lipschitz with respect to the Euclidean norm defined on 𝒵. Then, for any integer n and any 0<δ<1, with probability at least 1-δ over samples of length n, every f in ℱ_R satisfies
	
    sup_P∈𝒫_P[ℓ(Y,f(X))]   ≤ 2
    	_Q^n[ℓ̃(y,f(x))]
       +2L_ψ Bℜ^n(ℱ)+B √(8ln(2/δ) n)+Br2,

where Bsup_(y,z)∈𝒴×𝒵ℓ̃(y,z), and 𝒫={P∈ℳ(𝒳×𝒴):D_KL(P||Q)≤ r, P≪ Q }.
	□


The proof is presented in Appendix <ref>.

Let us make two remarks about the distributionally robust generalization bound in Eq. (<ref>).  First, the result of Bartlett and Mendelson <cit.> regarding the standard generalization bound is as follows

    sup_P∈𝒫_P[ℓ(Y,f(X))]   ≤_Q^n[ℓ̃(y,f(x))]+2L_ψℜ^n(ℱ)+√(8ln(2/δ) n).

Therefore, for r=0, the bound in Eq. (<ref>) is not expected to be tight. Second, due to Theorem <ref>, the Rademacher complexity of the function class ℱ_m(ℛ) in the generalization bound of Eq. (<ref>) can be related to the spectral norm of the kernel matrix via the following inequality

    ℜ_n(ℱ_m(R))≤2RnD√(192π N m)(K(ω)_2+𝒪(m√(N)) )^1 2,

where the upper bounds on the spectral norm of the mixture kernel matrix K(ω)_2 are established in Lemmas <ref>.



§ EMPIRICAL EVALUATION: PERTURBATION OF INPUT FEATURES








 §.§ Synthetic data-set

For the numerical experiments with the synthetic data, we adapt the model of <cit.>. In particular, we generate synthetic i.i.d. data (x_i,y_i)_1≤ i≤ n∼_i.i.d. Q whereby (x_1,⋯,x_n)∼_i.i.d.𝖭(0,I_2× 2) with the class labels y_i=sgn(x_i_2-√(2)),i=1,2,⋯,n. To
widen the separating margin of the two classes, we remove data points whose norms falls inside the interval x_i_2∈ (√(2)/1.3,1.3√(2)). To train the mixture of the base kernels, we consider a set of radial Gaussian kernels K_i(x,x)=exp(-γ_ix-x_2^2), with the bandwidth parameters γ_i∈{0.5,1,1.5,⋯,9.5,10}.
 
 
 In Figure <ref>(a), we illustrate the decision boundaries of the kernel SVM with the radius r=0.01 (dash-dot line) and r=100 (dash line). Clearly, for a larger radius, the decision boundary is pushed outward. This observation is in line with the one that is made in <cit.>. Namely, since 70% of data is accumulated in the inner region x_i_2≤√(2)/1.3, to incur the maximum classification error, an adversery pushes the features in the region x_i_2≤√(2)/1.3 outwards close to the boundaries of x_2=1.3/√(2). For a reference, in Figure <ref>(b), we also show the decision boundary of the kernel SVM, when the kernels are mixed uniformly, i.e., ω=1/m.  In Figures <ref>(a) and <ref>(b), the level sets of the deicision function
 
    x↦Ψ(x)sgn(ω_0+∑_i=1^n-1ω_iy_iK(x,x_i)),

 for r=0.01 and r=100 are shown, respectively, where sgn(·) is the sign function. Clearly, increasing the radius of the distribution ball 𝒫 changes the decision boundaries of the resulting predictor.
 
 
 

 §.§ MNIST data-set
 We apply our robust optimization method to the adversarial perturbations of the out of sample (test) data of a model trained on the MNIST data-set.[The Jupyter notebook of our Python 3 codes for this experiment is available in the Github repository: <https://github.com/mbadieik/Adversarial-MKL>] All computations of this part were performed on a DGX Station from NVIDIA running Linux operating system with an Intel Xeon E5-2698 v4 2.2 GHz (20-Core) CPU and two of four total Tesla V100 GPUs (32 GB memory for each GPU). We present our results for the robust classification of images from MNIST databases <cit.>. We use Pytorch in Python 3.5. We first train a convolutional neural network (CNN) to extract features of input images on unmodified training data-set, and use the extracted features for classification with kernel SVM. The trained CNN has two convolutional layers followed by the max pooling layer. The archtiecture of our CNN is as follows:

	
  * Convolutional: Output Channel: 32, Kernel size: 3× 3,  Activation: ReLU,  Max Pooling: 2× 2,
	
	
  * Convolutional: Output Channel 16, Kernel size: 3× 3,  Activation: ReLU,  Max Pooling: 2× 2,

    
  * Fully connected: Input: 5× 5× 32,  Output:100, Activation: ReLU,
    
    
  * Kaiming Initialization <cit.>,
    
    
  * Fully connected: Input: 100,  Output:10, Activation: ReLU.

 To train the CNN, we split the data-set into 60,000 training data and 10,000 test data points. We use a binary cross entropy loss function in conjunction with the SGD with the momentum 0.9 and the learning rate 0.01 for the optimization of the loss. 
 
 
 
 

 §.§ Adversarial models
 In the sequel, we briefly review the adversarial models we consider in this paper. The adversarial models in the sequel are primarily devised to test the robustness of the end-to-end deep neural networks. Nevertheless, since the features for the downstream kernel SVM are extracted from the penultimate layer of a CNN— before the soft-max output layer— these adversarial models are also useful tools to systematically perturb the extracted features in order to examine the robustness of the learned kernel mixture model using Algorithms <ref> and <ref>. 
 









  §.§.§ Fast Gradient Signed Method (FGSM)  <cit.>
  This method was proposed to improve the robustness of a neural network model against input purturbations. Specifically, given a loss function ℓ((x,y);θ) for deep neural networks with the weights θ, the i-th out-of-sample feature vector is perturbed by the additive noise x̃_i=x_i+Δx_i(θ), where Δx_i(θ) is the maximal perturbation computed via the following optimization problem

 
    Δx_i(θ)   = min_n:n_∞≤ϵℓ(x_i+n,y_i;θ)
       =-ϵ·sgn(∇_xℓ(x_i,y_i;θ)^T·n).


where sgn(·) is the sign function, and the parameter ϵ>0 determines the amount of the adverserial perturbations. 
  
 

  §.§.§ Projected Gradient Method (PGM) <cit.>
 This method is an iterative approach to compute the adversarial peturbations. The PGM augments the stochastic gradient steps for the parameter θ with the projected gradient ascent over x↦ℓ(x,y;θ), where
 
 
    Δx^t+1_i(θ)   =max_n:n_p≤ϵ∇_xℓ(x_i,y_i;θ)^T·n
    x_i^t+1   =𝒫__ϵ^p(x^t_i)(x_i^t+α_tΔx^t+1_i(θ) ),    t=1,2,⋯,T_adv,


where η_t is the step-size (learning rate), 𝒫(·) is the Euclidean projection, and _ϵ^p(x^t_i){x∈^n: x-x^t_i_p≤ϵ} is the p-norm Euclidean ball of the radius ϵ centered at x_i^t. 



  §.§.§ Decoupled Direction and Norm Perturbation (DDN) <cit.>
 This method induces misclassification with low L_2 norm. This advarserial model optimizes the cross entropy loss, and instead of penalizing the norm in each iteration, projects the perturbation onto a L_2-sphere centered at the original image. In particular, the following iterative method is used


    x̃^t   =x+η^tδ^tδ^t_2,
    δ^t   =δ^t-1+α m ∇_xℓ( x^t-1,y;θ) ∇_xℓ( x^t-1,y;θ)_2,


where α>0 and η^t>0 are fixed and time-varying step-sizes, and m is a parameter taking the value of m=-1 for a targeted attack and m=1 otherwise. 



  §.§.§ Carlini and Wagner (C&W) Method <cit.>
 The C&W L_2 model minimizes two criteria at the same time: the perturbation that makes the sample adversarial, and the L_2 norm of the perturbation. Instead of using a box-constrained optimization method, they propose changing variables using the tanh function, and instead of optimizing the cross-entropy of the adversarial example, they use a difference between logits. For a targeted attack aiming to obtain class j, with Z(·) denoting the model output before the softmax activation (logits), it optimizes:

    min_δ∈x-x̃(δ)_2^2+Cf(x̃(δ)),

where


    f(x̃(δ))   max{max_i≠ j{Z(x̃(δ))_i}-Z(x̃(δ))_j,-ϵ},
    x̃(δ)   12(tanh(arctan(x)+δ)+1).

 
In Equation (<ref>), ϵ is the confidence parameter. The larger ϵ, the adversarial sample will be misclassified with higher confidence. Moreover, Z(x̃)_i denotes the logit corresponding to the ith class label. To use this model in the untargeted settings, the definition of f is modified to 

    f(x̃(δ))=max(Z(x̃(δ))_y-max_i≠y{Z(x̃(δ))_i},-ϵ).





 §.§ Alternative MKL methodologies


We compare our method with the following traditional MKL learning paradigms for classfication of the standard test datasets:



  * AverageMKL: simple average of base kernels  <cit.>, 


  * EasyMKL: fast and memory efficient margin-based combination <cit.>, 


  * GRAM: radius/margin ratio optimization  <cit.>, 


  * MEMO: margin maximization and complexity minimization <cit.>, 


  * RMKL: margin and radius based multiple kernel learning <cit.>, 


  * FHeuristic: heuristic based on kernels alignment  <cit.>, 


  * CKA: centered kernel alignment <cit.>,


  * PWMK: heuristic based on individual kernels performance <cit.>.


We implement these methods by leveraging the MKLpy library <cit.>.[<https://pypi.org/project/MKLpy/>] For GRAM, MEMO, and RMKL, we select the step-size (learning rate) of η=0.1, and the number of iterations T=500. For EasyMKL,  the regularization parameter of λ=0.1 is adapted in MKLpy library which we also use in our experiments.



 §.§ Numerical results
  In Table <ref>, we tabulate the test error of different MKL paradigms for different parameteres ϵ∈{0,0.1,⋯,0.9} of the adverserial models. For PGM model, we use the step-size α_t=2/255 and T_adv=40 iterations. For Algorithm <ref>, we use the step-sizes of β=0.7 for the primal and η=0.3 for the dual vectors. We also use T=200 iterations without applying any stopping criterion. In addition, our simulations are reported for the batch size of B=200. To train the kernel in kernel SVMs, we only use a fraction of training data-set (1000 training samples out of 60,000), while the test is performed on the entire test data-set of 10000 samples. The reduction of the size of training data-set is due to the fact that certain MKL methods, such as CKA or GRAM, scale poorly to large training data-sets, and to include these methods in our comparision, we had to use a smaller number of training data samples. In our experiments with Algorithm <ref>, we leverage a distributional ball with the radius R=0.1 which has shown a good performance on the MNIST data-set.

From Table <ref>, we osberve that increasing ϵ degrades the accuracy of CNN significantly on FGSM, and PGM model, while it increases the accuracy of C&W model. The accuracy of DDN is independent of the parameter ϵ, and remiains the same throughout the experiments. For ϵ=0, FGSM and PGM return the unperturbed test data, and clearly the accuracy of CNN is higher than that of kernel methods (%88 versus %82). The fact that a deep neural network outperforms the kernel SVMs is natural since the size of the training data for training deep neural network is large (60,000), and end-to-end classification methods outperform alternative machine learning paradigms. Although for ϵ>0, the extracted features feeded to the downstream classifier is similarly perturbed in CNN and kernel SVMs, there is a significant performace degradation of the CNN model under PGM and FGSM attack models compared to that of the kernel SVM. This is due to the fact that these adversarial models are devised to particularly attack end-to-end DNNs and as such they are less effective on kernel SVMs.  From Table <ref>, we also observe that our MKL training achieves a better accuracy on the perturbed test data-set for all range of ϵ∈{0.1,⋯,0.9}, thus validating our MKL approach.




			
	






































































































































































































































































































































































































































































































































































































§ DISCUSSION AND CONCLUDING REMARKS




In this paper, we have proposed a novel multiple kernel learning approach that is certifiably robust against adverserial examples. In particular, we proposed a distributionally robust optimization with respect to KL divergence. We characterized the distributionally robust optimization problem as a minimax vector optimization. We then proposed a biased stochastic primal-dual (SPD) algorithm. To debias the SPD, we used a Gumbel max perturbation technique to estimate the log-sum expression in the objective function. We provided theoretical performance guarantees for the proposed SPD algorithms. In particular, we established non-asymptotic consistency and asymptotic normality of the Monte Carlo sample average approximation associated with the empirical loss function. We also proved a min-max lower bound for the estimation problem associated with the weights of the mixture kernel model. Moreover, we proved a novel distributionally robust generalization bound based on the notion of the Rademacher and Gaussian complexities of a function class. We also derived upper bounds on the Rademacher and Gaussian complexity of function classes that are expressed in terms of random features which are tighter than previous known bounds in the MKL literature. To validate our proposed multiple kernel learning technique, we applied our method to synthetic and MNIST benchmark data-sets. Our numerical results shows that the learned kernels using our method is indeed robust to ℓ_2 PGM perturbations compared to the standard multiple kernel learning approaches in the litearture. 





§ 




Notation and definitions. We denote the vectors by bold small letters, e.g. x=(x_1,⋯,x_n)∈^n, and matrices by the bold capital letters, e.g., M=[M_ij]∈^n× m. The unit sphere in n-dimensions centered at the origin is denoted by S^n-1= {x∈^n:∑_i=1^nx_i^2=1 }. We denote the n-by-n identity matrix with I_n, and the vector of all ones with 1_n=(1,1,⋯,1)∈^n. For a symmetric matrix M=[M_ij]∈^n× n, let M_2=sup_x∈S^n-1⟨x,Mx⟩ and M_F=√(Tr(MM^T))=√(∑_i,j=1^n|M_ij|^2) denotes the spectral and Frobenius norms, respectively. The eigenvalues of the matrix M are ordered and denoted by λ_1(M)≥⋯≥λ_n(M). We alternatively write λ_min(M)=λ_n(M) and λ_max(M)=λ_1(M) for the minimum and maximum eigenvalues of the matrix M, respectively. 




















(Orlicz Norm)
	
	The Young-Orlicz modulus is a convex non-decreasing function ψ:_+→_+ such that ψ(0)=0 and ψ(x)→∞ when x→∞. Accordingly, the Orlicz norm of an integrable random variable X with respect to the modulus ψ is defined as
	
    X_ψinf{β>0:[ψ(|X|β)]≤ 1}.



In the sequel, we consider the Orlicz modulus ψ_ν(x)exp(x^ν)-1 . Accordingly, the cases of ·_ψ_2 and ·_ψ_1 norms are called the sub-Gaussian and the sub-exponential norms and have the following alternative definitions:



(Sub-Gaussian Norm)
	The sub-Gaussian norm of a random variable Z, denoted by Z_ψ_2, is defined as
	
    Z_ψ_2= sup_q≥ 1 q^-1/2(|Z|^q)^1/q.

	For a random vector Z∈^n, its sub-Gaussian norm is defined as 
	
    Z_ψ_2=sup_x∈S^n-1⟨x,Z⟩_ψ_2.




(Sub-exponential Norm)
	
	The sub-exponential norm of a random variable Z, denoted by Z_ψ_1, is defined as follows
	
    Z_ψ_1=sup_q≥ 1 q^-1([|Z|^q])^1/q.

	For a random vector Z∈^n, its sub-exponential norm is defined as 
	
    Z_ψ_1= sup_x∈S^n-1⟨Z,x⟩_ψ_1.



We use asymptotic notations throughout the paper. We use the standard asymptotic notation for sequences. If a_n and b_n are positive
sequences, then a_n=𝒪(b_n) means that limsup_n→∞ a_n/b_n< ∞, whereas  a_n = Ω(b_n) means that
liminf_n→∞ a_n/b_n > 0. Furthermore, a_n=𝒪(b_n) implies a_n=𝒪(b_npolylog(b_n)). Moreover a_n=o(b_n) means that lim_n→∞a_n/b_n=0 and a_n=ω(b_n) means that lim_n→∞ a_n/b_n=∞. Lastly, we have a_n=Θ(b_n) if a_n=𝒪(b_n) and a_n=Ω(b_n). 



 §.§ Proof of Lemma <ref>



The proof is a small adaptation of the robust optimization methods of <cit.> for the functional optimization problem in Eq. (<ref>). We present the proof for completeness. First, consider the Lagrangian form of the functional optimization problem in Eq. (<ref>),

	

    max_L∈𝕃(Q)_Q^⊗ 2[ Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)-λ( Llog L- r/2 ) ]
       s.t.: _Q^⊗ 2[L]=1,


where 𝕃(Q){L∈𝕃(Q):L≥ 0, a.s.}. Now, consider the following functionals 


    F[L(x,y)]   _Q^⊗ 2[Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)-λ(Llog L-(r/2))],
    
    G[L(x,y)]   _Q^⊗ 2[L]-1.


The functionals F(L) and G(L) are convex and linear in L, respectively. Therefore, we can calculate the directional derivative of F[L(x,y)] in the direction U(x,y) as below

    D_U(F)[L]   lim_t→ 0F[L(x,y)+tU(x,y)]-F[L(x,y)]t
       =lim_t→ 0(_Q^⊗ 2[(L+tU)yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)-α (L+tU)log(L)]t
       -_Q^⊗ 2[Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)-α L log (L)]t)
       =_Q^⊗ 2[Uyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)]
       -λlim_t→ 0_Q^⊗ 2[(L+tU)log(L+tU)-Llog Lt].

Note that the function ylog y is convex in y in _+. Therefore, for any y and direction u, the function [((y+tu)log(y+tu)-ylog y)/t] is monotone in t. Therefore, by the monotone convergence theorem <cit.>, we can interchange the order of the expectation and the limit. We then obtain

    D_U(F)[L]   =_Q^⊗ 2[Uyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)]
       -λ_Q^⊗ 2[lim_t→ 0(L+tU)log(L+tU)-Llog L t]
       =_Q^⊗ 2[Uyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)]-λ_Q^⊗ 2[(log(L)+1)U].

Similarly, the directional derivative of G[L] is given by

    D_U(G)[L]=_Q^⊗ 2[U].

We now consider the Lagrangian form of the functional optimization problem in Eq. (<ref>) if  

    ℒ[L](λ)=   _Q^⊗ 2[Lyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)-λ(Llog(L)-(r/2))]
       +α (_Q^⊗ 2[L]-1).
 
Due to  the result of Bonnas and Shapiro <cit.>, L^∗ is an optimal solution of Problem (<ref>) if L^∗∈𝕃(Q), _Q^⊗ 2[L^∗]=1, and 

    L^∗∈argmax_L∈𝕃(Q)ℓ(L,λ^∗).

This is an unconstrained optimization problem whose directional derivative is given by

    D_U(ℒ)[L](λ)=_Q^⊗ 2[Uyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ)-λ(log(L)+1)U+α U].

Therefore, the optimal solution has the following form

    L^∗(α)=exp(α-λλ)·exp(1λ yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ) ).

Now, suppose that the Lagrange multiplier belongs to the following set 

    λ∈Λ{s∈: s>0,_Q^⊗ 2[exp(yỹs∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ))]<+∞}.

Then, by choosing the Lagrange multiplier 

    α^∗=-λlog_Q^⊗ 2[exp(yỹλ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ))]+λ,
 
the feasibility constraint _Q^⊗ 2[L^∗]=1 is satisfied. Plugging α^∗ into Eq. (<ref>) yields

    L^∗=L^∗(λ^∗)=exp(1λyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ) )_Q^⊗ 2[exp(1λyỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ))].

The pair (λ^∗,L^∗) satisfies Bonnas and Shapiro optimality criterion. Now, plugging L^∗ into yields the following value function

    max_L∈𝕃^Q: _Q^⊗ 2[L]=1 F[L(x,y)]=λlog_Q^⊗ 2[exp(yỹ∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ))]+λ r 2.

To complete the proof, we note that due Assumption <ref>, we have that for any s>0,

    _Q^⊗ 2[exp(yỹs∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ))]   =_Q^⊗ 2[exp(yỹms∑_i=1^mω_iK_i(x;x̃))]
       ≤_Q^⊗ 2[exp(|yỹms∑_i=1^mω_iK_i(x;x̃)|)]
       ≤exp(B/s).
 
Thus, as long as s>0, we have that  

    _Q^⊗ 2[exp(yỹs∫_Ξφ(x;ξ)φ(x̃;ξ)μ_ω(dξ))]<+∞.

Hence, Λ=_+\{0}.




 §.§ Proof of Lemma <ref>



The proof is a minor adaptation of <cit.>. We present the proof for completeness.  We first establish the asymptotic normality of the following U-statistic

    U_λ(ψ_N,z_1:n)2n(n-1)∑_1≤ i<j≤ nexp(1λψ_N(z_i,z_j)).

Let Ψ_N(z_i,z_j)exp(1λψ_N(z_i,z_j)). Consider the following projection functions:

    Ψ_N^1(z_1)   =[Ψ_N(z_1,z_2)|z_1],  Ψ_N^1(z_1)=Ψ_N^1(z_1)-[Ψ_1^N]
    Ψ_N^2(z_1,z_2)   =[Ψ_N(z_1,z_2)|z_1,z_2],   Ψ^2_N(z_1,z_2)=Ψ^2_N(z_1,z_2)-[Ψ_2^N].

The Hoeffding's canonical terms are defined as follows

    g_N^1(z_1)   =Ψ_N^1(z_1)
    
    g_N^2(z_1,z_2)   =Ψ_N^2(z_1,z_2)-g_N^1(z_1)-g_N^2(z_2).

The kernel Ψ can be written as the sum of canonical terms

    Ψ_N(z_1,z_2)- [Ψ_N(z_1,z_2)]=g_N^1(z_1)+g_N^1(z_2)+g_N^2(z_1,z_2).

All the canonical terms in Equation (<ref>) are un-correlated. Hence, we
have:

    Var[Ψ_N(z_1,z_2)]=2[g_N^1(z_1)]+[g_N^2(z_1,z_2)].

The U-statistics can also be written as follows

    U_λ(ψ_N,z_1:n)-[U_λ]   =2n(n-2)∑_1≤ i<j≤ n(Ψ_N(z_1,z_2)-Ψ_N)
       =2n(n-1)((n-1)∑_i=1^ng_N^1(z_i)+∑_1≤ i<j≤ ng_N^2(z_i,z_j)).

We define the leading term of Eq. (<ref>) as the Hájek projection

    U_λ(ψ_N,z_1:n)2n∑_i=1^ng_N^1(z_i).

Note that Var(U_λ(ψ_N,z_1:n))=4 nVar(Ψ_N(z_1)). Since the Hájek projection is the average of the independent and identically distributed terms, by the Lindeberg-Lèvy Central Limit Theorem (CLT), we obtain

    √(n)U_λ(ψ_N,z_1:n)2Var^1 2(Ψ_N(z_1))d𝖭(0,1).

In the sequel, we prove that the reminder term converges to zero in probability, i.e.,

    limsup_n→∞(|U_λ-[U_λ] -U_λ4Var(Ψ_N(z_1))|≥δ)=0,  ∀δ >0.

Notice that

    [(U_λ-[U_λ]-U_λ)^2]   =2n(n-1)[(g^2_N(z_1,z_2))^2]
       ≤4n^2[(g^2_N(z_1,z_2))^2]
       ≤4n^2Var[Ψ_N].

Now, Var[Ψ_N] is bounded from above for λ>0, since ψ_N(z_i,z_j)=1 N⟨ y_iφ(x_i;ξ) ,y_jφ(x_j;ξ) ⟩ is bounded. Therefore,

    [(U_λ-[U_λ]-U_λ)^2]Var[Ψ_N]≤4 n^2Var[Ψ_N]4 nVar[Ψ_N]=1n→ 0,  as n→∞.

Applying the standard δ-method to λlog U_λ completes the proof.




 §.§ Proof of Theorem <ref>



We leverage the methods of the empircal process theory <cit.> to establish the stochastic equicontinuity of the underlying U-statistics. Let (ℱ,·) be a subset of a normed space of real functions f:𝒳→ on some
set 𝒳. Typically, the underlying normed space is the L_r(P)-space associated with the probability measures P∈ℳ(𝒳), equipped with the following norms:


    f_L_r(P)   (∫_𝒳f^r(x)P(dx))^1 r,
    f_L_∞(P)   sup_x∈supp(P)|f(x)|.


For a function f∈ℱ from the function class ℱ, we define 


    ℙf    _P[f(X)], 
    ℙ_nf    1n∑_i=1^nf(X_i),    X_1,⋯,X_n∼_i.i.d. P.


Furthermore, 𝔾_nf √(n)(ℙ_n-ℙ)f. Then (𝔾_nf)_f∈ℱ is an empirical process indexed by ℱ endowed with the norm 𝔾_nf _ℱ=sup_f∈ℱ|𝔾_nf|.

(ε-Bracket) Given two functions l(·) and u(·), the bracket [l,u] is the set of functions f∈ℱ with l(x)≤ f(x)≤ u(x) for all x∈𝒳. An ϵ-bracket is a bracket with l-u_L_r(P)≤ϵ.


(Bracketing, Covering, and Packing Numbers)  The bracketing number, denoted by 𝒩_[](ε, ℱ,L_r(P)), is the minimum number of ε-brackets required to cover ℱ. The covering number 𝒩(ε,ℱ,L_r(P)) is the minimum number of balls ^r_ε(f_i){f∈ℱ:f-f_i_L_r(P)≤ε} of radius ε, f_i∈ℱ needed to cover the set ℱ. The packing number ℳ(ε,ℱ,L_r(P)) is the largest number such that there exist functions f_1,⋯,f_ℳ∈ℱ satisfying f_i-f_j_L_r(P)≥ε, i≠j.



It is well-known that for an arbitrary function class ℱ, the ϵ-bracketing number is an upper bound for the ϵ-covering number, i.e.,

    𝒩(ε,ℱ,L_r(P))≤𝒩_[](2ε,ℱ,L_r(P)).
 
Indeed, if f∈ℱ is the 2ϵ-bracket [l,u], then it is also in the metric ball _r^ϵ((l+u)/2){f∈ℱ:f-(l+u)/2_L_r(P)≤ϵ}. In addition, the following inequalities hold between the covering and packing numbers

    ℳ(2ε,ℱ,L_r(P)) ≤𝒩(ε,ℱ,L_r(P))≤ℳ(ε,ℱ,L_r(P)).




The following result, due to Khosravi, et al. <cit.> characterizes a concentration result for the U-statistics using the empirical process theory:

(Stocahstic Equicontinuity with the Bracketting Integral, <cit.>)

	Consider a function space ℱ of symmetric functions from some data space 𝒵^s to , and consider a U-statistc of the order s, with the kernel f over n samples:
	 
    U_s(f,z_1:n)=1n  s∑_1≤ i_1≤ i_2≤⋯≤ i_s≤ nf(z_i_1,⋯,z_i_s).

Suppose sup_f∈ℱf_L_2(P)≤η, sup_f∈ℱf_L_∞(P)≤ G, and let κ_0=n/s. Then for κ_0≥G^2log N_[](1/2,ℱ,·_P,2) with the probability of at least 1-δ we  have

    sup_f∈ℱ|U_s(f,Z_1:n)-[f(Z_1:n)]|
       =𝒪(inf_ρ>01√(κ_0)∫_ρ^2η√(log(𝒩_[](ϵ,ℱ,L_2(P))))dϵ+η√(log(1/δ)+loglog(η/ρ)κ)+ρ).

□

To obtain a bound based on Lemma <ref>, the bracketing number 𝒩_[](ϵ,𝒢_mN,L_2(P)) as well as the constants η and G must be calculated, where 𝒢_mN is the function class defined in Eq. (<ref>). Nevertheless, the computation of the ϵ-bracketing number 𝒩_[](ϵ,ℱ,L_2(P)) is not readily amenable to the underlying composite class 𝒢_mN in Theorem <ref>. To alleviate this issue, we establish the following alternative bound based on the Dudley's metric entropy integral. The proof is  postponed to Appendix <ref>:
(Stocahstic Equicontinuity with the Metric Entropy Integral)
	
	Consider a function space ℱ of symmetric functions from some data space 𝒵^s to , and consider a U-statistc of the order s, with the kernel f over n samples defined in Equation <ref> of Lemma <ref>.  Suppose  and let κ=⌈ n/s⌉=⌈κ_0⌉. Furthermore, suppose
	
    δsup_f,g∈ℱf-g_L_2(P)<+∞.
	
	Then, with the probability of at least 1-ϱ we have
	
    sup_f∈ℱ|U_s(f,Z_1:n)-[f(Z_1:n)]|≤1ϱ4√(κ)∫_0^δ/2√(log𝒩(ϵ,ℱ,L_2(P)))dϵ.



The proof of Lemma <ref> relies on the standard chaining argument similar to <cit.>. However, the proof is different from <cit.> in that we leverage a symmetrization approach to attain the metric entropy integral term. In addition,  in light of Inequality (<ref>) in Remark <ref>, the bound in Eq. (<ref>) of Lemma <ref> can be potentially tighter than that of Eq. (<ref>) in Lemma <ref>.


(Growth function, VC dimension, Shattering,<cit.>) Let ℱ denote a class of functions from 𝒳 to {0, 1} (the hypotheses, or the classification rules). For any non-negative integer m, we define the growth function of ℋ as follows
	
    Π_ℱ(n) max_x_1,⋯,x_n∈𝒳 |(f(x_1),⋯,f(x_m)): f ∈ℱ|.

	If |(f(x_1),⋯,f(x_n)): f ∈ℱ|= 2^n, we say ℱ shatters the set {x_1,⋯,x_n}. The Vapnik-Chervonenkis dimension of ℱ, denoted by dim_VC(ℱ), is the size of the largest shattered set, i.e., the largest n such that Π_ℱ(n)=2^n. If there is no largest n, we define dim_VC(ℱ) = ∞.


We also define the following generalization of VC dimension: 
(Pollard's Pseudo-dimension, <cit.>) 
	Let ℱ denote a class of real-valued functions mapping 𝒳 to _+. Consider the function class 𝒢 defined as follows
	
    𝒢{g:𝒳×→{0,1}:x↦𝕀_{f(x)≥ c}, f∈ℱ,c∈}.

	Then, the Pollard's pseudo-dimension is defined as follows
	
    dim_P(ℱ)dim_VC(𝒢).





For any function class ℱ, let F(x)sup_f∈ℱ|f(x)| denotes the envelop function. Suppose F_L_r(P)≤∞. Then, there is a universal constant K such that for any ϵ>0 and r≥ 1, the following inequality holds

    sup_P∈ℳ(𝒳)𝒩(ϵF_L_r(P),ℱ,L_r(P))≤(Klog (K/ϵ^r)ϵ^r)^dim_VC(ℱ)≤(K'ϵ)^r(dim_VC(ℱ) -1)+δ,

for all  δ>0, where K=3e^2/(e-1)≈ 12.9008.  Alternatively,

    sup_P∈ℳ(𝒳)𝒩(ϵF_L_r(P),ℱ,L_r(P))≤K̃dim_VC(ℱ) (4e)^dim_VC(ℱ)(1ϵ)^r (dim_VC(ℱ) -1),

for some universal constant K̃. Inequality <ref> is due to Dudley <cit.>, and Inequality <ref> is due to Haussler <cit.>.




For any function class ℱ, clearly we have dim_VC(ℱ) ≤dim_P(ℱ). 


The following lemma is proved in Appendix <ref>:
(ϵ-Covering Number of the Composite Class) 
	
Consider the function class ℱ of real valued functions on 𝒳 , and let ψ:→_+ denotes a L_ψ-Lipschitz function satisfying |ψ(s)-ψ(s̃)|≤ L_ψ|s-s̃|,   ∀ s∈𝒮 where 𝒮⊂ is a compact domain. Let 

    ℱ'{g:(𝒳×𝒴)^2→   :(x,y),(x̃,ỹ)↦ψ(yỹ1 N∑_k=1^N∑_i=1^mω_i f_i^k(x)f^k_i(x̃))
    
        : f_i^k∈ℱ, ∀ i∈ [m],∀ k∈ [N],∀ω∈S^+_m},

denotes the composite class on 𝒳×𝒴 equipped with the measure P∈ℳ(𝒳×𝒴) with the marginal Q∈ℳ(𝒳). Then, the ϵ-covering entropy of the composite class ℱ' is bounded from above as follows

    log𝒩(ϵ,ℱ',L_r(P))≤ Nmlog𝒩((ϵ)^1 r2mL_ψF_L_2r(Q),ℱ,L_2r(Q)),

where F is the envelop function associated with the function class ℱ. □



Now, let ψ(ξ)=exp(1λξ) for λ>0. Due to Assumption <ref>, we have that 

    1N|⟨ yφ_ω(x), ỹφ_ω(x̃) ⟩|   =1N|∑_i=1^m∑_k=1^Nω_iφ(x;ξ_i^k)φ(x̃;ξ_i^k)  | 
       ≤ L^2,   ∀ (x,y),(x̃,ỹ)∈𝒳×𝒴.

Thus, the function ψ(ξ) with ξ=1 N⟨ yφ_ω(x), ỹφ_ω(x̃) ⟩ is Lipschitz with the constant L_ψ=exp(L^2/λ)/λ.
Therefore, using Inequality <ref> of Lemma <ref>, we obtain

    𝒩(ϵ,𝒢_N,m,L_r(P))≤(𝒩(λ (ϵ)^1 r 2mexp(L^2/λ) F_L_2r(Q),ℱ,L_2r(Q)))^Nm,

where ℱ is the function class defined in Theorem <ref>. To compute a bound on the covering number 𝒩(ϵ',ℱ,L_2r(Q)), we leverage the fact that φ(x;ξ_i^k)=φ_0(⟨x,ξ_i^k⟩+b_i^k), where b_i^k∈ and ξ_i^k∈^d is bounded from above by L (cf. Assumption <ref>). Therefore, the constant function F(x)=L for all x∈𝒳 is an envelop for the function class ℱ with F_L_2r(Q)=L. We can then simplify the upper bound in Eq. (<ref>) as follows

    𝒩(ϵ,𝒢_N,m,L_r(P))≤(𝒩(ϵ',ℱ,L_2r(Q)))^Nm,
 
where ϵ'λ (ϵ)^1 r 2mexp(L^2/λ)L. Moreover, since x↦φ_0(x) is 1-Lipschitz, we have the following inequality

    𝒩(ϵ',ℱ,L_2r(Q))≤𝒩(ϵ',ℒ,L_2r(Q)).

where ℒ is the class of linear functions

    ℒ{ f:^d→:x↦⟨x,ξ⟩+b: ξ∈^d,b∈}.

To compute a bound on 𝒩(ϵ',ℒ, L_2(P)), we leverage Remarks <ref> to obtain

    𝒩(ϵ',ℒ,L_2(P))≤(Klog (K/ϵ'^2)ϵ'^2)^dim_VC(ℱ').

Moreover, dim_VC(ℒ)=dim_VC(sgn(ℒ)), where sgn(ℒ)={sgn(f):f∈ℒ} and sgn(·) is the sign function. Therefore, we can alternatively focus on the following function class

    sgn(ℒ)= { f:^d→:x↦[⟨x,ξ⟩+b]_+: ξ∈^d,b∈},

where [u]_+max (u, 0). 
We now invoke the following result from the convex geometry:
(Radon's Theorem, <cit.>) 
		
	A set 𝒜⊂^m of m+2 points can be partitioned into two disjoint sets 𝒜_1 and 𝒜_2, such that
	
    Convex(𝒜_1)∩Convex(𝒜_2)≠∅,

	where Convex(𝒜_i) denotes the convex hull of the set 𝒜 defined as follows
	
    Convex(𝒜_i){∑_k=1^|𝒜_i|λ_kx_k: ∑_k=1^|𝒜_i|λ_k=1, λ_k≥ 0, k=1,2,⋯,|𝒜_i| },    i=1,2.

	□

We will show that dim_P(sgn(ℒ))≤ d+ 2. The argument is by contradiction. Suppose dim_P(sgn(ℱ))>d+ 2. It must be that there exists
a shattered set

    {(x_1,b_1,c_1),(x_2,b_2,c_2),⋯,(x_(d+3), b_(d+3),c_(d+3))}⊂^d××.

such that, for all e∈{0,1}^d+3, there exists a vector ξ_e∈^d satisfying

    [⟨ξ_e,x_i⟩+b_i]_+≥ c_i, iff e_i=1,   ∀ 1≤ i≤ d+3.


Observe that we must have c_i∈_+ for all i=1,2,⋯,d, since if c_i≤ 0, then no such shattered set can be demonstrated. But if c_i∈_+, for all ξ_e∈^d, then

	
    [⟨ξ_e,x_i⟩+b_i]_+≥ c_i⇒⟨ξ_e,x_i⟩≥ c_i-b_i
       [⟨ξ_e,x_i⟩+b_i]_+<c_i⇒⟨ξ_e,x_i⟩≤ c_i-b_i.


For each 1≤ i≤ d+ 3, define the vector s_i=(s_i^1,⋯,s_i^d+1)∈^d+1 component-wise according to

    s_i^j{[   x_i^j   j<d+1; c_i-b_i   j=d+1 ].


Let 𝒜={z_1, z_2,⋯, z_(d+3)}⊂^d+1, and let 𝒜_1 and 𝒜_2 be subsets of 𝒜 satisfying the conditions of Radon's lemma (cf. Lemma <ref>). Define a vector e∈{0,1}^d+3 component-wise according to

    e_i=𝕀_{z_i∈𝒜_1}.

Then, for the vector ξ_e, we have,

	
	
    ∑_i=1^dξ_e,jz_j   ≥  z_d+1,  ∀ x∈𝒜_1
    ∑_i=1^dξ_e,jz_j   < z_d+1,  ∀ x∈𝒜_2.


Now, let x_0∈^d+1 be a point contained in both the convex hull of Conv(𝒜_1) and the convex hull of Conv(𝒜_2). Such a point must exist by Radon’s lemma (cf. Lemma <ref>). Since x_0 satisfies both inequalities in Eqs. (<ref>)-(<ref>) simultaneously, this yields a contradiction. Therefore, dim_P(sgn(ℒ))< d+2, and due to Remark <ref>, we obtain dim_VC(sgn(ℒ))< d+2.  This bound is essentially tight in the sense that dim_VC(sng(ℒ))≥ d+1. To see this, for any given the labels y_1,⋯,y_d+1∈{±}^d+1, consider the function f∈ℱ” with b=y_d+1 and ξ=(ξ_1,⋯,ξ_d) with ξ_i=y_i-y_d+1. Then, f(0)=[⟨ξ,0⟩+y_d+1 ]_+=y_d+1, and f(e_i)=[⟨ξ,e_i⟩+y_d+1]_+=[ξ_i+y_d+1]_+=[y_i]_+=y_i, where e_i is the i-th basis vector. Therefore, we shatter the points e_1,⋯,e_d,0.

Combining all the previous steps yields

    𝒩(ϵ,𝒢_n,N,L_2(P))   ≤( 𝒩(ϵ',ℱ, L_2(P)))^Nm
       =(𝒩(ϵ',ℒ,L_2(P)))^Nm
       ≤(Klog (K/ϵ'^2)ϵ'^2)^Nmdim_VC(ℒ)
       ≤(Klog (K/ϵ'^2)ϵ'^2)^Nmdim_VC(sgn(ℒ))
       =(Klog (K/ϵ'^2)ϵ'^2)^Nm(d+2),

where ϵ'λ (ϵ)^1 r 2mexp(L^2/λ)L. Plugging the upper bound in Eq. (<ref>) into Inequality (<ref>) of Lemma <ref> completes the proof.  ▪







 §.§ Proof of Lemma <ref>



In this section, we establish the proofs of the upper bound in Theorem <ref> regarding the consistency of the finite sample approximations in Section <ref>. The proof is the adaptation of the one given in <cit.>. However, our proof crucially uses the Gumbel max perturbation technique.  We first recall the following definition of the population and finite sample estimates


    H(λ;ω)   =λlog_Q^⊗ 2[exp(-yỹλ_μ_ω[φ(x_i;ξ)φ(x_j;ξ) ])]+λ r2,
    
    H_n,N(λ;ω)   =λlog2n(n-1)∑_1≤ i<j≤ nexp(-y_iy_jλ_μ^N_ω[φ(x_i;ξ)φ(x_j;ξ)] )  +λ r2.


Now, define 


    T_ω(P)   _P^⊗ 2[y
    ỹ_μ_ω[φ(x;ξ)φ(x̃;ξ)]]
    T_ω(P)   1N_P^⊗ 2[yỹ⟨φ_ω(x), φ_ω(x̃) ⟩].


From Lemma <ref>, we recall that


    sup_ω∈S_+^mmin_λ>0H(λ;ω)   = sup_ω∈S_+^minf_P∈𝒫T_ω(P)
    sup_ω∈S_+^mmin_λ>0H_n,N(λ;ω)   =sup_ω∈S_+^minf_P^n∈𝒫^nT_ω(P^n),


where 𝒫 and 𝒫^n are defined as follows


    𝒫   { P∈ℳ(𝒳×𝒴): D_KL(P||Q)≤ r, P≪ Q },
    𝒫^n   { P∈ℳ(𝒳×𝒴): D_KL(P||Q^n)≤ r, P≪Q^n}.


Furthermore, lets define

    (ω_∗,P_∗^n)=sup_ω∈S_+^minf_P^n∈𝒫^n1 N_P^n,⊗ 2[yỹ⟨φ_ω(x), φ_ω(x̃) ⟩].
 
Fix ω∈S_+^m. We wish to upper bound the following difference term

    |sup_ω∈S_+^minf_P∈𝒫T_ω(P)-T_ω_∗(P_∗^n)|≤𝖲_1+𝖲_2+𝖲_3,

where 𝖲_1,𝖲_2, and 𝖲_3 are defined as below

    𝖲_1   |sup_ω∈S_+^minf_P∈𝒫T_ω(P)-sup_ω∈S_+^minf_P∈𝒫T_ω(P)|,
    𝖲_2   |sup_ω∈S_+^minf_P∈𝒫T_ω(P)- T_ω_∗(P_∗^n)|,
    𝖲_3   | T_ω_∗(P_∗^n)-T_ω_∗(P_∗^n)|.

We now consider the following upper bound on each term:

Upper Bound on 𝖲_1 and 𝖲_3:

To compute upper bounds on 𝖲_1 and 𝖲_3, we leverage the following inequalities


    𝖲_1   |sup_ω∈S_+^minf_P∈𝒫T_ω(P)-sup_ω∈S_+^minf_P∈𝒫T_ω(P)|≤sup_ω∈S_+^msup_P∈𝒫|T_ω(P)-T_ω(P)|,
    𝖲_3   | T_ω(P_∗^n)-T_ω(P_∗^n)|≤sup_ω∈S_+^msup_P∈𝒫^n|T_ω(P)-T_ω(P)|.


To establish a uniform concentration bound, we use the fact that ω∈S_m^+ and the simplex S_m^+ is compact with the diameter diam(S_m^+)=max_ω_0,ω_1∈S_m^+ω_0-ω_1_2≤ 2. Therefore, we can find an ε-net that covers S_m^+, using at most M=(4diam(S_+^m)/ε)^m=(8/ε)^m balls of the radius ε>0. Lets {ω_i}_i=1^M denotes the center (anchor) of these balls. Now, define the error term

    E_N(z,z̃)_P^⊗ 2[yỹ_μ_ω_i[φ(x;ξ)φ(x̃;ξ)]]-_P^⊗ 2[yỹ N⟨φ_ω_i(x), φ_ω_i(x̃) ⟩],

where z(y,x),z̃ (ỹ,x̃), and z,z̃∈𝒵=𝒳×𝒴. Invoking the Hölder inequality |⟨ f,g⟩|≤f_pg_q,p^-1+q^-1=1 for the measure space L^p(𝒵^2,P^⊗ 2) with f=E_N(z_0,z_1), g≡ 1 and p=q=2, it follows that 

    |∫_𝒵×𝒵E_N(z,z̃)dP^⊗ 2(z,z̃)|≤(∫_𝒵×𝒵|E_N(z,z̃)|^2dP^⊗ 2(z,z̃))^1 2.

Due to the non-negativity of the integrand on the right hand side of the preceding inequality, the supremum can be moved inside the square root, i.e.,

    sup_P∈𝒫|∫_𝒵×𝒵E_N(z,z̃)dP^⊗ 2(z,z̃)|   ≤sup_P∈𝒫(∫_𝒵×𝒵|E_N(z,z̃)|^2dP^⊗ 2(z,z̃))^1 2
       ≤(sup_P∈𝒫∫_𝒵×𝒵|E_N(z,z̃)|^2dP^⊗ 2(z,z̃))^1 2.

We leverage Lemma <ref> to obtain

    (sup_P∈𝒫∫_𝒵×𝒵|E_N(z,z̃)|^2dP^⊗ 2(z_0,z_1))^1 2   =(inf_λ>0λlog_Q^⊗ 2[exp(1λ|E_N(z,z̃)|^2)]+λ r2)^1 2
       ≤(λ_0log_Q^⊗ 2[exp(1λ_0|E_N(z,z̃)|^2)]+λ_0 r2)^1 2,

where λ_0∈_+\{0} is a free parameter of the upper bound which we will specify in the sequel. Using the Chernoff bound, we obtain for β≥ 0 that

    (sup_P∈𝒫| ∫_𝒵×𝒵E_N(z_0,z_1)dP^⊗ 2(z_0,z_1)|≥δ)
       ≤(λ_0log_Q^⊗ 2[exp(1λ_0|E_N(z_0,z_1)|^2)]+λ_0 r2≥δ^2)
       ≤exp(-βδ^2)·exp(βλ_0r2)( _Q^⊗ 2[exp(1λ_0|E_N(z_0,z_1)|^2)])^λ_0β.


To compute the expectation, we now establish the following auxiliary result:


Consider the error term defined in Eq. (<ref>). Then, E_N(z_0,z_1) is zero-mean sub-Gaussian random variable with the Orlicz norm of E_N(z_0,z_1)_ψ_2≤L^2 2√(N).


	The proof is presented in Appendix <ref>.


We leverage the result of Lemma <ref> to compute an upper bound on the expectation on the right hand side of (<ref>). In particular, we let λ_0=1/E_N^2_ψ_2, and notice that [exp(|E_N|^2/E_N^2_ψ_2)]≤ 2. Then,

    (sup_P∈𝒫| ∫_𝒵×𝒵E_N(z_0,z_1)dP^⊗ 2(z_0,z_1)|≥δ)
       ≤exp(-βδ^2)exp( β r2E_N^2_ψ^2)exp(βln(2)E_N^2_ψ_2),

for all β∈_+. Let β=E_N_ψ_2^2 (r+2ln(2)) with E_N_ψ_2=L^2 2√(N). Then, we obtain that 

    (sup_P∈𝒫| ∫_𝒵×𝒵E_N(z_0,z_1)dP^⊗ 2(z_0,z_1)|≥δ)≤ 2exp(- L^4δ^2 2N(r+2ln(2))).

We thus conclude that

    (sup_P∈𝒫|T_ω_i(P)-T_ω_i(P)|≥δ)≤ 2exp(- L^4δ^2 2N(r+2ln(2))).

Applying the union bound then yields

    (max_1≤ i≤ Msup_P∈𝒫|T_ω_i(P)-T_ω_i(P)|≥δ)≤ 2(8ε)^mexp(- L^4δ^2 2N(r+2ln(2))).

Therefore, with the probability of at least 1-ρ, we obtain that

    max_1≤ i≤ Msup_P∈𝒫|T_ω_i(P)-T_ω_i(P)|≤√(2N(r+2ln(2)) L^4log(2× 8^mρε^m)).

It is easy to see that the mapping ω↦ T_ω(P)-T_ω(P) is Lipschitz with the constant 2L^2. Therefore, with the probability of at least 1-ρ, we have

    sup_ω∈S_m^+sup_P∈𝒫|T_ω(P)-T_ω(P)|   ≤max_1≤ i≤ Msup_P∈𝒫|T_ω_i(P)-T_ω_i(P)|+2L^2ε
       ≤√(2N(r+2ln(2)) L^4log(2× 8^mρε^m))+2L^2ε.

Due to Inequality (<ref>), we obtain

    |sup_ω∈S_+^minf_P∈𝒫T_ω(P)-sup_ω∈S_+^minf_P∈𝒫T_ω(P)|≤√(2N(r+2ln(2)) L^4log(2× 8^mρε^m))+2L^2ε.

Letting ε=12L^4√(2N(r+2ln(2))) yields

    |sup_ω∈S_+^minf_P∈𝒫T_ω(P)-sup_ω∈S_+^minf_P∈𝒫T_ω(P)|≤ 2√(2N(r+2ln(2)) L^4log(2× (16L^4)^mρ (2N(r+2ln(2))^m 2) )).

Similarly, it can be shown that with the probability of at least 1-ρ,

    | T_ω(P_∗^n)-T_ω(P_∗^n)|≤ 2√(2N(r+2ln(2)) L^4log(2× (16L^4)^mρ (2N(r+2ln(2))^m 2) )).




Upper Bound on 𝖲_2: 
In this case, we employ Talagrand's concentration of measure for Lipschitz functions:
(Talagrand's Concentration of Measure <cit.>)
	Let X=(X_1,⋯, X_n) be a random variable with independent components taking values |X_i|≤ K, i=1,2,⋯,n, for K>0. Let f:^n→ be a convex L-Lipschitz function. Then, for all t>0
	
    (|f(X)-[f(X)]|≥ Kδ)≤ 4e^-δ^2/4L^2,

	where [f(X)] is the median of the random variable f(X) defined as follows
	
    [f(X)]sup{δ∈:(f(X)≤δ)≤1 2}.

	□


Let us mention that the concentration inequality in Eq. (<ref>) provides the following bound on the distance between the median and the expectation

    |[f(X)]-[f(X)]|   ≤[|f(X)-[f(X)]|
       = ∫_0^∞(|f(X)-[f(X)]|≥δ)dδ
       ≤∫_0^∞ 4e^-δ^2/4L^2K^2=8KL√(4π).

Hence, we have 

    [f(X)]-8KL√(4π)≤[f(X)]≤[f(X)]+8KL√(4π).

Therefore, due to parts (iii) and (iv) of <cit.>, concentration around the median implies the concentration around the mean with different constants, i.e.,

    (|f(X)-[f(X)]|≥ Kδ)≤ 2exp(δ^2K^2L^2).

We recall the definition

    T_ω(P_∗^n)   =sup_P^n∈𝒫^nT_ω(P^n)
       =min_λ>0λlog_Q^n,⊗ 2[ exp(-yỹλ_μ^N_ω[φ(x;ξ)φ(x̃;ξ)] )]  +λ r2.

Furthermore, let z_i=(y_i,x_i),i=1,2,⋯,n, and

    X_ij X(z_i,z_j)_μ^N_ω[y_iy_jφ(x_i;ξ)φ(x_j;ξ)].

Consider the mapping

    X=(X_ij)_1≤ i<j≤ n↦ f(X)min_λ>0F(X,λ)λlog_Q^n,⊗ 2[exp(-1λ X(z,z̃))]+λ r2.

To show that this mapping is Lipschitz, we first show that the (unique) minimizer of the optimization problem in Eq. (<ref>) is bounded, i.e., there exists c c(n,r)>0 and 0<C C(n,r)<+∞ such that c≤λ_∗≤ C, where

    λ_∗min_λ>0F(X,λ).

To this end, for a fixed X∈𝒵, consider the partial derivative

    ∂ F(X,λ)∂λ   =log_Q^n,⊗ 2[exp(-1λ X(z,z̃))]+r2
       +∑_1≤ i<j≤ n1λX(z_i,z_j)exp(-1λX(z_i,z_j))  ∑_1≤ i<j≤ nexp( -1λ X(z_i,z_j)).

In the limit of λ↓ 0,  the soft-max terms turns into the maximization over the indices i,j∈{1,2,⋯,n}, i.e.,

    lim_λ↓ 0∂ F(X,λ)∂λ=lim_λ↓ 0max_1≤ i<j≤ n-2λX_ij+r2→ +∞.

Moreover, since |X_ij|<L^2 due to Assumption <ref>, we have

    lim_λ→ +∞∂∂λF(X,λ)=r2>0.

The partial derivative ∂ F(X,λ)/∂λ is a continuous function of λ.  It can thus only vanish in the interior of the non-negative orthant λ_∗∈_+\{0,∞}. Therefore, the mapping f(X)=F(X,λ_∗) is Lipschitz with the constant  L= C n^2exp(2L^2c). Based on Talagrand's concentration inequality, for the anchor nodes {ω_i}_i=1^M we have that

    (|sup_P^n∈𝒫^nT_ω_i(P^n)-[sup_P^n∈𝒫^nT_ω_i(P^n)] |≥δ)≤ 2exp(-δ^2n^2K^2L^2),

where K=Cexp(2L^2 c). From the union bound, we obtain

    (max_1≤ i≤ M|sup_P^n∈𝒫^nT_ω_i(P^n)-[sup_P^n∈𝒫^nT_ω_i(P^n)] |≥δ)≤ 2(8ε)^mexp(-δ^2n^2K^2L^2).

Therefore, with the probability of at least 1-ρ, the following inequality holds

    max_1≤ i≤ M|sup_P^n∈𝒫^nT_ω_i(P^n)-[sup_P^n∈𝒫^nT_ω_i(P^n)] |≤KLn√(log(2× 8^mρ×ε^m)).

In the following lemma, we characterize an upper bound and a lower bound on the expectation on the left hand side of the previous display:

	
For all the realizations of the data samples (y_i,x_i)_1≤ i≤ N∼_i.i.d. Q as well as random feature samples (ξ_i^k)_1≤ k≤ N∼_i.i.d.μ_i, the following upper bound holds 

    _Q^⊗ 2[sup_P^n∈𝒫^nT_ω(P^n)]≤sup_P∈𝒫T_ω(P).

Furthermore, the following lower bound holds

    _Q^⊗ 2[sup_P^n∈𝒫^nT_ω(P^n)]≥sup_P∈𝒫T_ω(P)-C^3K^2 n^2,

where K=Cexp(2L^2 c).


	The proof is presented in Appendix <ref>. 


Using the bounds in Eqs. (<ref>) and (<ref>) of Lemma <ref> yields

    max_1≤ i≤ M|sup_P^n∈𝒫^nT_ω_i(P^n)-sup_P∈𝒫T_ω(P) |≤KLn√(log(2× 8^mρ×ε^m))+C^3K^2n^2.

We then obtain

    sup_ω∈S_m^+|sup_P^n∈𝒫^nT_ω(P^n)-sup_P∈𝒫T_ω(P) |   ≤max_1≤ i≤ M|sup_P^n∈𝒫^nT_ω_i(P^n)-sup_P∈𝒫T_ω(P) |+2L^2ε.

Combining the preceding inequality with Eq. (<ref>) yields

    sup_ω∈S_m^+|sup_P^n∈𝒫^nT_ω(P^n)-sup_P∈𝒫T_ω(P) |≤KLn√(log(2× 8^mρ×ε^m))+C^3K^2n^2+2L^2ε.

Letting ε=K 2Ln yields

    𝖲_2=|sup_ω∈S_+^minf_P∈𝒫T_ω(P)- T_ω_∗(P_∗^n)|   ≤sup_ω∈S_m^+|sup_P^n∈𝒫^nT_ω(P^n)-sup_P∈𝒫T_ω(P) |
       ≤2KLn√(log(2× (16Ln)^mρ× K^m))+C^3K^2n^2.




 §.§ Proof of Theorem <ref>



Let Θ denotes a set of parameters containing the element θ which we wish to estimate. Assume there is a class 𝒫 = {P_θ:θ∈Θ} of probability measures on 𝒳 indexed by Θ. Suppose d:Θ×Θ→_+ is a metric on Θ. LeCam's method now can be encapsulated in the following theorem:
(LeCam's Lower Bound, see, e.g., <cit.>)

Let P^0,P^1∈𝒫. Let θ(P) denotes a parameter taking values in the metric space (Θ,d). Then,

    inf_θ∈Θsup_P∈𝒫_P[d(θ,θ(P))]≥Δ4∫_𝒳min{p^0_n(x),p^1_n(x)}dx≥Δ8e^-n D_KL(P^0||P^1),

where Δ d(θ(P^0),θ(P^1)). Moreover, p^0_n(x)∏_i=1^np^0(x_i) and p^1_n(x)∏_i=1^np^1(x_i) where p^0(x)dP^0/dx and p^1(x)dP^1/dx are the Lebesgue densities.


Now, suppose P(y)=Q(y), and consider the case of a balanced data-set. Then, following Eq. (<ref>) and the ensuing discussion in Section <ref>, we equivalently can consider the minimax estimation rate of the following optimization problem

    (P_+,P_-)↦ω(P_+,P_-)=max_ω∈S_m^+∑_i=1^mω_iMMD^2_K_i[P_+,P_-],

where (P_+,P_-)∈𝒫_±. Consider the following normal distributions for the marginals:


    P_+   =𝖭(μ_+^P,σ^2I_d× d),     P_-=𝖭(μ_-^P,σ^2I_d× d),
    
    Q_+   =𝖭(μ_+^Q,σ^2I_d× d),    Q_-=𝖭(μ_-^Q,σ^2I_d× d),


where Q_+⊗ Q_- is the center of the distribution ball 𝒫_±. We impose the following conditions on the means and variances of the normal distributions:

	
  (C.1) μ_-^P-μ_-^Q_2^2+μ_+^P-μ_+^Q_2^2≤ 4rσ^2,
	
  (C.2) μ_-^P-μ_+^P_2^2≥ 4σ^2 and μ_-^Q-μ_+^1_2^Q≥ 4σ^2.

The KL divergence between P_+⊗ P_- and Q_+⊗ Q_- is 

    D_KL(P_+⊗ P_-||Q_+⊗ Q_-)=12σ^2μ_-^P-μ_-^Q_2^2+12σ^2μ_+^P-μ_+^Q_2^2.

Therefore, P_+⊗ P_-∈𝒫_± iff (C.1) is satisfied. In addition, from <cit.>, we obtain

    MMD_K_i^2[P_+,P_-]   =∫_0^∞2(11+4tσ^2)^d/2(1-exp(-tμ_+^P-μ_-^P_2^21+4tσ^2) )dν_i(t).

To compute an upper bound, we employ the elementary inequality 1-exp(-x)≤ x, ∀ x≥ 0. We have

    MMD_K_i^2[P_+,P_-]≤ 2μ_+^P-μ_-^P_2^2∫_0^∞t(1+4tσ^2)^(d+2)/2ν_i(dt).

A lower bound is also established in <cit.> for the right hand side of Eq. (<ref>),

    MMD_K_i^2[P_+,P_-]   ≥μ_+^P-μ_-^P_2^2∫_τ_0^τ_1t(1+4tσ^2)^(d+2)/2ν_i(dt)
       ≥μ_+^P-μ_-^P_2^2ν_i([τ_0,τ_1]) min{τ_0(1+4τ_0σ^2)^(d+2)/2,τ_1(1+4τ_1σ^2)^(d+2)/2},

where the lower bound holds for any 0<τ_0≤τ_1≤1μ_+^P-μ_-^P_2^2-4σ^2=τ_P. Notice that τ_P>0 iff (C.2) is satisfied.  Therefore, from Eqs. (<ref>) and (<ref>), we arrive at the following asymptotic result

    MMD_K_i^2[P_+,P_-]≍μ_+^P-μ_-^P_2^2=2σ^2D_KL(P_+||P_-).

Not surprisingly, the result of Eq. (<ref>) highlights the fact that MMD, as a measure of the distribution distance with respect to a kernel function, is proportional to f-divergences. Since the population MMD is non-negative and the optimization of the weights ω is with respect to the probability simplex S_m^+, the inequalities J_k,d(τ_P)≤1 2J_i,d(∞) and J_ℓ,d(τ_Q)≤1 2J_j,d(∞) for all k∈ [M]\{i} and ℓ∈ [M]\{j} in Theorem <ref> are sufficient conditions to ensure that the optimal solution ω of the population MMD optimization in Eq. (<ref>) is a basis vector whose only non-zero coordinate correspond to the basis kernel that yields the largest MMD value. Mathematically,


    ω   =e_i,  for (P_+,P_-)∈𝒫_±
    ω   =e_j,  for (Q_+,Q_-)∈𝒫_±,


where e_1,⋯,e_m∈^m are the standard basis vectors. Notice that (Θ,d) here is the simplex indowed with the total variation distance (S_m^+,d_TV). Thus,

    d_TV(e_i,e_j)=1 2e_i-e_j_1=1.

From LeCam's minmax rate in Eq. <ref> of Thm. <ref>, we obtain

    inf_ω∈S_m^+sup_P∈𝒫_P[d_TV(ω_n,ω(P))]≥18e^-nD_KL(P_+⊗ P_-||Q_+⊗ Q_-)≥18e^-nr.





 §.§ Proof of Proposition <ref>



Recall the definition of the function class ℱ_m(R) from Eq. (<ref>).  We prove Part (i) by computing an upper bound on the empirical Rademacher complexity for the class of functions in ℱ_m(R) as follows


    ℜ_S^n(ℱ_m(R))   =1n_P_ε[sup_f∈ℱ_m(R)∑_i=1^nε_if(x_i)|x_1,⋯,x_n]
       =1n√(N)_P_ε[sup_β∈^2_r(0) ∑_i=1^n∑_k=1^N∑_m=1^Mε_iβ_m^k√(ω_m)ϕ_m(x_i;ξ_m^k) |x_1,⋯,x_n]
       =1n√(N)_P_ε[sup_β∈^2_r(0)ε^TΦ(ω)β|x_1,⋯,x_n],

where in the last equality, Φ(ω) (φ_ω(x_i))_1≤ i≤ n∈^n× mN is the feature matrix with and r=R√(mN).
From the Cauchy-Schwarz inequality, it is easy to see that the supremum in Eq. (<ref>) is attained when β and ε^TΦ are co-linear, i.e., 

    β= R√(mN)·ε^TΦ(ω)ε^TΦ(ω)_2.

Therefore, from Eq. (<ref>) we obtain that

    ℜ_S^n(ℱ_m(R))   =RnN√(m)_P_ε[ε^TΦ(ω)_2|x_1,⋯,x_n].
























We now compute the expectation (<ref>) via the following concentration inequality for the quadratic forms of independent random variables with bounded moments:

(Concentration Inequality for Quadratic Forms,  <cit.>)
		
	Let z=(z_1,⋯, z_n)∈^n be a random vector satisfying the following  Bernstein moment conditions for some K > 0:
	
    |z_i|^2p≤1 2p!b_i^2K^2(p-1),    p≥ 1.

	Let A∈^n× n be a real matrix. Then, for every t≥ 0,
	
    {|z^TAz-[z^TAz]|>t}≤exp(-min( t^2192K^2AD_b_F^2,t256K^2A_2) ),
	
	where  D_b=diag(b_1,⋯,b_n), and A_F∑_i,j=1^n|A_ij|^2. □


	Despite some resemblance between Inequality (<ref>) and the Hanson-Wright Inequality <cit.>, they are different in that the former does not have an implicit universal constant in the upper bound. Indeed, the concentration inequality in Eq. (<ref>) is sharper than the Hanson-Wright Inequality, albeit under the additional Bernestein's moment conditions in Eq. (<ref>).

Now, let us apply the concentration inequality (<ref>) in Theorem <ref> to compute the expectation in Eq. (<ref>). First, we show that Rademacher random variable ε∼ P_ε=Uniform{-1,1} satisfies the moment conditions (<ref>). In particular, for all p≥ 1, we have |ε_i|^2p=1. Therefore, the moment condition in Eq. (<ref>) is satisfied with b_i=1 for all i=1,2,⋯,n, and K=1. 

Let A=Φ(ω)Φ(ω)^T and z=ε. Then, z^TAz=ε^TΦ(ω)Φ^T(ω)ε=ε^TΦ_2^2,  [z^TAz]=[ε^TΦ(ω)Φ^T(ω)ε]=Φ(ω)_F^2. Furthermore, D_b=I_n.

For simplicity of notation, in the sequel we suppress the dependency of the random feature matrix to the mixing coefficients, i.e., Φ=Φ(ω). The concentration inequality in Eq. (<ref>) turns into

    {ε^TΦ^2_2-Φ_F^2>t | x_1,⋯,x_n}≤exp(-min(t^2192ΦΦ^T_F^2,t256Φ_2) ).

Also, note that since all Rademacher random variables ε_i have unit variance, we have K ≥  2^-1 2. Thus we obtain for any u≥  0 that

    {ε^TΦ^2_2-Φ_F^2>u|x_1,⋯,x_n}≤exp(-min(u^2192ΦΦ^T_F^2,u256Φ_2^2)).

Let δ≥ 0 be arbitrary, and let us use this estimate for u=δΦ^2_F. Since Φ^TΦ_F^2≤Φ^T_2^2Φ_F^2=Φ_2^2Φ_F^2, it follows that

    {ε^TΦ_2^2-Φ_F^2≥δΦ_F^2|x_1,⋯,x_n]}   ≤exp(- min(δ 192,δ^2 256)Φ_F^2Φ_2^2)
       ≤exp(-1 192min(δ,δ^2)Φ_F^2Φ_2^2).

Now let ϵ≥ 0 be arbitrary; we shall use this inequality for δ = max(ϵ,ϵ^2). Observe
that the (likely) event |ε^TΦ_2^2-Φ_F^2|≤δΦ_F^2 implies the event |ε^TΦ_2-Φ_F|≤ϵΦ_F. This can be seen by dividing both sides of the inequalities by Φ_F^2 and Φ_F respectively, and using the numeric bound max(|z-1|, |z- 1|^2) ≤ |z^2- 1|, which is valid for all z ≥ 0. Using this observation along with the identity min(δ,δ^2)= ϵ^2, we arrive from Eq. (<ref>),

    {ε^TΦ_2-Φ_F≥ϵΦ_F|x_1,⋯,x_n}≤exp(-1 192ϵ^2Φ_F^2Φ_2^2).

Letting ϵ=ϱΦ_F the yields

    {ε^TΦ_2-Φ_F≥ϱ|x_1,⋯,x_n}≤exp(- 1 192ϱ^2Φ_2^2).

Now, we return to computing the expectation in Eq. (<ref>). For the positive random variable ε^TΦ_2, its expectation can be computed as follows

    ℜ_S^n(ℱ_m(R))   =RnN√(m)_P_ε[ε^TΦ_2|x_1,⋯,x_n]
       =RnN√(m)∫_-Φ_F^∞[ε^TΦ_2-Φ_F>t|x_1,⋯,x_n]d t
       (a)≤RnN√(m)∫_-Φ_F^∞exp(- 1 192t^2Φ_2^2)dt 
       = RnN√(m)√(192π)Φ_2Q( -√(192)Φ_FΦ_2),

where (a) follows from the concentration inequality in Eq. (<ref>).  Using the basic inequality Φ_F≤√(Rank(Φ))Φ_2, with Rank(Φ)=min{mN,n} in conjunction with the fact that erfc(x) is monotone decreasing for all  x∈ yields the upper bound (<ref>) on the Rademacher complexity.

We remark that the upper bound we derived here is sharper than that of <cit.> which is based on the Khintchine-Kahane type inequality. More specifically, the Khintchine inequality yields the following upper bound


    ℜ_S^n(ℱ_m(R))   = RnN√(m)_P_ε[√(ε^TΦΦ^Tε)|x_1,⋯,x_n]
       ≤RnN√(m)(2344Tr(ΦΦ^T) )^1 2
       =RnN√(m)√(2344)Φ_F.

Since 0<erfc(x)≤ 1 for 0<x, and Φ_2≤Φ_F for any matrix Φ∈^n× N, the upper bound we established in Eq. (<ref>) is sharper than that of Eq. (<ref>) using techniques of  <cit.>.  We now prove Part (ii) of Proposition <ref>. Similar to the derivation in Eq. (<ref>), we have
that


    𝔊_S^n(ℱ_m(R))   =1n_P_σ[sup_f∈ℱ_m(R)∑_i=1^nσ_if(x_i)|x_1,⋯,x_n]
       =RnN√(m)_P_σ[σ^TΦ_2|x_1,⋯,x_n].

To compute the expectation, we use the following standard tail bound for the sum of χ^2 random variables due to Laurent and Massart <cit.>:

(Tail Bound for χ^2 random variables <cit.>) Let z_1,⋯,z_n be independent χ^2 random variables, each with one degree of freedom. For any vector a (a_1,⋯,a_n)∈_+^n with non-negative entries, and any t>0,
	
    {∑_i=1^na_iz_i≥a_1+2a_2√(t)+2a_∞t  }≤ e^-t.

	□


Now, consider the eigenvalue decomposition ΦΦ^T=VΛV, where V is a matrix of orthonormal eigenvectors, and Λdiag(λ_1, ⋯,λ_n) is the diagonal matrix of the corresponding eigenvalues λ (λ_1,⋯,λ_n). Due to the rotational invariance of the Gaussian distribution, zσV is a zero-mean isotropic multi-variate Gaussian random vector. Thus, σ^TΦ_2= z^TΛz= λ_1z_1^2+⋯+λ_nz_n^2, and the z_i^2's are independent χ^2 random variables, each with one degree of freedom. Therefore, using the concentration inequality in Eq. (<ref>) with λ_2=(Tr((ΦΦ^T)^2))^1 2, λ_1=Tr(ΦΦ^T)=Φ_F^2, and λ_∞=Φ_2^2 yields for all t>0,

    {σ^TΦ_2^2≥Φ_F^2+Tr^1 2((ΦΦ^T)^2)√(t) +2Φ_2^2t |x_1,⋯,x_n}≤ e^-t.

Alternatively, by letting 

    t=Q_ε(Φ) (√(εΦ_F^2 2Φ_2^2+Tr((ΦΦ^T)^2)  4Φ_2^4)-√(Tr((ΦΦ^T)^2)) 2Φ_2^2)^2,

the concentration bound in Eq. (<ref>) takes the following form

    {σ^TΦ_2^2-Φ_F^2≥εΦ_F^2}≤ e^-Q_ε(Φ).

Due to the inequality max{|z-1|,|z-1|^2}≤ |z^2-1|,z>0, the preceding inequality in turn implies that

    {σ^TΦ_2-Φ_F≥εΦ_F}≤ e^-Q_ε(Φ).

Letting ε=ϱ/Φ_F yields

    {σ^TΦ_2-Φ_F≥ϱ}≤exp(-Q_ϱΦ_F(Φ)).

We now leverage Inequality (<ref>). Then, similar to our derivation in Eq. (<ref>), we obtain that 

    𝔊_S^n(ℱ_m(R))   =RnD√(m)∫_0^∞[σ^TΦ_2>t|x_1,⋯,x_n]dt 
       ≤RnD√(m)∫_-Φ_F^∞exp(-Q_tΦ_F(Φ))dt.

Due to the elementary inequality exp(-(√(-a+b^2)-b)^2)≤exp(-a^2 4b^2) for all a,b>0, we obtain that

    exp(-Q_tΦ_F(Φ))≤exp(-Φ_F^24 Tr((ΦΦ^T)^2)t^2).

Plugging Eq. (<ref>) into Eq. (<ref>) yields

    𝔊_S^n(ℱ_m(R))   ≤RnN√(m)∫_-Φ_F^∞exp(-Φ_F^24 Tr((ΦΦ^T)^2)t^2)dt
       =RnN√(m)√(π)√(2)Tr^1 2((ΦΦ^T)^2)Φ_Ferfc(-Φ_F^22Tr^1 2((ΦΦ^T)^2)).

Now, recall that λ_2=(Tr((ΦΦ^T)^2))^1 2, and λ_1=Tr(ΦΦ^T)=Φ_F^2. Then, since λ_2≤λ_1≤√(n)λ_2, we obtain that 

    (Tr((ΦΦ^T)^2))^1 2≤Φ_F^2≤√(n)(Tr((ΦΦ^T)^2))^1 2.

Consequently, the upper bound in Eq. (<ref>) can be simplified as follows

    𝔊_S^n(ℱ_m(R))≤RnN√(m)√(π 2)Φ_F𝒬(-√(n 4)).






 §.§ Proof of Lemma <ref>











































We compute a concentration bound for the spectral norm Φ(ω)_2 of the feature matrix. To achieve this goal, we define the estimation error matrix Δ_n(ω)K(ω)-1 N(ΦΦ^T)(ω). We now use the standard ε-net argument due to <cit.>:
(Spectral Norm on a Net, <cit.>)
	
	Let A be a symmetric n× n matrix, and let N_ε be an ε-net of S^n-1 for some ε∈ [0, 1). Then
	
    A_2=sup_y∈S^n-1|⟨Ay,y⟩ |≤ (1-2ε)^-1sup_y∈ N_ε|⟨Ay,y⟩|.

	□

Let N_ε be ε-covering of the sphere S^n-1. It is shown in <cit.> that log N_ε≤ nlog(1+2ε). From Inequality (<ref>), we obtain that 

    Δ_n(ω)_2   ≤ (1-2ε)^-1sup_y∈ N_ε|⟨Δ_n(ω)y,y⟩|.

For each point in the cover y∈ N_ε, the inner product in Eq. (<ref>) has the following upper bound

    |⟨Δ_n(ω)y,y⟩|   =|⟨K(ω)-1 NΦΦ^T(ω)y,y⟩|
       = |∑_i,j=1^n((K(ω))_ij-1 N(ΦΦ^T(ω))_ij) y_iy_j|   
       =| ∑_i,j=1^n(∑_ℓ=1^mω_ℓK_ℓ(x_i,x_j)-1 N∑_k=1^N∑_ℓ=1^mω_ℓφ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ^k_ℓ)) y_iy_j|
       ≤∑_i,j=1^n|y_iy_j|∑_ℓ=1^mω_ℓ|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ^k_ℓ)φ_ℓ(x_j;ξ^k_ℓ)|.

By applying the Cauchy-Schwarz inequality, we obtain that

    ∑_i,j=1^n|y_iy_j|∑_ℓ=1^mω_ℓ|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ^k_ℓ)φ_ℓ(x_j;ξ^k_ℓ)| 
       ≤(∑_i,j=1^n(∑_ℓ=1^mω_ℓ|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ^k_ℓ)φ_ℓ(x_j;ξ^k_ℓ)|)^2)^1 2·(∑_i,j=1^n|y_iy_j|^2)^1 2.
	
Therefore, from Eq. (<ref>) we proceed as follows

    |⟨Δ_n(ω)y,y⟩|   ≤(∑_i,j=1^n(∑_ℓ=1^mω_ℓ|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ^k_ℓ)φ_ℓ(x_j;ξ^k_ℓ)|)^2)^1 2y_2^2
       =(∑_i,j=1^n(∑_ℓ=1^mω_ℓ|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ^k_ℓ)φ_ℓ(x_j;ξ^k_ℓ)|)^2)^1 2,

where the last equality is due to the fact that y∈S^n-1, and thus y_2=1. Due to the fact that ℓ_2-norm of a matrix is smaller than its ℓ_1-norm, we can obtain the following  upper bound

    |⟨Δ_n(ω)y,y⟩|
       ≤∑_i,j=1^n∑_ℓ=1^mω_ℓ|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ_ℓ^k)|.

Applying the Cauchy-Schwarz inequality yields

    |⟨Δ_n(ω)y,y⟩|   ≤ n^2·ω_2·(∑_ℓ=1^m(|K_ℓ(x,y)-1 N∑_k=1^Nφ_ℓ(x;ξ_ℓ^k)φ_ℓ(y;ξ_ℓ^k)|)^2)^1 2
       ≤ω_1∑_ℓ=1^m∑_i,j=1^n|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ_ℓ^k)|
       =∑_ℓ=1^m∑_i,j=1^n|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ_ℓ^k)|.

where in the last inequality, we used the fact that ω∈S_m^+, and thus ω_1=1. Taking the union bound over N_ε with ε=1/4 results in

    (Δ_n(ω)_2≥δ N)≤(sup_y∈ N_1/4|⟨Δ_n(ω)y,y⟩|≥δ 2N)
       ≤exp(3nlog 3)sup_y∈ N_1/4(|⟨Δ_n(ω)y,y⟩|≥δ N)    
       ≤exp(3nlog 3) (∑_ℓ=1^m∑_i,j=1^n|K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ_ℓ^k)|≥δN).

Now, define the random variable

    Z_ijℓ K_ℓ(x_i,x_j)-1 N∑_k=1^Nφ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ_ℓ^k),   ℓ=1,2,⋯,m.

Let (ξ_ℓ^1,⋯,ξ_ℓ^N) and  (ξ_ℓ^1,⋯, ξ̃_ℓ^k,⋯,ξ_ℓ^N),k∈{1,2,⋯,N} denote two vector of random features that differ in the k-th element, and let Z_ijℓ and Z_ijℓ denote the associated random variables. Then, by the triangle inequality, we obtain

    |Z_ijℓ-Z_ijℓ|   =1N|φ_ℓ(x_i;ξ_ℓ^k)φ_ℓ(x_j;ξ_ℓ^k)-φ_ℓ(x_i;ξ̃_ℓ^k)φ_ℓ(x_j;ξ̃_ℓ^k)|
       ≤1N|φ_ℓ(x_i;ξ_ℓ^k)||φ_ℓ(x_i;ξ_ℓ^k)|+1N |φ_ℓ(x_i;ξ_ℓ^k)||φ_ℓ(x_i;ξ_ℓ^k)|
       ≤2L^2 N,

where the last inequality is due to Assumption <ref>.  Since [Z_ijℓ]=0 for all 1≤ i,j≤ n and 1≤ℓ≤ m. Applying McDiarmid's Martingale inequality <cit.> yields

    (|Z_ijℓ|≥δ)≤exp(-Nδ^2L^2).

By Lemma <ref> of Appendix <ref>, Z_ijℓ is a sub-Gaussian random variable with the Orlicz norm of Z_ijℓ_ψ_2≤L√(2N).  Therefore, 

    (∑_i,j=1^n∑_ℓ=1^m|Z_ijℓ|≥δ)≤exp(-cNδ^2 n^2mL^2),

for some universal constant c>0. From Eqs. (<ref>), (<ref>) we obtain

    (Δ_n(ω)_2≥δ)≤exp(3nlog 3)·exp(-cNδ^2 n^2mL^2).

	
Using Weyl's eigenvalue inequality <cit.>, the following upper bound can be established on the difference between the spectral norm of the kernel matrix and that of the random feature matrix 

    |λ_i(K(ω))-λ_i(ΦΦ^T(ω)/N)|≤Δ_n(ω)_2,

for all i=1,2,⋯,n. Therefore,

    |K(ω)_2-1 NΦΦ^T(ω)_2|≤Δ_n(ω)_2.

For all ω∈S_m^+, it then holds that 

    (|K(ω)_2-1 NΦΦ^T(ω)_2|≥δ)   ≤(Δ_n(ω)_2≥δ)
       ≤exp(3nlog 3)exp(-cNδ^2 n^2mL^2),

To establish a uniform concentration bound, we use the fact that ω∈S_m^+ and the simplex S_m^+ is compact with the diameter Diam(S_m^+)=max_ω_0,ω_1∈S_m^+ω_0-ω_1_2≤ 2. Therefore, we can find an ε-net that covers S_m^+, using at most M=(4Diam(S_+^m)/ε)^m=(8/ε)^m balls of the radius ε>0. Lets {ω_i}_i=1^M denotes the center of these balls.  Now, define the function T(ω)K(ω)_2-N^-1ΦΦ^T(ω)_2. We have |T(ω)| < δ for all ω∈S_+^m if |T(ω_i)|< δ 2 and L_T<δ 2r for all i=1,2,⋯,m. In the sequel, we bound the probability of these two events.

The union bound followed by Eq. (<ref>) applied to the anchors in the ε-net yields

    (∪_i=1^M|T(ω_i)|≥δ 2)≤(8 r)^m·exp(3nlog 3)·exp(-cNδ^2 4n^2mL^2).
 
The function T(ω) is differentiatable, and its Lipschitz constant is defined by L_T∇ T(ω_∗)_2, where ω_∗min_ω∈S_+^mT(ω)_2. The Lipschitz constant is a random variable of the random feature samples. Moreover, its second moment has the following upper bound

    [L_T^2]   =[∇K(ω)_2-N^-1∇ΦΦ^T(ω) _2_2^2]
       (a)=[ ∑_i=1^m(Tr(K_iuv^T)-N^-1Tr( Φ_iΦ_i^Tũṽ^T))^2],
       = ∑_i=1^m(Tr(K_iuv^T))^2+N^-2[∑_i=1^m(Tr(Φ_iΦ_i^Tũṽ^T))^2]
       -2N^-1∑_i=1^m[Tr(Φ_iΦ_i^Tũṽ^T))]Tr(K_iuv^T)),

where in (a), u and v (respectively, ũ and ṽ) are the left and right singular vectors of K(ω_∗) (respectively, ΦΦ^T(ω_∗)). Moreover,

    (∇K(ω_∗)_2)_i=∂∂ω_iK(ω_∗)_2=∂K(ω_∗)∂ω_i∂K(ω_∗)_2∂K(ω_∗)= Tr(K_iuv^T),

for i=1,2,⋯,m. Due to Assumption <ref>, we now have that 


    Tr(K_iuv^T)   ≤K_i_Fuv^T_F≤ nL
    1 NTr(Φ_iΦ_i^Tũṽ^T)   ≤1 NΦ_iΦ_i^T_Fũṽ^T_F≤ nL.


Therefore, from Eq. (<ref>), we now obtain [L_T^2]≤ 3mn^2L^2. By Markov's inequality, we then get

    (L_T^2≥δ 2r)≤[4r^2 L_T^2]δ^2=(12mn^2r^2L^2δ^2).

Applying the union bound to Inequalities (<ref>) we have

    (sup_ω∈S_m^+| K(ω) _2-1NΦΦ^T(ω)_2|≥δ)
       ≤(L_T^2≥δ2r)+(∪_i=1^M|T(ω_i)|≥δ2)
       ≤(12mn^2r^2L^2δ^2)+(8 r)^mexp(3nlog 3)·exp(-cNδ^2 4n^2mL^2).

The upper bound has the form of κ_1 r^-m+κ_2 r^-2. Setting r= (κ_1κ_2)^1 m+2 turns this into 2κ_2^m m+2κ_1^2 m+2. Then,

    (sup_ω∈S_m^+| K(ω) _2-1NΦΦ^T(ω)_2|≥δ)
       ≤  2^14(m^2n^2L^2δ^2)exp(6nlog 3 m+2)·exp(-cNδ^2 2n^2m(m+2)L^2),

provided that 12mn^2L^2δ^2≥ 1. Therefore, with the probability of at least 1-ρ, we have that

    sup_ω∈S_m^+| K(ω) _2-1NΦΦ^T(ω)_2| 
       ≤√(4n^2m^2L^2 cN)W^1 2( 2^13·cN (m+2)ρexp(6nlog 3 m+2)),

where W is the Lambert-W function.[Recall that the Lambert-W functions is the inverse of the function f(W)=We^W.] Now, since W(x)≤ln(x), for x>e, we can rewrite the upper bound in Eq. (<ref>) in terms of the elementary functions

    sup_ω∈S_m^+| K(ω) _2-1NΦΦ^T(ω)_2| ≤√(4n^2m^2L^2 cN)ln^1 2(2^13cN (m+2)ρ)+√(24n^3m^2L^2 cN(m+2)).




 §.§ Proof of Lemma <ref>

To establish the result, we need the decoupling technique from the probability theory. To state this result, consider independent Bernoulli random variables δ_1,⋯,δ_n∈{0,1} with the expectation [δ_i]=m/n, often known as independent selectors. Then, we define the subset T={i∈ [n]:δ_i=1}. Its average size is [|T|]=[∑_i=1^nδ_i]=m. Now, we are in position to state the following lemma:

(Decoupling, <cit.>)
	
	Consider a double array of real numbers {a_ij}_i,j=1^n such
	that a_ii=0 for all i=1,2,⋯,n. Then,
	
    ∑_i,j∈ [n]a_ij=4∑_i∈ [T],j∈ [T^c]a_ij

	where T is a random subset of {1,2,⋯,n} with average size [|T|]=n/2. In particular,
	
    4min_T⊆ [n]∑_i∈ T,j∈ T^ca_ij≤∑_i,j∈ [n]a_ij≤ 4max_T⊂ [n]∑_i∈ T,j∈ T^ca_ij,

	where the maximum and the minimum are over all subsets T of [n].
	□

To establish the result for this kernels class, we use  the convexity of the spectral norm

    K(ω)_2≤∑_i=1^mω_iK_i_2.

Let N_1 4 be a 1 4-net of the unit sphere S^n-1 such that |N_1 4|≤  9^n. By Lemma <ref>, we then have 

    K_i_2   =sup_z∈S^n-1 |⟨z, K_iz⟩|≤ 2max_z∈ N_1/4|⟨z,K_iz⟩|
       =2max_z∈ N_1/4|∑_k=1^nz_k^2K_i(x_k,x_k)+2∑_1≤ k<ℓ≤ nz_kz_ℓK_i(x_k,x_ℓ)|.

We note that the base kernels are centered, i.e., K_i(x_k,x_k)=ψ_i(x_k-x_k)-ψ_i(0)1_{x_k=x_k}=0. Therefore, the decoupling technique in Lemma <ref> can be applied to obtain

    K_i_2   ≤ 4|max_z∈ N_1/4_T[∑_k∈ T,ℓ∈ T^cz_kz_ℓK_i(x_k,x_ℓ)]|
       ≤ 4|max_z∈ N_1/4_T[∑_k∈ T,ℓ∈ T^cz_kz_ℓ∫_Ξφ(x_k;ξ)φ(x_ℓ;ξ)μ_i(dξ)] |
       ≤ 4max_z∈ N_1/4∫_Ξ_T[|∑_k∈ Tz_kφ(x_k;ξ)||∑_ℓ∈ T^cz_ℓφ(x_ℓ;ξ) |]μ_i(dξ).

To simplify the notations, let ϕ_T(x,z;ξ)∑_k∈ Tz_kφ(x_k;ξ), and ϕ_T^c(x,z;ξ)∑_ℓ∈ T^cz_ℓφ(x_ℓ;ξ). The  random variables ϕ_T(x,z;ξ) and ϕ_T^c(x,z;ξ) are not centered. Nevertheless, using the triangle inequality, we can obtain the following centered random variables

    14K_i_2   ≤𝖠_1+𝖠_2+𝖠_3+𝖠_4,

where each term on the right hand side of Eq. (<ref>) is defined as below

    𝖠_1   max_z∈ N_1/ 4_T,μ_i[|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)| ],
    𝖠_2   max_z∈ N_1/ 4_T,μ_i[_x[|ϕ_T(x,z;ξ)|] |ϕ_T^c(x,z;ξ)|],
    𝖠_3   max_z∈ N_1/4_T,μ_i[_x[|ϕ_T^c(x,z;ξ)|]|ϕ_T(x,z;ξ)| ],
    𝖠_4   max_z∈ N_1/4_T,μ_i[_x[|ϕ_T^c(x,z;ξ)|] _x[|ϕ_T^c(x,z;ξ)|]],

where ϕ_T(x,z;ξ)ϕ_T(x,z;ξ)-_x[ϕ_T(x,z;ξ)], and ϕ_T^c(x,z;ξ)ϕ_T^c(x,z;ξ)-_x[ϕ_T^c(x,z;ξ)] are the centered random variables.


In the sequel, we analyze each term separately:

Analysis of 𝖠_1: We compute a concentration bound using the Chernoff bound

    (max_z∈ N_1/ 4_T,μ_i[|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)| ]≥δ)
       ≤ e^2nlog(3)·max_z∈ N_1/4(_T,μ_i[|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)| ]≥δ)
       ≤  e^2nlog(3)· e^-βδ·max_z∈ N_1/4_x[e^β_T,μ_i[|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)| ]].

By Jensen's inequality, we have that

    _x[e^β_T,μ_i[|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)| ]]   ≤_T,μ_i,x[e^β|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)|]
       =_T,μ_i_x[e^β|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)||ξ,T],

where the last step follows by the law of total expectation.  Due to Assumption <ref>, the random variable ϕ_T(x,z;ξ) is zero-mean and bounded from above by 

    |ϕ_T(x,z;ξ)|   ≤ 2L∑_ℓ∈ T|z_ℓ|
       ≤ 2L√(|T|),

where in the last inequality, we used the fact that z_2=1 as z∈ N_1/4⊂S^d-1, and thus ∑_ℓ∈ T|z_ℓ|≤√(|T|)(∑_ℓ∈ T|z_ℓ|^2)^1 2≤√(|T|)z_2=√(|T|). Therefore, it is sub-Gaussian with the Orlicz norm of ϕ_T(x,z;ξ)_ψ_2≤  2L√(|T|). Similarly, ϕ_T^c(x,z;ξ)_ψ_2≤ 2L√(|T^c|). Moreover, conditioned on ξ and T, the sub-Gaussian random variables ϕ_T(x,z;ξ) and ϕ_T^c(x,z;ξ) are independent. Consequently, by Laplace's condition for sub-Gaussian random variables, we obtain

    _x[e^β |ϕ_T(x,z;ξ)| |ϕ_T^c(x,z;ξ)|| ξ,T, x_[T^c]]   ≤[e^2L^2|T|β^2|ϕ_T^c(x,z;ξ)|^2].

Now, since ϕ_T^c(x,z;ξ) is sub-Gaussian, from the Definition <ref> of Orlicz norm we conclude that

    [e^2L^2|T|β^2|ϕ_T^c(x,z;ξ)|^2]≤ 2,

for all T⊂{1,2,⋯,n} provided β≤1 2L^2n.
Hence,

    (max_z∈ N_1/ 4_T,μ_i[|ϕ_T(x,z;ξ)||ϕ_T^c(x,z;ξ)| ]≥δ)   ≤ 2e^2nlog(3)e^-βδ,
 
for all β<1 2L^2n.


Analysis of 𝖠_2 and 𝖠_3: In the sequel, we analyze 𝖠_2. The analysis of 𝖠_3 is similar. By exponential Chebyshev's inequality, we derive

    (max_z∈ N_1/ 4_T,μ_i[_x[|ϕ_T(x,z;ξ)|] |ϕ_T^c(x,z;ξ)|]≥δ)
       ≤ e^2nlog(3)e^-βδmax_z∈ N_1/ 4_T,ξ,x[e^β_x[|ϕ_T(x,z;ξ)|]|ϕ_T^c(x,z;ξ)|)]
       ≤ e^2nlog(3)e^-βδmax_z∈ N_1/ 4e^2β^2L^2|T^c|(_x[|ϕ_T(x,z;ξ)|])^2,

where the last inequality follows by the Laplace's condition for sub-Gaussian random variables. Due to the fact that |ϕ_T(x,z;ξ)|≤ L∑_ℓ∈ T|z_ℓ|≤ L√(|T|), we have ([|ϕ_T(x,z;ξ)|])^2≤ L^2|T|. Therefore, for all β∈_+, the following inequality holds,

    (max_z∈ N_1/ 4_T,μ_i[_x[|ϕ_T(x,z;ξ)|] |ϕ_T^c(x,z;ξ)|]≥δ)   ≤ e^2nlog(3)e^-βδ_T[e^2β^2L^4|T||T^c|]
       ≤ e^2nlog(3)e^-βδe^2β^2L^4n^2,

where the last inequality follows by the fact that |T|≤ n and |T^c|≤ n.  Similarly, it can be shown that 

    (max_z∈ N_1/ 4_T,μ_i[_x[|ϕ_T^c(x,z;ξ)|] |ϕ_T(x,z;ξ)|]≥δ)≤ e^2nlog(3)e^-βδe^2β^2L^4n^2.


Analysis of 𝖠_4: Due to Assumption <ref> and the triangle inequality, we have that 

    max_z∈ N_1/4_T,μ_i[_x[|ϕ_T^c(x,z;ξ)|] _x[|ϕ_T^c(x,z;ξ)|]]
       ≤ L^2_T[√(|T| (n-|T|))(∑_t∈ T|z_k|^2)^1 2(∑_t∈ T^c|z_k|^2)^1 2]
       ≤ L^2_T[√(|T|(n-|T|))].

Now, recall that |T|∼Bionomial(n,1 2) is a bionomial random variable. Therefore, by Jensen's inequality and concavity of the square root function f(x)=√(x), we derive that

    _T[ √(|T|(n-|T|))]   ≤√(_T[|T|(n-|T|)])
       ≤√(n[|T|]-[|T|^2])
       =12n√(1-1n).

Combining results of 𝖠_1-𝖠_4. We now employ a union bound to compute a concentration bound. Combining the concentration inequalities for 𝖠_1-𝖠_4 yields

    (1 4K_i_2-12n√(1-1n)≥δ)   ≤ 2e^2nlog(3)e^-βδ 3(1+e^2β^2L^4n^2)
       ≤ 4e^2nlog(3)e^-βδ 3e^2β^2L^4n^2,

for all β≤1 2L^2n. Assume that L>1 and δ=δ(n)=o(n), and let β=δ 12L^4n^2. Then,

    (1 4K_i_2-12n√(1-1n)≥δ)≤ 4e^2nlog(3)e^-δ^2  72L^4n^2.
 
 Therefore, with the probability of 1-ρ, we obtain
 
    K_i_2≤  2n√(1-1n)+4√(ln3^2n× 4ρ).

 This completes the proof of the thesis.▪
 





























 

 §.§ Proof of Theorem <ref>

 
 
We provide a distributionally robust generalization bound which extends the result of Bartlett and Mendelson <cit.>. Since ℓ̃ dominates the loss function ℓ, for all f∈ℱ, we obtain that
 
    sup_P∈𝒫_P[ℓ(Y,f(X))]   ≤sup_P∈𝒫_P[ℓ̃(Y,f(X))]
       = min_λ∈Λλlog_Q[exp(1λℓ̃(Y,f(X)) )]+λ r2.

Now, we define
 
    _Q[exp(1λℓ̃(Y,f(X)) )]   ≤_Q^n[exp(1λℓ̃(Y,f(X)) )]
       +sup_h∈π∘ℒ∘ℱ(_Q[h]-_Q^n[h])
       ≤_Q^n[exp(1λℓ̃(Y,f(X)) )]
       +sup_h∈π∘ℒ∘ℱ(_Q[h]-_Q^n[h])
       +_Q[ℓ̃(y,0)]-_Q^n[ℓ̃(y,0)],

where ℒ∘ℱ= {(x,y)↦ℓ̃(y,f(x))-ℓ̃(y,0):f∈ℱ}, and π∘ℱ'={ x↦exp(-f(x)/λ)-1: f∈ℱ'}.
Consider the second term inside the parenthesis in Eq. (<ref>). When (Y_i,X_i) changes, the supremum changes by no more than 2/n. We leverage McDiarmid's Martingale inequality to obtain

    sup_h∈π∘ℒ∘ℱ(_Q[h]-_Q^n[h])≤_Q[sup_h∈π∘ℒ∘ℱ(_Q[h]-_Q^n[h])] +√(2ln(2/δ) n).

A similar argument in conjunction with the fact that _Q[_Q^n[ℓ̃(y,0)]]=_Q[ℓ̃(y,0)] establishes the following inequality 

    _Q[exp(1λℓ̃(Y,f(X)) )]≤   _Q^n[exp(1λℓ̃(Y,f(X)) )]
       +_Q[sup_h∈π∘ℒ∘ℱ(_Q[h]-_Q^n[h])]+√(8ln(2/δ) n),

with the probability of at least 1-δ. We now invoke the following symmetrisation approach of van der Vaart and Wellner <cit.>.
We reproduce it here for the sake of readability:
(Symmetrization, <cit.>)
	
	Let X_1,⋯,X_n∼_i.i.d. P denote the random variables drawn i.i.d.  from the distribution P with the support 𝒳=supp(P). Furthermore, let ℱ denotes the class of real valued functions on 𝒳. Then
	
    _P[sup_f∈ℱ|_P^n[f(X)]-_P[f(X)]|]≤ 2_P[sup_f∈ℱ|1n∑_i=1^nε_if(X_i)| ],

	where ε_1,⋯, ε_n∈{-1,+1} is a Rademacher sequence, independent of X_1,⋯,X_n.□

Using the symmetrization technique, it can be shown that the expectation on the right hand side of Eq. (<ref>) is proportional to the Rademacher complexity, see <cit.>. In particular,

    _Q[sup_h∈π∘ℒ∘ℱ(_Q[h]-_Q^n[h])]=2ℜ^n(π∘ℒ∘ℱ).

Plugging Eq. (<ref>) into Eq. (<ref>), we obtain the following inequality

    _Q[exp(1λℓ̃(y,f(x)) )]≤   _Q^n[exp(1λℓ̃(y,f(x)) )]
       +2ℜ^n(π∘ℒ∘ℱ)+√(8ln(2/δ) n).

We now wish to derive the Rademacher complexity in terms of the function class ℱ instead of the composite function class π∘ℒ∘ℱ. To this end, we invoke <cit.> and the fact that ψ(y,·):→_+
is L_ψ-Lipschitz  for all y∈𝒴, and exp(-x/λ) is 1/λ^2-Lipschitz for x>0.

    ℜ^n(π∘ℒ∘ℱ)≤L_ψλ^2ℜ^n(ℱ).

Therefore, from Eq. (<ref>), we obtain that

    _Q[exp(1λℓ̃(y,f(x)) )]≤   _Q^n[exp(1λℓ̃(y,f(x)) )]+2L_ψλ^2ℜ^n(ℱ)+√(8ln(2/δ) n).

Taking the logarithm from both sides and multiplying by λ>0 now yields

    λlog_Q[exp(1λℓ̃(y,f(x)) )]
       ≤λlog_Q^n[exp(1λℓ̃(y,f(x)) )]+λlog(1+ 2L_ψλ^2ℜ^n(ℱ)+√(8ln(2/δ)/n)_Q^n[exp(1λℓ̃(y,f(x)) )]).

We proceed from Eq. (<ref>) using the basic inequality log(1+x)≤ x for x≥ -1, as well as the fact that _Q^n[exp(1λℓ̃(y,f(x)) )]≥ 1 for all λ>0. The latter inequality holds since ℓ̃(y,f(x))≥ℓ(y,f(x)) ≥ 0 for all (x,y)∈𝒳×𝒴. From Eq. (<ref>), we then obtain that for all λ> 0 that

    λlog_Q[exp(1λℓ̃(y,f(x)) )]
       (a)≤λlog_Q^n[exp(1λℓ̃(y,f(x)) )]+λlog(1+ 2L_ψλ^2ℜ^n(ℱ)+√(8ln(2/δ)/n))
       (b)≤λlog_Q^n[exp(1λℓ̃(y,f(x)) )]+2L_ψλℜ^n(ℱ)+λ√(8ln(2/δ) n).

where in (a) we used the fact that

    log(1+ 2L_ψλ^2ℜ^n(ℱ)+√(8ln(2/δ)/n)_Q^n[exp(1λℓ̃(y,f(x)) )])	≤log(1+ 2L_ψλ^2ℜ^n(ℱ)+√(8ln(2/δ)/n)),

since as we noted earlier _Q^n[exp(1λℓ̃(y,f(x)) )]≥ 1. Furthermore, in (b), we once again used the basic inequality log(1+x)≤ x for x≥ -1.
The Taylor expansion with respect to λ>0 yields

    λlog_Q^n[exp(1λℓ̃(y,f(x)) )]   =λlog_Q^n[(1+∑_p=1^∞ℓ̃^p(y,f(x))p!λ^p)]
       ≤_Q^n[∑_p=1^∞ℓ̃^p(y,f(x))p!λ^p-1],

where the last step follows again using the basic inequality log(1+x)≤ x for x≥ -1. Plugging the upper bound in Equation (<ref>) yields

    sup_P∈𝒫_P[ℓ(Y,f(X))]
       ≤inf_λ>0(_Q^n[∑_p=1^∞ℓ̃^p(y,f(x))p!λ^p-1]+2L_ψλℜ^n(ℱ)+λ√(8ln(2/δ) n)+λ r2).
 
Now, we let λ=B where Bsup_x,y∈𝒳×𝒴ℓ̃(y,f(x)). Then, ℓ̃^p-1(y_i,f(x_i))/λ^p-1<1 for all (y_i,x_i)_1≤ i≤ n. We then obtain

    sup_P∈𝒫_P[ℓ(Y,f(X))]   ≤ (e-1)
    _Q^n[ℓ̃(y,f(x))]
       +2L_ψ Bℜ^n(ℱ)+B √(8ln(2/δ) n)+Br2.

 ▪
 

§ PROOF OF AUXILIARY RESULTS

 


 §.§ Proof of Lemma <ref>

 

The proof follows by applying McDiarmid's Martingale inequality. In particular, let (ξ^k_i)_1≤ i≤ m^1≤ k≤ N and (ξ̃^k_i)_1≤ i≤ m^1≤ k≤ N denote two vectors that differ only in (i_0,k_0) coordinate for some i_0∈{1,2,⋯,m} and k_0∈{1,2,⋯,N}. That is,

    ξ_i^k=ξ_i^k,   ∀ i∈{1,2,⋯,m}\{i_0}, ∀ k∈{1,2,⋯,N}\{k_0}.

Let E_N(z,z̃) and E_N'(z,z̃) denote the associated functions. Then, 

    |E_N(z,z̃)-E'_N(z,z̃)|   ≤ω_i_0N|_P^⊗ 2[yỹφ(x;ξ_i_0^k_0)φ(x̃;ξ_i_0^k_0) ]-_P^⊗ 2[yỹφ(x;ξ_i_0^k_0)φ(x̃;ξ_i_0^k_0) ]|
       ≤2L^2ω_i_0N,

where the last step follows by Assumption <ref>. By McDiarmid's Martingale inequality and the fact that [E_N(z,z̃)]=0, we then have that

    (|E_N(z,z̃)|≥ε)≤ 2exp(-2Nε^2ω_2^2L^4).

Since ω=(ω_1,⋯,ω_m)∈S_m^+, ω_2≤ω_1= 1, and we can simplify the upper bound to obtain

    (|E_N(z,z̃)|≥ε)≤ 2exp(-2Nε^2L^4).

From Lemma <ref>, we thus conclude E_N_ψ_2≤L^2 2√(N). ▪



 §.§ Proof of Lemma <ref>



To establish the proof, in the sequel, we treat the upper and lower bounds separately:




  §.§.§ The Upper Bound
Recall the definition of X(z_i,z_j) from Eq. (<ref>).  From Equation (<ref>), we have that

    _Q^⊗ 2[sup_P^n∈𝒫^nT_ω(P^n)]   =_Q^⊗ 2[inf_λ>0H_n,N(λ) ]
       =_Q^⊗ 2[min_λ>0λlog2n(n-1)∑_1≤ i<j≤ nexp(-X(z_i,z_j)λ)  +λ r2]
       ≤inf_λ>0_Q^⊗ 2[λlog2n(n-1)∑_1≤ i<j≤ nexp(-X(z_i,z_j)λ)+λ r2]
       (a)≤inf_λ>0λlog_Q^⊗ 2[2n(n-1)∑_1≤ i<j≤ nexp(-X(z_i,z_j)λ) ]+λ r2
       =inf_λ>0λlog_Q^⊗ 2[exp(-X(z,z̃)λ)  ]+λ r2
       =sup_P∈𝒫T_ω(P),

where (a) follows from Jensen's inequality, and concavity of the log function.



  §.§.§ The Lower Bound
: To establish the lower bound, we invoke Lemma <ref> to obtain

    _Q^⊗ 2[sup_P^n∈𝒫^nT_ω(P^n)]   =_Q^⊗ 2[inf_λ>0H_n,N(λ) ]
       =_Q^⊗ 2[inf_λ>0(H_n,N(λ)-[H_n,N(λ)]+[H_n,N(λ)])]
       ≥inf_λ>0_P^⊗ 2[H_n,N(λ)]-[sup_λ>0|H_n,N(λ)-[H_n,N(λ)] | ].

To compute a lower bound on the first term, we leverage the Gumbel max perturbation in Eq. (<ref>) to obtain

    inf_λ>0_Q^⊗ 2[H_n,N(λ)]   =inf_λ>0_Q^⊗ 2[ λlog2n(n-1)∑_1≤ i<j≤ nexp(-X(z_i,z_j)λ)  +λ r2]
       =inf_λ>0_Q^⊗ 2,ν[max_1≤ i<j≤ n{-X(z_i,z_j)+λζ_ij}]+λlog2n(n-1)  +λ r2,
       ≥_Q^⊗ 2[-X(z,z̃)].

The last term in Eq. (<ref>) can be written as the limit

 
    _Q^⊗ 2[-X(z,z̃)]   =lim_λ↓ 0λlog_Q^⊗ 2[ exp(-X(z,z̃)λ)]
       =lim_λ↓ 0λlog_Q^⊗ 2[ exp(-X(z,z̃)λ)]+λlog2n(n-1)+λ r2.

 
We thus proceed as follows
 
    inf_λ>0_Q^⊗ 2[H_n,N(λ)]   ≥lim_λ↓ 0λlog_Q^⊗ 2[ exp(-X(z,z̃)λ)]+λlog2n(n-1)  +λ r2
       ≥inf_λ>0log_Q^⊗ 2[ exp(-X(z,z̃)λ)]+λlog2n(n-1)  +λ r2
       =sup_P∈𝒫T_ω(P) .

To compute a lower bound for the second term of Eq. (<ref>), we once again leverage Talagrand's concentration of measure in Appendix <ref> . In particular, we recall from Appendix <ref> that c≤λ_∗≤ C. Moreover, recall that the mapping 

    X=(X_ij)_1≤ i<j≤ n↦ f(X)=H_n,N(λ)=min_λ>0λlog_Q^n,⊗ 2[exp(-1λX(z,z̃) )]+λ r2,

is C^2n^2exp(2L^2 c)-Lipschitz. Therefore, based on Talagrand's concentration of measure, for any λ∈ [c,C], we have

    (|H_n,N(λ)-[H_n,N(λ)]|≥ε)≤ 2exp(-δ^2n^2K^2L^2),

where K . Therefore, H_n,N(λ) is sub-Gaussian with the Orlicz norm of H_n,N(λ)_ψ_2≤ nKL. Now, consider a ε-cover 𝒩_ε={λ_i}_i=1^N_ε of the interval [c,C], where N_ε≤(C-c)ε. The maximal inequality for the sub-Gaussian random variables in Lemma <ref> yields

    [max_i≤ N_ε|H_n,N(λ_i)-[H_n,N(λ_i)]| ]
       ≤KL n√(2log 2N_ε)
       ≤KL n√(2log(2(C-c)ε)).

Due to the Lipschitz continuity of the mapping λ↦H_n,N(λ), we have that

    [sup_λ∈ [c,C]|H_n,N(λ)-[H_n,N(λ)] | ]   ≤[max_i≤ N_ε|H_n,N(λ_i)-[H_n,N(λ_i)]| ]+εC^2K^2 n^2
       ≤KL n√(2log2(C-c)ε)+C^2K^2ε n^2.

Plugging Inequalities (<ref>)-(<ref>) in Eq. (<ref>) yields

    _Q^⊗ 2[sup_P^n∈𝒫^nT_ω(P^n)]≥sup_P∈𝒫T_ω(P)-KLn√(2log2(C-c)ε)-C^2K^2εn^2.

Letting ε=2(C-c) yields

    _Q^⊗ 2[sup_P^n∈𝒫^nT_ω(P^n)]   ≥sup_P∈𝒫T_ω(P)-2C^3K^2 n^2.

▪



 §.§ Proof of Lemma <ref>



Define the following empirical process

    𝔾_s,nf=ℙf-ℙ_s,nf,

where

    ℙf_Pf(Z_1:n),   ℙ_s,nf U_s(f,Z_1:n).

We wish to bound 𝔾_s,nf_ℱsup_f∈ℱ|𝔾_s,nf| with a high probability. Without loss of generality, we suppose ℱ contains the zero function, since we can always augment ℱ with the zero function without changing the order of its covering number. We apply Markov's inequality to obtain

    (𝔾_s,nf_ℱ≥ t )≤_P[𝔾_s,nf^p_ℱ]t^p=ℙ𝔾_s,nf^p_ℱt^p,

for p≥ 1. The following lemma is an extension of the symmetrization technique in Theorem <ref> for the U-statistic of the order s:
(Symmetrization of the U-statistic)

Consider the empirical process 𝔾_s,nf characterized in Eq. (<ref>). Then, the following inequality holds

    ℙ(sup_f∈ℱ|𝔾_s,nf|)^p≤ 2^spℙ(sup_f∈ℱ | ℙ^ε_s,nf|)^p,

where

    ℙ^ε_s,nf1n  s∑_1≤ i_1≤⋯≤ i_s≤ nε_i_1ε_i_2⋯ε_i_sf(Z_i_1,Z_i_2,⋯,Z_i_s),

is the symmetrized U-statistic, and ε_1,⋯ε_n∼_i.i.d.Uniform{-1,+1} are the Rademacher random variables.

The proof of Lemma <ref> for the special case of s=2 can be found in <cit.>.

In the sequel, we find an upper bound for the right hand side of Eq. (<ref>) in Lemma <ref>.  To compute the right hand side of Eq. (<ref>), we levereage a standard chaining argument similar to <cit.>. Specifically, let ℱ̅={f_1,f_2,⋯, f_𝒩(ε,ℱ,L_2(P))} denotes a minimal ε-covering of ℱ. Then, using the one step discretization yields

    sup_f,g∈ℱ | ℙ^ε_s,n(f-g)|≤ 2max_f,g∈ℱ̅| ℙ^ε_s,n(f-g)|+2sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|.

Using the basic inequality (∑_i=1^Na_i)^p≤ N^p-1∑_i=1^Na_i^p and subsequently taking the expectation yields

    ℙ(sup_f,g∈ℱ | ℙ^ε_s,n(f-g)|)^p≤   2^pℙ(max_f,g∈ℱ̅| ℙ^ε_s,n(f-g)|)^p
       +2^pℙ(sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|)^p.

We first bound the first term on the right hand side of Eq. (<ref>). Suppose that

    δsup_f,g∈ℱf-g_L_r(P)<+∞.

For each m=1,2,⋯ let ε_m 2^-mδ, and let ℱ̅_m⊂ℱ denotes the ε_m-covering of ℱ̅. Futhermore, define the mapping π_m:ℱ̅→ℱ̅_m

    π_m(f)min_g∈ℱ̅_mf-g_L_r(P),    f∈ℱ̅.

For each f∈ℱ̅, define the sequence of points (f_1,⋯,f_M) in ℱ such that f_M=f and f_m=π_m(f_m+1). Here, M is the smallest number such that given the ε-covering {f_1,⋯,f_N} of ℱ with N=𝒩(ε,ℱ,L_2(P)), the norm balls ^r_ε_L(f_i) do not intersect. That is,

    f-g_L_r(P)>ε_M=2^-Mδ,   for all f,g∈ℱ̅.

Since M is the smallest integer satisfying Eq. (<ref>), we know that there exists some f,g∈ℱ such that f-g_L_r(P)<ε_M-1=2^-(M-1)δ, since otherwise, M-1 will be the smallest such integer instead. At the same time, we know that ℱ̅ is a ε-covering of ℱ, so the following inequality holds

    ε≤f-g_L_r(P)≤ 2^-(M-1)δ,   for all f,g∈ℱ̅.

Therefore, M≤ 1+log_2(δ/ε). Using the linearity of the empirical process ℙ^ε_s,n and the triangle inequality yields

    | ℙ^ε_s,n(f-f_1)|≤∑_m=2^M|ℙ^ε_s,n(f_m-f_m-1)|.

Similarly, for another function g∈ℱ̅, we obtain

    | ℙ^ε_s,n(g-g_1)|≤∑_m=2^M| ℙ^ε_s,n(g_m-g_m-1)|.

Thus, for f,g∈ℱ̅ we obtain

    max_f,g∈ℱ̅| ℙ^ε_s,n(f-g)|≤   max_f_1,g_1∈ℱ_1| ℙ^ε_s,n(f_1-g_1)|
       +2∑_m=2^Mmax_f∈ℱ_m| ℙ^ε_s,n(f-π_m-1(f))|.

We raise both sides to the power of p≥ 1, use the basic inequality (∑_i=1^Na_i)^p≤ N^p-1∑_i=1^Na_i^p, and then take the expectation to obtain

    ℙ(max_f,g∈ℱ̅| ℙ^ε_s,n(f-g)| )^p≤   M^p-1ℙ(max_f_1,g_1∈ℱ_1| ℙ^ε_s,n(f_1-g_1)| )^p
       +2^pM^p-1∑_m=2^Mℙ(max_f∈ℱ_m| ℙ^ε_s,n(f-π_m-1(f))|)^p.

To obtain a bound for the second term, we first recognize that

    max_f∈ℱ_mf-π_m-1(f)_L_r(P)≤  2^-mδ,

due to the fact that π_m-1(f) is the best approximation of f from ℱ_m. Let κ=⌈ n/s ⌉ and for any fixed Rademacher sequence ε_1,⋯,ε_n∈{-1,+1}^n, define

    ψ_m(Z_1,⋯,Z_n)1κ∑_j=1^κε_s(j-1)+1ε_s(j-1)+2⋯ε_sjg_m(Z_s(j-1)+1,⋯,Z_sj),

where g_m f-π_m-1f. We now have

    κ∑_(σ_1,⋯,σ_n)∈Π_nψ_m(Z_σ_1,⋯,Z_σ_n) = κ s!(n-s)!∑_i_1<i_2<⋯<i_mε_i_1ε_i_2⋯ε_i_sg_m(Z_i_1,⋯,Z_i_s),

where Π_n is the set of the permutations of the set {1,2,⋯,n}. Therefore,

    ℙ_s,n^ε(f-π_m-1f)=1n!∑_(σ_1,⋯,σ_n)∈Π_nψ_m(Z_σ_1,⋯,Z_σ_n).

The function ψ_m(Z_σ_1,⋯,Z_σ_n) is the average of κ i.i.d. random variables since the terms in the sum in Eq. (<ref>) are non-overlapping. Let r=2. Due to Eq. (<ref>), we have that

    ε_iε_i+1⋯ε_i+sg_m(Z_i,⋯,Z_i+s)_L_2(P⊗ Q)   =g_m(Z_i,⋯,Z_i+s)_L_2(P)
       = f-π_m(f)_L_2(P)≤δ 2^-m,

for all f∈ℱ_m, where Q=Uniform{-1,+1}. Furthermore, ℙ(ε_iε_i+1⋯ε_i+sg_m(Z_i,⋯,Z_i+s))=0. Therefore, each term in the numerator of Eq. (<ref>) is zero mean with the variance bounded by σ^2=δ^2 2^-2m. Thus, ψ_m(Z_σ_1,⋯,Z_σ_n) is sub-Gaussian, i.e., 

    [exp(s ψ_m(Z_σ_1,⋯,Z_σ_n))]≤exp(δ^2 2^-2m s^22κ),   ∀ s>0.

The inequality in the previous display also implies

    [exp(s ℙ_s,n^ε(f-π_m-1f)) ]   =[exp( s n!∑_(σ_1,⋯,σ_n)∈Π_nψ_m(Z_σ_1,⋯,Z_σ_n) )]
       (a)≤1n!∑_(σ_1,⋯,σ_n)∈Π_n[exp(s  ψ_m(Z_σ_1,⋯,Z_σ_n) )]
       (b)≤exp(δ^2 2^-2m s^22κ),   ∀ s>0,

where (a) is due to Jensen's inequality, and (b) is due to Eq. (<ref>). Therefore, ℙ_s,n^ε(f-π_m-1f) is also sub-Gaussian. We leverage the sub-Gaussian maximal inequality in Lemma <ref> to obtain

    ℙ(max_f∈ℱ_m| ℙ^ε_s,n(f-π_m-1(f))|)^p≤δ^p 2^-pmκ^p/2(log𝒩(δ 2^-m, ℱ,L_2(P)))^p/2.

Similarly, it can be shown that

    ℙ(max_f_1,g_1∈ℱ_1| ℙ^ε_s,n(f_1-g_1)| )^p≤(δ/2)^pκ^p/2(log𝒩(δ/2, ℱ,L_2(P)))^p/2.

Substituing Eqs. (<ref>) and (<ref>) into Eq. (<ref>) to obtain

    ℙ(max_f,g∈ℱ̅| ℙ^ε_s,n(f-g)| )^p≤ 2^p+1M^p-1∑_m=1^M(δ 2^-m)^pκ^p/2(log𝒩(δ 2^-m, ℱ,L_2(P)))^p/2.

The function s↦ (log N(s,ℱ,L_2(P)))^p/2 is monotone increasing on [0,δ]. Therefore, we can upper bound the sum in Eq. (<ref>) with an integral as follows

    ℙ(max_f,g∈ℱ̅| ℙ^ε_s,n(f-g)| )^p   ≤2^p+2κ^p/2M^p-1∑_m=1^M∫_δ 2^-(m+1)^δ 2^-m(log𝒩(s,ℱ,L_2(P)) )^p/2ds
       ≤2^p+2κ^p/2M^p-1∫_δ 2^-(M+1)^δ/2(log𝒩(s,ℱ,L_2(P)) )^p/2ds.

We further proceed using the inequality ε/4≤δ/2^M+1 to plug for the value of M

    ℙ(max_f∈ℱ̅| ℙ^ε_s,n(f-g)| )^p≤2^p+2κ^p/2( 2δεlog(2))^p-1∫_ε/4^δ/2(log𝒩(s,ℱ,L_2(P)) )^p/2ds.

Plugging Eq. (<ref>) into Eq. (<ref>) yields

    ℙ(sup_f,g∈ℱ| ℙ^ε_s,n(f-g)| )^p   ≤ 2^pℙ(sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|)^p
       +2^p+2κ^p/2( 2δεlog(2))^p-1∫_ε/4^δ/2(log𝒩(s,ℱ,L_2(P)) )^p/2ds.

Now consider the following two cases:


  * p=1: In this case, the upper bound in Eq. (<ref>) reduces to

    ℙ(sup_f,g∈ℱ| ℙ^ε_s,n(f-g)| )   ≤ 2ℙ(sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|)
       +4√(κ)∫_ε/4^δ/2√(log𝒩(s,ℱ,L_2(P)))ds.

Using the monotone convergance theorem <cit.> yields

    lim_ε↓ 0ℙ(sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|)   =ℙ(lim_ε↓ 0sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|)
       =0.

Therefore,

    ℙ(sup_f,g∈ℱ| ℙ^ε_s,n(f-g)| )≤4√(κ)∫_0^δ/2√(log𝒩(s,ℱ,L_2(P)))ds.


  * p>1: In this case, letting ε↓ 0 blows up the upper bound in Eq. (<ref>). However, we note that due to sub-Gaussianity of the empirical process, we have

    ℙ(sup_f,g∈ℱ:f-g_L_r(P)≤ε | ℙ^ε_s,n(f-g)|)^p=Ω(ε^p).



Let g=0 (zero function) and consider p=1 in the sequel.  Using the symmetrization result of Lemma <ref> and Markov inequality yields

    (𝔾_s,nf_ℱ≥ t )≤1t4√(κ)∫_0^δ/2√(log𝒩(s,ℱ,L_2(P)))ds.

for all p≥ 1. Therefore, with the probability of at least 1-ϱ, we obtain

    𝔾_s,nf_ℱ≤1ϱ4√(κ)∫_0^δ/2√(log𝒩(s,ℱ,L_2(P)))ds.


▪


 §.§ Proof of Lemma <ref>



Consider the function class ℱ' defined in Lemma <ref>. Let f_ω (√(ω_1)f^k_i)_i=1,2,⋯,m^k=1,2,⋯,N, f^k_i∈ℱ and consider the ϵ-covering balls 

    _2r^ϵ(f^0_ℓ){f∈ℱ:  f-f^0_ℓ_L_2r(Q)≤ϵ},

for ℓ∈{1,2,⋯,𝒩(ϵ,ℱ,L_r(Q))}. Let π:{1,2,⋯,N}×{1,2,⋯,m}↦{1,2,⋯,𝒩(ϵ,ℱ,L_r(Q))} denotes a mapping that assigns the (i,k) index of f_i^k to the center of a covering ball, i.e., f^i_k∈_2r^ϵ(f^0_π(i,k)). Since ψ is L_ψ-Lipschitz, we obtain the following inequality

    |ψ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ψ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)|
       ≤L_ψ N|yỹ⟨f(x),f(x̃)⟩-yỹ⟨f_π^0(x),f_π^0(x̃)⟩|
        =L_ψ N|⟨f(x),f(x̃)⟩-⟨f^0_π(x),f^0_π(x̃)⟩|,

where f_π^0 (f^0_π(i,k))_i=1,2,⋯,m^k=1,2,⋯,N, and in the last step follows by the fact that |yỹ|=1 due to binary class labels y,ỹ∈{-1,+1}. We proceed from Eq. (<ref>) by applying the triangle inequality

    |ψ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ψ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)|
       ≤L_ψ N| ⟨f_ω(x),f_ω(x̃)⟩-⟨f_ω(x),f^0_π(x̃)⟩|+L_ψ N| ⟨f_ω(x),f^0_π(x̃)⟩-⟨f^0_π(x),f^0_π(x̃)⟩|
       ≤L_ψ N∑_k=1^N∑_i=1^mω_i|f^k_i(x)| |f^k_i(x̃)-f^0_π(i,k)(x̃)|+ L_ψ N∑_i=1^N|f^0_π(i)(x̃)| |f^k_i(x)-f^0_π(i,k)(x)|
       ≤L_ψ NF(x)∑_k=1^N∑_i=1^mω_i|f_i^k(x̃)-f^0_π(i,k)(x̃)|+L_ψ NF(x̃)∑_i=1^N∑_i=1^mω_i|f_i^k(x)-f^0_π(i,k)(x)|,

where F(x)sup_f∈ℱ|f(x)| is the envelope function. We raise both sides of the inequality to the power of r≥ 1 and use the basic inequality |∑_i=1^nx_i|^r≤ n^r-1∑_i=1^n|x_i|^r to obtain

    |ϕ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ϕ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)|^r
       ≤(2Nm)^r-1 N^r L_ψ^rF^r(x)∑_k=1^N∑_i=1^mω^r_i|f_i^k(x̃)-f^0_π(i,k)(x̃)|^r
       +(2Nm)^r-1 N^r L_ψ^rF^r(x̃)∑_k=1^N∑_i=1^mω^r_i|f_i^k(x)-f^0_π(i,k)(x)|^r.

Taking the expectation with respect to the product of the joint distribution P^⊗ 2, P∈ℳ(𝒳×𝒴) with the marginal Q∈ℳ(𝒳) now yields

    ϕ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ϕ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)^r_L_r(P)
       ≤(Nm)^r-1 N^r2^rL_ψ^r∑_k=1^N∑_i=1^mω^r_iF·|f_i^k-f^0_π(i,k)|^r_L_r(Q).

Using the fact that |F|=F yields

    ϕ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ϕ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)^r_L_r(P)
       (a)≤(2Nm)^r-1 N^r∑_k=1^N∑_i=1^mω_i^rF^2_L_r(Q)^r/2·(f_i^k-f^0_π(i,k))^2^r/2_L_r(Q)
       = (Nm)^r-1 N^r2^rL^r∑_k=1^N∑_i=1^mω_i^rF_L_2r(Q)^r·f_i^k-f^0_π(i,k)^r_L_2r(Q),

where (a) is due to the generalized Hölder inequality |f|^θ· |g|^1-θ_p≤f_p_1^θ·g_p_2^1-θ such that 1 p=θ p_1+(1-θ) p_2 for θ∈ (0,1). Due to the fact that f_i^k∈_2r^ϵ(f^0_π(i,k)), we obtain from Eq. (<ref>) that

    ϕ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ϕ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)^r_L_r(P)≤ m^r-1(2LF_L_2r(Q)ϵω_r)^r.

Since ω∈S^+_m, ω_r≤ω_1=1 for r≥ 1. Therefore, since m≥ 1, we can simplify the upper bound as follows

    ϕ(1 Nyỹ⟨f_ω(x),f_ω(x̃)⟩)-ϕ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩)^r_L_r(P)≤ (2mLF_L_2r(Q)ϵ)^r.

Therefore, ϕ∈_r^ϵ'(ϕ_k^0), where ϵ' (2mLF_L_2r(Q)ϵ)^r, ϕ_k^0ϕ(1 Nyỹ⟨f^0_π(x),f^0_π(x̃)⟩), and the index k∈{0,1,⋯, (𝒩(ϵ,ℱ,L_2r(Q)))^mN}. Consequently,

    𝒩((2mLF_L_2r(Q)ϵ)^r,ℱ',L_r(P))≤ (𝒩(ϵ,ℱ,L_2r(Q)))^mN.

Alternatively,

    log𝒩(ϵ',ℱ',L_r(P))≤ mMlog(𝒩((ϵ')^1 r2mLF_L_2r(Q),ℱ,L_2r(Q))).

▪


§ USEFUL PROPERTIES OF THE SUB-EXPONENTIAL AND SUB-GAUSSIAN RANDOM VARIABLES


Recall the notions of the sub-Gaussian and sub-exponential norms from Definition <ref>. In the sequel we collect several useful lemmas regarding the properties of the sub-Gaussian and sub-exponential random variables:

 (Sum of Sub-Gaussian and Sub-Exponential Random Variables)
		
	There exists a universal constant C_s, such that the sum of two dependent sub-Gaussian random variables with parameters K_1 and K_2 is C_s(K_1 +K_2)-sub-Gaussian, and the sum of two dependent sub-exponential random variables with parameters K_1 and K_2 is C_s(K_1+K_2)-sub-exponential. □
	


(Norm of Difference of Sub-Gaussian Random Variables)
	
	Suppose X∈^d and Y∈^d are two sub-Gaussian random vectors such that X_ψ_2= K_1 and Y_ψ_2= K_2. Then, Z=X-Y^2_2 is sub-exponential with the Orlicz constant of
	
    Z_ψ_1≤ 2K_1+2K_2+K_1K_2.

	Furthermore, its moments satisfy the following upper bounds
	
    [|Z|^p]≤ 2^2p-1d^pC_2pX_ψ_2^2p+2^2p-1d^pC_2pY^2p_ψ_2.

□
 

Proof. We begin the proof by expanding the squared ℓ_2-norm as follows

    Z=X_2^2+Y_2^2-2⟨X,Y⟩

We now prove that each term on the right hand side is sub-exponential. First, consider the squared terms X_2^2 and Y_2^2. We can assume X_ψ_2=1 by scale invariance. Let W∼𝖭(0,I_d× d) be independent of X. It is known that [e^λ Z^2]=1√(1-2λ), Z∼𝖭(0,1), and λ<1/2. So, we have that

    [λW_2^2]=∏_i=1^d[λ W_i^2]=1(1-2λ)^d/2,

for any λ<1/2. Now, for any λ>0, we evaluate the quantity [√(2λ)⟨X,W⟩] in two ways by conditioning on X and then W. We have

    [exp(√(2λ)⟨X,W⟩)]   =[[exp(√(2λ)⟨X,W⟩)]|X]
       = [exp(√(2λ)X_2^2/2)]
       =[e^λX_2^2].

On the other hand, we have

    [exp(√(2λ)⟨X,W⟩)]   =[[exp(√(2λ)⟨X,W⟩)]|W]
       ≤[e^√(2λ)X_2/2]
       =[e^λW_2^2]
       =1(1-2λ)^d/2.

Now, by Jensen's inequality [e^λX_2^2]≥ e^λ[X_2^2]. Further, putting together Eqs. (<ref>) and (<ref>), yields

    [e^λ (X_2^2-[X_2^2])]   ≤[e^λX_2^2]
       ≤1(1-2λ)^d/2
       ≤exp(4λ^2),
  
i.e., X_2^2 satisfies the Laplace's property for λ<1/2, and is thus sub-exponential with the Orlicz norm of X_2^2_ψ_1≤ 2K_1. Similarly, Y_2^2_ψ_1≤ 2K_2. Now, consider the inner product term ⟨X,Y⟩. Using the iterated law of expectation and the Laplace inequality of sub-Gaussian random variables, we obtain that for all λ>0 

    [exp(λ⟨X,Y⟩)]   =[[exp(λ⟨X,Y⟩)|Y]]
       =[[exp(λY_2⟨X,YY_2⟩)|Y]]
       = [exp(1 2λ^2K_1^2Y_2^2)],

where we used the fact that X∈^d is a sub-Gaussian vector if ⟨u,X⟩ is sub-Gaussian for any vector u∈S^d-1. Now, since Y_2^2 is 2K_2-sub-exponential, we conclude that if λ≤12K_1^2K^2_2, we have that 

    [exp(λ⟨X,Y⟩)]   = [exp(1 2λ^2K_1^2Y_2^2)],
       =∑_p≥ 0λ^2pK_1^2p2^pp![Y_2^2p]
       ≤∑_p≥ 0λ^2pK_1^2pp!(2K_2)^2p
       =exp(λ^2K_1^2K_2^2),

where the inequality follows from Definition <ref> of the sub-exponential random variable. Thus, we proved that ⟨X,Y⟩_ψ_1≤ K_1K_2. Now, from the expansion in Eq. (<ref>), we observe that Z is the sum of sub-exponential random variables. By Lemma <ref>, Z is also sub-exponential with the constant Z_ψ_1=2K_1+2K_2+K_1K_2.

To compute the moments of the random variable Z, we use the following expansion

    [|Z|^p]   =[X-Y^2p_2]
       (a)≤[(X_2+Y_2)^2p]
       (b)≤ 2^2p-1[X_2^2p]+2^2p-1[Y_2^2p].

where (a) is due to the triangle inequality, and (b) is due to the basic inequality |x-y|^p≤ 2^p-1(|x|^p+|y|^p). Now, for a sub-Gaussian random vector X∈^d, the following inequality holds for all u∈^d independent of X (cf. <cit.>),

    [⟨u,X⟩|^2p]≤ C_2pu_2^2pX_ψ_2^2p,

where C_2p=p!2^p+1. Letting u=e_j∈^d, yields that

    [|X_j|_2^2p]≤ C_2pX_ψ_2^2p,

where we used the fact that e_j_2=1. Now, since

    [X_2^2p]=[(∑_j=1^dX^2_j)^p]≤ d^p-1∑_j=1^d[|X_j|_2^2p]≤ C_2pd^pX_ψ_2^2p.

Plugging Inequality (<ref>) into (<ref>) yields

    [|Z|^p]≤ 2^2p-1d^pC_2pX_ψ_2^2p+2^2p-1d^pC_2pY^2p_ψ_2.
 
▪


The proof of lemma <ref> follows directly from the equivalet definition of sub-Gaussian and sub-exponential random variables based on the Orlicz norms.

(Bernstein inequality for sub-exponential random variables) 
	
Let X_1, ⋯,X_n be independent sub-exponential random variables with X_i_ψ_1≤ b. Then, there exists a universal constant c>0 such that, for all δ>0,

    (|∑_i=1^n(X_i-[X_i])|≥δ)≤exp(-c·min(δ^2 nb^2,δ b)).



The following lemma provides the Orlicz norm of a sub-Gaussian random variable satisfying a concentration inequality:

	
Let Z denotes a random variable with zero mean [Z]=0 satisfying the following concentration inequality:

    (|Z|≥δ)≤exp(-λδ^2).

Then, Z is sub-Gaussian with the Orlicz norm of Z_ψ_2≤ 1/√(2λ).



Proof: We establish an upper bound on the 2p-moments of the random variable |Z| as follows

    [|Z|^2p]   =∫_0^∞2pu^2p-1(|Z|≥ u)du
       ≤∫_0^∞2pu^2p-1exp(-λ u^2)du
       ≤ pλ^-pΓ(p ),

for p∈, where we used the fact that Γ(x)∫_0^∞t^x-1exp(-t)dt. Now, since Γ(p)=(p-1)!, we have 

    [exp(|Z|^2/β^2)]   =∑_p=0^∞1p!β^2p[|Z|^2p]
       ≤∑_p=0^∞(1β^2λ)^p
       ≤11-β^2λ.

Therefore, when β≤1/√(2λ), we have  [exp(|Z|^2/β^2)]≤ 2, i.e., Z_ψ_2≤ 1/√(2λ). ▪
		


(Sub-Gaussian Maximal Inequality) Let X_1,⋯,X_n denotes centered sub-Gaussian random variables with the variance proxy of σ^2. Then, for any p≥ 1, we have 

    [max_1≤ i≤ N |X_i|^p]≤σ^p(log(2N))^p 2.


The proof for the case of p=1 can be found in literature; see, e.g., <cit.>. To establish the proof for the general case, consider the Orlicz function ψ(x)=e^x^2 p-1. Since for p≥ 2, ψ is a non-negative, covex, strictly increasing function on _+, we have

    ψ([max_1≤ i≤ N|X_i|^p_iσ^p] )   ≤[max_1≤ i≤ Nψ(|X_i|^p_iσ^p)]
       ≤∑_i≤ N[ψ(|X_i|^pσ^p)]
       ≤∑_i≤ N[exp(|X_i|^2σ^2)]-1
       ≤ N,

where the last step follows from the definition of the sub-Gaussian random variable. Taking the inverse we obtain

    [max_1≤ i≤ N|X_i|^p_i]    ≤σ^pψ^-1(N)
       ≤σ^p(log(N+1))^p 2
       ≤σ^p(log(2N))^p 2.






























amsplain



mybib19.bib
	
@articletverberg1966generalization,
	title=A generalization of Radon's theorem,
	author=Tverberg, Helge,
	journal=Journal of the London Mathematical Society,
	volume=1,
	number=1,
	pages=123–128,
	year=1966,
	publisher=Wiley Online Library
	
		
@articleshelhamer2016fully,
		title=Fully convolutional networks for semantic segmentation,
		author=Shelhamer, Evan and Long, Jonathan and Darrell, Trevor,
		journal=arXiv preprint arXiv:1605.06211,
		year=2016

	
@articlefan2008sure,
	title=Sure independence screening for ultra-high dimensional feature space,
	author=Fan, Jianqing and Lv, Jinchi,
	journal=Journal of the Royal Statistical Society: Series B (Statistical Methodology),
	volume=70,
	number=5,
	pages=849–911,
	year=2008,
	publisher=Wiley Online Library

@inproceedingssinha2016learning,
	title=Learning kernels with random features,
	author=Sinha, Aman and Duchi, John C,
	booktitle=Advances in Neural Information Processing Systems,
	pages=1298–1306,
	year=2016

	
	@articleshahrampour2017data,
		title=On Data-Dependent Random Features for Improved Generalization in Supervised Learning,
		author=Shahrampour, Shahin and Beirami, Ahmad and Tarokh, Vahid,
		journal=arXiv preprint arXiv:1712.07102,
		year=2017
	
@articlebaram2005learning,
	title=Learning by kernel polarization,
	author=Baram, Yoram,
	journal=Neural Computation,
	volume=17,
	number=6,
	pages=1264–1275,
	year=2005,
	publisher=MIT Press


@inproceedingsrahimi2008random,
	title=Random features for large-scale kernel machines,
	author=Rahimi, Ali and Recht, Benjamin,
	booktitle=Advances in neural information processing systems,
	pages=1177–1184,
	year=2008


@inproceedingsscholkopf2001generalized,
	title=A generalized representer theorem,
	author=Schölkopf, Bernhard and Herbrich, Ralf and Smola, Alex J,
	booktitle=International conference on computational learning theory,
	pages=416–426,
	year=2001,
	organization=Springer


@articlefan2008sure,
	title=Sure independence screening for ultrahigh dimensional feature space,
	author=Fan, Jianqing and Lv, Jinchi,
	journal=Journal of the Royal Statistical Society: Series B (Statistical Methodology),
	volume=70,
	number=5,
	pages=849–911,
	year=2008,
	publisher=Wiley Online Library

@inproceedingsrahimi2009weighted,
	title=Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning,
	author=Rahimi, Ali and Recht, Benjamin,
	booktitle=Advances in neural information processing systems,
	pages=1313–1320,
	year=2009

@articledrineas2005nystrom,
	title=On the Nyström method for approximating a Gram matrix for improved kernel-based learning,
	author=Drineas, Petros and Mahoney, Michael W,
	journal=journal of machine learning research,
	volume=6,
	number=Dec,
	pages=2153–2175,
	year=2005


@inproceedingschen2017kernel,
	title=Kernel feature selection via conditional covariance minimization,
	author=Chen, Jianbo and Stern, Mitchell and Wainwright, Martin J and Jordan, Michael I,
	booktitle=Advances in Neural Information Processing Systems,
	pages=6946–6955,
	year=2017


@articleguyon2003introduction,
	title=An introduction to variable and feature selection,
	author=Guyon, Isabelle and Elisseeff, André,
	journal=Journal of machine learning research,
	volume=3,
	number=Mar,
	pages=1157–1182,
	year=2003

@articlefan2010sure,
	title=Sure independence screening in generalized linear models with NP-dimensionality,
	author=Fan, Jianqing and Song, Rui and others,
	journal=The Annals of Statistics,
	volume=38,
	number=6,
	pages=3567–3604,
	year=2010,
	publisher=Institute of Mathematical Statistics


	@articleguo2015automated,
	title=Automated lesion detection on MRI scans using combined unsupervised and supervised methods,
	author=Guo, Dazhou and Fridriksson, Julius and Fillmore, Paul and Rorden, Christopher and Yu, Hongkai and Zheng, Kang and Wang, Song,
	journal=BMC medical imaging,
	volume=15,
	number=1,
	pages=50,
	year=2015,
	publisher=BioMed Central


@articlede2018automated,
	title=Automated soft tissue lesion detection and segmentation in digital mammography using a FCN deep learning network,
	author=de Moor, Timothy and Rodriguez-Ruiz, Alejandro and Mann, Ritse and Teuwen, Jonas,
	journal=arXiv preprint arXiv:1802.06865,
	year=2018

@articlegudbjartsson1995rician,
	title=The Rician distribution of noisy MRI data,
	author=Gudbjartsson, Hákon and Patz, Samuel,
	journal=Magnetic resonance in medicine,
	volume=34,
	number=6,
	pages=910–914,
	year=1995,
	publisher=Wiley Online Library

@articlefarr2010use,
	title=Use of magnetic resonance imaging to predict outcome after stroke: a review of experimental and clinical evidence,
	author=Farr, Tracy D and Wegener, Susanne,
	journal=Journal of Cerebral Blood Flow & Metabolism,
	volume=30,
	number=4,
	pages=703–717,
	year=2010,
	publisher=SAGE Publications Sage UK: London, England


@articlebruna2013invariant,
	title=Invariant scattering convolution networks,
	author=Bruna, Joan and Mallat, Stéphane,
	journal=IEEE transactions on pattern analysis and machine intelligence,
	volume=35,
	number=8,
	pages=1872–1886,
	year=2013,
	publisher=IEEE


@articlewiatowski2018mathematical,
	title=A mathematical theory of deep convolutional neural networks for feature extraction,
	author=Wiatowski, Thomas and Bölcskei, Helmut,
	journal=IEEE Transactions on Information Theory,
	volume=64,
	number=3,
	pages=1845–1866,
	year=2018,
	publisher=IEEE

@articlegu2012generalized,
	title=Generalized fisher score for feature selection,
	author=Gu, Quanquan and Li, Zhenhui and Han, Jiawei,
	journal=arXiv preprint arXiv:1202.3725,
	year=2012


@articlegu2012generalized,
	title=Generalized fisher score for feature selection,
	author=Gu, Quanquan and Li, Zhenhui and Han, Jiawei,
	journal=arXiv preprint arXiv:1202.3725,
	year=2012

@inproceedingschen2017kernel,
	title=Kernel feature selection via conditional covariance minimization,
	author=Chen, Jianbo and Stern, Mitchell and Wainwright, Martin J and Jordan, Michael I,
	booktitle=Advances in Neural Information Processing Systems,
	pages=6946–6955,
	year=2017

@inproceedingsgidaris2015object,
	title=Object detection via a multi-region and semantic segmentation-aware cnn model,
	author=Gidaris, Spyros and Komodakis, Nikos,
	booktitle=Proceedings of the IEEE International Conference on Computer Vision,
	pages=1134–1142,
	year=2015


@articlejiang2018medical,
	title=Medical image semantic segmentation based on deep learning,
	author=Jiang, Feng and Grigorev, Aleksei and Rho, Seungmin and Tian, Zhihong and Fu, YunSheng and Jifara, Worku and Adil, Khan and Liu, Shaohui,
	journal=Neural Computing and Applications,
	volume=29,
	number=5,
	pages=1257–1265,
	year=2018,
	publisher=Springer


@inproceedingssiam2017deep,
	title=Deep semantic segmentation for automated driving: Taxonomy, roadmap and challenges,
	author=Siam, Mennatullah and Elkerdawy, Sara and Jagersand, Martin and Yogamani, Senthil,
	booktitle=Intelligent Transportation Systems (ITSC), 2017 IEEE 20th International Conference on,
	pages=1–8,
	year=2017,
	organization=IEEE


@inproceedingslong2015fully,
	title=Fully convolutional networks for semantic segmentation,
	author=Long, Jonathan and Shelhamer, Evan and Darrell, Trevor,
	booktitle=Proceedings of the IEEE conference on computer vision and pattern recognition,
	pages=3431–3440,
	year=2015


@inproceedingskrizhevsky2012imagenet,
	title=Imagenet classification with deep convolutional neural networks,
	author=Krizhevsky, Alex and Sutskever, Ilya and Hinton, Geoffrey E,
	booktitle=Advances in neural information processing systems,
	pages=1097–1105,
	year=2012

@articlesimonyan2014very,
	title=Very deep convolutional networks for large-scale image recognition,
	author=Simonyan, Karen and Zisserman, Andrew,
	journal=arXiv preprint arXiv:1409.1556,
	year=2014


@inproceedingslong2015fully,
	title=Fully convolutional networks for semantic segmentation,
	author=Long, Jonathan and Shelhamer, Evan and Darrell, Trevor,
	booktitle=Proceedings of the IEEE conference on computer vision and pattern recognition,
	pages=3431–3440,
	year=2015


@inproceedingsscholkopf2001generalized,
	title=A generalized representer theorem,
	author=Schölkopf, Bernhard and Herbrich, Ralf and Smola, Alex J,
	booktitle=International conference on computational learning theory,
	pages=416–426,
	year=2001,
	organization=Springer


@bookwahba1990spline,
	title=Spline models for observational data,
	author=Wahba, Grace,
	volume=59,
	year=1990,
	publisher=Siam

@inproceedingslong2015fully,
	title=Fully convolutional networks for semantic segmentation,
	author=Long, Jonathan and Shelhamer, Evan and Darrell, Trevor,
	booktitle=Proceedings of the IEEE conference on computer vision and pattern recognition,
	pages=3431–3440,
	year=2015


@articlezellner1986assessing,
	title=On assessing prior distributions and Bayesian regression analysis with g-prior distributions,
	author=Zellner, Arnold,
	journal=Bayesian inference and decision techniques,
	year=1986,
	publisher=Elsevier Science


@articlebernardo2003bayesian,
	title=Bayesian factor regression models in the “large p, small n” paradigm,
	author=Bernardo, JM and Bayarri, MJ and Berger, JO and Dawid, AP and Heckerman, D and Smith, AFM and West, M,
	journal=Bayesian statistics,
	volume=7,
	pages=733–742,
	year=2003

@inproceedingszhang2009posterior,
	title=Posterior consistency of the Silverman g-prior in Bayesian model choice,
	author=Zhang, Zhihua and Jordan, Michael I and Yeung, Dit-Yan,
	booktitle=Advances in Neural Information Processing Systems,
	pages=1969–1976,
	year=2009


@articlefan2008high,
	title=High dimensional classification using features annealed independence rules,
	author=Fan, Jianqing and Fan, Yingying,
	journal=Annals of statistics,
	volume=36,
	number=6,
	pages=2605,
	year=2008,
	publisher=NIH Public Access


@inproceedingssinha2016learning,
	title=Learning kernels with random features,
	author=Sinha, Aman and Duchi, John C,
	booktitle=Advances in Neural Information Processing Systems,
	pages=1298–1306,
	year=2016


@inproceedingsrahimi2008random,
	title=Random features for large-scale kernel machines,
	author=Rahimi, Ali and Recht, Benjamin,
	booktitle=Advances in neural information processing systems,
	pages=1177–1184,
	year=2008


@articleshahrampour2017data,
	title=On Data-Dependent Random Features for Improved Generalization in Supervised Learning,
	author=Shahrampour, Shahin and Beirami, Ahmad and Tarokh, Vahid,
	journal=arXiv preprint arXiv:1712.07102,
	year=2017


@articlebaram2005learning,
	title=Learning by kernel polarization,
	author=Baram, Yoram,
	journal=Neural Computation,
	volume=17,
	number=6,
	pages=1264–1275,
	year=2005,
	publisher=MIT Press


@inproceedingsrahimi2009weighted,
	title=Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning,
	author=Rahimi, Ali and Recht, Benjamin,
	booktitle=Advances in neural information processing systems,
	pages=1313–1320,
	year=2009

@inproceedingsszegedy2015going,
	title=Going deeper with convolutions,
	author=Szegedy, Christian and Liu, Wei and Jia, Yangqing and Sermanet, Pierre and Reed, Scott and Anguelov, Dragomir and Erhan, Dumitru and Vanhoucke, Vincent and Rabinovich, Andrew,
	booktitle=Proceedings of the IEEE conference on computer vision and pattern recognition,
	pages=1–9,
	year=2015


@articlerobnik2003theoretical,
	title=Theoretical and empirical analysis of ReliefF and RReliefF,
	author=Robnik-Šikonja, Marko and Kononenko, Igor,
	journal=Machine learning,
	volume=53,
	number=1-2,
	pages=23–69,
	year=2003,
	publisher=Springer


@articlegu2012generalized,
	title=Generalized fisher score for feature selection,
	author=Gu, Quanquan and Li, Zhenhui and Han, Jiawei,
	journal=arXiv preprint arXiv:1202.3725,
	year=2012


@articlepeng2005feature,
	title=Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy,
	author=Peng, Hanchuan and Long, Fuhui and Ding, Chris,
	journal=IEEE Transactions on pattern analysis and machine intelligence,
	volume=27,
	number=8,
	pages=1226–1238,
	year=2005,
	publisher=IEEE


@articlekohavi1997wrappers,
	title=Wrappers for feature subset selection,
	author=Kohavi, Ron and John, George H,
	journal=Artificial intelligence,
	volume=97,
	number=1-2,
	pages=273–324,
	year=1997,
	publisher=Elsevier

@articleliu2005toward,
	title=Toward integrating feature selection algorithms for classification and clustering,
	author=Liu, Huan and Yu, Lei,
	journal=IEEE Transactions on knowledge and data engineering,
	volume=17,
	number=4,
	pages=491–502,
	year=2005,
	publisher=IEEE

@inproceedingschen2017kernel,
	title=Kernel feature selection via conditional covariance minimization,
	author=Chen, Jianbo and Stern, Mitchell and Wainwright, Martin J and Jordan, Michael I,
	booktitle=Advances in Neural Information Processing Systems,
	pages=6946–6955,
	year=2017


@inproceedingscao2007feature,
	title=Feature selection in a kernel space,
	author=Cao, Bin and Shen, Dou and Sun, Jian-Tao and Yang, Qiang and Chen, Zheng,
	booktitle=Proceedings of the 24th international conference on Machine learning,
	pages=121–128,
	year=2007,
	organization=ACM

@inproceedingssong2007supervised,
	title=Supervised feature selection via dependence estimation,
	author=Song, Le and Smola, Alex and Gretton, Arthur and Borgwardt, Karsten M and Bedo, Justin,
	booktitle=Proceedings of the 24th international conference on Machine learning,
	pages=823–830,
	year=2007,
	organization=ACM

@articlesong2012feature,
	title=Feature selection via dependence maximization,
	author=Song, Le and Smola, Alex and Gretton, Arthur and Bedo, Justin and Borgwardt, Karsten,
	journal=Journal of Machine Learning Research,
	volume=13,
	number=May,
	pages=1393–1434,
	year=2012


@bookberlinet2011reproducing,
	title=Reproducing kernel Hilbert spaces in probability and statistics,
	author=Berlinet, Alain and Thomas-Agnan, Christine,
	year=2011,
	publisher=Springer Science & Business Media


@inproceedingscristianini2002kernel,
	title=On kernel-target alignment,
	author=Cristianini, Nello and Shawe-Taylor, John and Elisseeff, Andre and Kandola, Jaz S,
	booktitle=Advances in neural information processing systems,
	pages=367–373,
	year=2002

@inproceedingspollard1990empirical,
	title=Empirical processes: theory and applications,
	author=Pollard, David,
	booktitle=NSF-CBMS regional conference series in probability and statistics,
	pages=i–86,
	year=1990,
	organization=JSTOR


@incollectionvapnik2015uniform,
	title=On the uniform convergence of relative frequencies of events to their probabilities,
	author=Vapnik, Vladimir N and Chervonenkis, A Ya,
	booktitle=Measures of complexity,
	pages=11–30,
	year=2015,
	publisher=Springer


@inproceedingsrahimi2008random,
	title=Random features for large-scale kernel machines,
	author=Rahimi, Ali and Recht, Benjamin,
	booktitle=Advances in neural information processing systems,
	pages=1177–1184,
	year=2008


@inproceedingsgould2009decomposing,
	title=Decomposing a scene into geometric and semantically consistent regions,
	author=Gould, Stephen and Fulton, Richard and Koller, Daphne,
	booktitle=Computer Vision, IEEE 12th International Conference on,
	pages=1–8,
	year=2009,
	organization=IEEE


@articlezhang2011bayesian,
	title=Bayesian generalized kernel mixed models,
	author=Zhang, Zhihua and Dai, Guang and Jordan, Michael I,
	journal=Journal of Machine Learning Research,
	volume=12,
	number=Jan,
	pages=111–139,
	year=2011


@miscbernardo2001bayesian,
	title=Bayesian theory,
	author=Bernardo, José M and Smith, Adrian FM,
	year=2001,
	publisher=IOP Publishing


@inproceedingsrahimi2008random,
	title=Random features for large-scale kernel machines,
	author=Rahimi, Ali and Recht, Benjamin,
	booktitle=Advances in neural information processing systems,
	pages=1177–1184,
	year=2008


@inproceedingschen2017kernel,
	title=Kernel feature selection via conditional covariance minimization,
	author=Chen, Jianbo and Stern, Mitchell and Wainwright, Martin J and Jordan, Michael I,
	booktitle=Advances in Neural Information Processing Systems,
	pages=6946–6955,
	year=2017


@inproceedingstschannen2017deep,
	title=Deep structured features for semantic segmentation,
	author=Tschannen, Michael and Cavigelli, Lukas and Mentzer, Fabian and Wiatowski, Thomas and Benini, Luca,
	booktitle=Signal Processing Conference (EUSIPCO), 2017 25th European,
	pages=61–65,
	year=2017,
	organization=IEEE


@articlecortes2009new,
	title=New generalization bounds for learning kernels,
	author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
	journal=arXiv preprint arXiv:0912.3309,
	year=2009


@articlecortes2012algorithms,
	title=Algorithms for learning kernels based on centered alignment,
	author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
	journal=Journal of Machine Learning Research,
	volume=13,
	number=Mar,
	pages=795–828,
	year=2012


@articlede2003linear,
	title=The linear programming approach to approximate dynamic programming,
	author=De Farias, Daniela Pucci and Van Roy, Benjamin,
	journal=Operations research,
	volume=51,
	number=6,
	pages=850–865,
	year=2003,
	publisher=INFORMS


@inproceedingsmasaeli2010transformation,
	title=From transformation-based dimensionality reduction to feature selection,
	author=Masaeli, Mahdokht and Dy, Jennifer G and Fung, Glenn M,
	booktitle=Proceedings of the 27th International Conference on Machine Learning (ICML-10),
	pages=751–758,
	year=2010


@articleyamada2014high,
	title=High-dimensional feature selection by feature-wise kernelized lasso,
	author=Yamada, Makoto and Jitkrittum, Wittawat and Sigal, Leonid and Xing, Eric P and Sugiyama, Masashi,
	journal=Neural computation,
	volume=26,
	number=1,
	pages=185–207,
	year=2014,
	publisher=MIT Press


@articleshahrampourlearning,
	title=Learning Bounds for Greedy Approximation with Explicit Feature Maps from Multiple Kernels,
	author=Shahrampour, Shahin and Tarokh, Vahid


@articlerudelson2013hanson,
	title=Hanson-Wright inequality and sub-gaussian concentration,
	author=Rudelson, Mark and Vershynin, Roman and others,
	journal=Electronic Communications in Probability,
	volume=18,
	year=2013,
	publisher=The Institute of Mathematical Statistics and the Bernoulli Society


@techreportbellec2014concentration,
	title=Concentration of quadratic forms under a Bernstein moment assumption,
	author=Bellec, P,
	year=2014,
	institution=Technical report, Ecole Polytechnique


@articleweisstein2002lambert,
	title=Lambert W-function,
	author=Weisstein, Eric W,
	year=2002,
	publisher=Wolfram Research, Inc.


@articlekleywegt2002sample,
	title=The sample average approximation method for stochastic discrete optimization,
	author=Kleywegt, Anton J and Shapiro, Alexander and Homem-de-Mello, Tito,
	journal=SIAM Journal on Optimization,
	volume=12,
	number=2,
	pages=479–502,
	year=2002,
	publisher=SIAM


@bookellis2007entropy,
	title=Entropy, large deviations, and statistical mechanics,
	author=Ellis, Richard S,
	year=2007,
	publisher=Springer


@articlelaurent2000adaptive,
	title=Adaptive estimation of a quadratic functional by model selection,
	author=Laurent, Beatrice and Massart, Pascal,
	journal=Annals of Statistics,
	pages=1302–1338,
	year=2000,
	publisher=JSTOR

@articlevershynin2010introduction,
	title=Introduction to the non-asymptotic analysis of random matrices,
	author=Vershynin, Roman,
	journal=arXiv preprint arXiv:1011.3027,
	year=2010


@articlevershynin2010introduction,
	title=Introduction to the non-asymptotic analysis of random matrices,
	author=Vershynin, Roman,
	journal=arXiv preprint arXiv:1011.3027,
	year=2010


@inproceedingsminh2006mercer,
	title=Mercer’s theorem, feature maps, and smoothing,
	author=Minh, Ha Quang and Niyogi, Partha and Yao, Yuan,
	booktitle=International Conference on Computational Learning Theory,
	pages=154–168,
	year=2006,
	organization=Springer


@articlebartlett2002rademacher,
	title=Rademacher and Gaussian complexities: Risk bounds and structural results,
	author=Bartlett, Peter L and Mendelson, Shahar,
	journal=Journal of Machine Learning Research,
	volume=3,
	number=Nov,
	pages=463–482,
	year=2002

@articlekasiviswanathan2015spectral,
	title=Spectral norm of random kernel matrices with applications to privacy,
	author=Kasiviswanathan, Shiva Prasad and Rudelson, Mark,
	journal=arXiv preprint arXiv:1504.05880,
	year=2015

@articleel2010spectrum,
	title=The spectrum of kernel random matrices,
	author=El Karoui, Noureddine and others,
	journal=The Annals of Statistics,
	volume=38,
	number=1,
	pages=1–50,
	year=2010,
	publisher=Institute of Mathematical Statistics

@articlelanckriet2004learning,
	title=Learning the kernel matrix with semidefinite programming,
	author=Lanckriet, Gert RG and Cristianini, Nello and Bartlett, Peter and Ghaoui, Laurent El and Jordan, Michael I,
	journal=Journal of Machine learning research,
	volume=5,
	number=Jan,
	pages=27–72,
	year=2004


@articlevoiculescu1986addition,
	title=Addition of certain non-commuting random variables,
	author=Voiculescu, Dan,
	journal=Journal of functional analysis,
	volume=66,
	number=3,
	pages=323–346,
	year=1986,
	publisher=Academic Press


@articlefan2015spectral,
	title=The spectral norm of random inner-product kernel matrices,
	author=Fan, Zhou and Montanari, Andrea,
	journal=Probability Theory and Related Fields,
	pages=1–59,
	year=2015,
	publisher=Springer


@articlehofmann2008kernel,
	title=Kernel methods in machine learning,
	author=Hofmann, Thomas and Schölkopf, Bernhard and Smola, Alexander J,
	journal=The annals of statistics,
	pages=1171–1220,
	year=2008,
	publisher=JSTOR


@articlezhang2011bayesian,
	title=Bayesian generalized kernel mixed models,
	author=Zhang, Zhihua and Dai, Guang and Jordan, Michael I,
	journal=Journal of Machine Learning Research,
	volume=12,
	number=Jan,
	pages=111–139,
	year=2011


@articlebernardo1994bayesian,
	title=Bayesian theory. 1994,
	author=Bernardo, José M and Smith, Adrian FM,
	journal=John Willey and Sons. Valencia (España),
	year=1994


@inproceedingsronneberger2015u,
	title=U-net: Convolutional networks for biomedical image segmentation,
	author=Ronneberger, Olaf and Fischer, Philipp and Brox, Thomas,
	booktitle=International Conference on Medical image computing and computer-assisted intervention,
	pages=234–241,
	year=2015,
	organization=Springer

@articleben2010theory,
	title=A theory of learning from different domains,
	author=Ben-David, Shai and Blitzer, John and Crammer, Koby and Kulesza, Alex and Pereira, Fernando and Vaughan, Jennifer Wortman,
	journal=Machine learning,
	volume=79,
	number=1-2,
	pages=151–175,
	year=2010,
	publisher=Springer


@articlexie2015transfer,
	title=Transfer learning from deep features for remote sensing and poverty mapping,
	author=Xie, Michael and Jean, Neal and Burke, Marshall and Lobell, David and Ermon, Stefano,
	journal=arXiv preprint arXiv:1510.00098,
	year=2015


@articlecortes2012algorithms,
	title=Algorithms for learning kernels based on centered alignment,
	author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
	journal=Journal of Machine Learning Research,
	volume=13,
	number=Mar,
	pages=795–828,
	year=2012


@articlecortes2012algorithms,
	title=Algorithms for learning kernels based on centered alignment,
	author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
	journal=Journal of Machine Learning Research,
	volume=13,
	number=Mar,
	pages=795–828,
	year=2012


@inproceedingschen2017kernel,
	title=Kernel feature selection via conditional covariance minimization,
	author=Chen, Jianbo and Stern, Mitchell and Wainwright, Martin J and Jordan, Michael I,
	booktitle=Advances in Neural Information Processing Systems,
	pages=6946–6955,
	year=2017



@inproceedingsbeirami2017optimal,
	title=On optimal generalizability in parametric learning,
	author=Beirami, Ahmad and Razaviyayn, Meisam and Shahrampour, Shahin and Tarokh, Vahid,
	booktitle=Advances in Neural Information Processing Systems,
	pages=3455–3465,
	year=2017


@articlewang2018approximate,
	title=Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions,
	author=Wang, Shuaiwen and Zhou, Wenda and Lu, Haihao and Maleki, Arian and Mirrokni, Vahab,
	journal=arXiv preprint arXiv:1807.02694,
	year=2018


@articlegiordano2018return,
	title=Return of the Infinitesimal Jackknife,
	author=Giordano, Ryan and Stephenson, Will and Liu, Runjing and Jordan, Michael I and Broderick, Tamara,
	journal=arXiv preprint arXiv:1806.00550,
	year=2018


@articlelowe2004distinctive,
	title=Distinctive image features from scale-invariant keypoints,
	author=Lowe, David G,
	journal=International journal of computer vision,
	volume=60,
	number=2,
	pages=91–110,
	year=2004,
	publisher=Springer


@articletola2010daisy,
	title=DAISY: An efficient dense descriptor applied to wide-baseline stereo,
	author=Tola, Engin and Lepetit, Vincent and Fua, Pascal,
	journal=IEEE transactions on pattern analysis and machine intelligence,
	volume=32,
	number=5,
	pages=815–830,
	year=2010,
	publisher=IEEE


@bookabsil2009optimization,
	title=Optimization algorithms on matrix manifolds,
	author=Absil, P-A and Mahony, Robert and Sepulchre, Rodolphe,
	year=2009,
	publisher=Princeton University Press



@inproceedingsbach2004multiple,
	title=Multiple kernel learning, conic duality, and the SMO algorithm,
	author=Bach, Francis R and Lanckriet, Gert RG and Jordan, Michael I,
	booktitle=Proceedings of the twenty-first international conference on Machine learning,
	pages=6,
	year=2004,
	organization=ACM


@articlecortes2009new,
	title=New generalization bounds for learning kernels,
	author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
	journal=arXiv preprint arXiv:0912.3309,
	year=2009


@inproceedingslong2015fully,
	title=Fully convolutional networks for semantic segmentation,
	author=Long, Jonathan and Shelhamer, Evan and Darrell, Trevor,
	booktitle=Proceedings of the IEEE conference on computer vision and pattern recognition,
	pages=3431–3440,
	year=2015


@inproceedingsronneberger2015u,
	title=U-net: Convolutional networks for biomedical image segmentation,
	author=Ronneberger, Olaf and Fischer, Philipp and Brox, Thomas,
	booktitle=International Conference on Medical image computing and computer-assisted intervention,
	pages=234–241,
	year=2015,
	organization=Springer


@articlelanckriet2004learning,
	title=Learning the kernel matrix with semidefinite programming,
	author=Lanckriet, Gert RG and Cristianini, Nello and Bartlett, Peter and Ghaoui, Laurent El and Jordan, Michael I,
	journal=Journal of Machine learning research,
	volume=5,
	number=Jan,
	pages=27–72,
	year=2004


@inproceedingscortes2010two,
	title=Two-Stage Learning Kernel Algorithms.,
	author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
	booktitle=ICML,
	pages=239–246,
	year=2010


@articlegonen2011multiple,
	title=Multiple kernel learning algorithms,
	author=Gönen, Mehmet and Alpaydın, Ethem,
	journal=Journal of machine learning research,
	volume=12,
	number=Jul,
	pages=2211–2268,
	year=2011


@articlegonen2011multiple,
	title=Multiple kernel learning algorithms,
	author=Gönen, Mehmet and Alpaydın, Ethem,
	journal=Journal of machine learning research,
	volume=12,
	number=Jul,
	pages=2211–2268,
	year=2011


@inproceedingschen2017kernel,
	title=Kernel feature selection via conditional covariance minimization,
	author=Chen, Jianbo and Stern, Mitchell and Wainwright, Martin J and Jordan, Michael I,
	booktitle=Advances in Neural Information Processing Systems,
	pages=6946–6955,
	year=2017


@bookvillani2008optimal,
	title=Optimal transport: old and new,
	author=Villani, Cédric,
	volume=338,
	year=2008,
	publisher=Springer Science & Business Media


@articlebenamou2000computational,
	title=A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem,
	author=Benamou, Jean-David and Brenier, Yann,
	journal=Numerische Mathematik,
	volume=84,
	number=3,
	pages=375–393,
	year=2000,
	publisher=Springer


@bookkriegl1997convenient,
	title=The convenient setting of global analysis,
	author=Kriegl, Andreas and Michor, Peter W,
	volume=53,
	year=1997,
	publisher=American Mathematical Soc.


@articleotto2001geometry,
	title=The geometry of dissipative evolution equations: the porous medium equation,
	author=Otto, Felix,
	year=2001,
	publisher=Taylor & Francis


@articlegibilisco2003wigner,
	title=Wigner–Yanase information on quantum state space: the geometric approach,
	author=Gibilisco, Paolo and Isola, Tommaso,
	journal=Journal of Mathematical Physics,
	volume=44,
	number=9,
	pages=3752–3762,
	year=2003,
	publisher=AIP



@articlejordan1997free,
	title=Free energy and the Fokker-Planck equation,
	author=Jordan, Richard and Kinderlehrer, David and Otto, Felix,
	journal=Physica D: Nonlinear Phenomena,
	volume=107,
	number=2-4,
	pages=265–271,
	year=1997,
	publisher=Elsevier


@articlejordan1998variational,
	title=The variational formulation of the Fokker–Planck equation,
	author=Jordan, Richard and Kinderlehrer, David and Otto, Felix,
	journal=SIAM journal on mathematical analysis,
	volume=29,
	number=1,
	pages=1–17,
	year=1998,
	publisher=SIAM


@articleshashua2009introduction,
	title=Introduction to machine learning: Class notes 67577,
	author=Shashua, Amnon,
	journal=arXiv preprint arXiv:0904.3664,
	year=2009


@inproceedingskhan2016comparison,
	title=A comparison of deep learning and hand crafted features in medical image modality classification,
	author=Khan, Sameer and Yong, Suet-Peng,
	booktitle=Computer and Information Sciences (ICCOINS), 2016 3rd International Conference on,
	pages=633–638,
	year=2016,
	organization=IEEE


@bookbochner2005harmonic,
	title=Harmonic analysis and the theory of probability,
	author=Bochner, Salomon,
	year=2005,
	publisher=Courier Corporation


@bookamari2007methods,
	title=Methods of information geometry,
	author=Amari, Shun-ichi and Nagaoka, Hiroshi,
	volume=191,
	year=2007,
	publisher=American Mathematical Soc.


@articletakatsu2011wasserstein,
	title=Wasserstein geometry of Gaussian measures,
	author=Takatsu, Asuka and others,
	journal=Osaka Journal of Mathematics,
	volume=48,
	number=4,
	pages=1005–1026,
	year=2011,
	publisher=Osaka University and Osaka City University, Departments of Mathematics


@inproceedingsmhaskar2017and,
	title=When and why are deep networks better than shallow ones?,
	author=Mhaskar, Hrushikesh and Liao, Qianli and Poggio, Tomaso A,
	year=2017


@articlemhaskar2016deep,
	title=Deep vs. shallow networks: An approximation theory perspective,
	author=Mhaskar, Hrushikesh N and Poggio, Tomaso,
	journal=Analysis and Applications,
	volume=14,
	number=06,
	pages=829–848,
	year=2016,
	publisher=World Scientific


@inproceedingshe2016deep,
	title=Deep residual learning for image recognition,
	author=He, Kaiming and Zhang, Xiangyu and Ren, Shaoqing and Sun, Jian,
	booktitle=Proceedings of the IEEE conference on computer vision and pattern recognition,
	pages=770–778,
	year=2016


@articlenanni2017handcrafted,
	title=Handcrafted vs. non-handcrafted features for computer vision classification,
	author=Nanni, Loris and Ghidoni, Stefano and Brahnam, Sheryl,
	journal=Pattern Recognition,
	volume=71,
	pages=158–172,
	year=2017,
	publisher=Elsevier



@articlemaaten2008visualizing,
	title=Visualizing data using t-SNE,
	author=Maaten, Laurens van der and Hinton, Geoffrey,
	journal=Journal of machine learning research,
	volume=9,
	number=Nov,
	pages=2579–2605,
	year=2008


@articlekingma2014adam,
	title=Adam: A method for stochastic optimization,
	author=Kingma, Diederik P and Ba, Jimmy,
	journal=arXiv preprint arXiv:1412.6980,
	year=2014


@articleabsil2012projection,
	title=Projection-like retractions on matrix manifolds,
	author=Absil, P-A and Malick, Jérôme,
	journal=SIAM Journal on Optimization,
	volume=22,
	number=1,
	pages=135–158,
	year=2012,
	publisher=SIAM


@articlechen2018unified,
	title=A Unified Particle-Optimization Framework for Scalable Bayesian Sampling,
	author=Chen, Changyou and Zhang, Ruiyi and Wang, Wenlin and Li, Bai and Chen, Liqun,
	journal=arXiv preprint arXiv:1805.11659,
	year=2018


@articlesrivastava2014dropout,
	title=Dropout: a simple way to prevent neural networks from overfitting,
	author=Srivastava, Nitish and Hinton, Geoffrey and Krizhevsky, Alex and Sutskever, Ilya and Salakhutdinov, Ruslan,
	journal=The Journal of Machine Learning Research,
	volume=15,
	number=1,
	pages=1929–1958,
	year=2014,
	publisher=JMLR. org


@articlescardapane2017group,
	title=Group sparse regularization for deep neural networks,
	author=Scardapane, Simone and Comminiello, Danilo and Hussain, Amir and Uncini, Aurelio,
	journal=Neurocomputing,
	volume=241,
	pages=81–89,
	year=2017,
	publisher=Elsevier


@articlegoodfellow2013maxout,
	title=Maxout networks,
	author=Goodfellow, Ian J and Warde-Farley, David and Mirza, Mehdi and Courville, Aaron and Bengio, Yoshua,
	journal=arXiv preprint arXiv:1302.4389,
	year=2013


@articlemarvcenko1967distribution,
	title=Distribution of eigenvalues for some sets of random matrices,
	author=Marčenko, Vladimir A and Pastur, Leonid Andreevich,
	journal=Mathematics of the USSR-Sbornik,
	volume=1,
	number=4,
	pages=457,
	year=1967,
	publisher=IOP Publishing


@bookscholkopf2001learning,
	title=Learning with kernels: support vector machines, regularization, optimization, and beyond,
	author=Scholkopf, Bernhard and Smola, Alexander J,
	year=2001,
	publisher=MIT press


@articlechen2018unified,
	title=A Unified Particle-Optimization Framework for Scalable Bayesian Sampling,
	author=Chen, Changyou and Zhang, Ruiyi and Wang, Wenlin and Li, Bai and Chen, Liqun,
	journal=arXiv preprint arXiv:1805.11659,
	year=2018


@inproceedingszhang2018online,
	title=Online Kernel Selection via Incremental Sketched Kernel Alignment.,
	author=Zhang, Xiao and Liao, Shizhong,
	booktitle=IJCAI,
	pages=3118–3124,
	year=2018


@articlegretton2012kernel,
	title=A kernel two-sample test,
	author=Gretton, Arthur and Borgwardt, Karsten M and Rasch, Malte J and Schölkopf, Bernhard and Smola, Alexander,
	journal=Journal of Machine Learning Research,
	volume=13,
	number=Mar,
	pages=723–773,
	year=2012


@onlineScikit,
	author = ,
	title = ,
	year =,
	url = https://scikit-learn.org.,
	urldate = 


@onlineShogun,
	author = ,
	title = ,
	year =,
	url = http://shogun-toolbox.org.,
	urldate = 


@articlefukumizu2009kernel,
	title=Kernel dimension reduction in regression,
	author=Fukumizu, Kenji and Bach, Francis R and Jordan, Michael I and others,
	journal=The Annals of Statistics,
	volume=37,
	number=4,
	pages=1871–1905,
	year=2009,
	publisher=Institute of Mathematical Statistics


@articlemuandet2017kernel,
	title=Kernel mean embedding of distributions: A review and beyond,
	author=Muandet, Krikamol and Fukumizu, Kenji and Sriperumbudur, Bharath and Schölkopf, Bernhard and others,
	journal=Foundations and Trends® in Machine Learning,
	volume=10,
	number=1-2,
	pages=1–141,
	year=2017,
	publisher=Now Publishers, Inc.


@articlelim2010discrete,
	title=The discrete shearlet transform: a new directional transform and compactly supported shearlet frames.,
	author=Lim, Wang-Q,
	journal=IEEE Trans. Image Processing,
	volume=19,
	number=5,
	pages=1166–1180,
	year=2010


@articlewiatowski2018mathematical,
	title=A mathematical theory of deep convolutional neural networks for feature extraction,
	author=Wiatowski, Thomas and Bölcskei, Helmut,
	journal=IEEE Transactions on Information Theory,
	volume=64,
	number=3,
	pages=1845–1866,
	year=2018,
	publisher=IEEE


@incollectionkutyniok2012introduction,
	title=Introduction to shearlets,
	author=Kutyniok, Gitta and Labate, Demetrio,
	booktitle=Shearlets,
	pages=1–38,
	year=2012,
	publisher=Springer


@articleholschneider1995wavelets,
	title=Wavelets,
	author=Holschneider, Matthias,
	journal=An analysis tool,
	year=1995,
	publisher=Oxford Science Publications


@articledudley1969speed,
	title=The speed of mean Glivenko-Cantelli convergence,
	author=Dudley, RM,
	journal=The Annals of Mathematical Statistics,
	volume=40,
	number=1,
	pages=40–50,
	year=1969,
	publisher=JSTOR


@articlemcdiarmid1989method,
	title=On the method of bounded differences,
	author=McDiarmid, Colin,
	journal=Surveys in combinatorics,
	volume=141,
	number=1,
	pages=148–188,
	year=1989,
	publisher=Norwich


@inproceedingstolstikhin2016minimax,
	title=Minimax estimation of maximum mean discrepancy with radial kernels,
	author=Tolstikhin, Ilya O and Sriperumbudur, Bharath K and Schölkopf, Bernhard,
	booktitle=Advances in Neural Information Processing Systems,
	pages=1930–1938,
	year=2016

@articletolstikhin2017minimax,
	title=Minimax estimation of kernel mean embeddings,
	author=Tolstikhin, Ilya and Sriperumbudur, Bharath K and Muandet, Krikamol,
	journal=The Journal of Machine Learning Research,
	volume=18,
	number=1,
	pages=3002–3048,
	year=2017,
	publisher=JMLR. org



@onlineDuchi_Testing,
	author = John Duchi,
	title = ,
	year =,
	url = https://scikit-learn.org.,
	urldate = https://web.stanford.edu/class/stats311/Lectures/lec-03.pdf


@articleben2013robust,
	title=Robust solutions of optimization problems affected by uncertain probabilities,
	author=Ben-Tal, Aharon and Den Hertog, Dick and De Waegenaere, Anja and Melenberg, Bertrand and Rennen, Gijs,
	journal=Management Science,
	volume=59,
	number=2,
	pages=341–357,
	year=2013,
	publisher=INFORMS


@inproceedingssinha2016learning,
	title=Learning kernels with random features,
	author=Sinha, Aman and Duchi, John C,
	booktitle=Advances in Neural Information Processing Systems,
	pages=1298–1306,
	year=2016

@articleben2013robust,
	title=Robust solutions of optimization problems affected by uncertain probabilities,
	author=Ben-Tal, Aharon and Den Hertog, Dick and De Waegenaere, Anja and Melenberg, Bertrand and Rennen, Gijs,
	journal=Management Science,
	volume=59,
	number=2,
	pages=341–357,
	year=2013,
	publisher=INFORMS


@articlepolyanskiy2016wasserstein,
	title=Wasserstein continuity of entropy and outer bounds for interference channels,
	author=Polyanskiy, Yury and Wu, Yihong,
	journal=IEEE Transactions on Information Theory,
	volume=62,
	number=7,
	pages=3992–4002,
	year=2016,
	publisher=IEEE


@booktao2012topics,
	title=Topics in random matrix theory,
	author=Tao, Terence,
	volume=132,
	year=2012,
	publisher=American Mathematical Soc.


@bookbhatia2013matrix,
	title=Matrix analysis,
	author=Bhatia, Rajendra,
	volume=169,
	year=2013,
	publisher=Springer Science & Business Media


@articleMHV,
	title=A Two-Sample Test for Learning Mixture Kernels with Application to the Semantic Segmentation,
	author=Ren, Hongyi  and Badiei Khuzani, Masoud  and Vasudevan, Varun and Xiao, Jia  and Xing, Lei,
	journal=submitted to IEEE Transactions on Medical Imaging,
	volume=,
	number=,
	pages=,
	year=2018,
	publisher=IEEE





@articleledoux1997talagrand,
	title=On Talagrand's deviation inequalities for product measures,
	author=Ledoux, Michel,
	journal=ESAIM: Probability and statistics,
	volume=1,
	pages=63–87,
	year=1997,
	publisher=EDP Sciences


@miscbhatia1997matrix,
	title=Matrix Analysis Graduate Texts in Mathematics, 169,
	author=Bhatia, Rajendra,
	year=1997,
	publisher=Springer New York


@incollectionsimons1995minimax,
	title=Minimax theorems and their proofs,
	author=Simons, Stephen,
	booktitle=Minimax and applications,
	pages=1–23,
	year=1995,
	publisher=Springer


@bookpollard2012convergence,
	title=Convergence of stochastic processes,
	author=Pollard, David,
	year=2012,
	publisher=Springer Science & Business Media


@incollectionvan1996weak,
	title=Weak convergence,
	author=Van Der Vaart, Aad W and Wellner, Jon A,
	booktitle=Weak convergence and empirical processes,
	pages=16–28,
	year=1996,
	publisher=Springer



@onlineASU,
	author = ,
	title = ,
	year =,
	url = http://featureselection.asu.edu/datasets.php,
	urldate = 



@articlenguyen2010estimating,
	title=Estimating divergence functionals and the likelihood ratio by convex risk minimization,
	author=Nguyen, XuanLong and Wainwright, Martin J and Jordan, Michael I,
	journal=IEEE Transactions on Information Theory,
	volume=56,
	number=11,
	pages=5847–5861,
	year=2010,
	publisher=IEEE


@articlesauer1972density,
	title=On the density of families of sets,
	author=Sauer, Norbert,
	journal=Journal of Combinatorial Theory, Series A,
	volume=13,
	number=1,
	pages=145–147,
	year=1972,
	publisher=Elsevier


@incollectionvapnik2015uniform,
	title=On the uniform convergence of relative frequencies of events to their probabilities,
	author=Vapnik, Vladimir N and Chervonenkis, A Ya,
	booktitle=Measures of complexity,
	pages=11–30,
	year=2015,
	publisher=Springer


@articledavies1984ultracontractivity,
	title=Ultracontractivity and the heat kernel for Schrödinger operators and Dirichlet Laplacians,
	author=Davies, Edward Brian and Simon, Barry,
	journal=Journal of Functional Analysis,
	volume=59,
	number=2,
	pages=335–395,
	year=1984,
	publisher=Academic Press


@inproceedingspollard1990empirical,
	title=Empirical processes: theory and applications,
	author=Pollard, David,
	booktitle=NSF-CBMS regional conference series in probability and statistics,
	pages=i–86,
	year=1990,
	organization=JSTOR


@articletverberg1966generalization,
	title=A generalization of Radon's theorem,
	author=Tverberg, Helge,
	journal=Journal of the London Mathematical Society,
	volume=1,
	number=1,
	pages=123–128,
	year=1966,
	publisher=Wiley Online Library


@articleradon1921mengen,
	title=Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten,
	author=Radon, Johann,
	journal=Mathematische Annalen,
	volume=83,
	number=1,
	pages=113–115,
	year=1921,
	publisher=Springer


@articlezhao2015fastmmd,
	title=Fastmmd: Ensemble of circular discrepancy for efficient two-sample test,
	author=Zhao, Ji and Meng, Deyu,
	journal=Neural computation,
	volume=27,
	number=6,
	pages=1345–1372,
	year=2015,
	publisher=MIT Press


@articleszegedy2013intriguing,
	title=Intriguing properties of neural networks,
	author=Szegedy, Christian and Zaremba, Wojciech and Sutskever, Ilya and Bruna, Joan and Erhan, Dumitru and Goodfellow, Ian and Fergus, Rob,
	journal=arXiv preprint arXiv:1312.6199,
	year=2013


@articlehu2013kullback,
	title=Kullback-Leibler divergence constrained distributionally robust optimization,
	author=Hu, Zhaolin and Hong, L Jeff,
	journal=Available at Optimization Online,
	year=2013


@articlehazan2012partition,
	title=On the partition function and random maximum a-posteriori perturbations,
	author=Hazan, Tamir and Jaakkola, Tommi,
	journal=arXiv preprint arXiv:1206.6410,
	year=2012


@articlefan2018dnn,
	title=DNN: A two-scale distributional tale of heterogeneous treatment effect inference,
	author=Fan, Yingying and Lv, Jinchi and Wang, Jingbo,
	journal=Available at SSRN 3238897,
	year=2018


@articleschoenberg1938metric,
	title=Metric spaces and completely monotone functions,
	author=Schoenberg, Isaac J,
	journal=Annals of Mathematics,
	pages=811–841,
	year=1938,
	publisher=JSTOR


@bookboucheron2013concentration,
	title=Concentration inequalities: A nonasymptotic theory of independence,
	author=Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal,
	year=2013,
	publisher=Oxford university press



@articletolstikhin2017minimax,
	title=Minimax estimation of kernel mean embeddings,
	author=Tolstikhin, Ilya and Sriperumbudur, Bharath K and Muandet, Krikamol,
	journal=The Journal of Machine Learning Research,
	volume=18,
	number=1,
	pages=3002–3048,
	year=2017,
	publisher=JMLR. org


@articlenaor2008concentration,
	title=Concentration of Measure,
	author=Naor, Assaf,
	journal=lecture notes
	url = https://scikit-learn.org.,
	year=2008


@articlesion1958general,
	title=On general minimax theorems.,
	author=Sion, Maurice and others,
	journal=Pacific Journal of mathematics,
	volume=8,
	number=1,
	pages=171–176,
	year=1958,
	publisher=Pacific Journal of Mathematics


@articlebartlett2002rademacher,
	title=Rademacher and Gaussian complexities: Risk bounds and structural results,
	author=Bartlett, Peter L and Mendelson, Shahar,
	journal=Journal of Machine Learning Research,
	volume=3,
	number=Nov,
	pages=463–482,
	year=2002



@articlebartlett2002rademacher,
	title=Rademacher and Gaussian complexities: Risk bounds and structural results,
	author=Bartlett, Peter L and Mendelson, Shahar,
	journal=Journal of Machine Learning Research,
	volume=3,
	number=Nov,
	pages=463–482,
	year=2002


@articleli2020tilted,
	title=Tilted Empirical Risk Minimization,
	author=Li, Tian and Beirami, Ahmad and Sanjabi, Maziar and Smith, Virginia,
	journal=arXiv preprint arXiv:2007.01162,
	year=2020


@articlesinha2017certifying,
	title=Certifying some distributional robustness with principled adversarial training,
	author=Sinha, Aman and Namkoong, Hongseok and Duchi, John,
	journal=arXiv preprint arXiv:1710.10571,
	year=2017


@articleparikh2014proximal,
	title=Proximal algorithms,
	author=Parikh, Neal and Boyd, Stephen,
	journal=Foundations and Trends in optimization,
	volume=1,
	number=3,
	pages=127–239,
	year=2014,
	publisher=Now Publishers Inc. Hanover, MA, USA


@articleyang2012multiple,
	title=Multiple kernel learning from noisy labels by stochastic programming,
	author=Yang, Tianbao and Mahdavi, Mehrdad and Jin, Rong and Zhang, Lijun and Zhou, Yang,
	journal=arXiv preprint arXiv:1206.4629,
	year=2012


@articlegretton2012kernel,
	title=A kernel two-sample test,
	author=Gretton, Arthur and Borgwardt, Karsten M and Rasch, Malte J and Schölkopf, Bernhard and Smola, Alexander,
	journal=The Journal of Machine Learning Research,
	volume=13,
	number=1,
	pages=723–773,
	year=2012,
	publisher=JMLR. org


@articlezeiler2012adadelta,
	title=Adadelta: an adaptive learning rate method,
	author=Zeiler, Matthew D,
	journal=arXiv preprint arXiv:1212.5701,
	year=2012


@articlegoodfellow2014explaining,
	title=Explaining and harnessing adversarial examples,
	author=Goodfellow, Ian J and Shlens, Jonathon and Szegedy, Christian,
	journal=arXiv preprint arXiv:1412.6572,
	year=2014


@articlemadry2017towards,
	title=Towards deep learning models resistant to adversarial attacks,
	author=Madry, Aleksander and Makelov, Aleksandar and Schmidt, Ludwig and Tsipras, Dimitris and Vladu, Adrian,
	journal=arXiv preprint arXiv:1706.06083,
	year=2017


@inproceedingshe2015delving,
	title=Delving deep into rectifiers: Surpassing human-level performance on imagenet classification,
	author=He, Kaiming and Zhang, Xiangyu and Ren, Shaoqing and Sun, Jian,
	booktitle=Proceedings of the IEEE international conference on computer vision,
	pages=1026–1034,
	year=2015


@inproceedingsrony2019decoupling,
	title=Decoupling direction and norm for efficient gradient-based l2 adversarial attacks and defenses,
	author=Rony, Jérôme and Hafemann, Luiz G and Oliveira, Luiz S and Ayed, Ismail Ben and Sabourin, Robert and Granger, Eric,
	booktitle=Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
	pages=4322–4330,
	year=2019


@inproceedingscarlini2017towards,
	title=Towards evaluating the robustness of neural networks,
	author=Carlini, Nicholas and Wagner, David,
	booktitle=2017 ieee symposium on security and privacy (sp),
	pages=39–57,
	year=2017,
	organization=IEEE



@articlelecun1998gradient,
	title=Gradient-based learning applied to document recognition,
	author=LeCun, Yann and Bottou, Léon and Bengio, Yoshua and Haffner, Patrick and others,
	journal=Proceedings of the IEEE,
	volume=86,
	number=11,
	pages=2278–2324,
	year=1998,
	publisher=Taipei, Taiwan


@articlesinha2017certifying,
	title=Certifying some distributional robustness with principled adversarial training,
	author=Sinha, Aman and Namkoong, Hongseok and Volpi, Riccardo and Duchi, John,
	journal=arXiv preprint arXiv:1710.10571,
	year=2017


@articlechen2007robust,
	title=A robust optimization perspective on stochastic programming,
	author=Chen, Xin and Sim, Melvyn and Sun, Peng,
	journal=Operations research,
	volume=55,
	number=6,
	pages=1058–1071,
	year=2007,
	publisher=INFORMS



@articledelage2010distributionally,
	title=Distributionally robust optimization under moment uncertainty with application to data-driven problems,
	author=Delage, Erick and Ye, Yinyu,
	journal=Operations research,
	volume=58,
	number=3,
	pages=595–612,
	year=2010,
	publisher=INFORMS


@articleduchi2016statistics,
	title=Statistics of robust optimization: A generalized empirical likelihood approach,
	author=Duchi, John and Glynn, Peter and Namkoong, Hongseok,
	journal=arXiv preprint arXiv:1610.03425,
	year=2016


@articleben2013robust,
	title=Robust solutions of optimization problems affected by uncertain probabilities,
	author=Ben-Tal, Aharon and Den Hertog, Dick and De Waegenaere, Anja and Melenberg, Bertrand and Rennen, Gijs,
	journal=Management Science,
	volume=59,
	number=2,
	pages=341–357,
	year=2013,
	publisher=INFORMS


@articlebertsimas2018data,
	title=Data-driven robust optimization,
	author=Bertsimas, Dimitris and Gupta, Vishal and Kallus, Nathan,
	journal=Mathematical Programming,
	volume=167,
	number=2,
	pages=235–292,
	year=2018,
	publisher=Springer


@inproceedingslam2015quantifying,
	title=Quantifying input uncertainty in stochastic optimization,
	author=Lam, H and Zhou, E,
	booktitle=Proceedings of the 2015 Winter Simulation Conference. IEEE,
	year=2015


@inproceedingsnamkoong2016stochastic,
	title=Stochastic gradient methods for distributionally robust optimization with f-divergences,
	author=Namkoong, Hongseok and Duchi, John C,
	booktitle=Advances in neural information processing systems,
	pages=2208–2216,
	year=2016


@articleesfahani2018data,
	title=Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations,
	author=Esfahani, Peyman Mohajerin and Kuhn, Daniel,
	journal=Mathematical Programming,
	volume=171,
	number=1-2,
	pages=115–166,
	year=2018,
	publisher=Springer



@articleblanchet2019robust,
	title=Robust Wasserstein profile inference and applications to machine learning,
	author=Blanchet, Jose and Kang, Yang and Murthy, Karthyek,
	journal=Journal of Applied Probability,
	volume=56,
	number=3,
	pages=830–857,
	year=2019,
	publisher=Cambridge University Press


@articlegao2016distributionally,
	title=Distributionally robust stochastic optimization with Wasserstein distance,
	author=Gao, Rui and Kleywegt, Anton J,
	journal=arXiv preprint arXiv:1604.02199,
	year=2016


@articleblanchet2017data,
	title=Data-driven optimal transport cost selection for distributionally robust optimization,
	author=Blanchet, J and Kang, Y and Zhang, F and Murthy, K,
	journal=stat,
	volume=1050,
	pages=19,
	year=2017


@inproceedingsabadeh2015distributionally,
	title=Distributionally robust logistic regression,
	author=Abadeh, Soroosh Shafieezadeh and Esfahani, Peyman Mohajerin Mohajerin and Kuhn, Daniel,
	booktitle=Advances in Neural Information Processing Systems,
	pages=1576–1584,
	year=2015


@articletolstikhin2017minimax,
	title=Minimax estimation of kernel mean embeddings,
	author=Tolstikhin, Ilya and Sriperumbudur, Bharath K and Muandet, Krikamol,
	journal=The Journal of Machine Learning Research,
	volume=18,
	number=1,
	pages=3002–3048,
	year=2017,
	publisher=JMLR. org


@articletalagrand1995concentration,
	title=Concentration of measure and isoperimetric inequalities in product spaces,
	author=Talagrand, Michel,
	journal=Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques,
	volume=81,
	number=1,
	pages=73–205,
	year=1995,
	publisher=Springer

@articlekurakin2016adversarial,
	title=Adversarial machine learning at scale,
	author=Kurakin, Alexey and Goodfellow, Ian and Bengio, Samy,
	journal=arXiv preprint arXiv:1611.01236,
	year=2016


@articlemadry2017towards,
	title=Towards deep learning models resistant to adversarial attacks,
	author=Madry, Aleksander and Makelov, Aleksandar and Schmidt, Ludwig and Tsipras, Dimitris and Vladu, Adrian,
	journal=arXiv preprint arXiv:1706.06083,
	year=2017


@articlemiyato2018virtual,
	title=Virtual adversarial training: a regularization method for supervised and semi-supervised learning,
	author=Miyato, Takeru and Maeda, Shin-ichi and Koyama, Masanori and Ishii, Shin,
	journal=IEEE transactions on pattern analysis and machine intelligence,
	volume=41,
	number=8,
	pages=1979–1993,
	year=2018,
	publisher=IEEE


@inproceedingspapernot2016distillation,
	title=Distillation as a defense to adversarial perturbations against deep neural networks,
	author=Papernot, Nicolas and McDaniel, Patrick and Wu, Xi and Jha, Somesh and Swami, Ananthram,
	booktitle=2016 IEEE Symposium on Security and Privacy (SP),
	pages=582–597,
	year=2016,
	organization=IEEE


@articlesamangouei2018defense,
	title=Defense-gan: Protecting classifiers against adversarial attacks using generative models,
	author=Samangouei, Pouya and Kabkab, Maya and Chellappa, Rama,
	journal=arXiv preprint arXiv:1805.06605,
	year=2018



@inproceedingszhang2018efficient,
	title=Efficient neural network robustness certification with general activation functions,
	author=Zhang, Huan and Weng, Tsui-Wei and Chen, Pin-Yu and Hsieh, Cho-Jui and Daniel, Luca,
	booktitle=Advances in neural information processing systems,
	pages=4939–4948,
	year=2018


@articleathalye2018robustness,
	title=On the robustness of the cvpr 2018 white-box adversarial example defenses,
	author=Athalye, Anish and Carlini, Nicholas,
	journal=arXiv preprint arXiv:1804.03286,
	year=2018


@articleathalye2018obfuscated,
	title=Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples,
	author=Athalye, Anish and Carlini, Nicholas and Wagner, David,
	journal=arXiv preprint arXiv:1802.00420,
	year=2018


@inproceedingsbunel2018unified,
	title=A unified view of piecewise linear neural network verification,
	author=Bunel, Rudy R and Turkaslan, Ilker and Torr, Philip and Kohli, Pushmeet and Mudigonda, Pawan K,
	booktitle=Advances in Neural Information Processing Systems,
	pages=4790–4799,
	year=2018


@inproceedingscarlini2017adversarial,
	title=Adversarial examples are not easily detected: Bypassing ten detection methods,
	author=Carlini, Nicholas and Wagner, David,
	booktitle=Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,
	pages=3–14,
	year=2017


@inproceedingscheng2017maximum,
	title=Maximum resilience of artificial neural networks,
	author=Cheng, Chih-Hong and Nührenberg, Georg and Ruess, Harald,
	booktitle=International Symposium on Automated Technology for Verification and Analysis,
	pages=251–268,
	year=2017,
	organization=Springer


@inproceedingscroce2019provable,
	title=Provable robustness of relu networks via maximization of linear regions,
	author=Croce, Francesco and Andriushchenko, Maksym and Hein, Matthias,
	booktitle=the 22nd International Conference on Artificial Intelligence and Statistics,
	pages=2057–2066,
	year=2019


@inproceedingsdutta2018output,
	title=Output range analysis for deep feedforward neural networks,
	author=Dutta, Souradeep and Jha, Susmit and Sankaranarayanan, Sriram and Tiwari, Ashish,
	booktitle=NASA Formal Methods Symposium,
	pages=121–138,
	year=2018,
	organization=Springer


@articledvijotham2018training,
	title=Training verified learners with learned verifiers,
	author=Dvijotham, Krishnamurthy and Gowal, Sven and Stanforth, Robert and Arandjelovic, Relja and O'Donoghue, Brendan and Uesato, Jonathan and Kohli, Pushmeet,
	journal=arXiv preprint arXiv:1805.10265,
	year=2018


@inproceedingsehlers2017formal,
	title=Formal verification of piece-wise linear feed-forward neural networks,
	author=Ehlers, Ruediger,
	booktitle=International Symposium on Automated Technology for Verification and Analysis,
	pages=269–286,
	year=2017,
	organization=Springer


@inproceedingscao2017mitigating,
	title=Mitigating evasion attacks to deep neural networks via region-based classification,
	author=Cao, Xiaoyu and Gong, Neil Zhenqiang,
	booktitle=Proceedings of the 33rd Annual Computer Security Applications Conference,
	pages=278–287,
	year=2017


@articlecohen2019certified,
	title=Certified adversarial robustness via randomized smoothing,
	author=Cohen, Jeremy M and Rosenfeld, Elan and Kolter, J Zico,
	journal=arXiv preprint arXiv:1902.02918,
	year=2019


@inproceedingslecuyer2019certified,
	title=Certified robustness to adversarial examples with differential privacy,
	author=Lecuyer, Mathias and Atlidakis, Vaggelis and Geambasu, Roxana and Hsu, Daniel and Jana, Suman,
	booktitle=2019 IEEE Symposium on Security and Privacy (SP),
	pages=656–672,
	year=2019,
	organization=IEEE


@articleli2018certified,
	title=Certified adversarial robustness with additive gaussian noise,
	author=Li, Bai and Chen, Changyou and Wang, Wenlin and Carin, Lawrence,
	journal=arXiv preprint arXiv:1809.03113,
	year=2018


@inproceedingsliu2018towards,
	title=Towards robust neural networks via random self-ensemble,
	author=Liu, Xuanqing and Cheng, Minhao and Zhang, Huan and Hsieh, Cho-Jui,
	booktitle=Proceedings of the European Conference on Computer Vision (ECCV),
	pages=369–385,
	year=2018


@articleuesato2018adversarial,
	title=Adversarial risk and the dangers of evaluating against weak attacks,
	author=Uesato, Jonathan and O'Donoghue, Brendan and Oord, Aaron van den and Kohli, Pushmeet,
	journal=arXiv preprint arXiv:1802.05666,
	year=2018


@articlemiyato2018virtual,
	title=Virtual adversarial training: a regularization method for supervised and semi-supervised learning,
	author=Miyato, Takeru and Maeda, Shin-ichi and Koyama, Masanori and Ishii, Shin,
	journal=IEEE transactions on pattern analysis and machine intelligence,
	volume=41,
	number=8,
	pages=1979–1993,
	year=2018,
	publisher=IEEE


@inproceedingspollard1990empirical,
	title=Empirical processes: theory and applications,
	author=Pollard, David,
	booktitle=NSF-CBMS regional conference series in probability and statistics,
	pages=i–86,
	year=1990,
	organization=JSTOR


@articlekhosravi2019non,
	title=Non-parametric inference adaptive to intrinsic dimension,
	author=Khosravi, Khashayar and Lewis, Greg and Syrgkanis, Vasilis,
	journal=arXiv preprint arXiv:1901.03719,
	year=2019


@incollectionyu1997assouad,
	title=Assouad, fano, and le cam,
	author=Yu, Bin,
	booktitle=Festschrift for Lucien Le Cam,
	pages=423–435,
	year=1997,
	publisher=Springer


	@inproceedingsindyk1998approximate,
	title=Approximate nearest neighbors: towards removing the curse of dimensionality,
	author=Indyk, Piotr and Motwani, Rajeev,
	booktitle=Proceedings of the thirtieth annual ACM symposium on Theory of computing,
	pages=604–613,
	year=1998


@inproceedingsdatar2004locality,
	title=Locality-sensitive hashing scheme based on p-stable distributions,
	author=Datar, Mayur and Immorlica, Nicole and Indyk, Piotr and Mirrokni, Vahab S,
	booktitle=Proceedings of the twentieth annual symposium on Computational geometry,
	pages=253–262,
	year=2004


	
@inproceedingsraginsky2009locality,
	title=Locality-sensitive binary codes from shift-invariant kernels,
	author=Raginsky, Maxim and Lazebnik, Svetlana,
	booktitle=Advances in neural information processing systems,
	pages=1509–1517,
	year=2009



@articlekingma2014adam,
	title=Adam: A method for stochastic optimization,
	author=Kingma, Diederik P and Ba, Jimmy,
	journal=arXiv preprint arXiv:1412.6980,
	year=2014


@bookbonnans2013perturbation,
	title=Perturbation analysis of optimization problems,
	author=Bonnans, J Frédéric and Shapiro, Alexander,
	year=2013,
	publisher=Springer Science & Business Media



@incollectionvan1996weak,
	title=Weak convergence,
	author=Van Der Vaart, Aad W and Wellner, Jon A,
	booktitle=Weak convergence and empirical processes,
	pages=16–28,
	year=1996,
	publisher=Springer



@articlecortes2010two,
		title=Two-stage learning kernel algorithms,
		author=Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin,
		year=2010



@articleqiu2008framework,
	title=A framework for multiple kernel support vector regression and its applications to siRNA efficacy prediction,
	author=Qiu, Shibin and Lane, Terran,
	journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics,
	volume=6,
	number=2,
	pages=190–199,
	year=2008,
	publisher=IEEE


@inproceedingslauriola2018minimum,
	title=The minimum effort maximum output principle applied to Multiple Kernel Learning.,
	author=Lauriola, Ivano and Polato, Mirko and Aiolli, Fabio,
	booktitle=ESANN,
	year=2018


@inproceedingslauriola2017radius,
	title=Radius-margin ratio optimization for dot-product boolean kernel learning,
	author=Lauriola, Ivano and Polato, Mirko and Aiolli, Fabio,
	booktitle=International conference on artificial neural networks,
	pages=183–191,
	year=2017,
	organization=Springer


@articleaiolli2015easymkl,
	title=EasyMKL: a scalable multiple kernel learning algorithm,
	author=Aiolli, Fabio and Donini, Michele,
	journal=Neurocomputing,
	volume=169,
	pages=215–224,
	year=2015,
	publisher=Elsevier


@inproceedingsdo2009margin,
	title=Margin and radius based multiple kernel learning,
	author=Do, Huyen and Kalousis, Alexandros and Woznica, Adam and Hilario, Melanie,
	booktitle=Joint European Conference on Machine Learning and Knowledge Discovery in Databases,
	pages=330–343,
	year=2009,
	organization=Springer


@articlelauriola2020mklpy,
	title=MKLpy: a python-based framework for Multiple Kernel Learning,
	author=Lauriola, Ivano and Aiolli, Fabio,
	journal=arXiv preprint arXiv:2007.09982,
	year=2020


@inproceedingstanabe2008simple,
	title=Simple but effective methods for combining kernels in computational biology,
	author=Tanabe, Hiroaki and Ho, Tu Bao and Nguyen, Canh Hao and Kawasaki, Saori,
	booktitle=2008 IEEE International Conference on Research, Innovation and Vision for the Future in Computing and Communication Technologies,
	pages=71–78,
	year=2008,
	organization=IEEE


@articlegamarnik2018computing,
	title=Computing the partition function of the sherrington-kirkpatrick model is hard on average,
	author=Gamarnik, David and Kizildag, Eren,
	journal=arXiv preprint arXiv:1810.05907,
	year=2018


@incollectionvapnik2015uniform,
	title=On the uniform convergence of relative frequencies of events to their probabilities,
	author=Vapnik, Vladimir N and Chervonenkis, A Ya,
	booktitle=Measures of complexity,
	pages=11–30,
	year=2015,
	publisher=Springer


@articledudley1978central,
	title=Central limit theorems for empirical measures,
	author=Dudley, Richard M,
	journal=The Annals of Probability,
	pages=899–929,
	year=1978,
	publisher=JSTOR



@articlehaussler1995sphere,
	title=Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension,
	author=Haussler, David,
	journal=Journal of Combinatorial Theory, Series A,
	volume=69,
	number=2,
	pages=217–232,
	year=1995,
	publisher=Elsevier


@articleradon1921mengen,
	title=Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten,
	author=Radon, Johann,
	journal=Mathematische Annalen,
	volume=83,
	number=1,
	pages=113–115,
	year=1921,
	publisher=Springer


@articlebartlett1996fat,
	title=Fat-shattering and the learnability of real-valued functions,
	author=Bartlett, Peter L and Long, Philip M and Williamson, Robert C,
	journal=journal of computer and system sciences,
	volume=52,
	number=3,
	pages=434–452,
	year=1996,
	publisher=Elsevier


@inproceedingspeel2010empirical,
	title=Empirical Bernstein inequalities for U-statistics,
	author=Peel, Thomas and Anthoine, Sandrine and Ralaivola, Liva,
	booktitle=Neural Information Processing Systems (NIPS),
	number=23,
	pages=1903–1911,
	year=2010


@bookpena1999decoupling,
	title=Decoupling: From dependence to independence,
	author=Peña, Víctor H and Giné, Evarist,
	year=1999,
	publisher=Springer


@incollectionvan1996maximal,
	title=Maximal Inequalities and Covering Numbers,
	author=van der Vaart, Aad W and Wellner, Jon A,
	booktitle=Weak Convergence and Empirical Processes,
	pages=95–106,
	year=1996,
	publisher=Springer


@articleendou2008lebesgue,
	title=The Lebesgue monotone convergence theorem,
	author=Endou, Noboru and Narita, Keiko and Shidama, Yasunari,
	journal=Formalized Mathematics,
	volume=16,
	number=2,
	pages=167–175,
	year=2008



