Learning large-scale Kernel Networks
Authors: Amirhesam Abedsoltan
Parthe Pandit
Misha Belkin
Venue: Submitted to ICLR 2023 (2023)
Keywords: Kernel machines
RBF networks
large-scale datasets
data augmentation

Abstract:     This paper concerns large-scale training of *Kernel Networks*, a generalization of kernel machines that allows the model to have arbitrary centers. We propose a scalable training algorithm -- EigenPro 3.0 -- based on alternating projections with preconditioned SGD for the alternating steps. In contrast to classical kernel machines, but similar to neural networks, our algorithm enables decoupling the learned model from the training set. This empowers kernel models to take advantage of modern methodologies in deep learning, such as data augmentation. We demonstrate the promise of EigenPro 3.0 on several experiments over large datasets. We also show data augmentation can improve performance of kernel models.

LEARNING LARGE-SCALE KERNEL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
This paper concerns large-scale training of Kernel Networks, a generalization kernel machines that allows the model have arbitrary centers. We propose a scalable training algorithm - EigenPro based on alternating projections with preconditioned SGD for the alternating steps. This is the first linear space algo- rithm for training kernel networks, which enables training models with large num- ber of centers. contrast to classical kernel machines, but similar to neural ner- works, our algorithm enables decoupling the learned model from the training set. This empowers kernel models to take advantage of modern methodologies in deep learning, such as data augmentation. We demonstrate the promise of EigenPro 3.0 on several experiments over large datasets. We also show data augmentation can improve performance of kernel models.
INTRODUCTION
Kernel Machines are predictive models described by the non-parametric estimation problem,
1 Σ L(vi, f(z:)) | 2
min SEH
(())
where H. is reproducing kemne Hilbert space (RKHS), and (X, y) {ær, Vi Ti=1 training samples. By the representer theorem Wahba (1990), the solution to this problem has the form,
f(xz)
Σ a; (x, x;) E H.
where K is the reproducing kernel corresponding to H. The weights = (as) R" are chosen to fit (X, y). For example, kernel ridge regression takes the square loss L(u, = (u - v)², and the weights R" of the learned model are the unique solution to the n linear system of equations,
(K(X + AI,)a= = y.
(3)
where X) K (æ,, æ;) is the matrix of pairwise kernel evaluations between samples.
However, observe that the kernel machine from equation (2), is strongly coupled to the training set, i.e., predictions from learned model require access the entire training dataset. There is no explicit control on the model size, it is always the same as the size of the dataset n. Such a coupling inconvenient from an engineering perspective. and limits the scalability to large datasets for inference as well as for training. For instance, when fresh training samples are available, larger system of equations needs to be solved, from scratch, to retrain the model.
In contrast, neural networks are decoupled from the training set. In particular, pretrained neural network can be finetuned without any access to the original dataset. This decoupling affords the practitioner tremendous flexibility and is crucial for large-scale learning.
Deep learning methodologies take advantage of this scalability. For example, data augmentation widely used training technique to boost performance of neural networks, see Shorten & Khosh- goftaar (2019) for a review. Here, we augment the training set with artificial samples, which are obtained via perturbations or transformations to the true samples. For kernel machines, data aug- mentation means increasing the size of the dataset, and hence implicitly also the model size. Hence, data augmentation is prohibitively expensive for learning standard kernel machines.
Kernel Networks generalize kernel machines by allowing the flexibility to choose arbitrary centers. Perhaps most importantly, this leads the learned model to be decoupled from the training set.

---

Definition 1 (Kernel Network). Given a kernel K(;,)) set of centers Z : {z, 1- and weights a = -aa)) E I,," a kernel network is a function a + f(æ; Z, a) given by
f(:; a, Σ a,K(x,
(4)
We refer to p as the model size, since there are p degrees of freedom for the predictor.
Note that by definition, kernel networks do not require access to the training set to make predictions. This helps inference as well as training when p < n, and enables models to be trained on large- scale datasets. This also provides explicit capacity control by choosing p. Such a control is lacking in classical kernel machines since the model size is always n.
Kernel networks are classically studied in machine learning in the form of RBF networks, which cor- respond to radial kernels K (x, z) = 6[| z|]). RBF networks were introduced by Broomhead & LLwe (1988) as function approximation technique. Like neural networks, they are universal approximators for functions in L' (2()),), see Park & Sandberg (1993); Poggio & Girosi (1990). Our definition extends to all positive definite kernels. This extension allows using kernels like the Con- volutional Neural Tangent Kernel, which is neither radial nor rotationally invariant, among others.
1.1 PRIOR WORK
In the case when Z = X, which corresponds to standard kernel machines, there exist several solvers Wang et al. (2019); Gardner et al. (2018a); van der Wilk et al. (2020). For certain special kernels Si et al. (2014) enable speed-ups depending on the scale hyperparameter.
Classical procedures to learn kernel networks in their full generality, are to plug-in the functional form of equation (4) to solve problem
(1). For example for the square loss, the solution satisfies, (K(X 2 K Z) + (Z, = K(X, Z)T y.
(5)
where ( Z) E RTx is the pairwise kernel evaluation between data x; and centers Zj. Notice when À small, the solution converges to (XX, Z) y. which involves the pseudo-inverse. For other loss functions, iterative methods such gradient descent can be used for minimizing the objective in terms of the weights a. Several regularized ERM approaches have been studied, see Que & Belkin (2016) and Scholkopf et al. (1997) for review and comparisons. These methods suffer from poorly conditioned matrices, which significantly limits their rate of convergence, See Figure 3 in the Appendix for a deeper discussion on this approach and comparison with problem-specific solvers.
Nyström approximation: Kernel networks with Z C X have been studied extensively following Williams & Seeger (2000). This is perhaps the predominant strategy for applying kernel machines at scale, in the general case when random feature are hard to compute. Methods such as NYTRO Camoriano et al. (2016), and FALKON Rudi al. (2017) are designed to work with such models. These methods require quadratic memory in terms of the model size. For example Meanti et al. (2020) only train models with 100,000 centers. Scaling these methods to higher model sizes is memory intensive. While these methods were not designed to train kernel networks in their gener- ality, they perform surprisingly well for this task in high dimensions, since the distribution of the centers often closely resembles the distribution of the data. However one must exercise caution for training general kernel networks using these methods, i.c., when Z of X.
Random features model: Decoupled models for kernel machines have been considered earlier, perhaps most elegantly in the Random Features framework by Rahimi & Recht (2007). However, it is not straightforward to find the correct distribution that yields desired target kernel, since sampling from the Fourier measure is not always tractable in high dimensions, especially for kernels that are not rotation invariant.
Gaussian Process: In the literature on GPs, sparse GPs Titsias (2009) is similar to kernel networks considered above. These models have so-called inducing points that reduce the model complexity. While several follow-ups such as Wilson & Nickisch (2015) and Gardner et al. (2018b) have been applied in practice, they require quadratic memory in terms of the number of inducing points, pre- venting scaling to large models. Indeed the inducing points interpretation is perhaps the most useful in choosing 'good' centers for kernel networks.
2

---

EigenPro: (short for Eigenspace Projections) is iterative algorithm for kernel regression, i.e., when Z = X. solves the linear system (3) by taking advantage of the problem structure. The algo- rithm applies preconditioned Richarson iteration Richardson (1911), based projecting gradients to certain eigenspaces of ((X, X). EigenPro 2.0 Ma & Belkin (2019) improved upon EigenPro 1.0 Ma & Belkin (2017) by reducing the computational and memory costs for the preconditioner, by applying a stochastic approximation for estimating, and projecting onto the relevant eigenspaces.
EigenPro 2.0 cannot solve the general problem of learning kernel machine, i.e., when Z + X. Our extension EigenPro 3.0, proposed in this paper fills this gap.
1.2 MAIN CONTRIBUTIONS
We develop scalable iterative algorithm for learning kernel networks with low memory foot- print. Our training algorithm derived using alternating but separate eigenspace projection steps. Importantly, our preconditioning preserves the decoupling between the model and the training set. EigenPro serves as the basis for our approach, and we use the same form for the preconditioner for more general problem of learning kernel networks. Our algorithm requires an additional projection step neccessary for this problem, which can be solved by decoupled instance of EigenPro.
The focus of this paper is the design of the algorithm for training kernel networks in full generality with linear space complexity in terms of the model size. We omit generalization and optimization properties of the algorithm, and will consider them follow-up works. As such, these methods are expected to converge and behave well with analyses from linear systems and convex quadratic optimization being directly applicable. Furthermore, our method converges to consistent estimator if we consider student-teecher setup with known model centers.
Some noteworthy highlights of our training algorithm EigenPro 3.0 are:
Model decoupled from training data: Our algorithm fully respects the decoupling between the model and training data, and allows for any configuration of model centers. In particular, do not require any label information on the centers. The flexibility of a decoupled model allows us apply data augmentation for learning kernel networks. We demonstrate a gain in performance with this approach. We can also train overparameterized kernel networks with p > n.
2. Linear space complexity: Our algorithm can run with O(p) memory, and O(p²) computations per iteration. Consequently, we can handle very large model sizes with a potential to scale much further. For example in our numerical experiments, we have trained models with 512,000 degrees of freedom. To our knowledge, this is the first general kernel network of this size trained with < 100 GB RAM.
Organization: In Section 3, we derive a vanilla version of our algorithm as a function space projected preconditioned gradient descent, with a decoupled model aggeostgiostic preconditioner. In Sec- tion 4, we introduce several stochastic approximations that make our algorithm much faster and makes it scalable to large-scale datasets. Section 5 demonstrate the scalability of our algorithm to large datasets and large models over several datasets. Proofs are relegated to the Appendix.
2 PRELIMINARIES AND NOTATION
In what follows, functions are lowercase letters a, sets are uppercase letters A, vectors are lowercase bold letters a, matrices are uppercase bold letters A, operators are caligraphic letters A, spaces and subspaces are bolfdace caligraphic letters A. Subscripts to sets, vectors, matrices indicate size.
If K is reproducing kernel for RKHS H. then we have
(a, K(, ((,,))) = a(x: Va E H.
(K(, x)
= K(x, = K(2, x))
(6)
Evaluations and kernel matrices: The vector of evaluations of a function f over a set X
{ is f(X) = (f(x.)) E R=. We denote the kernel matrices K(X, 2) E Ruxp,
K(X,X) X) Raxn K(Z,7) 7) RPxp, and K(Z, X) K(X, Similarly, K(; X) Hix
3

---

and () E HPx and for set A {ail and vector (as) E R use the notation
A(a Σ K((aa))ay H.
K(z, A)a
Σ K K2z e.
Finally, for an operator A, a function a, and set = (ai))==11 by
Afa) = (b(a:)) E R2 where b= Aa),
(8)
Definition 2. [Top-q eigensystem] Let \ d2 ... Ans be the eigenvalues of her- mitian matrix A E Rax", i... for unit-norm ei we have Ae = Aee. Then we call the tuple (Aq; Egg )g+1) } the top-q eigensystem, where Ag diag(>1, 22 Ag) E R8x9 and ,,,
Egg = (11, 62, Egg IR=xq.
Fréchet derivative: Given a function J - R. the Frech derivative of J with respect to a linear functional, denoted V JJ such that
J(f + - J(f) v.J(M) = 0.
| lim
|1
Since v is linear functional, it lies in the dual space H¹ Since H is a Hilbert space, it is self-dual, whereby H¹ H. If L is the square loss for given dataset (X, i... L(f) := 1= (f(z;) y1)² we can apply the chain rule, and using equation (6), and the fact that 1. = g. we get, that the Fréchet derivative =o is,
vyL(fo) E(fole.) n.) (ff(a) E -.)( x.) K(, X)(6(X - y). (10)
Hessian operator: The Hessian operator ViL H H for the square loss is given by,
: Σ K( & K(,,,,, KC = Σ K(z,x K(z, X)f(x)
(11)
Note that K. is surjective X, and hence invertible when restricted to X. Note that when a; for some measure F. the above summation, on rescaling by 4, converges due to strong law as,
iid P.
K [ff) Tk (f) (f) k() dP))
lim
(12)
which is an integral operator. The following lemma relates the spectra of K. and K XX. Proposition 1 (Nyström extension). For 1 < n, let X; be eigenvalue of K., and v,, its unit H-norm eigenfunction, i..., IC [w:} = A,3h/- Then A; is also an eigenvalue of (X,,)), Moreover if e,, is its unit-norm eigenvector, i.e., K (XX, X)e; X,e, we have,
e,
3/ = K(, X)
(13)
We review EigenPro 2.0 which is a closely related algorithm for kernel regression, i.e., when Z X.
Background on EigenPro (short for Eigenspace Projections): Proposed in Ma & Belkin (2017).
EigenPro 1.0 is an iterative solver for solving the linear system equation (3) based on a precondi- tioned stochastic gradient descent in the Hilbert space,
gh+ p+1=ftt - 1
[[))(
(14)
Here P is preconditioner. Due to its iterative nature, EigenPro can handle À = 0 in equation equation (3), corresponding to the problem kernel interpolation, since in that case, the learned model satisfies f(x,) = y for all samples in the training set.
can be shown that the following iteration in R.
[+1
-+1
nIIn
y),
(15)
4

---

emulates equation (14) in H. see Lemma 3 in the Appendix. The above iteration is preconditioned version of the Richardson iteration, Richardson (1911), with well-known convergence properties. Here, Q rank-q symmetric matrix obtained from the top-q eigensystem of K (X,X)), with & n.
The preconditioner, P acts to flatten the spectrum of the Hessian K.. In R the matrix I, Q has the same effect on (X,X)). The largest stable learning rate is then Aq+1 larger 4, allows faster training when P is chosen appropriately.
instead of 2. Hence a T
EigenPro 2.0 proposed in Ma & Belkin (2019), applies a stochastic approximation for P based on the Nyström extension. We apply EigenPro 2.0 to perform inexact projection step in algorithm.
3 EigenPro 3.0: PROJECTED PRECONDITIONED GRADIENT DESCENT
In this section we derive EigenPro Dexacc-ppojecctee kernel network. This algorithm is based on function space projected gradient method. However it does not scale well. In Section we make scalable by applying stochastic approximations, which finally yields EigenPro 3.0 (Algorithm 1).
precursor to EigenPro 3.0, for learning a
We want to solve the following constrained infinite dimensional problem.
minimize L(f)= = = (f(x)) - f
subject to f 2 = span (I(())))==)) (16)
2=1
Thus the learned model f is a linear combination of functions ( {K(z,, 1 just like Definition 1. We will apply the function-space projected gradient method to solve this problem,
p++1 =projz (f* - 1/ (V)((()))),
where projz (u) = argmin 1|u- - fll (17) fez
where V ()(() is the Fréchet derivative at ʃ given in equation (10), P is preconditioning
operator given in equation (25), 1) is learning rate, and proj H 2 is the projection operator that projects functions from H onto the subspace Z.
Remark 1. Note that even though equation (17) is an iteration over functions which are infinite dimensional objects he2 we can represent this iteration in finite dimensions as [a')20 where
04 E R.. To see this, observe that f Z, whereby express as,
= K(, Z)a' E H.
for an a' E R..
(18)
Furthermore, the evaluation of the function Ie above at X,
f'(X) K(X, Z)a' ER"
(19)
Gradient: Due equations (10) and (19) together, the gradient is given by the function, Z)a' -y) E x= Observe that the gradient does not lie in Z and hence step of gradient descent would leave Z, and the constraint is violated. This necessitates a projection onto Z. For finitely generated subspaces such Z, the projection operation involves solving finite dimensional linear system.
Vyl(")=K(-
(x) (
{ (K(s =pan( )) (00)
H-norm projection: Functions in can be expressed as K(,, (). Hence we can rewrite the projection problem in equation (17) minimization in R.P, with 0 as the unknowns. Observe that,
argmin
||ʃ 111 argmin || u| 7 argmin (f 2 (f, u)
f
since ||ull does not affect the solution. Further, using / = K(, 2)0, we can show that (f.f)x 2 (f, u)xx 0 KZ, Z)0 20 u(Z). This yields a simple method to calculate the projection onto Z.
(21)
proj {u]
argmin |lf u/1x = Z) = K(: K), - E Z,
(22)
fez
where i
argmin 0 K(Z 20 u(Z) K(Z, 2) ((Z,)))~uu(2
(23)
DER*
Notice that @ above is linear in u, and (z) K(Z, Z) Hence we have the following lemma.
5

---

Algorithm 1 EigenPro3.0
Algorithm 2 EigenPro ex..0exxcttrrooo exaceccc-eooo
Require: Data (X, y), centers Z, batch size m.
Require: Data (X, y), centers Z, initialization
Nyström size 8,, preconditioner level
a preconditioning level q-
1: Fetch subsample X, X of size
1: (E, A) t- top-y eigensystem of K(X,
2: (E, A) + top-q eigensystem of (x),,.))
2: Q = -ELL A
E R
Rex 4: while Stopping criterion is not reached do
3: C- C=,(Z,XX) - A =)
while Stopping criterion not reached do
4:
g + K(X, Z)
5: Fetch minibatch (Xm. ym)
K(Z. (I, Q)g
6:
9m f K (XXm Z)a ym
6:
0 0 1-, Z)
7:
h KZZ, Xm 9m CK(Xs; Xm)gm
7:
a-aa a r
8:
0 + EigenPro 2.0 ( h)
8:
end while
9:
a f a
22 7
EigenPro 2.0 h)) approximates ( 7 See Table for comparison of costs.
10: end while
Proposition 2 (Projection). The projection step in equation (17) can be simplified as,
(P(V, (
(2)) E Z.
(24)
Hence, in order to perform the update, only need to know P (VV) which can be evaluated efficiently for suitably chosen preconditioner.
Data preconditioner agnostic to model: Just like with usual gradient descent, the largest stable learning rate is governed by the largest eigenvalue of the Hessian the objective in equation (16), which is given by equation (I1). The preconditioner P in equation (17) acts reduce the effect of a few large eigenvalues. We choose P given in equation (25), just like Ma & Belkin (2017).
P - Σ
{(1-
21-22
Ag+1 Xg
1/: 2 v/s
H - H.
(25)
Recall from Section that v); are eigenfunctions of the Hessian K. characterized Proposition Note that this preconditioner is independent of Z. Since V VfL( E X, we only need to understand P on X. Let (Aq, Eg)) the top-q eigensystem K K(X, X), see Def. Define the rank-q matrix,
Q EE \ E R
(26)
The following lemma outlines the computation involved in preconditioning. Proposition 3 (Preconditioner). The action of P from equation (25) on functions in is given by,
()(: K(; - -Q)a Va E IR...
(27)
Since know from equation (20) that V,T(J) (K, 7)a² y), have, P L()) (Z) = K(Z,X)(I, - (X(() Z)a' -))
(28)
The following lemma combines this with Proposition 2 to get the update equation from Algorithm 2. Lemma (Algorithm 2 iteration). The following iteration in Rº emulates equation (17) in H. a - ((, ((Z,)))) (K(K)XXXXXXXXXXX... Z)x²
(K
y). -
(29)
Algorithm 2 does not scale well large models and large datasets. We propose stochastic approximations that drastically make it scalable to both large models as well as large datasets.
4 SCALING UP COMPUTATIONS VIA MULTIPLE STOCHASTIC APPROXIMATIONS
Algorithm suffers from 3 main issues. It requires (i) access to entire dataset of size O(n) at each iteration, (ii) (n²?) memory to calculate the preconditioner Q. and (iii) O for the matrix inversion corresponding exact projection. This prevents scalability to large and p.

---

Computation
Memory
setup
per iteration
EigenPro 3.0 3.0
ng mp + ms + 98 + ps + Tep2
sq
8² sm + Mop2 pn + n²
EigenPro 3. bexacct-rojecttoon
np + nq
FALKON
np
p²
(Order complexity analysis.) Table 4 in the Appendix clearly states all symbols. Here Tep2 is the time it takes to run EigenPro 2.0 for the approximate projection. In practice we only run epoch of EigenPro 2.0 for large scale experiments for which Tep2 O(p²). Similarly, Map2 = Op)) is the memory rquired for running EigenPro 2.0. We assume the cost single kernel evaluation is O(1) and the number of targets is ((1).
Table 1:
CIFARSM *
CIFARSM
89
EP3: 16000
70
16000
EP3: 64000
87
KR 64000
Test accuracy (%)
EP3: 256000
KR 256000
85
16
2556
500
2000
16
64
255
500
2000
ImageNet*
HIGGS
MNIST8M
80
65
72
74
60
55
62
56
50
50
64
1000
256 2000
16
256 500
2000
Number of training samples (x 1000)
Figure 1: (Large scale training.) We randomly subsample to get model centers. The Kernel Regres- sion (KR) baselines (dashed) are obtained from standard kernel machine over the centers and their corresponding labels. Solid lines shows the performance of kernel networks trained using our algo- rithm, for varying number of training samples. Similar neural networks, performance improves with more training samples. This is consistent across data sets. we applied feature extraction before applying the kernel.
In this section we present 3 stochastic approximation schemes stochsatic gradients, Nyström pre- conditioning, and inexact projection that drastically reduce the computational cost and memory requirements. These approximations together give Algorithm 1.
Algorithm 2 emulates equation (17), whereas Algorithm is designed emulate its approximation,
g++ f n projz (Ps (P,((1)))))
(30)
where V,I(f") is stochastic gradient obtained from subsample of size m. P. is preconditioner obtained via Nyström extension based preconditioner from a subset of size s, and projg is an inexact projection using EigenPro 2.0 solve the projection equation K ((Z, Z)0 h.
7

---

Stochastic gradients: We can replace the gradient with stochastic gradients, whereby Vf((f")
only depends on a batch (Xm. ymm of size m, denoted Xm = f J==1 and ym = (8ky) E R."..
,イ(())= (V())) vt, (,,) (m,,X,)(((A))))) Z) -ym) E X.
(31)
Remark 2. Here need scale the learning rate by a m
get unbiased estimates of VyL(f*).
Nyström preconditioning: We obtain an approximation for the preconditioner P from equa- tion (25), which requires access all samples. We use the Nystrom extension, see Williams & Seeger (2000). Consider a subset of size X, { S X. We introduce the Nyström preconditioner.
Pe I=:=I- E
9+1 15
2/ 2
O8S. vG.
(32)
where vig are eigenfunctions of == = k== K(, ) k(, Dii)) Note that K ~ 1 K. since both approximate TK as shown in equation (12). However the scaling doesn't 't affect the preconditioner Ps. since uif are unit norm. This preconditioner was first proposed in Ma & Belkin (2019).
Next, we need to understand the action P. on elements X. Let (E,, Ag) be the top-q eigensys- tem of K K(,,, X,). Define the rank-q matrix,
Q, = (I, A E Rx*
(33)
Lemma 2 (Nyström preconditioning). Let a E R and Xm chosen like in equation (31), then,
Pa [K((, K(;Xmma K(,,X.) Xm)a.
(34)
Consequently, using equation (31), we get,
P. { (V,(()) (2) (K Xm) K(Z, (m)) Xm)) (K Z) ym)) E RR. (35)
Inexact projection: The projection step in Algorithm 2 requires the inverse of K 2) which is computationally expensive. However this step solving the p x p linear system
K(Z, Z)0 = K(Z,
((X,, xm.) (K(Xm, Z)a' ym)
(36)
Notice that this is the kernel interpolation problem EigenPro 2.0 can solve. This leads to the update, a = a
m 0
(EigenPro update)
where 0T is the solution to equation (36) after steps EigenPro 2.0 given in Algorithm in the Appendix. Algorithm 1 implements the update above. Furthermore, EigenPro 2.0 itself applies preconditioner which only depends on Z. no dependence on X, thus maintaining the decoupling.
Remark 3 (Details mmxxact-projectio using EigenPro 2.0). We apply T steps of EigenPro 2.0 for the approximate projection. This algorithm itself applies a fast preconditioned SGD to solve the problem. The algorithm needs no hyperparameters adjustment. More details in the Appendix.
We compare the order complexity of the run-time and memory requirement of Algorithm I before and after stochastic approximations with FALKON solver in Table 1.
Complexity analysis:
5 NUMERICAL EXPERIMENTS
We perform experiments on these datasets: (1) CIFAR10, Krizhevsky et al. (2009), (2) CIFARSM, Nakkiran et al. (2020), (3) ImageNet, Deng et al. (2009), (4) MNIST, LeCun (1998), (5) MNIST8M.
Loosli et al. (2007), (6) Fashion-MNIST Xiao et al. (2017), and (7) HIGGS, Baldi et al. (2014). All experiments are performed with the Laplacian kernel with a fixed bandwidth=5. In some cases, we perform a feature extraction using MobileNetv2 pretrained on the ImageNet dataset. The pre- trained model was obtained from Wightman (2019). Details on our implementation are in Appendix C. We treat K-class classification problems as & independent regression problems with targets from {0, 1)
8

---

CIFARIO (p- = 50000)
FashionMNIST (p- 60000)
MNIST (p 60000)
89
98
90
Test accuracy (5)
89
88
97
88
87
96
87
MixUp
AWGN d 0.1
AWGN o 0.1
86
random cropping-flping
86
AWGN 0
AWGN 0² 0.3
95
AWGN o²_ AWNN of
w/o augmentation
W/o angmentation
w/o sugmencation
85
85
94
25
50
75
100
25
50
75
100
0
25
50
100
Number of epochs
Figure 2: (Data augmentation.) We used the entire datasets as the model centers. We then trained the model the augmented set. For CIFAR1O dataset, we apply MixUp and Crop+Flip augmenta- tions, whereas for MNIST and FaSHionMNIST we add white gaussian noise with different variances. Performance improves by ~ 1.5% which is comparable to the gains seen by neural networks. The model without augmentation uses EigenPro 2.0 to solve the kernel regression problem on the dataset.
Large scale training: In this experiment, we want to demonstrate we can learn models with 256,000 centers and 2,000,000 training samples. We also see that increasing the number of samples on fixed model increases performance of the model. As baseline, we compare with a standard kernel machine with the same model size p (i.e., a kernel machine trained on the p centers).
We apply our Algorithm 1 to train model with p centers which are random subset of dataset with n samples. We then systematically study the performance as we vary n as well as p. Figure shows that for fixed model size adding more data improves performance significantly.
Data augmentation: Data augmentation is an important tool for enhancing the performance of deep networks. We demonstrate how this can improve performance of kernel models.
We conduct our experiment on CIFARIO with feature extraction, raw images of MNIST and Fash- ionMNIST. For CIFARIO 10 augmentation, we performed random cropping and flipping before feature extraction. Also for CIFARIO 10, we tried mix-up augmentation method in Zhang et al. (2017) after feature extraction. For MNIST and FashionMNIST augmentation we added Gaussian noise with different variances. In all cases, mented data set using the same training set. We performed 100 epochs for all of them. This means augmentation makes each data effectively 100x in size.
used the entire training set as the centers and we generated aug-
Figure shows we have significant improvements in accuracy. We show results for the Laplacian kernel with fixed bandwidth. We did not tune for the optimal bandwidth.
Flexible choice of model centers: In model, the centers 2, do not need to be subset of the training samples. More importantly, the model is agnostic to labels at these points, in contrast to Falkon Rudi et al. (2017). In this experiment we show example choice of centers that yields better performance than sub-sampling the dataset. We choose centers as the centroids from K- means clustering procedure with K p using Omer (2020).
Comparison to other works: We demonstrate, in Table 3, that existing methods center-based kernel regression for large data sets fail when number of centers are large. We compared our method with FALKON Rudi et al. (2017) and Gpytorch Gardner et al. (2018a). We used fixed 100GB RAM in all methods. For Gpytorch we tried to reproduce the version Rudi et al. (2017) used in their ex- periment, stochastic variational GPs (SVGP). We noticed they used SVGP with very small number of centers z 2000. We could not run Gpytorch with large number of centers. Also, note FALKON orginally did not have any notion of centers. They only used sub-sampling for more efficient com- putation. However, we found out that their code can also be used when centers are not a sub-set of the original data.
Herr we store the full K K(Z, , Z) matrix GPU. This is possible for larger number of centers.

---

Dataset
Model
Solver
p = 100
= 1000
p = 10000
k means
EP3.0 (ours)
36.24
45.12
52.72
CIFARIU 10 (n 50000)
random
EP3,0 (ours)
33.37 0.50
44.19 0.09
49.92 : 0.08
random
FALKON
34.16::0.36
44.44:1.114
50,40=0012
CIFARIO 10
k- means
EP3.0 (ours)
82.69
86.58
89.11
(MobileNetV2)
random
EP3.0 (ours)
74.29 1 0.44
84.38 + 0.15
86.58 1 0.06
(n 50000)
random
FALKON
74.57.10.71
84.8111.114
86.82.10.09
means
EP3.0 (ours)
91.89
95.96
97.69
MNIST
random
EP3.0 (ours)
87.24 +: 0.015
94.96 = 0.102
97.31 +: 0.004
(n 60000)
random
FALKON
88.43 + 0.604
95.39 + 0.047
97.64 + 0.080
k means
EP3.0 (ours)
78.66
$5.55
88.13
FaSSionMNIST (n 60000)
random
EP3.0 (ours)
76.24 + 0.003
84.59 + 0.069
87.84 + 0.036
random
FALKON
77.33 + 0.631
85.15 = 0.214
88.27 + 0.093
Table (Flexible model.) The separation between model and data empowers us choose model centers which better represent the underlying data distribution. We compare two model types, and two solvers. The k -e-ms model, as suggested by Que Belkin (2016), chooses centers to be k-means of the training set, whereas the random model chooses random subset to be the centers. Choosing centers as k-means improves the performance, especially when model size p is consider- ably smaller than dataset size
Model Size
FigenPro 3.0
EigenPro 3.0'
FALKON
Gpytorch
p 32K (CIFAR5M)
87.92% (727.78s )
87.93% (322.45s)
88.04% (163.59s)
(CIFARSMM
88.15% (2178.8s
88.14 % (515.94s)
87.23 (368.892s)
(2SK(CI)ARSM)
88.35% (7453.772s)
p (56K(CIFARSM) 88.46% (24386.28s)
=
88.55% (71784.236)
Table 3: (Large model size.) We preformed this experiment extracted feature of CIFARSM dataset. This shows that both Gpytorch and FALKON fail for large number of centers. Also, note that not using any tricks to optimize algorithm for best time performance. However, if we could store the whole K(Z, 2) matrix, third column, we can get a significant speed up.
6 CONCLUSION
Kernel networks, unlike kernel machines are class of kernel models decoupled from the training dataset. In this paper we presented a fast and scalable training algorithm - EigenPro 3.0 - for learning general kernel networks on large scale datasets, manner that preserves the decoupling property of the learned model, and does not require label information at the model centers.
The method relies on alternating projection operations with preconditioning, one dependent only on the training data, while the other only on the model centers. We proposed stochastic approximations that make our algorithm scalable to large datasets as well as large model sizes. The algorithm has linear space complexity in terms of the number of model centers and does not require any matrix inversion.
Through numerical experiments, provided evidence that demonstrates the promise of this algo- rithm on several datasets from across problem domains. In particular, we showed kernel models can benefit from data augmentation without increasing the model complexity. Our algorithm enables various modern machine learning techniques for training kernel methods. The next step to scale up the algorithm train large models with millions of centers and billions of samples.
10

---

REFERENCES
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1):1-9, 2014.
David S Broomhead and David Lowe. Radial basis functions, multi- variable functional interpolation and adaptive networks. Technical report, Royal Signals and Radar Establishment Malvern (United Kingdom), 1988.
Raffaello Camoriano, Tomás Angles, Alessandro Rudi, and Lorenzo Rosasco. Nytro: When sub- sampling meets early stopping. Artificial Intelligence and Statistics, pp. 1403-1411. PMIR, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew Wilson. Gpytorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018a.
Jacob Gardner, Geoff Pleiss, Ruihan Wu, Kilian Weinberger, and Andrew Wilson. Product kernel in- terpolation for scalable gaussian processes. International Conference on Artificial Intelligence and Statistics, pp. 1407-1416. PMLR, 2018b.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/ 1998.
Gaëlle Loosli, Stéphane Canu, and Léon Bottou. Training invariant support vector machines using selective sampling. Large scale kernel machines, 2, 2007.
Siyuan Ma and Mikhail Belkin. Diving into the shallows: a computational perspective on large-scale shallow learning. Advances in neural information processing systems, 30, 2017.
Siyuan Ma and Mikhail Belkin. Kernel machines that adapt to gpus for effective large batch training. Proceedings of Machine Learning and Systems, 1:360-373. 373, 2019.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern parrperraetriized learning, International Conference on Machine Learning, pp. 3325-3334, 2018.
Giacomo Meanti, Luigi Carratino, Lorenzo Rosasco, and Alessandro Rudi. Kernel methods through the roof: handling billions of points efficiently. Advances in Neural Information Processing Systems, 33:14400-14422, 2020.
Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. arXiv preprint arXiv:2010.08127, 2020.
Sehban Omer. fast_ bist_pytorch_ kmeans.
pyttrch__keaaaae kmeans, 2020.
Jooyoung Park and Irwin Sandberg. Approximation and basis-funciioon networks. Neural computation, 5(2):305-316, 1993.
Tomaso Poggio and Federico Girosi. Networks for approximation and learning. Proceedings of the IEEE, 7819):1481-1444 1491 1990.
Qichao Que and Mikhail Belkin. Back to the future: Radial basis function networks revisited. In Artificial intelligence and statistics, pp. 1375-1383. PMLR, 2016.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.

---

Lewis Fry Richardson. Ix. the approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam. Philosophical Transactions of the Royal Society of London. Series A. Containing Papers of Mathematical or Physical Character, 210/459-470;330733377 1911.
Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. Falkon: An optimal large scale kernel method. Advances neural information processing systems, 30, 2017.
Bernhard Scholkopf, Kah-Kay Sung, Christopher JC Burges, Federico Girosi, Partha Niyogi, Tomaso Poggio, and Vladimir Vapnik. Comparing support vector machines with gaussian kernels to radial basis function classifiers. IEEE transactions on Signal Processing, 1997.
Connor Shorten and Taghi M Khoshgoftaar. survey image data augmentation for deep learning. Journal of big data, 6(1):1-48, 2019.
Si Si, Cho-Jui Hsieh, and Inderjit Dhillon. Memory efficient kernel approximation. In International Conference on Machine Learning, pp. 701-709. PMLR, 2014.
Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial intelligence and statistics, pp. 567-574. PMLR, 2009.
J. Towns. Т. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. Scott, and N. Wilkins-Diehr. Xsede: Accelerating scien- tific discovery. Computing in Science & Engineering, 16(05):62-74, sep 2014. ISSN 1558-366X. doi: 10.1 10.100//SSS.2....800..
Mark van der Wilk, Vincent Dutordoir, ST John, Artem Artemev, Vincent Adam, and James Hensman. framework for interdomain and multioutput gaussian processes. arXiv preprint arXiv:2003.01 115, 2020.
Pauli Virtanen. Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Ker,, Eric Larson, C.J Carey, Ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature Methods, 272,, 2020. doi: 10.1038//41152-009--666 -19-0-......
Grace Wahba. Spline models for observational data. SIAM, 1990.
Ke Wang, Geoff Pleiss, Jacob Gardner, Stephen Tyree, Kilian Q Weinberger, and Andrew Gordon Wilson. Exact gaussian processes on million data points. Advances in Neural Information Processing Systems, 32, 2019.
Ross Wightman. Pytorch image models. ietto--iimmmmmmdeeee 1s, 2019.
Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. Advances in neural information processing systems, 13, 2000.
Andrew Wilson and Hannes Nickisch. Kernel interpolation for scalable structured gaussian pro- cesses (kiss-gp). In International conference machine learning, pp. 1775-1784. PMLR, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint
2017.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv: 1710.09412. 2017.
12


Reviews:
[{"review_id": "ljgNSsyCFn", "reviewer": "Reviewer_ner6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents EigenPro3.0, an efficient algorithm for learning large scale kernel networks. EigenPro3.0 can be seen as an extension of the EigenPro2.0 method (Ma and Belkin, 2019) to the case where the function being learning is a “kernel network” instead of a “kernel machine”; a “kernel network” is a function of the form $f(x) = \\sum_{i=1}^p a_i k(x, x_i)$, where the set of “centers” $\\\\{x_i\\\\}_{i=1}^p$ is allowed to be an arbitrary set of points in the input space X (as opposed to having to equal the training set, which is the case for “kernel machines”). Importantly, “kernel networks” decouple the size of the model from the size of the training set, which allows for efficiently applying methods like data augmentation to kernel learning.\n\nEmpirically, the paper demonstrates that:\n1. When using a fixed number of centers $p$, performance improves as the amount of training data $n$ grows larger than $p$ (thus “kernel networks” are better than “kernel machines”), and\n2. Applying data augmentation to kernel learning (while keeping the model centers equal to the unaugmented training set) leads to better performance than simply learning with the unaugmented dataset (again showing that “kernel networks” are better than “kernel machines”, as they allow applying data augmentation without increasing the model size).\n", "summary_of_the_review": "This work presents a nice extension of EigenPro2.0 to the “kernel network” setting, where kernel model size is decoupled from the training set size. While this is a very nice technical contribution, an important limitation of the paper in its current form is that it does not compare to other large-scale kernel learning methods which also decouple the model size from the training set size (e.g., Nystrom, Random Fourier Features), thus making it hard to fully evaluate this work. Thus, I lean toward rejecting this paper, and recommending it be resubmitted to a future venue once discussion and comparison with related work is provided.", "strength_and_weaknesses": "Strengths:\n- The algorithmic contribution is non-trivial: the paper presents an efficient way of performing kernel network learning with pre-conditioning. The pre-conditioning is important as it can significantly reduce the number of SGD steps necessary to learn a model (as discussed in the EigenPro and EigenPro 2.0 papers).\n- I agree with the paper that it is very important to decouple the size of a kernel model from the size of the dataset used to train it, thus allowing the model to scale to very large training sets (with efficient training/inference), and use methods like data augmentation. Adapting pre-conditioning methods to this setting is an important contribution.\n- The empirical results are relatively interesting, and demonstrate the important of the above-mentioned “decoupling”.\n\nWeaknesses:\n- It seems to me that the paper neglects to discuss (and compare with) other efficient methods for kernel learning which decouple the model from the training set. For example, the Nystrom method (Williams & Seegar, 2001) can be used with arbitrary model centers from the input space; Zhang and Kwok (2010) showed that using k-means on the training set is an effective way of choosing the model centers for Nystrom. As another example, random Fourier features (Rahimi and Recht, 2007) also decouple the model from the training set, making it trivial to use methods like data augmentation together with large-scale kernel learning. While it is still possible that EigenPro3.0 is in many ways better (e.g., more efficient training, more compact models, better generalization, etc.) than these existing methods, these comparisons have not been explored at all, and thus the various trade-offs between these methods are not currently understood.\n- The paper is often quite hard to follow. It could be beneficial to move most of the math related to functional spaces and Frechet derivatives to the appendix, and focus on the finite dimensional optimization problems instead. It could also be beneficial to describe EigenPro2.0 in more detail, especially because it is directly invoked from the EigenPro3.0 algorithm (line 8 of Algorithm 1). Simplifying the mathematical presentation as much as possible would be valuable (I’m aware this is non-trivial, given the complexity of the method, but I still think the presentation could be significantly improved).\n- Currently, no theoretical results are provided about EigenPro3.0. Can the convergence/generalization properties of this algorithm be analyzed?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bkqJ1kfovlQ", "reviewer": "Reviewer_nu3W", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The author(s) proposed an preconditioned gradient descent algorithm for kernel networks. The algorithm is built on EigenPro 2.0. Experiments on real-world datasets are conducted to evaluate the proposed EigenPro 3.0.", "summary_of_the_review": "Overall the paper is well-written and seems to be a descent contribution to the training of kernel networks. Related work is not well-addressed. I will raise my score if the author(s) can address the questions I raised and add more about discussion about related works.", "strength_and_weaknesses": "Strengths:\n- The paper is well-written and well-motivated;\n- The analysis is quite thorough and easy to follow.\n\nWeakness:\n- My major concern is that related works are not well-addressed. I think it is better to inlcude an \"related work\" section. I am not an experts in kernel machine, but I think there should be a lot of related work on kernal networks (Nyström approximate kernel networks). For example, see [1] and the references therein.\n\nSome questions:\n- There is not comparison on convergence speed betwen EigenPro 3.0 and other baseline methods? Is there a particular reason not to include this experiment?\n- I am not very clear about the technical novelty of this paper compared to EigenPro 2.0 and EigenPro 1.0. It seems that EigenPro 3.0 uses similar technique as previous works (preconditioned gradient descent), the only difference is that the problem is kernel networks instead of the kernel machine. Is there any particular technical challenges of applying preconditioned gradient descent to kernel networks? Can the author(s) explain the technical contribution compared with EigenPro 2.0 and 1.0?\n\n[1] Memory Efficient Kernel Approximation, Si et al. JMLR 2017.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WLqbkYnO-J", "reviewer": "Reviewer_qfN8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies how to scale up the training/inference of kernel network. It uses data center to reduce the memory and inference cost. It proposes to use inexact stochastic approximation to approximate functional gradient and the preconditioner. Such stochastic gradient allows us to use data augmentation during the training that improves the performance.", "summary_of_the_review": "The work is clearly presented. However, I have some major concerns over its novelty. ", "strength_and_weaknesses": "Strength:\nIt seems impressive to make kernel network work on datasets such as Cifar and Imagenet.\n\nI have several concerns of this paper:\n\n1. Novelty:\nThe novelty of the contribution seems quite limited. The idea of using data center instead of the whole training data in kernel network is not new. The main contribution seems using a stochastic gradient for training, however such approach is very standard and has quite limited novelty. I also believe such inexact approximation should have nice convergence property compared with the exact version since the approximation is unbiased (if the subset of preconditioner and functional gradient is chosen independently)?\n\n2. What’s the advantage of kernel network in practice?\nAll the experiments used in this paper is typical benchmark used to evaluate deep learning model. And the reported performance is much weaker than neural network. I believe it would be nice to work on dataset that kernel network has its unique advantage over neural network rather than the dataset the deep learning model is so much stronger than other model. This helps to justify the necessity of studying the kernel network.\n\nQuestion:\nHow do you select the center Z? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TK1Z0AmlBN", "reviewer": "Reviewer_fRby", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is more related to kernel methods rather than neural networks. This paper presented a preconditioned SGD methods based on alternating projections (data centers) for solving kernel (ridge) regression. And the authors further devise Nystr\\\"om based algorithm to reduce the required examples.", "summary_of_the_review": "The paper has some merits, but overall, I think the contribution of this paper is limited based on the following reasons: 1) the novelty of algorithms are limited. This paper modified EigenPro 2.0 with projection gradient descent. 2) The work requires more discussion on the importance of data centers (subspace) and how to choose them. 3)This paper lacks essential convergence analysis and generalization guarantees. ", "strength_and_weaknesses": "Strength:\n1. This paper considers the generated subspace instead of the original space and projection gradient methods to solve kernel regression based on data centers.\n2. Iterative SGD methods are independent on the number of training examples. (same to EigenPro 2.0)\n3. Preconditioning can reduce the iterative complexity. (same to EigenPro 2.0)\n4. Nystroem methods further reduce the computation complexity per iteration. (same to EigenPro 2.0)\n\nWeakness:\n1. The title is rather confused, which is more related to conventional kernel methods rather than kernel networks. In my understanding, kernel networks usually stack kernels or random features.\n2. The contribution of this paper is obscure. Some claimed contributions belong to prior work. It should clearly point between this work the the prior work.\n3. In my opinion, the main contribution of this work lies in the incorporation between EigenPro 2.0 and projection gradient methods. However, this work doesn't emphasize the necessity of projection to the subspace and how to define the subspace.\n4. Data centers or the subspace are rather import to this work, but it fails to introduce the difference between them to Nystroem centers and the sampling methods. If the data centers are sampled with data-dependent strategy, the sampling complexity is usually high, for example leverage score sampling. If the data centers are sampled uniformly, what's the benefits from data centers?\n5. This work lacks the convergence analysis. Specifically, the convergence rate of preconditioning projection gradient methods, which is important to the overall computational complexity of the proposed algorithms.\n6. This paper lacks generalization guarantees. As we known, the generalization error bounds of kernel ridge regression (KRR) have been well established. It have proven the minimax optimal rates for KRR. Since this work solves KRR with preconditioning SGD, it should also provide generalization guarantees. For example, the authors should analyze the generalization impacts from the number of data centers and the iteration number.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject