Two-layer neural network on infinite dimensional data:  global optimization guarantee in the mean-field regime
Authors: Naoki Nishikawa
Taiji Suzuki
Atsushi Nitanda
Denny Wu
Venue: NeurIPS 2022 Accept (2022)
Keywords: mean-field regime
neural network
optimization
functional data analysis

Abstract: Analysis of neural network optimization in the mean-field regime is important as the setting allows for feature learning. Existing theory has been developed mainly for neural networks in finite dimensions, i.e., each neuron has a finite-dimensional parameter. However, the setting of infinite-dimensional input naturally arises in machine learning problems such as nonparametric functional data analysis and graph classification. In this paper, we develop a new mean-field analysis of two-layer neural network in an infinite-dimensional parameter space. We first give a generalization error bound, which shows that the regularized empirical risk minimizer properly generalizes when the data size is sufficiently large, despite the neurons being infinite-dimensional. Next, we present two gradient-based optimization algorithms for infinite-dimensional mean-field networks, by extending the recently developed particle optimization framework to the infinite-dimensional setting. We show that the proposed algorithms converge to the (regularized) global optimal solution, and moreover, their rates of convergence are of polynomial order in the online setting and exponential order in the finite sample setting, respectively. To our knowledge this is the first quantitative global optimization guarantee of neural network on infinite-dimensional input and in the presence of feature learning. 

Two-layer neural network on infinite-dimensional data: global optimization guarantee in the mean-field regime
Naoki Nishikawa
Taiji Suzuki University of Tokyo RIKEN AIP
University of Tokyo
nishikawa-nakki22550 u-tokyo. ac.
tai feajiimist..m wu-.okyo..oa ac
Atsushi Nitanda
Denny Wu University Toronto
Kyushu Institute of Technology
RIKEN AIP
Vector Institute
nitanda@ai
kyutech. .itanda@ai.kyutechh.
ac.
dennyuuccs. wwwnayuuuccs..ootooooo. www.ttooooooooo
edu
Abstract
Analysis of neural network optimization the mean-field regime is important as the setting allows for feature learning. Existing theory has been developed mainly for neural networks in finite dimensions, i.c., each neuron has a mnite-dimensional parameter. However, the setting of infinit-diimensional input naturally arises in ma- chine learning problems such as nonparametric functional data analysis and graph classification. In this paper, develop neural network in an infinite-dimensionee parameter space. We first give gener- alization error bound, which shows that the regularized empirical risk minimizer properly generalizes when the data size is sufficiently large, despite the neurons being difiite-dimmnsiinall Next, we present two gradient-based optimization algorithms for Piinite-dimensionns mean-field networks, by extending the recently developed particle optimization framework to the show that the proposed algorithms converge to the (regularized) global optimal solution, and moreover, their rates of convergence are of polynomial order in the online setting and exponential order in the finite sample setting, respectively. To our knowledge this is the first quantitative global optimization guarantee of neural network on infiniteddmmnsson dimensional input and in the presence of feature learning.
mean-field analysis of two-layer
setting. We
1 Introduction
A variety of machine learning problems need to handle input from infiniteddimensional spaces. For instance, [iing and Vieu (2018): Ferraty al. (2007) studied non-parametric function regression problems where the input is function in infinite-dimnniin (2020) studied graph classification problems using kernel method, which can cast as a learning problem with inputs from infinie-dimensionn reproducing kernel Hilbert space.
functional space, and Kricge et al.
Among various models that deal with those infinite- dimensiaa input problems, neural networks are particularly interesting due to their ability to learn features and model nonlinear data. For example, Rossi and Conan -ueez (2005) proposed the Functional Multi-Lav Layti-Layer Perceptron, where the input of functional data is converted to vector form by basis expansion and then fed into neural network: the universal approximation and statistical consistency of the proposed model were also analyzed. Recently, Yao et al. (202T) proposed the Adaptive Functional Neural Network, which replaces the fixed basis functions in Rossi and Conan- Guez (2005) with adaptive bases, order to leverage the power of representation (feature) learning and the flexibility of deep learning. While neural
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

network based models with optimization using gradient-bai based methods is not well-understood. In particular, no optimization guarantee has been shown for any algorithm in the presence of feature learning such theoretical result can be challenging to establish even for finite-dimensiona data.
input have been applied in many applications, their
It is experimentally observed that the gradient-based optimization methods can yield sufficiently small training error in training neural network models, despite the non-convexity of the landscape. Theoretical explanations of this observation often rely on overparametterization. that is, to consider sufficiently wide neural network compared with the data size, and the model parameterization can be divided into the mean-field regime (Nitanda and Suzuki, 2017 Mei et al., 2018 Chizat and Bach 2018) and the neural tangent kernel regime (Jacot et al. [0118] Du al. 2218). In this work we focus on the mean- field regime, as it captures the presence of feature learning, which is one of the main advantages of neural network (Chizat et al. 2019 Yang and Hu 202T).
In the mean-field analysis, the dynamics of gradient descent is described by Wasserstein gradient flow in the space of probability distributions on the parameters. Mei et al. (2018) showed that the mean-field Langevin dynamics converges to the global optimal solution, and Hu et al. (2019) proved linear convergence with respect to the objective function with sufficiently strong KL divergence regularization. However, those studies mainly analyzed the algorithm in continuous time, and do not establish quantitative convergence rate for discrete time and finite width settings.
To overcome this limitation, Nitanda et al. (202T) proposed the Particle Dual Averaging (PDA)
method that globally optimizes the KI.-regularized objective with polynomial order computational complexity, in a completely discrete time and finite width setting. Furthermore, in the case of finite- sum objective, Oko et al. (2022) proposed the Particle Stochastic Dual Coordinate Ascent (P-SDCA) method which further improves the computational complexity to an exponential order with respect to its outer loop iteration. Both PDA and P-SDCA employ a double-loop structure, and make use of Monte Carlo sampling from an intermediate target distribution in the inner loop. In particular, Nitanda al. (202T) applied the convergence rate of the overdamped Langevin algorithm in Vempala and Wibisono (2019) for their optimization analysis, whereas Oko et al. (2022) also considered the Metropolis- adjjustd Langevin algorithm (MALA) (Ma et al., (2019) for the inner loop sampling. However, if we naively apply these algorithms to infinite-dimen dimensional input, then the optimization guarantee becomes meaningless due the dimension dependence. Therefore, we need to construct a new methodology and theory for the infinite-dimensional problem.
Our contributions. In this work, we extend the mean-field analysis for neural network train- ing to infiniteddimensional parameter space, which covers two-layer neural network with infinite- dimensional inputs. First, we establish a generalization error bound which entails that our model generalizes properly when the number of training data is sufficiently large. Next, we propose two gradient-based algorithms that globally optimize the KL-regularized objective, corresponding to the infinitediimensional extension of PDA and P-SDCA, respectively.
As mentioned above, PDA and P-SDCA require Monte Carlo sampling, and in our setting sampling is performed in an -nfinitediimensional Hilbert space. We therefore adapt an nnfintte-iimensionlll (Bréhier,201e the weak convergence of which has been established in Muzellec et al. (2022). Our contributions can be summarized as follows:
gradient Langevin dynamics (Debussche)
We introduce two-layer neural network in the mean-field regime whose input is anfiite-dimensional and establish generalization error bound of the regularized empirical risk minimizer.
We propose two optimization algorithms for our infnite-dimenssoonal neural network by incorporat- ing the infnite-dimensionall Langevin dynamics in the inner loop of PDA and P-SDCA
We prove that our nimenseadimensionall extension of PDA achieves polynomial order convergence, and that of P-SDCA achieves exponential (outer loop) convergence even in an ddinite-dimensional " To the best of our knowledge, this the first quantitative global optimization guarantee of neural network in the infinite-dimensional mean-field regime with the presence of feature learning.
Other related works. Ferré and Villa (2066) proposed the SIR-NNr, which incorporates the dimension reduction method termed "sliced inverse regression" into neural network. In addition,
We however note that there is an exponential dependency on the regularization parameter, similar to prior works on Langevin- based algorithms.
2

---

Rossi et al. 2005) introduced a radial-basis function network as nonlinear model whose input is function. As previously discussed, although statistical properties (e.g. consistency) of these models have been studied, convergence guarantee of gradient-based optimization has not been established.
2 Two-layer neural network with infinite-dimennsinalll input
In this section we introduce the mean-field two-layer neural network with infinite- dimneesoiaa input. We first formulate mathematical notations and prepare assumptions required for our theoretical analyses, and then present a generalization error of the proposed model.
Neural network model. We consider setting where the input is included in (possibly infinite- dimensional) separable Hilbert space H. Since separable, there is complete orthonomal system
(e))_= for which it holds that H. { Li= Ajej Σj=o a3 00 and H is equipped with the inner product given by (f.9) 2 == =i= رnbs, where f = Ej= 00 Ho be a subset of H defined by Ho := {0- ep + - neural network model that takes an infinitediimensional input x E X C Ho and gives an output E y S IR, where X' and Y' are domains of input and output, respectively. Each neuron in the network has parameter == aeo + w E H for a E R and w E Ho. and is represented by
Czej- Σド= byez E H. Let Σj=1 az < oo). We consider a
ho(x) == (1
where 01 02: IR IR are activation functions, which assume be bounded and smooth (such as tanh) We also denote ha (x) by h(0,z) x). Let the number of neurons be M and denote the set of parameters by O- (0.) (0-) Then, in the mean-field regime, the two layer neural network model (with
input) can be expressed as the average over the M neurons:
ho(x)
he, (z).
M
This can be seen finite sum approximation of the integral form Bhox(ho(xr)) for distribution on the parameter space. Indeed, if (M) are i.i.d. realizations from æ, then he (z) would converge to the integral form M increases. This viewpoint motivates us to design optimization algorithms for the distribution of parameters and utilize the convexity of the objective in the space of measures.
Notations. To introduce method, we need to define Gaussian process taking its value in H. For that purpose, we define a subspace HK- C H for y 2 0 as follows. First, we define a linear operator Tw: H -> H as Tx =iz= Myajez for = Žドー azej, where (14) corresponds to the spectrum of Tk satisfying p. > 0 (Vj) and is sorted decreasing order (P1 2 μ2 2 ..... Note that the orthonormal system (e,) is taken so that it coincides with the eigen- digen-function of
Tk. Then, we detine HK* T H [T h E H. and
naturally equip HKT with norm || == -E 12 ag for f Σş= agez E HK. For concise notation we simply write HK == HxT Next, define an operator A = Ax for positive regularization parameter A > 0, azez
i.e., Aʃ = Aι Σj=o 10j Lajee, for f Ei= azez E HK. and let v be Gaussian measure in H whose mean is and its covariance is A (i.e., (2, (z (z~~)) v) obeys the Gaussian distribution with mean 0 and covariance (x,, A A-xx)n for any x E HHS Finally, we define the Kullback-Leibler (KL) divergence from a probability measure 22 probability measure 1/1 that is absolutely continuous with respect to 122 as KL(vil(e2) == Ey, log du dog
Eug
de deg
log
dei dug
Objective. Now we define the objective of our optimization method. Suppose that the pairs of input and output are independently identically distributed from D. and let E(.,-) V ) + R be a loss function. In the mean-fiell regime, we optimize the following regularized risk minimization problem with respect to the distribution of parameters where the regularization term is given by the KL-divergence from the Gaussian measure V/:
min PEP2
[(T) == Exx,)~= [e (ho + (T(L()
We focus on this model parameterization for better interpretabiliity although our mean-field analysis covers more general models. For precise definition of Gaussian measure in
Hilbert space see Da Prato and Zabczyk 1996
3

---

where A2 > 0 and P2 is the entire set of probability measures that satisfy Eg [ < co and are absolutely continuous with respect to the Gaussian measure v. We may consider the empirical measure of n training data points (x:;; Mi Di)==1 as D, for which the first term of the objective function is written as 1 >i=1 E (Eg=a [ [1] v.). In this setting, the problem can be regarded as a regularized empirical risk minimization problem. As for the second term, in a finiteddimensional setting where A I, we can easily see that the KL divergence is decomposed into the sum of l² (f-reulaarizaton A, [[0][]] and negative entropy Eg~= (log dr (0) /dd Here the negative entropy naturally arises from the mean-field Langevin dynamics (Hu et al.) 2019 Nitanda et al.) [ 2022). Indeed, it known that, we optimize a loss function L(g) with respect to a probability distribution q E P2 by the mean-field Langevin dynamics with temperature parameter X2. then its stationary distribution is given by q" = arg mingssensity
[.q) + >2 [lo[(]] which satisfies oLig"), ). where oL1g) H + R is the derivative with respect to the distribution q such bg
9" X exp( X2 o9
that ʃ (L(n) 5q
(O)d(p- ()) lim ! (epp + (1 c)q) L()] for any distribution p E P2-
One important example that we can apply our model to is the paraamenttiii functional regression problem (Ling and Vieu 2018 Ferraty et al. 2007). Suppose that the input æ is a function on R (such as time evolution of temperature) included in some reproducing kernel Hilbert space Hx. One typical definition of Hx is given by Hk = / where H I.2 for a probability measure jr (s) for a positive definite kernel K (Caponnetto and De Vito 2007 Steinwart and Christmann, 2008). The goal is to estimate some non-linear functional from the input Hæ output y (using neural network (T).
and TK is an integral operator given by f() := s(,,,) f (d)))
Generalization bound. We now give generalization error bound for our two-layer neural network in the empirical risk minimization setting, which confirms that the model properly generalizes when the data size is sufficiently large. Specially, we show the generalization bound for two problem settings: binary classification and regression. The following theorem stats the generalization bound for binary classification problems. We defer the regression case to Appendix A due to space limitation.
Theorem 1. Let D be distribution of X x y. É be the smoothed hinge loss, and denote the 0-1 loss by foı (z, v). i.e., (Z, y) == [zy < Oj. Let n. be the optimal solution of the empirical risk minimization problem ②2 for a given set S of n training data points (i.i.d. from D). Suppose there exists a distribution To E P2 such that (x)y 2 1/2 for all (z. y) E suppD, and that [z)] S 1 holds for all A E H. E X. Then, the following holds with probability 1 with respect to the choice of S C X:
KL(T V)
1 log
E(x,y) (hr,. (X), S 12KL(= + 8/22
5V
n
2n
8
The KL-term is bounded when TO is a variation of the Gaussian measure V such that d= log( du
dr is
de integrable with respect to v. Note that if we set A = 1/vVi, the generalization error is ( /n).
This order matches that in the finite-dimensional input setting shown in Nitanda et al. (2021)
3 Mean-field optimization with infiite-ddimenionna Langevin algorithm
As previously remarked, the core idea of the mean-field analysis is to directly optimize the distribution of the parameters (2). For that purpose, the ideal situation would be maintain infinitely many particles (neurons) to represent the distribution; however, in a tractable algorithm we need to use an approximation with finite number of particles. This dinite-particle approximation may lead to instability due to the interaction between particles, which is known to be difficult to control.
To overcome this difficulty, we employ the linearization technique that was used in the original PDA and P-SDCA algorithms (Nitanda et al., 2021; Oko et al., (022).. We provide short summary of this idea: given the t-th step solution Te. we apply first-orde approximation of the loss function ((T) := E( [6 (Eewa [he (X), Y) as (π n.) (L.))) := - (L(m)) (0)d(x (O)) (8). Then, T++1 updated as the minimizer of the linearized loss objective: argmin,
8x
6L(s)) + (TII). T,) b=
which can be written d exp( - <L(m))) dv. Hence we just need to draw particles from T-- in the inner loop. Importantly, the interaction between particles disappear due to the linearization and we may sample in an i.i.d. manner. The original algorithms of PDA and P-SDCA for (finite- dimensional input) employed the gradient Langevin dynamics (GLD) and its variant such MALA,

---

input is non-trivial, and to gradient Langevin the convergence rate of which have been extensively studied (Raginsky et al., 2017; Vempala and Wibisono 2019 Ma et al., 2019). However, in our setting we need to solve an sampling problem, which cannot be directly extended from the finiteddimensional counterpart.
Let be a distribution on that satisfies da (x) & exp (=)) (e.g,, = ( Then we know is the stationary distribution of the infinite-dimennionaal stochastic differential equation,
de
dX, (V) + AX,) dt + v2dW,,
where (Wo) is a cylindrical Brownian motion on H (Da Prato et al. 1996 and VG the Riesz representer of the Fréchet derivative of G on H. To discretize the continuous-time SDE, employ the semi-implicit Euler scheme:
X = X (VG(X.) + 4X + 22
i.e, X = S, (XA V)C)))) + v2n/(a) where ÇE is realization of standard Gaussian process on H. and S, := (Id + nA)- where Id is an identity mapping. We remark that our choice of semi- implicit scheme is due the fact that Ç& H in the infinit-dimensiional setting, and thus the naive Suler-Maruyant discretization does not ensure X E H while the semi-implict scheme does.
In practice, need approximate the infinite- dimensional vector X by dimtee-aimesional one. For that purpose, we apply the Galerkin approximation. Let PN be the orthogonal projection from H HN = span(eo: .... EN ), and vG (xx PN (VGaaN))) Then the fiitt-ddimensional approximation of the semi-implicit Fuler scheme is given as
x S. [ -V + (2nPN(x)
(3)
A convergence rate analysis of the rnfinie-dimensiione gradient Langevin dynamics (3) with time discretization and inite-dimensional approximation was given by Muzellec et al. (2022). ). which an important ingredient of our convergence rate analysis (the details can be found in Appendix B
4 Infniiteddimensional Particle Dual Averaging
In this section, we present our first algorithm to solve the risk minimization problem (2] which an infinite-dimensionee extension of the Particle Dual Averaging (PDA) method Nitanda al. (202I). PDA is a combination of Nesterov's s dual averaging (Nesterov) 2009) and particle sampling; it is guaranteed to converge globally at a sublinear rate, but is tailored to the finite-diment nitee-dimensional setting. Extending the algorithm and convergence analysis to do so make of the weak convergence property of the
dynamics (GLD) shown in Muzellec et al. (202)).
Algorithm description of infinite-dimensional PDA. Here provide the algorithm description of PDA with employ online gradient descent approach: we draw 1-th iteration, and update the parameter by replacing the expected loss with a single-sample loss l (EE (ho(x)), ye). In addition, we apply the following linearization to the loss at each outer loop
input. Since we are optimizing the expected loss directly, we
input-output pair (Ia, Be) from 'D the
step: suppose that we have M particles ((t) = ( M= whose empirical measure is denoted by (1) 37 Em 1ew (i.e., hoge Bo (+)( Then the loss can be linearized around (t)
(π - (()) 8e (EE~ (ho(2)) Wc)
Eaax (0.8 (E [M(0, x.. v1) 1(0,, xx)) + const.
+1)))))
We denote the gradient component in the right hand side as g (0) = d thgre (z) ye (0,, xx). The idea of the Nesterov's dual averaging method is to take its weighted sum of the gradient over its history: (i) := xa((+21(t11 E'_ (H), and update the distribution as
π (++1) = argmin Ea- [ (0) + (T
As we have seen above, the Radon-Nykodym deriatives of n. ((+1) with respect is given by dr((++1) de (0) exp (0). Hence in the inner loop, sample particles from n. (t+1) using
5

---

anfiite-dimenseee gradient Langevin dynamics (3) by setting G = g= (0). That is, we obtain the M M-particle approximation by iteratively calculating the following updates:
1 = S.. (0%)) 71 V
(0) (o 2 PN(S),
where Sy (Id nA)- and VgN (-) PN (P )) We repeat the GLD iterations for T3 times in the inner loop and obtain the set of particles (0th ) (0 ( for the next outer loop update. We denote by (0) the distribution of each particle ((2))
N.m (this is not the empirical
distribution 1 but its "true" distribution). We will show that (0) well approximates the ideal update I ((+1)(() (0) in the proof of Theorem below.
Finally, after T outer loop iterations, the algorithm outputs M parameters 0(0) ......0 0 where 8 E 22...,,++11 is randomly chosen according to distribution P(t) = T(T+3) (t 2.... T++)
The full algorithm is summarized in Appendix C
Convergence Analysis. Now establish the global convergence rate of proposed infinite- dimensional PDA. Let Px be the distribution of input x E X and 9 == suppPx. Our analyses rely on the following assumptions.
Assumption 2.
(AI) ph ,.. i.e. there exists constant 01,, 02 such that a k2 us 02-
(A2) y C [].. In addition, ((2,y) is 1-smooth convex function with respect to z. Moreover, for all y, V. (0_6(2, 3)1 holds.
(A3) Both an and 02 are thrice continuously differentiable. Moreover, it holds that max |loi 1 ooo ||02|ooo, |1o221 sos [ S b.
(A4) There exists 1 < < 2, Bx > such that || < Bx for all x E
Remark. (Al) a sufficient condition to guarantee convergence of gradient Langevin dynamics Muzellec al. 2022). in which the exponent k-2 may be generalized to k (p 1). but present the result only for and logistic loss. (A3) is satisfied by several practical activation functions such as sigmoid and tanh. Finally, (A4) is a regularity condition that is used in the convergence guneeggguo guarantee of GLD.
for simplicity. (A2) is satisfied by common loss functions such as square loss
We show the convergence of ciinite-dimmnsionaa PDA by the following two steps: (i) bounding the difference between the optimal solution Topt of the objective (2 and the optimal update n: at the i-th iteration (Theorem 4), (ii) bounding the difference between the optimum auxiliary solution T. (i) and its particle approximation (() (Theorem 5)
To begin with let
(t) e be the weak convergence error of sampling in terms of the network output, i.e.,
E ( [h(0, x]] - E (o [h(0.x))]
sup ZEG
This error can be bounded by the following theorem, proof of which can be found in Appendix C.
Theorem 3. Under assumptions (A4), for all t = I,...,T and E (0, 1/2), there exists Õr = 0 0 (1++)1)) exp (O (25"))). Ó₂ =
=
Ω (min(>1, X1 222 } exp (-0(2=1))) such that the following holds
12 82 $2
( cxp
(-A (M T - +C2 1/2-a ne m2/2-m))
Theorem establishes the convergence rate sampling via infinite-dimensional GLD in the PDA algorithm. According to this theorem, to achieve sufficiently small sampling error CA c, it suffices to take nN = O(e2/(1 ((e2/(122*), 7)t ((2/(1-2x) T, D(E
1666-1z - (A)()) with some
(0, 1/2). This result is comparable the finiteddimensional counterpart in Nitanda et al. 2021

---

where 7 = ((2)) and T, = loge=oool//////e log(1/c)/A) is shown to be sufficient, which is close to our bound up to factor of k despite the infinite dimensionality. It is worth noting that the dimes-dimensional analysis in Nitanda et al. (2021) is based on the convergence result of GLD under KI. KI--divegeecee (Vempala and Wihisono| 2019). However, in our infniiteddimensional setting, we generally do not expect convergence under the KI. metric since the distribution is hardly absolutely continuous with respect to another. Instead, our convergence guarantee is solely based on a weak convergence analysis, which allows to establish computational complexity bound that is close to that of the finiteddimensional counterpart in Nitanda et al. 2021
As for (i), the following theorem evaluates the difference between T. and x. with respect to the objective function value. The proof of this theorem can be found in Appendix C.2
Theorem 4. Suppose 8 > O and let e == ा(े43) E (0) Under (AI). (A2), (A3). for all distributions Tu E P2, the following inequality holds with probability d:
2 T(T +
T+1
Σ Et (((()=9)- ((T.)) 50 +V
log (7) M
1+ 1+ (.EETl19") 10 22 (L( (1) X2
T
T
This theorem shows that when the number of outer iteration T is larger than O(1/e), the excess objective function value of the auxiliary solution =!! becomes smaller than e. It known that this O(1/T) rate is the minimax optimal for online first-order methods when the objective is strongly convex (Agarwal et al., 2009). We note that the analysis in the original PDA algorithm (Nitanda et al.. 2021) heavily relies on the existence of probability density function of the parameters; however, this is not guaranteed in the infinite-dimensional setting. We overcame this difficulty by reformulating the update using the Radon-Nikodym density with respect to the Gaussian measure v. Interestingly, this new technique yields a refined analysis that is indeed dimension independent.
Next we control the particle discretization error (ii). i.... the difference between the auxiliary solution and its particle approximation. The proof can be found in Appendix [C3
Theorem 5. Under (AI), (A2), (A3), (A4), the following inequality holds with probability 1 - 8:
Bx Bx Bx + V Vlog (t+
M Σ h(0(9) , 00 1
=0(00
sup xe9
0~ [1(0, x]
VM
In particular, we have [L L(A ((#)0)) 0 + MMx Bx + v log (f))
Notice that since the particle approximation does not have a density, the bound above does not control the objective & including the KL-regularization, but instead the -orm error and the loss function L of the estimated function. By combining the previous theorems, we know that when the number of outer loops iterations O(1/e), and the number of particles M is ((L/e)² log(1/e)). then our proposed algorithm achieves e-crror in terms of the output of the model (or the loss function) from a solution with e-excess objective value.
Overall, the iteration complexity of our infinite-dimensionn PDA to obtain c-accurate solution is ((1/(Ae 7=3 log(L/e)) for some E (0, 1/2), i.c., it is possible to obtain a solution with the desired accuracy at polynomial order of iteration complexity (but with exponential dependency on 1 1/22, which would be unavoidable for any mean-field method). We emphasize that our analysis guarantees the convergence to the global optimal solution, not the stationary point or local minimizer.
5 Infnite-dimensionall Particle Stochastic Dual Coordinate Ascent
In the previous section, we considered the expected risk minimization problem. On the other hand, in the case of empirical risk minimization, we can improve the rate of convergence from polynomial to exponential by making use of the finite-sum property. For that purpose, we propose an infinite- dimensional extension of Particle Stochastic Dual Coordinate Ascent (P-SDCA) proposed in Oko al.) (2022). As in PDA, the original P-SDCA is also tailored to the finieeddimensional setting. parameter space necessitates
Especially, the lack of density function in the infinite-dimension careful modification of the update rule. Indeed, we reconstruct the algorithm based on the density with respect to the Gaussian measure v.
We also believe that the required I; in Nitanda et al. 2021 can be improved to O(c log(1/c)/A).
7

---

Algorithm description of diiinitediimessionall P-SDCA. Here we give an algorithmic description of our anfinitedimmnsinn extension of P-SDCA. The main ingredient of SDCA is to execute optimization in the Fenchel dual of the objective function that is derived in the following lemma.
Lemma 6. Suppose that e(. 9i) : R + R is a proper convex function and h(- x,, H - R is
bounded for i = ,...,, We denote the conjugate function of El., Ui) by E (,, Vi objective D RR. + as
Define the dual
D(g)= = Di=1 C" (gi. Vi)
X2 log (Eo cxp (-
1 Ei=1 geh m.)
(g E R").
nd2
Then, iinfzep, ((T) > -o holds, it holds that inf, L(T)) = SuPEER D(g)-
We construct the update rule based on this duality theorem. For dual variable g R", the exp( mxž Ei 9ch(0,az)) (indeed, corresponding primal solution can be retrieved by p(n](0)= B. [exp( maz Σi= 2ch(9.2.))
for the dual optimal solution 9" the primal optimal solution can be recovered by plg"(dv) In the SDCA algorithm, we randomly pick up one coordinate i, E [n]] from the uniform distribution, and update the corresponding coordinate so that it maximizes the dual objective. Suppose that we have the dual solution g(t) at the f-th iteration, then we update its i--th coordinate by the following formula where is E [n|] is chosen uniformly at random:
((+1)_ argmax si, {
E- (ghe U..) + E. x.) -l)) 100) (sl. -..i)
(xi, - (0) 2nd2
}
Pi.
9j 9j (t) for j it-
(t+1)
We can see that the update formula requires the expectation E, [h(0, x,.) ((0). We ap- proximate this expectation by weighted average of M particles as E, [1(00, mi.) ((0) w EM r ((01k(0m.R..) where I' is the weight of the m-th particle. Here, the particles (0m) MM are "refreshed" once in every ñ iterations, and in the remaining iterations, we only update the weightings of the particles (rm )M 1- In particular: (i) at the resampling steps (once in every ń iterations), we run the dimensiodii GLD generate M particles (fm) from the distribution n!!") that is given
(t)
ΣM ri
by dx(*)
di = (). and reset the weights as I'm 1/M for all m E [M]; (ii) in non-refirshingg steps, hi, (f. (em (++1) -0()) [[0)
we update the weights (rm M as T'm Tm exp
This re-weighting scheme allows us to reduce the number of sampling steps, which can be compurationally demanding.
(1)
Convergence analysis. Now we establish the convergence rate of the proposed infiniteddimensional P-SDCA. Suppose at the T-th sampling stage, we run the GLD with step size 7r for Jr iterations.
Then the sampling error can be bounded as follows: denote by p(8T) the distribution of the particles, under (A (A)) for all (0, 1/2), it holds that
Banntrr [6(0)]
(
<c,e -1
1/2-x OI JT- +C2 (NN+1 + 1
=
(AT)
where Č₁ C2 A are constants depending on 6, X1 A2 and Φ H + R is any test function satisfying |1 < 1 with sufficient smoothness (see Appendix D.3 for more details). Using the sampling error (AT) we can derive the iteration complexity of the algorithm.
and Theorem 7. Assume (A1) and [E(x, v:) - inf, ((x',2)) S Bi for all x E 1- bj
i E [n]. Let á = I-n and take any Teud 2 2 (1+11X))) log (n+ xx
1)
Bi B1+22i-mp
cp
for EP > 0. Suppose that EC (ir)) and M satisfy Ec (AT) Ci exp
A(22)x++1) (-#f) (VT E (Tend])
and M.
03 log (niifond) where Ö O X₂ It
C₂ exp
and O2
ndat1
(8max((P (12.8*)m)
P-SDCA, the duality gap can be bounded as E [[(plg((Tom))) - (TT()))) {] S for a higb--bro event E such that P(E)= 2 1 1-5. 8.
exp
Then, after üTend iterations of infiniteddimnniinn
'The convex conjugate of convex function f R -> P is given by f*(u) supsen f(x))
8

---

The detailed statement and proof of Theorem can be found in Appendix D.4 Here, the expectation taken over the choice of the coordinates in each step and the event & corresponds to measure concen- tration induced by the M-particle sampling. Consequently, P-SDCA can achieve a duality gap smaller than Ep with ( (()r) outer loop iterations. In combination with the sampling complexity, we see that the total iteration cost to obtain solution with ep duality gap is (((1/p)) log(1/ep)),
which is much better than that of PDA shown in Section 4
Numerical Experiments
We numerical evaluate our proposed methods non-linear functional regression problem. Let H be L [[0. 1)), which is a set of square integrable functions defined on [0. 1], and HK be the Sobolev space H ( 1),, which is a set of absolutely continuous functions defined on [0. 1] satisfying (0) = 0 and u' E (10, 1]). Then, H. is a Hilbert space equipped with inner product defined by
(xI, So (z) (t)dt, and Hx is Hilbert space equipped with inner product defined by (I1, 222 Hx = Jo o (1)))(()) Consequently, HK is reproducing kernel Hilbert space whose kernel function is given as ((s,t) t) = t).
We consider a teacher-student setup. The data is generated as y, = 8 (a (ōz(w( .x:)))) + C (i = ........)) n1) where e; ~ N(0, 1) and (.) = =ā2(.) = sign(.). The true parameters (a w)) E H are generated by a" ~ 5%) and wº = =E== w(ee, ej. where w() (0, We randomly generate H; from Gaussian process whose covariance operator is kernel function of Hgs, and accept when it holds that | < Bx with some Bx. In our implementation, we only used N bases of H to define w (note that w E Ho still holds for this implementation). We set N so that it larger than N that the number of bases for the Galerkin approximation.
In addition to demonstrating the validity of our proposed method, we also illustrate the benefit of feature learning. For that purpose, we compare the performance of the two-layer mean-field neural network against that of non-adaptive estimators: the ridge regression estimator and the Kudaraya-Watson estimator. Here, we use the terminology "non-adaptive" to indicate that they do not perform feature learning. For ridge regression, we implemented the estimator using an N-basis approximation, i.e., = Eij=0 O)e,, where .NN, E R- are chosen to minimize E (E 2 a2 Vi) + Ej= + oz with regularization parameter >> 0. As for the Nadaraya Wattson estimator, the estimator ý for an input x is given by ú where h > 0 is a bandwidth and k(u)= = max - u², 0} for u E R (Epanechnikov kernel).
Eist N: [a /h) Eim A| -||=;==|)//0)
We used the squared loss for the optimization of two- layer neural network. We employed tanh for the acti- vation functions T1, T2 of the student model. Hence, the teacher model is a bit out side of the student model. Our experiments were performed using the following hyperparameters: Upper bound of input data in Mgx2 Bx = 100; Number of basis functions to generate data: N 300; Number of training data = 100; Number of basis functions for Galerkin approximation:
Nidge: A-6.1
And
Nadleraya- h-0.8
Madammy--Watss::: h=0.9
Naddemys-WWassen: hm1.0
Test
P-SDCA
10-1
150; Regularization parame-
ters for PDA and P-SDCA: X = 10-2 X2 = 10-5;
Gradient evaluations
1e5
Number of particles: M = 200; Hyperparameters
for PDA: T, = 10, 77: 10-5 minibatch size 50; Figure 1: gradient calculations vs. test loss.
Hyperparameters for P-SDCA: Jr = 10, ñ = 1000, 7) = 10-4; Regularization parameter for ridge regression: X = 0. 1, 10 (we observed that À 1 achieved the best performance over all choices of A); Bandwidth for Nadaraya- Watson estimator: h = 0.8, 0.9.
As shown in Figure I PDA and P-SDCA converge and achieve small test loss. Moreover, for both algorithms, the eventual test loss is smaller than those of linear estimators (Ridge-regression and Nadaraya- Watson estimator), which illustrates that the miel-fieed two-layer neural network has better generalization ability than non-adaptive methods. This mainly due to the feature learning ability of the mean- mean-field networks, whereas the non-adaptive methods are not able to find informative features.

---

7 Conclusion
In this work we studied two-layer neural networks in the mean-field regime as model for machine learning problems with fiinnte-dimensionall input. We proposed two optimization algorithms to learn the neural network, by extending the Particle Dual Averaging and Particle Stochastic Dual Coordinate Ascent method to infiniteddimensional parameter space. Leveraging the convergence guarantee of infinitediimensionll gradient Langevin dynamics, we showed that our proposed methods can globally optimize the training objective rate of polynomial order for the online setting and exponential order for the finite-sum setting. Numerical experiments on synthetic data confirmed that mean-field neural network outperforms linear estimators that do not learn features.
Acknowledgments
NN partially supported by CREST (JPMICR2015). TS partially supported by Japan Digital Design and CREST (JPMICR2115), AN was partially supported by JSPS Kakenhi (22H03650) and JST-PRESTO (19M) DW was partially supported by the Borealis AI Fellowship.
References
A. Agarwal, M. Wainwright, P. Bartlett, and K. Ravikumar. Information-theoree thhorrtic lower bounds on the oracle complexity of convex optimization. In Advances in Neural Information Processing Systems 22, pages 1-9, 2009.
C.-E. Bréhier. Approximation of the invariant measure with an Euler scheme for stochastic PDEs driven by space-time white noise. Potential Analysis, 40(1):1-40, 2014.
A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computationall Mathematics, 7(3):331-36 2007.
L. Chizat. Mean-field langevin dynamics: Exponential convergence and annealing, 2022. URL https://arxiv. org/ abs 2202 01009
L. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018
L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming, Advances in Neural Information Processing Systems, 32, 2019.
G. Da Prato and J. Zabczyk. Ergodicity for Infinite Dimensional Systems. London Mathematical Society Lecture Note Series. Cambridge University Press, 1996.
G. Da Prato, J. Zabczyk, and Zabezyk. Ergodicity for Infinite Dimensional Systems, volume 229. Cambridge University Press, 1996.
A. Debussche. Weak approximation of stochastic partial differential equations: the nonlinear case. Mathematics of Computation, 80(273):89-117, 2011.
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes aver-parameterized neural networks. In International Conference Learning Representations, 2018.
Ferraty, A. Mas, and Vieu. Nonparametric regression on functional data: inference and practical aspects. Australian New Zealand Journal of Statistics, 49(3):267-286, 2007.
L. Ferré and N. Villa. Multilayer perceptron with functional inputs: an inverse regression approach. Scandinavian Journal of Statistics, 33(4):807-823, 2006.
K. Hu, Z. Ren, D. Siska, and L. Szpruch. Mcan-field langevin dynamics and energy landscape of neural networks. arXiv preprint 1rXiv:1905.07769, 2019.
A. Jacot, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. Advances in Neural Information Processing Systems, 31, 2018.
10

---

N. M. Kriege, F. D. Johansson, and C. Morri. A survey graph kernels. Applied Network Science, 5(1):1-422 2020.
N. Ling and P. Vieu, Nonparametric modelling for functional data: selected survey and tracks for future. Statistics, 52(4):934-949, 2018.
Y.-A. Ma, Y. Chen, C. Jin, N. Flammarion, and M. I. Jordan. Sampling be faster than optimization. Proceedings of the National Academy of Sciences, 116(42):20881-20888 2019.
S. Mei, A. Montanari, and P.-M. Nguyen. A mean field view the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, L15(33)E7665-E777) 2018
B. Muzellec, K. Sato, M. Massias, and Suzuki. Dimension-free convergence rates for gradient langevin dynamics in RKHS. In Proceedings of Thirty Fifth Conference on Learning Theory, page to appear. PMLR, 2022.
Y. Nesterov. Primal-dus subgradient methods for convex problems. Mathematical programming, 120(1):221-259, 2009.
A. Nitanda and T. Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint 172iv:1712.05438,, 2017.
A. Nitanda, D. Wu, and T. Suzuki. Particle dual averaging: Optimization of mean field neural networks with global convergence rate analysis. In Advances Neural Information Processing Systems, volume 34, 2021.
A. Nitanda, D. Wu, and T. Suzuki. Convex analysis of the mean field langevin dynamics. In G. Camps- Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings The 25th International Conference on Artificial Intelligence and Statisties, volume 151 of Proceedings of Machine Learning Research, pages 9741-9757. PMLR, 28-30 Mar 2022. URL ni nitanda22a html
mlr. patssprres/v//
K. Oko. T. Suzuki, A. Nitanda, and D. Wu. Particle stochastic dual coordinate ascent: Exponential convergent algorithm for mean field neural network optimization. International Conference on Learning Representations, 10, 2022.
M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703, PMLR, 2017.
Rossi and B. Conan-Guez. Functional multi multi-layer perceptron: a non-linear tool for functional data analysis. Neural networks, ((1),,5-60, 2005.
F. Rossi, N. Delannay, B. Conan-Guez, and M. Verleysen. Representation of functional data in neural networks. Neurocomputing, 64:183-210, 2005.
I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
S. Vempala and A. Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in Neural Information Processing Systems, 32:8094-8106, 2019.
G. Yang and E. Hu. Tensor programs iv: Feature learning infinite-width neural networks. In International Conference on Machine Learning, pages 11 PMM.P 2021.
J. Yao. J. Mueller, and J.-L. Wang. Deep learning for functional data analysis with adaptive basis layers. International Conference on Machine Learning, pages 11898-11990 PMLR, 2021.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are stated in the each theorem statements and Assumption 2
(b) Did you include complete proofs of all theoretical results? [Yes] All of the proofs of theoretical results are shown in the appendices.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The details of the experiments are shown in Section 6.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Figure
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The codes we used in the experiments are based on supplemental materials Oko et al. (2022).
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "WkwrIRpFfiP", "reviewer": "Reviewer_EsYc", "summary": "In this paper, the authors extend the mean-field limit in the two-layer neural networks with finite-dimensional input to the infinite-dimensional input setting. The generalization bound was derived to show the regularized empirical risk minimizer is provable generalized at rate of $O(1/\\sqrt{n})$. Two optimization algorithms (PDA, P-SDCA) based on gradient Langevin dynamics are proposed. Authors proved that two algorithms could converge to optimal solution under certain assumptions. Experiment results also support the theoretical analysis.", "questions": "1. In Theorem 7, at the last line what is the expectation taken over? Is it taken over the random noise during training?\n2. It would be better if authors could write a main theorem for PDA to combine Theorem 3,4,5 (just like Theorem 7 for P-SDCA).\n", "limitations": "Authors discuss the limitations of current work. As far as I could see, there are no potential negative social impacts.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n1. In general the paper is well organized and clearly written.\n2. Extending mean-field limit to the infinite-dimensional input setting to allow feature learning seems to be new. The two proposed optimization algorithms as well as the generalization bound also seem to be new in the literature.\n3. The theoretical results are well supported with proof ideas in the main text and complete proof in the appendix.\n4. This paper gives generalization bound $O(1/\\sqrt{n})$ that shows regularized empirical risk minimizer generalizes provided enough samples in the infinite-dimensional data setting. \n\nWeaknesses\n1. While the two proposed optimization algorithms could converge to optimal solution, their running time are exponential in regularization parameter $\\lambda_2$. As suggested by Thm 1, $\\lambda_2$ should be set to $1/\\sqrt{n}$, which implies an exponential runtime. This seems unavoidable in the general mean-field setting with gradient Langevin dynamics. However, it would be better if authors could clearly state this, since the current abstract and contribution part seems to suggest the runtime is polynomial.\n2. The generalization bound depends on $KL(\\pi^o||\\nu)$ where $\\pi^o$ is the target distribution and $\\nu$ is Gaussian distribution. It would be better if some discussion could be added to clarify in some common settings when this KL divergence is bounded (e.g., $O(1)$) and when it is not.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SOpqUjDkaJg", "reviewer": "Reviewer_JAao", "summary": "This paper studies the  mean field limit of two-layer neural network in an infinite-dimensional parameter space. The main contributions are:\n       \n- A generalization error bound of the regularized empirical risk minimizer.\n       \n- Two optimization algorithms for our infinite-dimensional neural network by incorporating the  infinite-dimensional Langevin dynamics in the inner loop of PDA and P-SDCA.\n\n- Theoretical guarantees for the convergence of the two algorithms. ", "questions": "I only have minor comments and questions. \n\n\n- Are the two distributions $P_{\\mathcal{X}}$ and $P_{X}$ in line 222 the same?\n\n- Can the author comment on the choice of the Gaussian measure as the reference measure in the regularization? In the finite dimensional case, obviously the flat Lebesgue measure is used as the reference. In the infinite dimensional case, I understand that Gaussians are the canonical choice. However, does the choice of Gaussian measure affect the generalization error? I would image the covariance of the Gaussian reference is essential since it determines the smoothness of functions that the Gaussian measure is supported.  \n\n- Is the Nesterov’s dual averaging essential for the main results (Theorems 3-5) to hold? I am not an expert on stochastic optimization, but is it possible to establish these results if one only use the  gradient information at the most recent step?\n", "limitations": "I am not aware of  potential negative societal impact of this work. The author did not discuss the limitations explicitly in the conclusion, but comment on some limitations of the main results after the statements. ", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths. This is a very nice (and perhaps the first) paper on the training analysis of  two-layer neural network on an infinite-dimensional space in the mean field regime. The extension from finite dimensional setting to infinite dimensions is highly nontrivial.  It is among the best of all papers I have reviewed in NeurIPS 2022. \n    \n - Weaknesses. In my opinion, the paper is strong enough to be accepted. I do not have comments on the weakness, except minor comments which requires some clarifications; see below. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "D_bHlZFRPH7H", "reviewer": "Reviewer_dM1S", "summary": "This submission studies the optimization of the neural network with infinite-dimensional input in the mean-field regime and provides a convergence guarantee based on weak convergence. This result utilizes the proximal gradient method which solves the optimization task by linearization and Langevin sampling approximation. The authors study the convergence rate in both finite-sum and online settings. Compared to previous work, this submission considers the infinite-dimensional case and makes use of the analysis in infinite-dimensional Langevin. Besides, the authors provide the experiment on functional regression. The primary contribution is the convergence guarantee of the algorithm with infinite-dimensional input.", "questions": "Refer to strengths and weaknesses.", "limitations": "Refer to strengths and weaknesses", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper provides a complete and detailed analysis on infinite-dimensional-input P-SDCA and PDA and provides the weak convergence result. First the paper is well-written and the analysis is rigorous and well-orginized. The assumptions are stated explicitly. The authors also llustrate the effectiveness by numerical experiments.\n\nWeakness:\n\nLack disscussion on the theoretical result. It would be better to discuss the implication of the convergence rate e.g. on $\\lambda_2$. I am not familiar with this field but it seems that this line of research cannot overcome the exponential dependency on sample size M which makes the bound less informative. \n\nMinor:\n\nIn proof of thm 4, drop the weight t.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept