Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics

## Abstract

Abstract We study the problem of learning multi-index models in high-dimensions
using a two-layer neural network trained with the mean-field Langevin algorithm. Under mild distributional assumptions on the data, we characterize the effective dimension d eff subscript 𝑑 eff d_{\mathrm{eff}} italic_d start_POSTSUBSCRIPT roman_eff end_POSTSUBSCRIPT that controls both sample and computational complexity by utilizing the adaptivity of neural networks to latent low-dimensional structures. When the data exhibit such a structure, d eff subscript 𝑑 eff d_{\mathrm{eff}} italic_d start_POSTSUBSCRIPT roman_eff end_POSTSUBSCRIPT can be significantly smaller than the ambient dimension.
We prove that the sample complexity grows almost linearly with d eff subscript 𝑑 eff d_{\mathrm{eff}} italic_d start_POSTSUBSCRIPT roman_eff end_POSTSUBSCRIPT , bypassing the limitations of the information and generative exponents that appeared in recent analyses of gradient-based feature learning. On the other hand, the computational complexity may inevitably grow exponentially with d eff subscript 𝑑 eff d_{\mathrm{eff}} italic_d start_POSTSUBSCRIPT roman_eff end_POSTSUBSCRIPT in the worst-case scenario. Motivated by improving computational complexity, we take the first steps towards polynomial time convergence of the mean-field Langevin algorithm by investigating a setting where the weights are constrained to be on a compact manifold with positive Ricci curvature, such as the hypersphere. There, we study assumptions under which polynomial time convergence is achievable, whereas similar assumptions in the Euclidean setting lead to exponential time complexity.

## 1 Introduction

A key characteristic of neural networks is their adaptability to the underlying statistical model. Several works have shown that shallow neural networks trained by (variants of) gradient descent can adapt to inherent structures in the learning problem, and learn functions of low-dimensional projections with a sample complexity that depends on properties of the nonlinear link function such as the information exponent [] or generative exponent [] for single-index models, and the leap complexity [] for multi-index models. Specifically, prior works typically established a sample complexity of $n\gtrsim d^{\Theta(s)}$ for gradient-based learning, where $s$ can be the information/leap exponent [, , , , , , ] or the generative exponent [, , , ], depending on the implementation of gradient descent. This sample complexity is also predicted by the framework of statistical query lower bounds [, , ].

On the other hand, neural networks can efficiently approximate arbitrary multi-index models regardless of the generative/leap exponent $s$ [, ]; moreover, if the (polynomial) optimization budget is not taken into consideration, there exist computationally inefficient training algorithms that can achieve sample complexity independent of $s$ [, ].
Intuitively speaking, a function depending on $k=O_{d}(1)$ directions of the input data has $kd=O(d)$ parameters to be estimated, and hence the information theoretically optimal algorithm only requires $n\asymp d$ samples. However, thus far it has been relatively unclear whether standard first-order optimization algorithms for neural networks inherit this optimality.

A promising approach to obtain statistically optimal sample complexity is to consider training neural networks in the mean-field regime [, , , , ], where overparameterization is utilized to lift the gradient descent dynamics into the space of measures so that global convergence can be established. While most existing results in this regime focus on optimization instead of generalization/learnability guarantees, recent works have shown that under restrictive data and target assumptions (such as XOR), mean-field neural networks can achieve a sample complexity that does not depend on the leap complexity [, , , ].
Among these works, [] proved quantitative convergence guarantees for learning $k$-parity with $n\asymp d$ samples, despite the target function having leap index $k$.
Key to this result is the convergence rate analysis of the mean-field Langevin algorithm (MFLA) [, , ]. However, existing learnability guarantees in the mean-field regime fall short in the following aspects:

- •
Learning general multi-index models. Prior works established optimal sample complexity for mean-field neural networks under stringent assumptions on the data distribution (isotropic Gaussian, hypercube, etc.) as well as on the target function such as single-index models with specific link functions [, ], or $k$-sparse parity classification [, , ].
Hence, the problem of universally learning functions of low-dimensional projections with minimal data assumptions using neural networks with a standard training procedure remains largely open.
- •
Polynomial computational complexity. To achieve optimal sample complexity, the computational complexity of the training algorithm in [, ] is exponential in the ambient (input) dimension. Although such exponential dependence may be unavoidable in the most general setting, sufficient conditions under which the mean-field algorithm can achieve statistical efficiency with polynomial compute is relatively under-explored, with the exception of a recent work that studied the specific example of the $k$-parity problem on anisotropic data [].

### 1.1 Our Contributions

Motivated by the above discussion, in this work we address two key questions. First, we ask

*Can we train two-layer neural networks using the MFLA to learn arbitrary multi-index models
with an (information theoretically) optimal sample complexity?*

We answer this in the affirmative by showing that empirical risk minimization on a standard variant of a two-layer neural network
can be achieved by the MFLA.
This result handles arbitrary multi-index models on subGaussian data with general covariance, hence enabling us to obtain a sample complexity with optimal dimension dependence up to polylogarithmic factors with standard gradient-based training.
However, such a universal guarantee will inevitably suffer from an exponential computational complexity; thus, the second fundamental question we aim to answer is

*Are there conditions under which the computational complexity of the MFLA can be improved
from exponential to (quasi)polynomial dimension dependence?*

We provide a positive answer in two problem settings. In the Euclidean setting, we show that the complexity of MFLA is governed by the effective dimension of the learning problem, instead of its ambient dimension; this implies an improved efficiency of MFLA when the data is anisotropic as studied in prior works [, ].
In the Riemannian setting, we outline concrete conditions on the Ricci curvature of the compact manifold defining the weight space under which MFLA converges in polynomial time.

### 1.2 Related Works

#### Mean-field Langevin dynamics.

The training dynamics of neural networks in the mean-field regime is described by a nonlinear partial differential equation in the space of parameter distributions [, , ]. Unlike the neural tangent kernel (NTK) description [, ] that freezes the parameters around the random initialization, the mean-field regime allows for the parameters to travel and learn useful features, leading to improved statistical efficiency. While convergence analyses for mean-field neural networks are typically qualitative in nature, in that they do not specify the rate of convergence or finite-width discrepancy, the mean-field Langevin algorithm that we study is a noticeable exception, for which the convergence rate [, , ] as well as uniform-in-time propagation of chaos [, , , ] have been established.

To utilize the MFLD to learn general classes of targets, a recent work [] considered a two-timescale dynamics where the second layer is optimized infinitely faster than the first layer, and provided statistical guarantees for learning Barron spaces with a bounded activation function. The concurrent work of [] studied this two-timescale approach to MFLD in a more general setting of optimization over signed measures without considering the estimation aspect and statistical guarantees. Our formulation here bypasses the need for two-timescale dynamics while learning a similarly large class of target functions.

#### Learning low-dimensional targets.

The benefit of feature learning has also been studied in a “narrow-width” setting, where parameters of the neural network align with the low-dimensional target function during gradient-based training. Examples of low-dimensional targets include single-index models [, , , , , ] and multi-index models [, , , , , , ].
While the information-theoretic threshold for learning such functions is $n\gtrsim d$ [, , ], the complexity of gradient-based learning is governed by properties of the link function. For instance, in the single-index setting, prior works established a sufficient sample size of $n\gtrsim d^{\Theta(s)}$ where $s$ is the information exponent for one-pass SGD on the squared/correlation loss [, , , ], and the generative exponent [] when the algorithm can reuse samples or access a different loss [, , , ].
This presents a gap between the information-theoretically achievable sample complexity and the performance of neural networks optimized by gradient descent, which we aim to close by studying the statistical efficiency of mean-field neural networks.

#### Notation.

We denote the Euclidean inner product with $\mathopen{}\mathclose{{}\left\langle{\cdot},{\cdot}}\right\rangle$, the Euclidean norm for vectors and the operator norm for matrices with $\mathopen{}\mathclose{{}\left\|{\cdot}}\right\|$, and the Frobenius norm with $\mathopen{}\mathclose{{}\left\|{\cdot}}\right\|_{\mathrm{F}}$. Given a topological space $\mathcal{W}$ endowed with an underlying metric and Lebesgue measure, we use $\mathcal{P}(\mathcal{W})$, $\mathcal{P}_{2}(\mathcal{W})$, and $\mathcal{P}^{\mathrm{ac}}_{2}(\mathcal{W})$ to denote the set of (Borel) probability measures, the set of probability measures with finite second moment, and the set of absolutely continuous probability measures with finite second moment, respectively. Finally, we use $\delta_{\boldsymbol{w}_{0}}$ to denote the Dirac measure at $\boldsymbol{w}_{0}$, i.e. $\int h(\boldsymbol{w})\mathrm{d}\delta_{\boldsymbol{w}_{0}}(\boldsymbol{w})=h(
\boldsymbol{w}_{0})$.

## 2 Preliminaries:
Optimization in Measure Space

#### Statistical model.

In this paper, we consider the regression setting where the input $\boldsymbol{x}\in\mathbb{R}^{d}$ is generated from some distribution and the response $y\in\mathbb{R}$ is given by the following multi-index model

$$ $y=g\Big{(}\tfrac{\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{1}},{ \boldsymbol{x}}}\right\rangle}{\sqrt{k}},\ldots,\tfrac{\mathopen{}\mathclose{{ }\left\langle{\boldsymbol{u}_{k}},{\boldsymbol{x}}}\right\rangle}{\sqrt{k}} \Big{)}+\xi.$ (2.1) $$

Here, $g:\mathbb{R}^{k}\to\mathbb{R}$ is the unknown link function, $\xi$ is a zero-mean $\varsigma$-subGaussian noise independent from $\boldsymbol{x}$; for simplicity, we assume $\varsigma^{2}\lesssim 1$. Without loss of generality, we assume that the unknown directions $\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k}$ are orthonormal, and define $\boldsymbol{U}=(\boldsymbol{u}_{1}/\sqrt{k},\ldots,\boldsymbol{u}_{k}/\sqrt{k}
)^{\top}\in\mathbb{R}^{k\times d}$; thus, we can use the shorthand notation $y=g(\boldsymbol{U}\boldsymbol{x})+\xi$. Throughout the paper, we consider the setting $k\ll d$, and treat $k$ as an absolute constant independent from the ambient input dimension $d$.

For a student model $\boldsymbol{x}\to\hat{y}(\boldsymbol{x};\boldsymbol{W})$ with $\boldsymbol{W}$ denoting its model parameters, we consider loss functions of the form $\ell(\hat{y},y)=\rho(\hat{y}-y)$ where $\rho:\mathbb{R}\to\mathbb{R}_{+}$ is convex.
In the classical regression setting where
we observe $n$ i.i.d. samples $\{(\boldsymbol{x}^{(i)},y^{(i)})\}_{i=1}^{n}$ from the data distribution,
the regularized population risk and the regularized empirical risk are defined respectively as

$$ $J_{\lambda}(\boldsymbol{W})\coloneqq\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\ell(\hat{y}(\boldsymbol{x};\boldsymbol{W}),y)}}\right]+ \frac{\lambda}{2}R(\boldsymbol{W})\ \ \text{ and }\ \ \hat{J}_{\lambda}( \boldsymbol{W})\coloneqq\frac{1}{n}\sum_{i=1}^{n}\ell(\hat{y}(\boldsymbol{x}^{ (i)};\boldsymbol{W}),y^{(i)})+\frac{\lambda}{2}R(\boldsymbol{W}),$ $$

where $R$ is some regularizer on the model parameters and the expectation is over the joint distribution of $(\boldsymbol{x},y)$. In practice, we minimize the empirical risk $\hat{J}_{\lambda}$
as the finite sample approximation of the population risk $J_{\lambda}$, anticipating that both minimizers are *close* to each other.

We use a two-layer neural network coupled with $\ell_{2}$ regularization to learn the statistical model (2.1),
where learning constitutes recovering both unknowns $\boldsymbol{U}$ and $g$.
Denoting the $m$ neurons with a matrix $\boldsymbol{W}\coloneqq(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{m})^{\top}$,
the student model and the $\ell_{2}$-regularizer are given as

$$ $\hat{y}_{m}(\boldsymbol{x};\boldsymbol{W})\coloneqq\frac{1}{m}\sum_{j=1}^{m} \Psi(\boldsymbol{x};\boldsymbol{w}_{j})\quad\text{ and }\quad R(\boldsymbol{W} )\coloneqq\frac{1}{m}\|\boldsymbol{W}\|_{\text{F}}^{2}=\frac{1}{m}\sum_{j=1}^{ m}\|\boldsymbol{w}_{j}\|^{2},$ (2.2) $$

where $\Psi:\mathbb{R}^{d}\times\mathcal{W}\to\mathbb{R}$ is the activation function, and $\boldsymbol{w}_{j}\in\mathcal{W}$ with $\mathcal{W}$ denoting a Riemannian manifold.
In this formulation, the second layer weights are all fixed to be $+1$.

To minimize an objective $J$ denoting either
$J_{\lambda}$ or $\hat{J}_{\lambda}$, we will consider a discretization of the following set of SDEs, which essentially define an interacting particle system over $m$ neurons:

$$ $\mathrm{d}\boldsymbol{w}^{t}_{j}=-m\nabla_{\boldsymbol{w}_{j}}J(\boldsymbol{w} ^{t}_{1},\ldots,\boldsymbol{w}^{t}_{m})\mathrm{d}t+\sqrt{\frac{2}{\beta}} \mathrm{d}\boldsymbol{B}^{j}_{t}\quad\text{ for }\quad 1\leq j\leq m,$ (2.3) $$

where $\nabla_{\boldsymbol{w}}$ is the Riemannian gradient and $(\boldsymbol{B}^{j}_{t})_{j=1}^{m}$ is a set of independent Brownian motions on $\mathcal{W}$. We scale the learning rate (prefactor in front of the gradient) by $m$ to compensate that the gradient will be of order $m^{-1}$ with respect to each neuron.
The case $\beta=\infty$ corresponds to the classical gradient flow over $J$, while the Brownian noise can help escaping from spurious local minima and saddle points.

#### Optimization in measure space.

Notice that the neural network and the regularizer in (2.2) are both invariant under permutations of the weights $(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{m})$; thus, an equivalent integral representation of these functions can be written using
Dirac measures $\delta_{\boldsymbol{w}_{j}}$ centered at $\boldsymbol{w}_{j}$ as follows

$$ $\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})\coloneqq\!\!\int\!\Psi( \boldsymbol{x};\cdot)\mathrm{d}\mu_{\boldsymbol{W}}\ \ \text{ and }\ \ \mathcal{R}(\mu_{\boldsymbol{W}})\coloneqq\!\!\int\!\!\|\cdot\|^{2}\mathrm{d} \mu_{\boldsymbol{W}}\quad\text{ with }\ \ \mu_{\boldsymbol{W}}=\frac{1}{m}\sum _{j=1}^{m}\delta_{\boldsymbol{w}_{j}}.$ (2.4) $$

Here, $\mu_{\boldsymbol{W}}$ is the empirical measure supported on $m$ atoms. Indeed, $\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})=\hat{y}_{m}(\boldsymbol{x};
\boldsymbol{W})$ and $\mathcal{R}(\mu_{\boldsymbol{W}})=R(\boldsymbol{W})$, and this formulation allows extension to infinite-width networks
by removing the condition that measures are supported on $m$ atoms, and
by expanding the feasible set of measures to $\mu\in\mathcal{P}_{2}(\mathcal{W})$. Thus,
we rewrite the population and the empirical risks in the space of measures as

$$ $\mathcal{J}_{\lambda}(\mu_{\boldsymbol{W}})\coloneqq J_{\lambda}(\boldsymbol{W })\quad\text{ and }\quad\hat{\mathcal{J}}_{\lambda}(\mu_{\boldsymbol{W}}) \coloneqq\hat{J}_{\lambda}(\boldsymbol{W}),$ $$

and allow their domain to be $\mu\in\mathcal{P}_{2}(\mathcal{W})$. Let $\mathcal{J}:\mathcal{P}_{2}(\mathcal{W})\to\mathbb{R}$ be the population risk $\mathcal{J}_{\lambda}$ or the empirical risk $\hat{\mathcal{J}}_{\lambda}$.
We can equivalently state the interacting SDE system (2.3)
as (see e.g. [, Proposition 2.4])

$$ $\mathrm{d}\boldsymbol{w}^{t}_{j}=-\nabla_{\boldsymbol{w}}\mathcal{J}^{\prime}[ \mu_{\boldsymbol{W}^{t}}](\boldsymbol{w}^{t}_{j})\mathrm{d}t+\sqrt{\frac{2}{ \beta}}\mathrm{d}\boldsymbol{B}^{j}_{t}\quad\text{ for }\quad 1\leq j\leq m,$ (2.5) $$

where $\mathcal{J}^{\prime}[\mu]\in L^{2}(\mathcal{W})$ denotes
the first variation of $\mathcal{J}(\mu)$ defined via

$$ $\int\mathcal{J}^{\prime}[\mu](\boldsymbol{w})\mathrm{d}(\nu-\mu)(\boldsymbol{w })=\lim_{\epsilon\downarrow 0}\frac{\mathcal{J}((1-\epsilon)\mu+\epsilon\nu)- \mathcal{J}(\mu)}{\epsilon},\quad\forall\nu\in\mathcal{P}_{2}(\mathcal{W}),$ (2.6) $$

which is unique up to additive constants when it exists [, Definition 7.12].

As $m\to\infty$, the stochastic empirical measure $\mu_{\boldsymbol{W}^{t}}$ weakly converges to a deterministic measure $\mu_{t}$ for all fixed $t$, a phenomenon known as the *propagation of chaos* []. Furthermore, $\mu_{t}$ can be characterized as the law of the solution of the following SDE and non-linear Fokker-Planck equation

$$ $\!\!\mathrm{d}\boldsymbol{w}^{t}=-\nabla_{\boldsymbol{w}}\mathcal{J}^{\prime}[ \mu_{t}](\boldsymbol{w}^{t})\mathrm{d}t+\sqrt{\frac{2}{\beta}}\mathrm{d} \boldsymbol{B}_{t}\quad\text{ and }\quad\partial_{t}\mu_{t}=\boldsymbol{\nabla }\cdot(\mu_{t}\nabla\mathcal{J}^{\prime}[\mu_{t}])+\beta^{-1}\boldsymbol{ \Delta}\mu_{t},$ (2.7) $$

where $\boldsymbol{\nabla}\cdot$ and $\boldsymbol{\Delta}$ are the Riemannian divergence and Laplacian operators, respectively.
Due to the existence of mean-field interactions, (2.7) is known as the *mean-field Langevin dynamics* (MFLD).

For a pair of probability measures $\mu\ll\nu$ both in $\mathcal{P}(\mathcal{W})$, we define the relative entropy $\mathcal{H}(\mu\,|\,\nu)$ and the relative Fisher information $\mathcal{I}(\mu\,|\,\nu)$ respectively as

$$ $\mathcal{H}(\mu\,|\,\nu)\coloneqq\int_{\mathcal{W}}\ln\frac{\mathrm{d}\mu}{ \mathrm{d}\nu}\mathrm{d}\mu\quad\text{ and }\quad\mathcal{I}(\mu\,|\,\nu) \coloneqq\int_{\mathcal{W}}\mathopen{}\mathclose{{}\left\|{\nabla\ln\frac{ \mathrm{d}\mu}{\mathrm{d}\nu}}}\right\|^{2}\mathrm{d}\mu.$ (2.8) $$

It is well-known at this point that
$\mu_{t}$ in (2.7) can be interpreted as the Wasserstein gradient flow of the entropic regularized functional $\mathcal{F}_{\beta}(\mu)\coloneqq\mathcal{J}(\mu)+\frac{1}{\beta}\mathcal{H}(
\mu\,|\,\tau)$,
where $\tau$ is
the uniform measure on compact $\mathcal{W}$ or the Lebesgue measure on a Euclidean space [, , ].
For this gradient flow to converge exponentially fast towards the minimizer $\mu^{*}_{\beta}\coloneqq\operatorname*{arg\,min}_{\mu}\mathcal{F}_{\beta}(\mu)$, we require
a *gradient domination* condition on $\mu^{*}_{\beta}$ in the space of probability measures, given as

$$ $\mathcal{H}(\mu\,|\,\mu^{*}_{\beta})\leq\frac{C_{\mathrm{LSI}}}{2}\mathcal{I}( \mu\,|\,\mu^{*}_{\beta}),\quad\forall\mu\in\mathcal{P}(\mathcal{W}),$ (2.9) $$

which is referred to as the log-Sobolev inequality (LSI).
If the measure ${\mathrm{d}\nu_{\mu_{t}}}\propto\exp(-\beta\mathcal{F}^{\prime}_{\beta}[\mu_{t
}])\mathrm{d}\tau$
satisfies LSI with constant $C_{\mathrm{LSI}}$ for all $t\geq 0$,
$\mu_{t}$ enjoys the following exponential convergence

$$ $\mathcal{F}_{\beta}(\mu_{t})-\mathcal{F}_{\beta}(\mu^{*}_{\beta})\leq e^{\frac {-2t}{\beta C_{\mathrm{LSI}}}}(\mathcal{F}_{\beta}(\mu_{0})-\mathcal{F}_{\beta }(\mu^{*}_{\beta}));$ (2.10) $$

see e.g. [, Theorem 3.2] and [, Theorem 1].

## 3 Learning Multi-index Models in the Euclidean Setting

In this section, we consider learning multi-index models in the Euclidean setting.
For technical reasons, we use an approximation of ReLU denoted by $z\mapsto\phi_{\kappa,\iota}(z)$ for some $\kappa,\iota>1$, which is given by $\phi_{\kappa,\iota}(z)=\kappa^{-1}\ln(1+\exp(\kappa z))$ for $z\in(-\infty,\iota/2]$ and extended on $(\iota/2,\infty)$ such that $\phi_{\kappa,\iota}$ is $C^{2}$ smooth, $\mathopen{}\mathclose{{}\left|{\phi_{\kappa,\iota}}}\right|\leq\iota$, $\mathopen{}\mathclose{{}\left|{\phi^{\prime}_{\kappa,\iota}}}\right|\leq 1$, and $\mathopen{}\mathclose{{}\left|{\phi^{\prime\prime}_{\kappa,\iota}}}\right|\leq\kappa$. Note that $\phi_{\kappa,\iota}$ recovers ReLU as $\kappa,\iota\to\infty$.
Recall that we freeze the second-layer weights as $+1$. Consequently,
non-negative activations can only learn non-negative functions. To alleviate this, we choose $\mathcal{W}=\mathbb{R}^{2d+2}$, and use the notation $\boldsymbol{w}=(\boldsymbol{\omega}_{1}^{\top},\boldsymbol{\omega}_{2}^{\top})
^{\top}$ with $\boldsymbol{\omega}_{1},\boldsymbol{\omega}_{2}\in\mathbb{R}^{d+1}$ to denote the first and the second half of weight coordinates, and use the activation function

$$ $\Psi(\boldsymbol{x};\boldsymbol{w})\coloneqq\phi_{\kappa,\iota}(\mathopen{} \mathclose{{}\left\langle{\tilde{\boldsymbol{x}}},{\boldsymbol{\omega}_{1}}} \right\rangle)-\phi_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\tilde {\boldsymbol{x}}},{\boldsymbol{\omega}_{2}}}\right\rangle),$ (3.1) $$

where
$\tilde{\boldsymbol{x}}\coloneqq(\boldsymbol{x},\tilde{r}_{x})^{\top}\in\mathbb
{R}^{d+1}$ for a constant $\tilde{r}_{x}$ corresponding to bias, to be specified later.
The above can also be seen as a 2-layer neural network with $\phi_{\kappa,\iota}$ as activation where the second-layer weights are frozen at $\pm 1$.

We use the neural network and the regularizer in (2.2)
with weights $\boldsymbol{W}\coloneqq(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{m})\in
\mathbb{R}^{2d+2}$,
and minimize the resulting empirical risk
$\hat{J}_{\lambda}(\boldsymbol{W})$ via
the *mean-field Langevin algorithm* (MFLA), which is a simple time discretization of (2.3) with the stepsize $\eta$ and the number of iterations $l>0$,

$$ $\boldsymbol{w}^{l+1}_{j}=\boldsymbol{w}^{l}_{j}-m\eta\nabla_{\boldsymbol{w}_{j }}\hat{J}_{\lambda}(\boldsymbol{W})+\sqrt{\frac{2\eta}{\beta}}\boldsymbol{\xi} ^{l}_{j},\quad 1\leq j\leq m,$ (3.2) $$

where $\boldsymbol{\xi}^{l}_{j}$ are independent standard Gaussian random vectors. When the stepsize is sufficiently small, MFLA approximately tracks the system of continuous-time SDEs (2.3) as well as their equivalent formulation in the measure space (2.5). If, in addition, the network width $m$ is sufficiently large,
propagation of chaos will kick in and the dynamics will be an approximation to MFLD (2.7), ultimately minimizing the corresponding entropic regularized objective
$\mathcal{F}_{\beta,\lambda}(\mu)\coloneqq\hat{\mathcal{J}}_{\lambda}(\mu)+
\frac{1}{\beta}\mathcal{H}(\mu\,|\,\tau)$.

We make the following assumption on the input distribution.

###### Assumption 1 .

The input $\boldsymbol{x}$ has zero mean and covariance $\boldsymbol{\Sigma}$.
Further, $\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}}}\right\|$ and $\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|$ are subGaussian
with respective norms $\sigma_{n}\|\boldsymbol{\Sigma}^{1/2}\|_{\mathrm{F}}$ and $\sigma_{u}\|\boldsymbol{\Sigma}^{1/2}\boldsymbol{U}^{\top}\|_{\mathrm{F}}$ for some absolute constants $\sigma_{n},\sigma_{u}$.

Even though the above assumption covers a wide range of input distributions,
it is mainly motivated by the Gaussian case $\boldsymbol{x}\sim\mathcal{N}(0,\boldsymbol{\Sigma})$ where $\mathopen{}\mathclose{{}\left\|{\boldsymbol{A}\boldsymbol{x}}}\right\|$ is
subGaussian with norm $\|\boldsymbol{\Sigma}^{1/2}\boldsymbol{A}\|$ for any matrix $\boldsymbol{A}$.
In settings we consider, we can replace the operator norm with the Frobenius norm to obtain a weaker assumption, since $\|\boldsymbol{A}\boldsymbol{x}\|$ is roughly concentrated near its mean, scaling with $\|\boldsymbol{\Sigma}^{1/2}\boldsymbol{A}^{\top}\|_{\mathrm{F}}$.
Without loss of generality, we will consider a scaling where $\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|\lesssim 1$.

A key quantity in our analysis is the *effective dimension* which governs the algorithmic guarantees.

###### Definition 1 (Effective dimension) .

Define $d_{\mathrm{eff}}\coloneqq c^{2}_{x}/r^{2}_{x}$ where $c_{x}\coloneqq\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})^{1/2}$,
$r_{x}\coloneqq\|\boldsymbol{\Sigma}^{1/2}\boldsymbol{U}^{\top}\|_{\mathrm{F}}$.

The effective dimension $d_{\mathrm{eff}}$ can be significantly smaller than the ambient dimension $d$,
leading to particularly favorable results in the following when $d_{\mathrm{eff}}=\operatorname{polylog}(d)$.
This concept has numerous applications from learning theory to statistical estimation; see e.g. [, , , ].
In covariance estimation, for example, the effective dimension is typically defined as $\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})/\mathopen{}\mathclose{{}
\left\|{\boldsymbol{\Sigma}}}\right\|$ (e.g. [, Example 6.4]), which is equivalent to $d_{\mathrm{eff}}$ in Definition 1 provided that $\boldsymbol{U}$ lives in the top eigenspace of $\boldsymbol{\Sigma}$. However,
in general, $d_{\mathrm{eff}}$ might be larger than $\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})/\mathopen{}\mathclose{{}
\left\|{\boldsymbol{\Sigma}}}\right\|$, which is expected as one can imagine a supervised learning setup where the variations of $\boldsymbol{x}$ provide very little information about target directions $\boldsymbol{U}$, making the target directions more difficult to be estimated. We make the following assumption on the link function in (2.1).

###### Assumption 2 .

The link function is locally Lipschitz: $\mathopen{}\mathclose{{}\left|{g(\boldsymbol{z}_{1})-g(\boldsymbol{z}_{2})}}
\right|\leq L\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}_{1}-\boldsymbol{z}
_{2}}}\right\|$ for
$\boldsymbol{z}_{1},\boldsymbol{z}_{2}\!\in\mathbb{R}^{k}$ satisfying
$\mathopen{}\mathclose{{}\left\|{\boldsymbol{z}_{1}}}\right\|\vee\mathopen{}
\mathclose{{}\left\|{\boldsymbol{z}_{2}}}\right\|\leq\tilde{r}_{x}\coloneqq r_
{x}(1+\sigma_{u}\sqrt{2(q+1)\ln(n)})$ for some $q>0$ and $L=\mathcal{O}(1/r_{x})$. We also assume $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}}\right]\lesssim
1$.

We emphasize that the above Lipschitz condition is only local, thus allowing polynomially growing link functions $g$. We scale the Lipschitz constant with $1/r_{x}$ to make sure $y$ has a variance of order $\Theta(1)$.

Recall from Section 2 that in order to prove convergence of the MFLD (and its time/particle discretization MFLA), it is sufficient for the Gibbs potential $\nu_{\mu_{\boldsymbol{W}_{t}}}\propto\exp(-\beta\hat{\mathcal{J}}_{\lambda}^{
\prime}[\mu_{\boldsymbol{W}_{t}}])$ to satisfy LSI uniformly along its trajectory. Here, it is straightforward to derive the first variation as

$$ $\hat{\mathcal{J}}_{\lambda}^{\prime}[\mu](\boldsymbol{w})\!=\!\hat{\mathcal{J} }_{0}^{\prime}[\mu](\boldsymbol{w})+\frac{\lambda}{2}\mathopen{}\mathclose{{} \left\|{\boldsymbol{w}}}\right\|^{2}\ \ \text{ with }\ \ \hat{\mathcal{J}}_{0} ^{\prime}[\mu](\boldsymbol{w})\!=\!\frac{1}{n}\sum_{i=1}^{n}\rho^{\prime}(\hat {y}(\boldsymbol{x}^{(i)};\mu)-y^{(i)})\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w}).$ (3.3) $$

The following assumption introduces the uniform LSI constant for the trajectory of MFLA.

###### Assumption 3 .

Let $\boldsymbol{W}^{l}=(\boldsymbol{w}^{l}_{1},\ldots,\boldsymbol{w}^{l}_{m})$ denote the trajectory of MFLA. Then, the measure $\nu_{\mu_{\boldsymbol{W}^{l}}}\propto\exp(-\beta\hat{\mathcal{J}}_{\lambda}^{
\prime}[\mu_{\boldsymbol{W}^{l}}])$ satisfies the LSI (2.9) with constant $C_{\mathrm{LSI}}$ for all $l\geq 0$. For simplicity, assume $C_{\mathrm{LSI}}\geq\beta$.

The above condition is stated to simplify the exposition and will be verified in our results by using the
boundedness of $\phi_{\kappa,\iota}$; $\hat{\mathcal{J}}_{\lambda}^{\prime}[\mu_{\boldsymbol{W}^{l}}]$ can be considered as a bounded perturbation of a strongly convex potential, thus satisfies LSI by the Holley-Stroock argument [].

###### Proposition 2 .

Suppose $\rho$ is $C_{\rho}$-Lipschitz. Then for any $\mu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$, the probability measure $\nu_{\mu}\propto\exp(-\beta\hat{\mathcal{J}}_{\lambda}^{\prime}[\mu])$ with $\hat{\mathcal{J}}_{\lambda}^{\prime}$ given by (3.3) satisfies the LSI (2.9) with constant

$$ $C_{\mathrm{LSI}}\leq\frac{1}{\beta\lambda}\exp(4C_{\rho}\iota\beta).$ (3.4) $$

For the squared loss, we can replace $C_{\rho}$ above with $\hat{\mathcal{J}}_{0}(\mu_{\boldsymbol{W}})^{1/2}$. With this, as $\hat{\mathcal{J}}_{0}(\mu_{\boldsymbol{W}})$ is uniformly bounded along the trajectory, convergence of the infinite-width MFLD can be established. However, for the finite-width MFLA, controlling $\hat{\mathcal{J}}_{0}(\mu_{\boldsymbol{W}})$ is challenging as there is non-trivial probability that neurons incur a large loss, which is why we require Lipschitz $\rho$.
Note that the right hand side of (3.4) is independent of $\kappa$; thus, by letting $\kappa\to\infty$, the proposition implies the same LSI constant for a bounded variant of ReLU. However, for MFLA (the time discretization of MFLD), we additionally require smoothness of the activation.

###### Assumption 1 .

###### Definition 1 (Effective dimension) .

###### Assumption 2 .

###### Assumption 3 .

###### Proposition 2 .

### 3.1 Statistical and Computational Complexity of MFLA

The main result of this section is stated in the following theorem.

###### Theorem 3 .

Under Assumptions 1, 2 and 3, consider MFLA (3.2)
with parameters $\lambda=\tilde{\lambda}r_{x}^{2}$, $\beta=\tilde{\Theta}(d_{\mathrm{eff}}/\tilde{\lambda})$, and $\eta\leq\tilde{\mathcal{O}}\big{(}\frac{1}{C_{\mathrm{LSI}}\kappa^{2}\bar{r}_{
x}^{4}(d+\bar{r}_{x}^{2}/\lambda)}\big{)}$, where $\bar{r}_{x}\coloneqq\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}
\right\|\lor\tilde{r}_{x}$. Suppose $\tilde{\lambda},\kappa^{-1}=o_{n}(1)$, $\iota=\Theta\big{(}\tfrac{\tilde{r}_{x}^{2}}{\tilde{\lambda}r_{x}^{2}}\big{)}$, the loss satisfies $\mathopen{}\mathclose{{}\left|{\rho^{\prime}}}\right|\lor\rho^{\prime\prime}\lesssim
1$, and
the algorithm is initialized with the weights sampled i.i.d. from some distribution $\boldsymbol{w}^{0}_{j}\sim\mu_{0}$ with $\operatorname{\mathbb{E}}\big{[}\|\boldsymbol{w}^{0}_{j}\|_{2}^{2}\big{]}\lesssim
1$. Then, with the number of samples $n$, the number of neurons $m$, and the number of iterations $l$ that can respectively be bounded by

$$ $n=\tilde{\mathcal{O}}(d_{\mathrm{eff}}),\quad m=\tilde{\mathcal{O}}\Big{(} \frac{C_{\mathrm{LSI}}\bar{r}_{x}^{4}\kappa^{2}}{\beta\lambda}\big{(}\frac{d}{ \beta}+\frac{\bar{r}_{x}^{2}}{\lambda}\big{)}\Big{)},\quad l=\tilde{\mathcal{O }}\big{(}\frac{C_{\mathrm{LSI}}\beta}{\eta}\big{)},$ (3.5) $$

with probability at least $1-\mathcal{O}(n^{-q})$
for some $q>0$, the excess risk satisfies

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{W}^{l}}\operatorname{\mathbb{E}}_{y, \boldsymbol{x}}[{\rho(y-\hat{y}_{m}(\boldsymbol{x};\boldsymbol{W}^{l}))}]- \operatorname{\mathbb{E}}_{\xi}[{\rho(\xi)}]\leq o_{n}(1).$ (3.6) $$

The above theorem demonstrates that $(i)$ the effective dimension of Definition 1 controls the sample complexity, and $(ii)$ the LSI constant of Assumption 3
controls the computational complexity. To that end, we can employ the LSI estimate of Proposition 2 to arrive at the following corollary.

###### Corollary 4 .

In the setting of Theorem 3, using the LSI estimate of Proposition 2, with the number of samples, the number of neurons, and the number of iterations, respectively bounded by

$$ $n=\tilde{\mathcal{O}}(d_{\mathrm{eff}}),\quad m=\tilde{\mathcal{O}}(de^{\tilde {\mathcal{O}}(d_{\mathrm{eff}})}),\quad l=\tilde{\mathcal{O}}(de^{\tilde{ \mathcal{O}}(d_{\mathrm{eff}})}),$ (3.7) $$

MFLA can achieve the excess risk bound (3.6) with $\tilde{\lambda}^{-1},\kappa=\operatorname{polylog}(n)$.

We observe that the above corollary demonstrates a certain adaptivity to the effective low-dimensional structure, both in terms of *statistical* and *computational* complexity. Remarkably, this property of MFLA emerges without explicitly encoding any information about the covariance structure in the algorithm.
In contrast, consider “fixed-grid” methods for optimization over the space of measures $\mathcal{P}(\mathbb{R}^{2d+2})$ (see [] and references therein), in which the algorithm fixes the first-layer of a two-layer network’s representation and only trains the second-layer, solving a convex problem similar to the random features regression [].
However, fixed-grid methods do not show any type of adaptivity to low-dimensions, and in particular their computational complexity always scales exponentially with the ambient dimension $d$, unless information about the covariance structure is explicitly used when specifying the fixed representation.

Table 1 compares recent works in various aspects.
[] requires $d^{\frac{k+3}{2}}$ sample complexity
for learning general $k$-index models, which is worse than the complexity $d_{\mathrm{eff}}$ of Theorem 3 even in the worst case $d_{\mathrm{eff}}=d$. The improvement in our bound is due to a refined control over $\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|$;
while [] assumes this quantity scales with $\sqrt{d}$, it can be verified that for centered $\boldsymbol{x}$, its expectation is independent of $d$. Further, [] does not provide a quantitative analysis of the optimization complexity, and it is not clear if their algorithm is adaptive to the covariance structure.
[] studied learning $k$-sparse parities, a subclass of multi-index models we considered, for which it is considerably simpler to construct optimal neural networks with bounded activation. While the effective dimension (and the resulting sample complexity) of [] is not explicitly scale-invariant, we derive a scale-invariant translation of their bound in Appendix C,
and show that it is always lower bounded by our effective dimension, especially when $\boldsymbol{\Sigma}$ is nearly rank-deficient.

**Table 1: Learning guarantees of neural networks with exponential compute (we focus on the dimension dependence). Our Theorem 3 improves upon prior bounds, with a potentially significant gap depending on the problem setup.**
| Work | Class of Targets | Sample Complexity | Input | Covariance | ​​<br>${d_{\mathrm{eff}}}$-adaptive<br>xCompute<br>​​​​ |
| --- | --- | --- | --- | --- | --- |
| [] | 2-parity | $d$ | hypercube | isotropic | ✗ |
| [] | $k$-parity | $d$ | hypercube | isotropic | ✗ |
| [] | $k$-parity | ​​$\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})\sum_{i=1}^{k}\|\boldsymbol{<br>\Sigma}^{1/2}\boldsymbol{u}_{i}\|^{-2}$​​ | parallelotope | full-rank | ✓ |
| [] | multi-index | $d^{\frac{k+3}{2}}$ | bounded | general | ✗ |
| Theorem 3 | multi-index | $\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})/\|\boldsymbol{\Sigma}^{1/2}<br>\boldsymbol{U}^{\top}\|_{\mathrm{F}}^{2}$ | subGaussian | general | ✓ |

Remark.
We make the following remarks on the computational complexity of learning multi-index models.

- •
Even though the complexity in Corollary 4
scales exponentially with $d_{\mathrm{eff}}$, in Section 3.2 we outline problem settings where $d_{\mathrm{eff}}=\operatorname{polylog}(d)$, under which it
is possible to achieve quasipolynomial runtime for the MFLA.
That said, the exponential dependence in $d_{\mathrm{eff}}$ is unavoidable in general in LSI-based analysis [], and is consequently present in the mean-field literature [, , ].
- •
In the isotropic setting $\boldsymbol{\Sigma}=\mathbf{I}_{d}$, recent works have shown that certain variants of SGD can learn single-index polynomials with almost linear sample complexity [, , ], which matches our sample complexity without needing exponential compute. However, these analyses crucially relied on the polynomial link function, which has generative exponent at most $2$ [] and is SQ-learnable with $n=\tilde{O}_{d}(d)$ samples [, , ].
In contrast, our assumption on the link function allows for arbitrarily large generative exponent, and hence the computational lower bound in [] implies that achieving learnability in the $n\asymp d$ scaling requires exponential compute for statistical query learners.

###### Theorem 3 .

###### Corollary 4 .

### 3.2 Utilizing the Effective Dimension

To better demonstrate the impact of effective dimension $d_{\mathrm{eff}}$, we consider two covariance models.

#### Spiked covariance.

We consider the spiked covariance model of []. Namely, given a spike direction $\boldsymbol{\theta}\in\mathbb{S}^{d-1}$, suppose the covariance and the target directions satisfy

$$ $\boldsymbol{\Sigma}=\frac{\mathbf{I}_{d}+\alpha\boldsymbol{\theta}\boldsymbol{ \theta}^{\top}}{1+\alpha},\quad\alpha\asymp d^{\gamma_{2}},\quad\mathopen{} \mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{\theta}}}\right\|\asymp d^{- \gamma_{1}},\quad\gamma_{2}\in[0,1],\quad\gamma_{1}\in[0,1/2].$ (3.8) $$

Note that in high-dimensional settings, $\gamma_{1}=1/2$ corresponds to a regime where $\boldsymbol{\theta}$ is sampled uniformly over $\mathbb{S}^{d-1}$, whereas $\gamma_{1}=0$ corresponds to the case where $\boldsymbol{\theta}$ has a strong (perfect) correlation with $\boldsymbol{U}$. We only consider $\gamma_{2}\leq 1$ since $\gamma_{2}>1$ corresponds to a setting where the input is effectively one-dimensional.
In this setting, effective dimension depends on $\gamma_{1}$ and $\gamma_{2}$.

###### Corollary 5 .

Under the spiked covariance model (3.8), we have $d_{\mathrm{eff}}\asymp d^{1-\mathopen{}\mathclose{{}\left\{(\gamma_{2}-2\gamma
_{1})\lor 0}\right\}}$.

To get improvements over the isotropic effective dimension $d$, either the spike magnitude $\alpha$ or the spike-target alignment $\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{\theta}}}\right\|$ needs to be sufficiently large so that $\gamma_{2}>2\gamma_{1}$. Recall that the effective dimension in the covariance estimation problem is $\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})/\mathopen{}\mathclose{{}
\left\|{\boldsymbol{\Sigma}}}\right\|\asymp d^{1-\gamma_{2}}$. Therefore, $d_{\mathrm{eff}}$ in Corollary 5 only matches its unsupervised counterpart when $\gamma_{1}=0$, i.e. $\boldsymbol{\theta}$ has a significant correlation with the target directions $\boldsymbol{U}$. As $\gamma_{2}\to 1$ and $\gamma_{1}\to 0$, the effective dimension will be smaller than $\operatorname{polylog}(d)$, leading to a computational complexity that is quasipolynomial in $d$.

###### Corollary 5 .

#### Scaling laws under power-law spectra.

Next,
we consider a more general power-law decay for the eigenspectrum. Specifically, suppose $\boldsymbol{\Sigma}=\sum_{i=1}^{d}\lambda_{i}\boldsymbol{\theta}_{i}
\boldsymbol{\theta}_{i}^{\top}$ is the spectral decomposition of $\boldsymbol{\Sigma}$, and

$$ $\frac{\lambda_{i}}{\lambda_{1}}\asymp i^{-\alpha},\quad\frac{\mathopen{} \mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{\theta}_{i}}}\right\|^{2}}{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{\theta}_{1}}}\right \|^{2}}\asymp i^{-\gamma},\quad\text{ for }\quad 1\leq i\leq d,$ (3.9) $$

for some absolute constants $\alpha,\gamma>0$. Notice that $\sum_{i=1}^{d}\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{\theta
}_{i}}}\right\|^{2}=\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}}}\right\|_{
\mathrm{F}}^{2}=1$.
The following corollary characterizes $d_{\mathrm{eff}}$ in terms of the parameters $\alpha$ and $\gamma$.

###### Corollary 6 .

Under the power-law eigenspectrum for the covariance matrix (3.9), we have

$$ $d_{\mathrm{eff}}\asymp\begin{cases}d^{1\land(2-\alpha-\gamma)}&\quad\alpha<1, \gamma<1\\ d^{1-\alpha}&\quad\alpha<1,\gamma\geq 1\\ d^{(1-\gamma)\lor 0}&\quad\alpha\geq 1\end{cases},$ $$

where $\asymp$ above hides $\operatorname{polylog}(d)$ dependencies.

Figure: Figure 1: $d_{\mathrm{eff}}$ according to Corollary 6.
Refer to caption: x1.png

The scaling of $d_{\mathrm{eff}}$ (and therefore the sample complexity) is illustrated in Figure 1.
We remark that the power-law assumption in (3.9) is parallel to the source condition and capacity condition in the nonparametric regression literature [, ], where the capacity condition measures the decay of feature eigenvalues, and the source condition measures the alignment between the target function and feature eigenvectors.
Also, based on the above result, the width and the number of iterations in Corollary 4 both become quasipolynomial in $d$ when $\alpha,\gamma\geq 1$. This corresponds to the setting where $\boldsymbol{\Sigma}$ is approximately low-rank with most of its eigenspectrum concentrated around the first few eigenvalues, and the corresponding eigenvectors are well-aligned with the row space of $\boldsymbol{U}$.

###### Corollary 6 .

## 4 Polynomial Time Convergence in the Riemannian Setting

The strong statistical learning guarantees in the previous section come at a computational price; MFLA may need $\exp(d_{\mathrm{eff}})$ many iterations and neurons to converge. This complexity arises since in the worst case, the LSI constant that governs the convergence of MFLD will be exponential in the inverse temperature parameter $\beta$ []. In this section, we provide first steps towards achieving polynomial-time complexity for MFLD. In particular, we show that if we constrain the weight space to be a compact Riemannian manifold with a uniformly lower bounded Ricci curvature such as the hypersphere $\mathbb{S}^{d-1}$, we can establish a uniform LSI constant with polynomial dimension dependence, while the same set of assumptions in the Euclidean setting results in exponential dimension dependence. Notice that due to the manifold constraint on the weights, we no longer require $\ell_{2}$-regularization, and simply consider the objective $\mathcal{F}_{\beta}(\mu)=\hat{\mathcal{J}}_{0}(\mu)+\beta^{-1}\mathcal{H}(\mu
\,|\,\tau)$.

Let $(\mathcal{W},\mathfrak{g})$ be a $(d-1)$-dimensional compact Riemannian manifold with metric tensor $\mathfrak{g}$. We denote the Ricci curvature of $\mathcal{W}$ with $\mathrm{Ric}_{\mathfrak{g}}$. We recall the neural network
$\hat{y}(\boldsymbol{x};\mu)=\int\Psi(\boldsymbol{x};\boldsymbol{w})\mathrm{d}
\mu(\boldsymbol{w})$
where, in this case, we choose a $C^{2}$-smooth activation $\Psi(\boldsymbol{x};\cdot):\mathcal{W}\to\mathbb{R}$ defined on the manifold.
We consider the following model example to demonstrate our results.

###### Example 7 .

$\mathcal{W}$ is the hypersphere $\mathbb{S}^{d-1}$ equipped with its canonical metric tensor, and the activation is $\Psi(\boldsymbol{x};\boldsymbol{w})=\phi(\mathopen{}\mathclose{{}\left\langle{
\boldsymbol{w}},{\boldsymbol{x}}}\right\rangle)$ for some smooth $\phi:\mathbb{R}\to\mathbb{R}$. Suppose $\mathopen{}\mathclose{{}\left|{\phi^{\prime}}}\right|,\mathopen{}\mathclose{{}
\left|{\phi^{\prime\prime}}}\right|\lesssim 1$, and the distribution of $\boldsymbol{x}$ satisfies the conditions of Assumption 1.

The following assumption plays an important role in the analysis.

###### Assumption 4 .

$(\mathcal{W},\mathfrak{g})$ satisfies the curvature-dimension condition
$\mathrm{Ric}_{\mathfrak{g}}\succcurlyeq\varrho d\mathfrak{g}$
for an absolute constant $\varrho>0$.
Further,
there exists some $\bar{\mu}\in\mathcal{P}(\mathcal{W})$ such that $\hat{\mathcal{J}}_{0}(\bar{\mu})\leq\bar{\varepsilon}$ and $\mathcal{H}(\bar{\mu}\,|\,\tau)\leq\bar{\Delta}$ for some constants $\bar{\varepsilon},\bar{\Delta}$, where $\tau$ is the uniform distribution on $\mathcal{W}$.

For the unit sphere $\mathbb{S}^{d-1}$, we have $\mathrm{Ric}_{\mathfrak{g}}\succcurlyeq(d-2)\mathfrak{g}$;
thus, the curvature-dimension condition is satisfied for sufficiently large $d$.
Moreover, if there exists some $\mu$ with $\hat{\mathcal{J}}_{0}(\mu)\leq\bar{\varepsilon}$
(e.g. the minimizer of $\hat{\mathcal{J}}_{0}$) for which $\mathcal{H}(\mu\,|\,\tau)=\infty$, one can construct $\bar{\mu}$ such that $\hat{\mathcal{J}}_{0}(\bar{\mu})\leq\tilde{\mathcal{O}}(\bar{\varepsilon})$ and $\mathcal{H}(\bar{\mu}\,|\,\tau)\leq\tilde{\mathcal{O}}(d)$, by smoothing $\mu$ via convolution with box kernels (see [, Theorem 4.1] and its proof). Therefore in the worst-case, we have $\bar{\Delta}=\tilde{\Theta}(d)$. However, under a reasonable model assumption, we can verify Assumption 4 with $\bar{\Delta}=o(d)$, which is demonstrated in the below proposition.

###### Proposition 8 .

Let $y=\int\Psi(\boldsymbol{x};\cdot)\mathrm{d}\mu^{*}$ for some $\mu^{*}\in\mathcal{P}(\mathcal{W})$ such that $\mathrm{d}\mu^{*}\propto e^{f}\mathrm{d}\tau$ for $f:\mathcal{W}\to\mathbb{R}$. Then, $\hat{\mathcal{J}}_{0}(\mu^{*})=0$ and $\mathcal{H}(\mu^{*}\,|\,\tau)\leq\int f(\mathrm{d}\mu^{*}-\mathrm{d}\tau)\leq
\mathrm{osc}(f)$ where $\operatorname{osc}(f)\coloneqq\sup f-\inf f$.

In the above result, the constants in
Assumption 4 can be identified as
$\bar{\varepsilon}=0$ and $\bar{\Delta}=\operatorname{osc}(f)$
which is
the oscillation of the log-density of $\mu^{*}$. Consequently, if the neurons in the teacher model are sufficiently present in all directions of the weight space, we get $\operatorname{osc}(f)=o(d)$; consider e.g. the extreme case $\mu^{*}=\tau$ which implies $f$ is constant.
Interestingly, in the case of $k$-multi-index models, this condition implies that $k$ grows with dimension, ruling out the case $k=\mathcal{O}(1)$.

For MFLD to converge to a minimizer of $\hat{\mathcal{J}}_{0}$, the parameter $\beta$ needs to satisfy $\beta\geq\tilde{\Omega}(\bar{\Delta})$ to ensure the entropic regularization is not the dominant term in the objective $\mathcal{F}_{\beta}$. In the Euclidean setting, this implies an LSI constant of order $\exp(\tilde{\mathcal{O}}(\bar{\Delta}))$,
resulting in a computational complexity
$\exp(\tilde{\mathcal{O}}(\bar{\Delta}))$ as shown in Theorem 3.
In what follows, we demonstrate via the Bakry-Émery theory [] that in the Riemmanian setting, under a uniform lower bound on the Ricci curvature, the LSI constant can be independent of $\bar{\Delta}$ and $d$ as long as we have $\bar{\Delta}=o(d)$.

###### Proposition 9 .

Suppose Assumption 4 holds and the loss $\rho$ is $C_{\rho}$-Lipschitz. Then, for all $\mu\in\mathcal{P}(\mathcal{W})$ and $\beta<{\varrho d}/{C_{\rho}K}$, the probability measure $\nu_{\mu}\propto\exp(-\beta\hat{\mathcal{J}}_{0}^{\prime}[\mu])$ satisfies the LSI with constant

$$ $C_{\mathrm{LSI}}\leq(\varrho d-\beta C_{\rho}K)^{-1},$ (4.1) $$

where
$K=\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|_{\mathfrak{g}
}=1}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}
\left|{\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\nabla^{2}_{
\boldsymbol{w}}\Psi(\boldsymbol{x};\boldsymbol{w})\boldsymbol{v}}}\right
\rangle}}\right|}\right]$,
and $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\cdot}\right]$ denotes the expectation under empirical data distribution over $n$ samples.

Remark.
In the setting of Example 7 with $n\geq\tilde{\Omega}(\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})/
\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|)$, we have $K\lesssim\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|$ with probability at least $1-\mathcal{O}(n^{-q})$ for some constant $q>0$.
Consequently, the LSI constant is independent of $d$.

We can now present the following global convergence guarantee to the minimizer of $\mathcal{J}_{0}$ for large $d$.

###### Theorem 10 .

Suppose Assumption 4 holds, and let $K$ be as in Proposition 9. Let $(\mu_{t})_{t\geq 0}$ denote the law of the MFLD. For any $\varepsilon>0$, let $\beta={\bar{\Delta}}/{\varepsilon}$ and $d\geq{2C_{\rho}K\bar{\Delta}}/{\varrho\varepsilon}$. Then, we have

$$ $\hat{\mathcal{J}}_{0}(\mu_{T})\lesssim\bar{\varepsilon}+\varepsilon,\quad\text {whenever }\quad T\geq\frac{\bar{\Delta}}{\varepsilon\varrho d}\ln\mathopen{} \mathclose{{}\left(\frac{\mathcal{F}_{\beta}(\mu_{0})}{\varepsilon}}\right).$ (4.2) $$

Moreover, in the setting of Example 7 and for a $1$-Lipschitz loss function, if we have
$d\gtrsim{\bar{\Delta}}/{\varrho\varepsilon}$
and
$n\geq\Omega(\bar{\Delta}(1+\bar{\varepsilon}/\varepsilon)/\varepsilon^{2})\lor
\tilde{\Omega}(\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})/\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|)\vee\tilde{\Omega}(1/
\varepsilon^{4})$, then

$$ $\mathcal{J}_{0}(\mu_{T})\lesssim\bar{\varepsilon}+\varepsilon,\quad\text{ whenever }\quad T\geq\frac{\bar{\Delta}}{\varepsilon\varrho d}\ln\mathopen{} \mathclose{{}\left(\frac{\mathcal{F}_{\beta}(\mu_{0})}{\varepsilon}}\right),$ (4.3) $$

with probability at least $1-\mathcal{O}(n^{-q})$ over the randomness of data, for some constant $q>0$.

The sample complexity is controlled by the maximum of $\bar{\Delta}$ and ${\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})}/{\mathopen{}\mathclose{{}
\left\|{\boldsymbol{\Sigma}}}\right\|}$ up to log factors. We remark that dependence on $\varepsilon$ is not our main focus, and it may be possible to improve $1/\varepsilon^{4}$ with a more refined analysis. Remarkably, the time complexity improves in high dimensions, thanks to the effect of the Ricci curvature. While the above result is for the continuous-time infinite-width MFLD, the uniform-in-time propagation of chaos for MFLD
strongly suggests that the cost of time/width discretizations will be polynomial, see e.g. [] for the Euclidean setting, and [] for the time-discretization of the Langevin diffusion on the hypersphere under LSI.

To compare the setting of this section to that of Section 3, as explored in Appendix A, we remark that the Euclidean $\ell_{2}$ and entropic regularizations can be combined into a single effective regularizer of the form $\beta^{-1}\mathcal{H}(\mu\,|\,\gamma)$, where $\gamma=\mathcal{N}(0,(\lambda\beta)^{-1}\mathbf{I}_{2d+2})$; therefore, in the Euclidean setting, $\gamma$ plays the role of $\tau$.
Further in the proof of Lemma 20, we show that in the Euclidean setting, $\bar{\Delta}\asymp\lambda\beta/r_{x}^{2}$ and $\bar{\varepsilon}\asymp c_{x}/\sqrt{\lambda\beta}$; thus, to learn with any non-trivial accuracy, we have $\bar{\Delta}\asymp c_{x}^{2}/r_{x}^{2}=d_{\mathrm{eff}}$.
As discussed above, controlling the effect of entropic regularization necessitates $\beta\geq\tilde{\Omega}(\bar{\Delta})$. Unlike its Riemannian counterpart, the Euclidean LSI estimate of Proposition 2 scales with $\exp(\beta)$, ultimately resulting in a large computational gap between the two settings under the same $\bar{\Delta}$.
This leaves open the question of whether $\bar{\Delta}\asymp d_{\mathrm{eff}}$ can be achievable in the Riemannian setting for $k$-multi-index models with $k=\mathcal{O}(1)$, which is an interesting direction for future exploration.

###### Example 7 .

###### Assumption 4 .

###### Proposition 8 .

###### Proposition 9 .

###### Theorem 10 .

## 5 Conclusion

In this paper, we investigated the mean-field Langevin dynamics for learning multi-index models. We proved that the statistical and computational complexity of this problem can be characterized by an effective dimension which captures the low-dimensional structure in the input covariance, along with its correlation with the target directions. In particular, the sample complexity scales almost linearly with the effective dimension, while without additional assumptions, the computational complexity may scale exponentially with this quantity. Through this effective dimension, we showed both statistical and computational adaptivity of the MFLD to low-dimensions when training neural networks, outperforming rotationally invariant kernels and statistical query learners in terms of statistical complexity, and fixed-grid convex optimization methods in terms of computational complexity. Further, we studied conditions under which achieving a polynomial LSI in the inverse temperature, and subsequently a polynomial-in-$d$ runtime guarantee for the MFLD is possible. Specifically, we showed that under certain assumptions, which are verified for teacher models with diverse neurons, constraining the weights to a Riemannian manifold with positive Ricci curvature such as the hypersphere can lead to such polynomial dependence. In contrast, the same assumptions in the Euclidean setting result in an LSI constant scaling exponentially with the inverse temperature.

We conclude with some limitations of our work, along with future directions.

- •
Further assumptions are required to go beyond the current exponential computational complexity of the MFLD. We leave the study of such conditions as an important direction for future work.
- •
While we focused on $k=\mathcal{O}(1)$, the versatility of the MFLD analysis may allow us to let $k$ grow with dimension as in [, , ], or $g$ to exhibit a more complex hierarchical structure [, ]. Learning these functions with the MFLD is an interesting direction for future research.
- •
Another important future direction is developing lower bounds for learning multi-index models with gradient-based methods, under more realistic assumptions (e.g., non-adversarial noise) than the statistical query setup. These lower bounds can highlight when exponential computation is inevitable for optimal sample complexity, and present rigorous information-computation tradeoffs.

## Acknowledgments

The authors thank Lénaïc Chizat, Mufan (Bill) Li, Fanghui Liu, and Taiji Suzuki for useful discussions.
MAE was
partially supported by the NSERC Grant [2019-06167], the CIFAR AI Chairs program, and the CIFAR Catalyst grant.

## Appendix A Proofs of Section 3

Before presenting the layout of the proofs, we introduce a useful reformulation of the objective $\mathcal{F}_{\beta,\lambda}(\mu)$. Recall that

$$ $\mathcal{F}_{\beta,\lambda}(\mu)=\hat{\mathcal{J}}_{0}(\mu)+\frac{\lambda}{2} \mathcal{R}(\mu)+\frac{1}{\beta}\mathcal{H}(\mu).$ $$

Let $\gamma\propto\exp\big{(}\frac{-\lambda\beta}{2}\mathopen{}\mathclose{{}\left\|
{\boldsymbol{w}}}\right\|^{2}\big{)}$ be the centered Gaussian measure on $\mathbb{R}^{2d+2}$ with variance $1/(\lambda\beta)$. Then, we can rewrite the above as

$$ $\mathcal{F}_{\beta,\lambda}(\mu)=\hat{\mathcal{J}}_{0}(\mu)+\frac{1}{\beta} \mathcal{H}(\mu\,|\,\gamma)+\frac{d}{2\beta}\ln\mathopen{}\mathclose{{}\left( \frac{\lambda\beta}{2\pi}}\right).$ $$

As a result, we can define

$$ $\tilde{\mathcal{F}}_{\beta,\lambda}(\mu)\coloneqq\hat{\mathcal{J}}_{0}(\mu)+ \frac{1}{\beta}\mathcal{H}(\mu\,|\,\gamma),$ (A.1) $$

which is non-negative and equivalent to $\mathcal{F}_{\beta}$ up to an additive constant. Notice that

$$ $\mu^{*}_{\beta}\coloneqq\operatorname*{arg\,min}_{\mu}\mathcal{F}_{\beta, \lambda}(\mu)=\operatorname*{arg\,min}_{\mu}\tilde{\mathcal{F}}_{\beta,\lambda }(\mu).$ $$

This reformulation, which was also used in [], allows us to combine the effect of weight decay and entropic regularization into a single non-negative term $\mathcal{H}(\mu\,|\,\gamma)$. Furthermore, the simple density expression for the Gaussian measure $\gamma$ allows us to achieve useful estimates for $\mathcal{H}(\mu\,|\,\gamma)$. In particular, as we will show below, it is possible to control $\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)$ with effective dimension rather than ambient dimension, which leads to dependence on $d_{\mathrm{eff}}$ rather than $d$ in our bounds.

We break down the proof of Theorem 3 into three steps:

- 1.
In Section A.2 we show that there exists a measure $\mu^{*}\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ where $\hat{y}(\cdot;\mu^{*})$ can approximate $g$ on the training set with bounds on $\mathcal{R}(\mu^{*})$. This construction provides upper bounds on $\hat{\mathcal{J}}_{0}(\mu^{*}_{\beta})$ and $\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)$.
- 2.
In Section A.3, given the bound on $\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)$, we perform a generalization analysis via Rademacher complexity tools which leads to a bound on $\mathcal{J}_{0}(\mu^{*}_{\beta})$.
- 3.
Finally, in Section A.4, we estimate the LSI constant and constants related to smoothness/discretization along the trajectory, which imply that $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})$ converges to $\mathcal{F}_{\beta}(\mu^{*}_{\beta})$, where $\mathcal{F}^{m}_{\beta,\lambda}$ is an adjusted objective over $\mathcal{P}(\mathbb{R}^{(2d+2)m})$ defined in (A.6). This bound implies the convergence of $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose
{{}\left[J_{0}(\boldsymbol{W})}\right]$ to $\mathcal{J}_{0}(\mu^{*}_{\beta})$, which was bounded in the previous step.

Before laying out these steps, in Section A.1, we will introduce the required concentration results. In the following, we will use the unregularized population $\mathcal{J}_{0}(\mu)\coloneqq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}
\left[{\ell(\hat{y}(\boldsymbol{x};\mu),y)}}\right]$ and empirical $\hat{\mathcal{J}}_{0}(\mu)=\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[
\ell(\hat{y}(\boldsymbol{x};\mu),y)}\right]$ risks, and also consider the finite-width versions $J_{0}(\boldsymbol{W})\coloneqq\mathcal{J}_{0}(\mu_{\boldsymbol{W}})$ and $\hat{J}_{0}(\boldsymbol{W})\coloneqq\hat{\mathcal{J}}_{0}(\mu_{\boldsymbol{W}})$. Additionally, we will use $\phi_{\infty}(z)\coloneqq z\lor 0$ to denote the ReLU activation.

### A.1 Concentration Bounds

We begin by specifying the definition of subGaussian and subexponential random variables in our setting.

###### Definition 11 .

*[]*
A random variable $x$ is $\sigma$-subGaussian if $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{e^{\lambda(x-
\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{x}}\right])}}}\right]
\leq e^{\lambda^{2}\sigma^{2}/2}$ for all $\lambda\in\mathbb{R}$, and is $(\nu,\alpha)$-subexponential if $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{e^{\lambda(x-
\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{x}}\right])}}}\right]
\leq e^{\lambda^{2}\nu^{2}/2}$ for all $\mathopen{}\mathclose{{}\left|{\lambda}}\right|\leq 1/\alpha$. If $x$ is $\sigma$-subGaussian, then

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({x-\operatorname{\mathbb{E}}\mathopen{ }\mathclose{{}\left[{x}}\right]\geq t}}\right)\leq\exp\big{(}\frac{-t^{2}}{2 \sigma^{2}}\big{)}.$ (A.2) $$

If $x$ is $(\nu,\alpha)$-subexponential, then

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({x-\operatorname{\mathbb{E}}\mathopen{ }\mathclose{{}\left[{x}}\right]\geq t}}\right)\leq\exp\big{(}-\frac{1}{2}\min \big{(}\frac{t^{2}}{\nu^{2}},\frac{t}{\alpha}\big{)}\big{)}$ (A.3) $$

Moreover, for centered random variables, let $\mathopen{}\mathclose{{}\left|{\cdot}}\right|_{\psi_{2}}$ and $\mathopen{}\mathclose{{}\left|{\cdot}}\right|_{\psi_{1}}$ denote the subGaussian and subexponential norm respectively [, Definitions 2.5.6 and 2.7.5]. Then $x$ is $\sigma$-subGaussian if and only if $\sigma\asymp\mathopen{}\mathclose{{}\left|{x-\operatorname{\mathbb{E}}
\mathopen{}\mathclose{{}\left[{x}}\right]}}\right|_{\psi_{2}}$, and is $(\nu,\nu)$-subexponential if and only if $\nu\asymp\mathopen{}\mathclose{{}\left|{x-\operatorname{\mathbb{E}}\mathopen{}
\mathclose{{}\left[{x}}\right]}}\right|_{\psi_{1}}$.

Next, we bound several quantities that appear in various parts of our proofs.

###### Lemma 12 .

Under Assumption 1, for any $q>0$ and all $1\leq i\leq n$, with probability at least $1-n^{-q}$,

$$ $\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}^{(i)}}}\right\| \leq r_{x}\big{(}1+\sigma_{u}\sqrt{2(q+1)\ln n}\big{)}=\tilde{r}_{x}.$ (A.4) $$

Proof.
By subGaussianity of $\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|$ from Assumption 1 and the subGaussian tail bound, with probability at least $1-n^{-q-1}$

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}^{(i) }}}\right\|$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|}}\right ]+\sigma_{u}r_{x}\sqrt{2(q+1)\ln n}$ $\displaystyle=r_{x}+\sigma_{u}r_{x}\sqrt{2(q+1)\ln n}.$ $$

The statement of lemma follows from a union bound over $1\leq i\leq n$.
∎

###### Lemma 13 .

Under Assumption 1, we have $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left
\|{\boldsymbol{x}}}\right\|^{2}}\right]\lesssim c_{x}^{2}$ with probability at least $1-\exp(-\Omega(n))$.

Proof.
By the triangle inequality,

$$ $\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}} }\right\|}}\right|_{\psi_{2}}\leq\mathopen{}\mathclose{{}\left|{\mathopen{} \mathclose{{}\left\|{\boldsymbol{x}}}\right\|-\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}} }\right\|}}\right]}}\right|_{\psi_{2}}+\mathopen{}\mathclose{{}\left|{ \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{ {}\left\|{\boldsymbol{x}}}\right\|}}\right]}}\right|_{\psi_{2}}\lesssim\sigma_ {n}\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}^{1/2}}}\right\|_{ \mathrm{F}}+\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})^{1/2}\lesssim \mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})^{1/2}.$ $$

Recall $c_{x}^{2}\coloneqq\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma})$. Furthermore, by [, Lemma 2.7.6] we have

$$ $\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}} }\right\|^{2}}}\right|_{\psi_{1}}=\mathopen{}\mathclose{{}\left|{\mathopen{} \mathclose{{}\left\|{\boldsymbol{x}}}\right\|}}\right|_{\psi_{2}}^{2}\lesssim c _{x}^{2}.$ $$

We arrive at a similar result for the centered random variable $\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}}}\right\|^{2}-\operatorname{
\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{
\boldsymbol{x}}}\right\|}}\right]^{2}=\mathopen{}\mathclose{{}\left\|{
\boldsymbol{x}}}\right\|^{2}-c_{x}^{2}$. We conclude the proof by the subexponential tail inequality,

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({\mathbb{E}_{S_{n}}\mathopen{} \mathclose{{}\left[\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}}}\right\|^{2 }}\right]-c_{x}^{2}\geq tc_{x}^{2}}}\right)\leq\exp(-\min(t,t^{2})\Omega(n)).$ $$

∎

###### Lemma 14 .

Under Assumption 1, we have $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[y^{2}}\right]\lesssim 1$ with probability at least $1-2\exp(-\Omega(n))$.

Proof.
We have

$$ $\mathopen{}\mathclose{{}\left|{y}}\right|^{2}\leq 3g(0)^{2}+3\mathcal{O}(1/r_{ x}^{2})\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|^ {2}+3\xi^{2}.$ $$

By a similar argument to Lemma 13 we have

$$ $\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\|{\boldsymbol{U} \boldsymbol{x}}}\right\|^{2}}}\right|_{\psi_{1}}=\mathopen{}\mathclose{{}\left |{\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|}} \right|_{\psi_{2}}^{2}\leq 2\mathopen{}\mathclose{{}\left|{\mathopen{} \mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|-\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{U}\boldsymbol{x}}}\right\|}}\right]}}\right|_{\psi_{2}}^{2}+2 \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{ {}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|}}\right]^{2}\lesssim(1+\sigma _{u}^{2})r_{x}^{2},$ $$

since $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|^{2}}}\right]=r_{x}^{2}$. As a result, by the subexponential tail bound,

$$ $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left \|{\boldsymbol{U}\boldsymbol{x}}}\right\|^{2}}\right]-\operatorname{\mathbb{E} }\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{\boldsymbol{U} \boldsymbol{x}}}\right\|^{2}}}\right]\lesssim(1+\sigma_{u}^{2})r_{x}^{2} \lesssim r_{x}^{2},$ $$

with probability at least $1-\exp(-\Omega(n))$. Similarly, $\mathopen{}\mathclose{{}\left|{\xi^{2}}}\right|_{\psi_{1}}\leq\mathopen{}
\mathclose{{}\left|{\xi}}\right|_{\psi_{2}}^{2}\lesssim\varsigma^{2}$, therefore,

$$ $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\xi^{2}}\right]-\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{\xi^{2}}}\right]\lesssim\varsigma^{2 }\lesssim 1,$ $$

with probability at least $1-\exp(-\Omega(n))$. The statement of the lemma follows by a union bound.
∎

###### Lemma 15 .

Under Assumption 1, for any $q>0$ and $n\gtrsim\tfrac{c_{x}^{2}}{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}
}\right\|}(1+\sigma_{n}^{2}(q+1)\ln(n))\ln(dn^{q})$, with probability at least $1-\mathcal{O}(n^{-q})$ we have $\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}
\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|$. Further, if $q\geq 1$, then $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\boldsymbol{x}
\boldsymbol{x}^{\top}}\right]}}\right\|^{1/2}}}\right]\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|^{1/2}$.

Proof.
First, note that by subGaussianity of $\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}}}\right\|$, for every fixed $i$, we have with probability at least $1-n^{-q-1}$,

$$ $\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}^{(i)}}}\right\|-\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{x}}}\right\|}}\right]\leq\sigma_{n}\mathopen{}\mathclose{{}\left\| {\boldsymbol{\Sigma}^{1/2}}}\right\|_{\mathrm{F}}\sqrt{2(q+1)\ln n}.$ $$

Since $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\boldsymbol{x}}}\right\|}}\right]\leq c_{x}$, via a union bound, with probability at least $1-n^{-q}$,

$$ $\mathopen{}\mathclose{{}\left\|{\boldsymbol{x}^{(i)}}}\right\|\leq c_{x}+ \sigma_{n}c_{x}\sqrt{2(q+1)\ln n}\eqqcolon\tilde{c}_{x}.$ $$

Define the clipped version of $\boldsymbol{x}$ via $\boldsymbol{x}_{c}=\boldsymbol{x}(1\land\tfrac{\tilde{c}_{x}}{\mathopen{}
\mathclose{{}\left\|{\boldsymbol{x}}}\right\|})$. Then, on the above event,

$$ $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\boldsymbol{x}\boldsymbol{x}^{ \top}}\right]=\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\boldsymbol{x}_{ c}\boldsymbol{x}_{c}^{\top}}\right].$ $$

Moreover,

$$ $\mathopen{}\mathclose{{}\left\|{\operatorname{\mathbb{E}}\mathopen{}\mathclose {{}\left[{\boldsymbol{x}_{c}\boldsymbol{x}_{c}^{\top}}}\right]}}\right\|=\sup_ {\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|\leq 1}\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\langle {\boldsymbol{x}_{c}},{\boldsymbol{v}}}\right\rangle^{2}}}\right]\leq\sup_{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|\leq 1}\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\langle {\boldsymbol{x}},{\boldsymbol{v}}}\right\rangle^{2}}}\right]=\mathopen{} \mathclose{{}\left\|{\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \boldsymbol{x}\boldsymbol{x}^{\top}}}\right]}}\right\|.$ $$

Finally, by the covariance estimation bound of [, Corollary 6.20] for centered subGaussian random vectors and the condition on $n$ given in the statement of the lemma,

$$ $\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\boldsymbol{x}_{c}\boldsymbol{x}_{c}^{\top}}\right]}}\right\|-\mathopen{ }\mathclose{{}\left\|{\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \boldsymbol{x}_{c}\boldsymbol{x}_{c}^{\top}}}\right]}}\right\|\lesssim \mathopen{}\mathclose{{}\left\|{\operatorname{\mathbb{E}}\mathopen{}\mathclose {{}\left[{\boldsymbol{x}\boldsymbol{x}^{\top}}}\right]}}\right\|$ $$

with probability at least $1-\mathcal{O}(n^{-q})$. Consequently, we have $\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}
\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|$ with probability at least $1-\mathcal{O}(n^{-q})$.

For the second part of the lemma, let $E$ denote the event on which the above $\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}
\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|$ holds. Then,

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen {}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[ \boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|^{1/2}}}\right]$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathbbm {1}(E)\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{ {}\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|^{1/2}}}\right]+ \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathbbm{1}(E^{C}) \mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|^{1/2}}}\right]$ $\displaystyle\lesssim\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}} \right\|^{1/2}+\mathbb{P}\mathopen{}\mathclose{{}\left({E^{C}}}\right)^{1/2} \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{ {}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\boldsymbol{x} \boldsymbol{x}^{\top}}\right]}}\right\|}}\right]^{1/2}$ $\displaystyle\lesssim\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}} \right\|^{1/2}+\mathcal{O}(n^{-q/2})c_{x}.$ $$

Suppose $q\geq 1$. Then for $n\gtrsim c^{2}_{x}/\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|$, we have $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\boldsymbol{x}
\boldsymbol{x}^{\top}}\right]}}\right\|^{1/2}}}\right]\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|^{1/2}$, which completes the proof.
∎

We summarize the above results into a single event.

###### Lemma 16 .

Suppose $n\gtrsim\tfrac{c_{x}^{2}}{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}
}\right\|}(1+\sigma_{n}^{2}(q+1)\ln(n))\ln(dn^{q})$. There exists an event $\mathcal{E}$ such that $\mathbb{P}\mathopen{}\mathclose{{}\left({\mathcal{E}}}\right)\geq 1-\mathcal{O
}(n^{-q})$, and on $\mathcal{E}$:

- 1.
$\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}^{(i)}}}\right\|
\leq\tilde{r}_{x}$ for all $1\leq i\leq n$.
- 2.
$\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left
\|{\boldsymbol{x}}}\right\|^{2}}\right]\lesssim c_{x}^{2}$.
- 3.
$\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}
\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}}\right\|\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|$.
- 4.
$\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\boldsymbol{x}
\boldsymbol{x}^{\top}}\right]}}\right\|^{1/2}}}\right]\lesssim\mathopen{}
\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|^{1/2}$.
- 5.
$\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[y^{2}}\right]\lesssim 1$.

We recall the variational lower bound for the KL divergence, which will be used at various stages of different proofs to relate certain expectations to the KL divergence.

###### Lemma 17 (Donsker-Varadhan Variational Formula for KL Divergence [ 34 ] ) .

Let $\mu$ and $\nu$ be probability measures on $\mathcal{W}$. Then,

$$ $\mathcal{H}(\mu\,|\,\nu)=\sup_{f:\mathcal{W}\to\mathbb{R}}\int f\mathrm{d}\mu- \ln\mathopen{}\mathclose{{}\left(\int e^{f}\mathrm{d}\nu}\right).$ $$

Finally, we state the following lemma which will be useful in estimating smoothness constants in the convergence analysis.

###### Lemma 18 .

Suppose $(z,\boldsymbol{x})\in\mathbb{R}\times\mathbb{R}^{d}$ are drawn from a probability distribution $\mathcal{D}$. Then,

$$ $\mathopen{}\mathclose{{}\left\|{\operatorname{\mathbb{E}}_{\mathcal{D}} \mathopen{}\mathclose{{}\left[z\boldsymbol{x}}\right]}}\right\|\leq\sqrt{ \operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{}\mathclose{{}\left[z^{2}} \right]\mathopen{}\mathclose{{}\left\|{\operatorname{\mathbb{E}}_{\mathcal{D}} \mathopen{}\mathclose{{}\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]}} \right\|}.$ $$

Proof.
We have

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\operatorname{\mathbb{E}}_{ \mathcal{D}}\mathopen{}\mathclose{{}\left[z\boldsymbol{x}}\right]}}\right\|= \sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|\leq 1}\mathopen {}\mathclose{{}\left\langle{\boldsymbol{v}},{\operatorname{\mathbb{E}}_{ \mathcal{D}}\mathopen{}\mathclose{{}\left[z\boldsymbol{x}}\right]}}\right\rangle$ $\displaystyle=\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\| \leq 1}\operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{}\mathclose{{}\left[z \mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\boldsymbol{x}}}\right \rangle}\right]$ $\displaystyle\leq\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right \|\leq 1}\sqrt{\operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{}\mathclose{{} \left[z^{2}}\right]\operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{} \mathclose{{}\left[\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{ \boldsymbol{x}}}\right\rangle^{2}}\right]}\quad\text{(Cauchy-Schwartz)}$ $\displaystyle\leq\sqrt{\operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{} \mathclose{{}\left[z^{2}}\right]\sup_{\mathopen{}\mathclose{{}\left\|{ \boldsymbol{v}}}\right\|\leq 1}\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{}\mathclose{ {}\left[\boldsymbol{x}\boldsymbol{x}^{\top}}\right]\boldsymbol{v}}}\right\rangle}$ $\displaystyle=\sqrt{\operatorname{\mathbb{E}}_{\mathcal{D}}\mathopen{} \mathclose{{}\left[z^{2}}\right]\mathopen{}\mathclose{{}\left\|{\operatorname{ \mathbb{E}}_{\mathcal{D}}\mathopen{}\mathclose{{}\left[\boldsymbol{x} \boldsymbol{x}^{\top}}\right]}}\right\|}.$ $$

∎

Notice that the distribution $\mathcal{D}$ can be both the empirical as well as the population distribution.

###### Definition 11 .

###### Lemma 12 .

###### Lemma 13 .

###### Lemma 14 .

###### Lemma 15 .

###### Lemma 16 .

###### Lemma 17 (Donsker-Varadhan Variational Formula for KL Divergence [ 34 ] ) .

###### Lemma 18 .

### A.2 Approximating the Target Function

We begin by stating the following approximation lemma which is the result of [, Proposition 6] adapted to our setting.

###### Proposition 19 .

Suppose $g:\mathbb{R}^{k}\to\mathbb{R}$ is $L$-Lipschitz and $\mathopen{}\mathclose{{}\left|{g(0)}}\right|=\mathcal{O}(L\tilde{r}_{x})$. On the event of Lemma 16, there exists a measure $\mu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ with $\mathcal{R}(\mu)\leq\Delta^{2}/\tilde{r}_{x}^{2}$ such that

$$ $\max_{i}\mathopen{}\mathclose{{}\left|{g(\boldsymbol{U}\boldsymbol{x}^{(i)})- \hat{y}(\boldsymbol{x}^{(i)};\mu)}}\right|\leq C_{k}L\tilde{r}_{x}\Big{(}\frac {\Delta}{L\tilde{r}_{x}}\Big{)}^{\frac{-2}{k+1}}\ln\Big{(}\frac{\Delta}{L \tilde{r}_{x}}\Big{)}+\frac{\ln 4}{\kappa},$ $$

for all $\Delta\geq C_{k}$, where $C_{k}$ is a constant depending only on $k$, provided that the hyperparameter $\iota$ satisfies $\iota\geq C_{k}L\tilde{r}_{x}\Big{(}\frac{\Delta}{L\tilde{r}_{x}}\Big{)}^{2k/(
k+1)}$.

Proof.
Throughout the proof, we will use $C_{k}$ to denote a constant that only depends on $k$, whose value may change across instantiations.
Let $\boldsymbol{z}\coloneqq\boldsymbol{U}\boldsymbol{x}\in\mathbb{R}^{k}$ and $\tilde{\boldsymbol{z}}\coloneqq(\boldsymbol{z}^{\top},\tilde{r}_{x})^{\top}\in
\mathbb{R}^{k+1}$. Recall that on the event of Lemma 12 we have $\|\boldsymbol{z}^{(i)}\|\leq\tilde{r}_{x}$ and $|g(\boldsymbol{z}^{(i)})|\lesssim L\tilde{r}_{x}$ for all $1\leq i\leq n$. Let $\tau$ denote the uniform probability measure on $\mathbb{S}^{k}$. By [, Proposition 6], for all $\Delta\geq C_{k}$, there exists $p\in L^{2}(\tau)$ with $\mathopen{}\mathclose{{}\left\|{p}}\right\|_{L^{2}(\tau)}\leq\Delta$ such that

$$ $\max_{i}\mathopen{}\mathclose{{}\left|{g(\boldsymbol{z}^{(i)})-\int_{\mathbb{S }^{k}}p(\boldsymbol{v})\phi_{\infty}\Big{(}\frac{1}{\tilde{r}_{x}}\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}},{\tilde{\boldsymbol{z}}^{(i)}}} \right\rangle\Big{)}\mathrm{d}\tau(\boldsymbol{v})}}\right|\leq C_{k}L\tilde{r }_{x}\big{(}\frac{\Delta}{L\tilde{r}_{x}}\big{)}^{\frac{-2}{k+1}}\ln\big{(} \frac{\Delta}{L\tilde{r}_{x}}\big{)}.$ $$

In fact, we have a stronger guarantee on $p$. Specifically, $p(\boldsymbol{v})$ is given by

$$ $p(\boldsymbol{v})=\sum_{j\geq 1}\lambda_{j}^{-1}r^{j}h_{j}(\boldsymbol{v}),$ $$

where $r\in(0,1),\lambda_{j},h_{j}:\mathbb{S}^{k}\to\mathbb{R}$ are introduced by [, Appendix D]. In particular,

$$ $h(\boldsymbol{v})=g\Big{(}\frac{\tilde{r}_{x}\boldsymbol{v}_{1:k}}{\boldsymbol {v}_{k+1}}\Big{)}\boldsymbol{v}_{k+1},$ $$

with the spheircal harmonics decomposition $h(\boldsymbol{v})=\sum_{j\geq 0}h_{j}(\boldsymbol{v})$.
It is shown in [, Appendix D.2] that $\lambda_{j}\leq C_{k}j^{(k+1)/2}$, and one can prove through spherical harmonics calculations (omitted here for brevity) that $\mathopen{}\mathclose{{}\left|{h_{j}(\boldsymbol{v})}}\right|\leq C_{k}\sup_{
\boldsymbol{v}\in\mathbb{S}^{k}}h(\boldsymbol{v})j^{(k-1)/2}\leq C_{k}L\tilde{
r}_{x}j^{(k-1)/2}$.
As a result,

$$ $\displaystyle\mathopen{}\mathclose{{}\left|{p(\boldsymbol{v})}}\right|\leq\sum _{j\geq 0}\lambda_{j}^{-1}r^{j}\mathopen{}\mathclose{{}\left|{h_{j}( \boldsymbol{v})}}\right|\leq\sum_{j\geq 1}\lambda_{j}^{-1}r^{j}\mathopen{} \mathclose{{}\left|{h_{j}(\boldsymbol{v})}}\right|\leq C_{k}L\tilde{r}_{x}\sum _{j\geq 1}j^{k}r^{j}\leq\frac{C_{k}L\tilde{r}_{x}}{(1-r)^{k}}.$ $$

Using $1-r=\Big{(}C_{k}L\tilde{r}_{x}/\Delta\Big{)}^{2/(k+1)}$ as in [, Appendix D.4] yields

$$ $\mathopen{}\mathclose{{}\left|{p(\boldsymbol{v})}}\right|\leq C_{k}L\tilde{r}_ {x}\Big{(}\frac{\Delta}{L\tilde{r}_{x}}\Big{)}^{2k/(k+1)}.$ $$

Define $p_{+}(\boldsymbol{v})\coloneqq p(\boldsymbol{v})\lor 0$ and $p_{-}(\boldsymbol{v})\coloneqq(-p(\boldsymbol{v}))\lor 0$. Then, by positive 1-homogeneity of ReLU,

$$ $\displaystyle\int_{\mathbb{S}^{k}}p(\boldsymbol{v})\phi_{\infty}\Big{(}\frac{1 }{\tilde{r}_{x}}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\tilde{ \boldsymbol{z}}}}\right\rangle\Big{)}\mathrm{d}\tau(\boldsymbol{v})$ $\displaystyle=\int_{\mathbb{S}^{k}}p_{+}(\boldsymbol{v})\phi_{\infty}\Big{(} \frac{1}{\tilde{r}_{x}}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{ \tilde{\boldsymbol{z}}}}\right\rangle\Big{)}\mathrm{d}\tau(\boldsymbol{v})- \int_{\mathbb{S}^{k}}p_{-}(\boldsymbol{v})\phi_{\infty}\Big{(}\frac{1}{\tilde{ r}_{x}}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\tilde{ \boldsymbol{z}}}}\right\rangle\Big{)}\mathrm{d}\tau(\boldsymbol{v})$ $\displaystyle=\int_{\mathbb{S}^{k}}\phi_{\infty}\Big{(}\frac{p_{+}(\boldsymbol {v})}{\tilde{r}_{x}}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{ \tilde{\boldsymbol{z}}}}\right\rangle\Big{)}\mathrm{d}\tau(\boldsymbol{v})- \int_{\mathbb{S}^{k}}\phi_{\infty}\Big{(}\frac{p_{-}(\boldsymbol{v})}{\tilde{r }_{x}}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\tilde{\boldsymbol {z}}^{(i)}}}\right\rangle\Big{)}\mathrm{d}\tau(\boldsymbol{v})$ $\displaystyle=\int_{\mathbb{\mathbb{R}}^{k+1}}\phi_{\infty}(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{v}},{\tilde{\boldsymbol{z}}}}\right \rangle)\mathrm{d}\tilde{\mu}_{1}(\boldsymbol{v})-\int_{\mathbb{\mathbb{R}}^{k +1}}\phi_{\infty}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{v}},{\tilde {\boldsymbol{z}}}}\right\rangle)\mathrm{d}\tilde{\mu}_{2}(\boldsymbol{v})$ $\displaystyle=\int_{\mathbb{\mathbb{R}}^{d+1}}\phi_{\infty}(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{w}},{\tilde{\boldsymbol{x}}}}\right \rangle)\mathrm{d}\mu_{1}(\boldsymbol{w})-\int_{\mathbb{\mathbb{R}}^{d+1}}\phi _{\infty}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\tilde{ \boldsymbol{x}}}}\right\rangle)\mathrm{d}\mu_{2}(\boldsymbol{w}),$ $$

where $\tilde{\mu}_{1}\coloneqq\frac{(\cdot)p_{+}(\cdot)}{\tilde{r}_{x}}\#\tau$ and $\tilde{\mu}_{2}\coloneqq\frac{(\cdot)p_{-}(\cdot)}{\tilde{r}_{x}}\#\tau$ are the corresponding pushforward measures, $\mu_{1}=T_{\boldsymbol{U}}\#\tilde{\mu}_{1}$ and $\mu_{2}=T_{\boldsymbol{U}}\#\tilde{\mu}_{2}$, where $T_{\boldsymbol{U}}(\boldsymbol{v})=(\boldsymbol{U}^{\top}\boldsymbol{v}_{k},v_
{k+1})^{\top}\in\mathbb{R}^{d+1}$ for $\boldsymbol{v}=(\boldsymbol{v}_{k}^{\top},v_{k+1})^{\top}\in\mathbb{R}^{k+1}$. In other words, $\boldsymbol{w}\sim\mu_{1}$ is generated by sampling $\boldsymbol{v}\sim\tilde{\mu}_{1}$ and letting $\boldsymbol{w}=(\boldsymbol{U}^{\top}\boldsymbol{v}_{k},v_{k+1})^{\top}$, with a similar procedure for $\boldsymbol{w}\sim\mu_{2}$.
Furthermore,

$$ $\displaystyle\mathcal{R}(\mu)=\int_{\mathbb{R}^{d+1}}\mathopen{}\mathclose{{} \left\|{\boldsymbol{w}}}\right\|^{2}\mathrm{d}\mu_{1}(\boldsymbol{w})+\int_{ \mathbb{R}^{d+1}}\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|^{2} \mathrm{d}\mu_{2}(\boldsymbol{w})$ $\displaystyle=\int_{\mathbb{R}^{k+1}}\mathopen{}\mathclose{{}\left\|{ \boldsymbol{v}}}\right\|^{2}\mathrm{d}\tilde{\mu}_{1}(\boldsymbol{v})+\int_{ \mathbb{R}^{k+1}}\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|^{2} \mathrm{d}\tilde{\mu}_{2}(\boldsymbol{v})$ $\displaystyle=\int_{\mathbb{S}^{k}}\frac{p(\boldsymbol{v})^{2}}{\tilde{r}_{x}^ {2}}\mathrm{d}\tau(\boldsymbol{v})\leq\frac{\Delta^{2}}{\tilde{r}_{x}^{2}}.$ $$

The last step is to replace $\phi_{\infty}$ with $\phi_{\kappa,\iota}$. Note that for all $i$, and almost surely over $\boldsymbol{w}\sim\mu_{1}$, we have $\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{
\boldsymbol{w}},{\tilde{\boldsymbol{x}}^{(i)}}}\right\rangle}}\right|\leq p_{+
}(\boldsymbol{v})\leq C_{k}L\tilde{r}_{x}\Big{(}\frac{\Delta}{L\tilde{r}_{x}}
\Big{)}^{2k/(k+1)}$, with a similar bound holding for $\boldsymbol{w}\sim\mu_{2}$. As a result, by choosing $\iota\geq C_{k}L\tilde{r}_{x}\Big{(}\frac{\Delta}{L\tilde{r}_{x}}\Big{)}^{2k/(
k+1)}$, we have $\phi_{\varkappa,\iota}\Big{(}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{
w}},{\tilde{\boldsymbol{x}}^{(i)}}}\right\rangle\Big{)}=\phi_{\varkappa}\Big{(
}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\tilde{\boldsymbol{x}}^
{(i)}}}\right\rangle\Big{)}$ for all $i$ and almost surely over $\boldsymbol{w}\sim\mu_{1}$ and $\boldsymbol{w}\sim\mu_{2}$.
By the triangle inequality, we have

$$ $\displaystyle\mathopen{}\mathclose{{}\left|{g(\boldsymbol{U}\boldsymbol{x}^{(i )})-\hat{y}(\boldsymbol{x}^{(i)};\mu)}}\right|\leq$ $\displaystyle\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\{ \int\phi_{\kappa,\iota}\Big{(}\mathopen{}\mathclose{{}\left\langle{\boldsymbol {w}},{\tilde{\boldsymbol{x}}^{(i)}}}\right\rangle\Big{)}-\phi_{\infty}\Big{(} \mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\tilde{\boldsymbol{x}}^{ (i)}}}\right\rangle\Big{)}}\right\}\mathrm{d}\mu_{1}(\boldsymbol{w})}}\right|$ $\displaystyle+\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\{ \int\phi_{\kappa,\iota}\Big{(}\mathopen{}\mathclose{{}\left\langle{\boldsymbol {w}},{\tilde{\boldsymbol{x}}^{(i)}}}\right\rangle\Big{)}-\phi_{\infty}\Big{(} \mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\tilde{\boldsymbol{x}}}} \right\rangle^{(i)}\Big{)}}\right\}\mathrm{d}\mu_{2}(\boldsymbol{w})}}\right|$ $\displaystyle+\mathopen{}\mathclose{{}\left|{g(\boldsymbol{U}\boldsymbol{x}^{( i)})-\int\phi_{\infty}\Big{(}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{ w}},{\tilde{\boldsymbol{x}}^{(i)}}}\right\rangle\Big{)}\mathopen{}\mathclose{{ }\left(\mathrm{d}\mu_{1}(\boldsymbol{w})-\mathrm{d}\mu_{2}(\boldsymbol{w})} \right)}}\right|$ $\displaystyle\leq$ $\displaystyle\frac{2\ln 2}{\kappa}+C_{k}L\tilde{r}_{x}\big{(}\frac{\Delta}{L \tilde{r}_{x}}\big{)}^{\frac{-2}{k+1}}\ln\big{(}\frac{\Delta}{L\tilde{r}_{x}} \big{)},$ $$

which completes the proof.
∎

Next, we control the effect of entropic regularization on the minimum of $\tilde{\mathcal{F}}_{\beta,\lambda}$ via the following lemma.

###### Lemma 20 .

Suppose $\rho$ is $C_{\rho}$ Lipschitz. For every $\mu^{*}\in\mathcal{P}(\mathbb{R}^{2d+2})$, we have

$$ $\min_{\mu\in\mathcal{P}^{\mathrm{ac}}(\mathbb{R}^{2d+2})}\tilde{\mathcal{F}}_{ \beta,\lambda}(\mu)\leq\hat{\mathcal{J}}_{0}(\mu^{*})+\frac{\lambda}{2} \mathcal{R}(\mu^{*})+\frac{2\sqrt{2}C_{\rho}}{\sqrt{\pi\lambda\beta}}\mathbb{E }_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left\|{\tilde{ \boldsymbol{x}}}}\right\|}\right].$ $$

Proof.
We will smooth $\mu^{*}$ by convoliving it with $\gamma$, i.e. we consider $\mu=\mu^{*}*\gamma$. Let $\boldsymbol{u}\sim\gamma$ independent of $\boldsymbol{w}\sim\mu^{*}$ and denote $\boldsymbol{u}=(\boldsymbol{u}_{1}^{\top},\boldsymbol{u}_{2}^{\top})^{\top}$ with $\boldsymbol{u}_{1},\boldsymbol{u}_{2}\in\mathbb{R}^{d+1}$. We first bound $\hat{\mathcal{J}}_{0}(\mu^{*}*\gamma)$. Using the Lipschitzness of the loss and of $\phi_{\kappa,\iota}$, we have

$$ $\displaystyle\hat{\mathcal{J}}_{0}(\mu^{*}*\gamma)-\hat{\mathcal{J}}_{0}(\mu^{ *})=$ $\displaystyle\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\ell\Big{(}\int \Psi(\boldsymbol{x};\boldsymbol{w})\mathrm{d}(\mu^{*}*\gamma)(\boldsymbol{w})- y\Big{)}-\ell\Big{(}\int\Psi(\boldsymbol{x};\boldsymbol{w})\mathrm{d}\mu^{*}( \boldsymbol{w})-y\Big{)}}\right]$ $\displaystyle\leq$ $\displaystyle C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[ \mathopen{}\mathclose{{}\left|{\int\Psi(\boldsymbol{x};\boldsymbol{w})\mathrm{ d}(\mu^{*}*\gamma)(\boldsymbol{w})-\int\Psi(\boldsymbol{x};\boldsymbol{w}) \mathrm{d}\mu^{*}(\boldsymbol{w})}}\right|}\right]$ $\displaystyle=$ $\displaystyle C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[ \mathopen{}\mathclose{{}\left|{\int(\operatorname{\mathbb{E}}_{\boldsymbol{u}} \mathopen{}\mathclose{{}\left[\Psi(\boldsymbol{x};\boldsymbol{w}+\boldsymbol{u })}\right]-\Psi(\boldsymbol{x};\boldsymbol{w}))\mathrm{d}\mu^{*}(\boldsymbol{w })}}\right|}\right]$ $\displaystyle\leq$ $\displaystyle C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\int \operatorname{\mathbb{E}}_{\boldsymbol{u}}\mathopen{}\mathclose{{}\left[ \mathopen{}\mathclose{{}\left|{\phi_{\kappa,\iota}(\mathopen{}\mathclose{{} \left\langle{\boldsymbol{\omega}_{1}+\boldsymbol{u}_{1}},{\tilde{\boldsymbol{x }}}}\right\rangle)-\phi_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle)}}\right|} \right]\mathrm{d}\mu^{*}(\boldsymbol{w})}\right]$ $\displaystyle+C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\int \operatorname{\mathbb{E}}_{\boldsymbol{u}}\mathopen{}\mathclose{{}\left[ \mathopen{}\mathclose{{}\left|{\phi_{\kappa,\iota}(\mathopen{}\mathclose{{} \left\langle{\boldsymbol{\omega}_{2}+\boldsymbol{u}_{2}},{\tilde{\boldsymbol{x }}}}\right\rangle)-\phi_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}_{2}},{\tilde{\boldsymbol{x}}}}\right\rangle)}}\right|} \right]\mathrm{d}\mu^{*}(\boldsymbol{w})}\right]$ $\displaystyle\leq$ $\displaystyle C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\int \mathopen{}\mathclose{{}\left\{\operatorname{\mathbb{E}}_{\boldsymbol{u}_{1}} \mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left|{\mathopen{} \mathclose{{}\left\langle{\boldsymbol{u}_{1}},{\tilde{\boldsymbol{x}}}}\right \rangle}}\right|}\right]+\operatorname{\mathbb{E}}_{\boldsymbol{u}_{2}} \mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left|{\mathopen{} \mathclose{{}\left\langle{\boldsymbol{u}_{2}},{\tilde{\boldsymbol{x}}}}\right \rangle}}\right|}\right]}\right\}\mathrm{d}\mu^{*}(\boldsymbol{\omega})}\right]$ $\displaystyle=$ $\displaystyle\frac{2\sqrt{2}C_{\rho}}{\sqrt{\pi\lambda\beta}}\mathbb{E}_{S_{n} }\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left\|{\tilde{ \boldsymbol{x}}}}\right\|}\right].$ $$

Next, we bound the KL divergence via its convexity in the first argument,

$$ $\mathcal{H}(\mu^{*}*\gamma\,|\,\gamma)=\mathcal{H}\mathopen{}\mathclose{{} \left(\int\gamma(\cdot-\boldsymbol{w}^{\prime})\mathrm{d}\mu^{*}(\boldsymbol{w }^{\prime})\,|\,\gamma}\right)\leq\int\mathcal{H}(\gamma(\cdot-\boldsymbol{w}^ {\prime})\,|\,\gamma(\cdot))\mathrm{d}\mu^{*}(\boldsymbol{w}^{\prime}).$ $$

Furthermore,

$$ $\mathcal{H}(\gamma(\cdot-\boldsymbol{w}^{\prime})\,|\,\gamma(\cdot))=\int\frac {\lambda\beta}{2}\big{(}-\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}- \boldsymbol{w}^{\prime}}}\right\|^{2}+\mathopen{}\mathclose{{}\left\|{ \boldsymbol{w}}}\right\|^{2}\big{)}\gamma(\mathrm{d}\boldsymbol{w}-\boldsymbol {w}^{\prime})=\frac{\lambda\beta\mathopen{}\mathclose{{}\left\|{\boldsymbol{w} ^{\prime}}}\right\|^{2}}{2}.$ $$

Consequently,

$$ $\mathcal{H}(\mu^{*}*\gamma\,|\,\gamma)\leq\frac{\lambda\beta}{2}\mathcal{R}( \mu^{*}),$ $$

which finishes the proof.
∎

Combining above results, we have the following statement.

###### Corollary 21 .

Suppose the event of Lemma 16 holds, $\rho$ is $C_{\rho}$ Lipschitz, and $\lambda\lesssim 1$. Then,

$$ $\min_{\mu\in\mathcal{P}^{\mathrm{ac}}(\mathbb{R}^{2d+2})}\tilde{\mathcal{F}}_{ \beta,\lambda}(\mu)-\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho(\xi)} \right]\lesssim C_{\rho}\frac{\tilde{r}_{x}}{r_{x}}\mathopen{}\mathclose{{} \left(\frac{r_{x}\Delta}{\tilde{r}_{x}}}\right)^{\frac{-2}{k+1}}\ln\mathopen{} \mathclose{{}\left(\frac{r_{x}\Delta}{\tilde{r}_{x}}}\right)+\frac{C_{\rho}}{ \kappa}+\frac{\lambda\Delta^{2}}{\tilde{r}_{x}^{2}}+\frac{C_{\rho}(c_{x}+ \tilde{r}_{x})}{\sqrt{\lambda\beta}},$ $$

for all $\Delta\geq C_{k}$, provided that $\iota\geq C_{k}\Delta^{2k/(k+1)}(r_{x}/\tilde{r}_{x})^{(k-1)/(k+1)}$.

Proof.
We will use Lemma 20 with $\mu^{*}\in\mathcal{P}(\mathbb{R}^{2d+2})$ constructed in Proposition 19. Then, for all $\Delta\geq C_{k}$,

$$ $\displaystyle\hat{\mathcal{J}}_{0}(\mu^{*})$ $\displaystyle=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\rho( \hat{y}(\boldsymbol{x};\mu^{*})-y)}}\right]$ $\displaystyle=\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho(\hat{y}( \boldsymbol{x};\mu^{*})-g(\boldsymbol{U}\boldsymbol{x})-\xi)}\right]$ $\displaystyle\leq\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho(\xi)} \right]+C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{} \mathclose{{}\left|{\hat{y}(\boldsymbol{x};\mu^{*})-g(\boldsymbol{U} \boldsymbol{x})}}\right|}\right]$ $\displaystyle\leq\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho(\xi)} \right]+C_{k}C_{\rho}\frac{\tilde{r}_{x}}{r_{x}}\mathopen{}\mathclose{{}\left( \frac{r_{x}\Delta}{\tilde{r}_{x}}}\right)^{-\frac{2}{k+1}}\ln\mathopen{} \mathclose{{}\left(\frac{r_{x}\Delta}{\tilde{r}_{x}}}\right)+\frac{C_{\rho}\ln 4 }{\kappa}.$ $$

Furthermore, Proposition 19 guarantees $\mathcal{R}(\mu^{*})\leq\Delta^{2}/\tilde{r}_{x}^{2}$. Combining these bounds with Lemma 20 completes the proof.
∎

###### Proposition 19 .

###### Lemma 20 .

###### Corollary 21 .

### A.3 Generalization Analysis

Let

$$ $\mu^{*}_{\beta}\coloneqq\operatorname*{arg\,min}_{\mu\in\mathcal{P}^{\mathrm{ ac}}_{2}(\mathbb{R}^{2d+2})}\mathcal{F}_{\beta,\lambda}(\mu)=\operatorname*{ arg\,min}_{\mu\in\mathcal{P}^{\mathrm{ac}}_{2}(\mathbb{R}^{2d+2})}\tilde{ \mathcal{F}}_{\beta,\lambda}(\mu).$ $$

Corollary 21 gives an upper bound on $\hat{\mathcal{J}}_{0}(\mu^{*})$. In this section, we transfer the bound to $\mathcal{J}_{0}(\mu^{*})$ via a Rademacher complexity analysis. Since Corollary 21 implies a bound on $\mathcal{H}(\mu\,|\,\gamma)$, we will control the following quantity,

$$ $\sup_{\mu:\mathcal{H}(\mu\,|\,\gamma)\leq\Delta^{2}}\mathcal{J}_{0}(\mu)-\hat{ \mathcal{J}}_{0}(\mu).$ $$

To be able to provide guarantees with high probability, we will prove uniform convergence over a truncated version of the risk instead, given by

$$ $\sup_{\mu:\mathcal{H}(\mu\,|\,\gamma)\leq\Delta^{2}}\mathcal{J}_{0}^{\varkappa }(\mu)-\hat{\mathcal{J}}_{0}^{\varkappa}(\mu),$ $$

where

$$ $\mathcal{J}_{0}^{\varkappa}(\mu)\coloneqq\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\rho_{\varkappa}(\hat{y}(\boldsymbol{x};\mu)-y)}}\right], \quad\hat{\mathcal{J}}_{0}^{\varkappa}(\mu)\coloneqq\mathbb{E}_{S_{n}} \mathopen{}\mathclose{{}\left[\rho_{\varkappa}(\hat{y}(\boldsymbol{x};\mu)-y)} \right],$ $$

and $\rho_{\varkappa}(\cdot)\coloneqq\rho(\cdot)\land\varkappa$. We will later specify the choice of $\varkappa$.

We are now ready to present the Rademacher complexity bound.

###### Lemma 22 ( [ 19 , Lemma 5.5] , [ 65 , Lemma 1] ) .

Suppose $\rho$ is either a $C_{\rho}$-Lipschitz loss or the squared error loss. Let $\vartheta\coloneqq\sqrt{2\varkappa}$ for the squared error loss and $C_{\rho}$ for the Lipschitz loss. Recall $\gamma=\mathcal{N}(0,\frac{\mathbf{I}_{d+1}}{\lambda\beta})$. Then,

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sup_{\{\mu\in\mathcal {P}^{\mathrm{ac}}(\mathbb{R}^{2d+2}):\mathcal{H}(\mu\,|\,\gamma)\leq M\}} \mathcal{J}_{0}^{\varkappa}(\mu)-\hat{\mathcal{J}}_{0}^{\varkappa}(\mu)}} \right]\leq 4\vartheta\iota\sqrt{\frac{2M}{n}}.$ $$

Proof.
We repeat the proof here for the reader’s convenience. Let $(\xi_{i})_{i=1}^{n}$ denote i.i.d. Rademacher random variables. Notice that for the squared error loss, $\rho_{\varkappa}$ is $\sqrt{2\varkappa}$ Lipschitz. Then, by a standard symmetrization argument and Talagrand’s contraction lemma, we have

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sup_{\mu :\mathcal{H}(\mu\,|\,\gamma)\leq M}\mathcal{J}_{0}(\mu)-\hat{\mathcal{J}}_{0}( \mu)}}\right]$ $\displaystyle\leq 2\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \sup_{\mu:H(\mu\,|\,\gamma)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\rho(\hat{y} (\boldsymbol{x}^{(i)};\mu)-y)}}\right]$ $\displaystyle\leq 2\vartheta\operatorname{\mathbb{E}}\mathopen{}\mathclose{{} \left[{\sup_{\mu:H(\mu\,|\,\gamma)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\hat{ y}(\boldsymbol{x}^{(i)};\mu)}}\right]$ $$

Next, we proceed to bound the Rademacher complexity. Specifically,

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{\xi}}\mathopen{}\mathclose {{}\left[\sup_{\mu:H(\mu\,|\,\gamma)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i} \int\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w})\mathrm{d}\mu(\boldsymbol{w})}\right]$ $\displaystyle=\operatorname{\mathbb{E}}_{\boldsymbol{\xi}}\mathopen{} \mathclose{{}\left[\frac{1}{\alpha}\sup_{\mu:H(\mu\,|\,\gamma)\leq M}\int\frac {\alpha}{n}\sum_{i=1}^{n}\xi_{i}\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w}) \mathrm{d}\mu(\boldsymbol{w})}\right]$ $\displaystyle\leq\frac{M}{\alpha}+\frac{1}{\alpha}\operatorname{\mathbb{E}}_{ \boldsymbol{\xi}}\mathopen{}\mathclose{{}\left[\ln\int\exp\mathopen{} \mathclose{{}\left(\frac{\alpha}{n}\sum_{i=1}^{n}\xi_{i}\Psi(\boldsymbol{x}^{( i)};\boldsymbol{w})}\right)\mathrm{d}\gamma(\boldsymbol{w})}\right]$ $\displaystyle\leq\frac{M}{\alpha}+\frac{1}{\alpha}\ln\int\operatorname{\mathbb {E}}_{\xi}\mathopen{}\mathclose{{}\left[\exp\mathopen{}\mathclose{{}\left( \frac{\alpha}{n}\sum_{i=1}^{n}\xi_{i}\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w}) }\right)}\right]\mathrm{d}\gamma(\boldsymbol{w}),$ $$

where the first inequality follows from the KL divergence lower bound of Lemma 17. Additionally, by sub-Gaussianity and independence of $(\xi_{i})$ and Lipschitzness of $\phi_{\kappa,\iota}$, we have

$$ $\displaystyle\operatorname{\mathbb{E}}_{\xi}\mathopen{}\mathclose{{}\left[\exp \mathopen{}\mathclose{{}\left(\frac{\alpha}{n}\sum_{i=1}^{n}\xi_{i}\Psi( \boldsymbol{x}^{(i)};\boldsymbol{w})}\right)}\right]$ $\displaystyle\leq\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2}}{2n^{2}} \sum_{i=1}^{n}\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w})^{2}}\right)$ $\displaystyle\leq\exp\mathopen{}\mathclose{{}\left(\frac{2\alpha^{2}\iota^{2}} {n}}\right)$ $$

Plugging this back into our original bound, we obtain

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{\xi}}\mathopen{}\mathclose {{}\left[\sup_{\mu:H(\mu\,|\,\gamma)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i} \hat{y}(\boldsymbol{x};\mu)}\right]\leq\frac{M}{\alpha}+\frac{2\alpha\iota^{2} }{n}.$ $$

Choosing $\alpha=\sqrt{\frac{Mn}{2\iota^{2}}}$, we obtain

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{\xi}}\mathopen{}\mathclose{{}\left[\sup _{\mu:\mathcal{H}(\mu\,|\,\gamma)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\hat{y }(\boldsymbol{x};\mu)}\right]\leq 2\iota\sqrt{\frac{2M}{n}},$ $$

which completes the proof.
∎

We can convert the above bound in expectation to a high-probability bound as follows.

###### Lemma 23 .

In the setting of Lemma 22, for any $\delta>0$, we have

$$ $\sup_{\mu\in\mathcal{P}^{\mathrm{ac}}(\mathbb{R}^{2d+2}):\mathcal{H}(\mu\,|\, \gamma)\leq M}\mathcal{J}_{0}^{\varkappa}(\mu)-\hat{\mathcal{J}}_{0}^{ \varkappa}(\mu)\lesssim\vartheta\iota\sqrt{\frac{M}{n}}+\varkappa\sqrt{\frac{ \ln(1/\delta)}{n}},$ $$

with probability at least $1-\delta$.

Proof.
As the truncated loss is bounded by $\varkappa$, the result is an immediate consequence of McDiarmid’s inequality.
∎

Next, we control the effect of truncation by bounding $\mathcal{J}_{0}(\mu)$ via $\mathcal{J}_{0}^{\varkappa}(\mu)$, which is achieved by the following lemma.

###### Lemma 24 .

Suppose $\mathcal{H}(\mu\,|\,\gamma)\leq M$. Then,

$$ $\mathcal{J}_{0}(\mu)-\mathcal{J}_{0}^{\varkappa}(\mu)\lesssim\mathopen{} \mathclose{{}\left(\iota+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{} \left[{y^{2}}}\right]^{1/2}}\right)\mathopen{}\mathclose{{}\left(e^{-\Omega( \varkappa^{2})}+n^{-q-1}}\right).$ $$

Proof.
Notice that since the loss is $C_{\rho}$-Lipschitz and $\rho(0)=0$, we have $\mathopen{}\mathclose{{}\left|{\rho(\hat{y}-y)}}\right|\leq C_{\rho}\mathopen{
}\mathclose{{}\left|{\hat{y}-y}}\right|$. Recall that we use $L$ for the Lipschitz constant of $g$, and $\mathopen{}\mathclose{{}\left|{\hat{y}(\boldsymbol{x};\mu)}}\right|\leq 2\iota$. Then,

$$ $\displaystyle\mathcal{J}_{0}(\mu)-\mathcal{J}_{0}^{\varkappa}(\mu)$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \mathbbm{1}(\rho(\hat{y}(\boldsymbol{x};\mu)-y)\geq\varkappa)\rho(\hat{y}( \boldsymbol{x};\mu)-y)}}\right]$ $\displaystyle\leq C_{\rho}\mathbb{P}\mathopen{}\mathclose{{}\left({\rho(\hat{y }(\boldsymbol{x};\mu)-y)\geq\varkappa}}\right)^{1/2}\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{(\hat{y}(\boldsymbol{x};\mu)-y)^{2}}}\right]^{1 /2}$ $\displaystyle\leq C_{\rho}\mathbb{P}\mathopen{}\mathclose{{}\left({2\iota+ \mathopen{}\mathclose{{}\left|{y}}\right|\geq\varkappa/C_{\rho}}}\right)^{1/2} \mathopen{}\mathclose{{}\left(\operatorname{\mathbb{E}}\mathopen{}\mathclose{{ }\left[{\hat{y}(\boldsymbol{x};\mu)^{2}}}\right]^{1/2}+\operatorname{\mathbb{E }}\mathopen{}\mathclose{{}\left[{y^{2}}}\right]^{1/2}}\right).$ $$

Additionally, by local Lipschitzness of $g$,

$$ $\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left({2\iota+\mathopen{} \mathclose{{}\left|{y}}\right|\geq\varkappa/C_{\rho}}}\right)$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({\big{\{}\{2\iota+ \mathopen{}\mathclose{{}\left|{y}}\right|\geq\varkappa/C_{\rho}\}\cap\{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|\leq \tilde{r}_{x}\}\big{\}}\cup\big{\{}\mathopen{}\mathclose{{}\left\|{\boldsymbol {U}\boldsymbol{x}}}\right\|\geq\tilde{r}_{x}\big{\}}}}\right)$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({2\iota+\mathopen{} \mathclose{{}\left|{g(0)}}\right|+L\mathopen{}\mathclose{{}\left\|{\boldsymbol {U}\boldsymbol{x}}}\right\|+\mathopen{}\mathclose{{}\left|{\xi}}\right|\geq \varkappa/C_{\rho}}}\right)+\mathbb{P}\mathopen{}\mathclose{{}\left({\mathopen {}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}}\right\|\geq\tilde{r}_{x} }}\right)$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({2\iota+\mathopen{} \mathclose{{}\left|{g(0)}}\right|+L\mathopen{}\mathclose{{}\left\|{\boldsymbol {U}\boldsymbol{x}}}\right\|+\mathopen{}\mathclose{{}\left|{\xi}}\right|\geq \varkappa/C_{\rho}}}\right)+n^{-(q+1)}.$ $$

Furthermore, Let $\varkappa/C_{\rho}\geq 4\iota+2\mathopen{}\mathclose{{}\left|{g(0)}}\right|+2
Lr_{x}+2\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}
\mathclose{{}\left|{\xi}}\right|}}\right]$, and recall that $L=\mathcal{O}(1/r_{x})$. Then, by a subGaussian concentration bound, we have

$$ $\mathbb{P}\mathopen{}\mathclose{{}\left({2\iota+\mathopen{}\mathclose{{}\left| {g(0)}}\right|+L\mathopen{}\mathclose{{}\left\|{\boldsymbol{U}\boldsymbol{x}}} \right\|+\xi\geq\varkappa/C_{\rho}}}\right)^{1/2}\leq e^{-\Omega\big{(}\frac{ \varkappa^{2}}{\sigma_{u}^{2}C_{\rho}^{2}}\big{)}}.$ $$

We conclude the proof by remarking that by our assumptions, $\sigma_{u}$ and $C_{\rho}$ are absolute constants.
∎

Finally, we combine the steps above to give an upper bound on $\mathcal{J}_{0}(\mu^{*}_{\beta})$, stated in the following lemma.

###### Lemma 25 .

Suppose $\lambda=\tilde{\lambda}r_{x}^{2}$ and $\beta=\frac{d_{\mathrm{eff}}+\tilde{r}_{x}^{2}/r_{x}^{2}}{\varepsilon^{2}
\tilde{\lambda}}$ for $\varepsilon,\tilde{\lambda}\lesssim 1$. Let $\tilde{\varepsilon}\coloneqq\tilde{\mathcal{O}}(\tilde{\lambda}^{\frac{1}{k+2}
})+\varepsilon+\kappa^{-1}$. Suppose
$n\gtrsim\frac{(d_{\mathrm{eff}}+\tilde{r}_{x}^{2}/r_{x}^{2})\iota^{2}}{\tilde{
\lambda}\varepsilon^{4}}$ and $\iota\gtrsim\tilde{\lambda}^{-\frac{k}{k+2}}(\tilde{r}_{x}/r_{x})^{\frac{2(k+1
)}{k+2}}$. Then,

$$ $\mathcal{J}_{0}(\mu^{*}_{\beta})-\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\rho(\xi)}}\right]\lesssim\tilde{\varepsilon},\quad\text{ and}\quad\beta^{-1}\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)\lesssim \operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\rho(\xi)}}\right]+ \tilde{\varepsilon}\lesssim 1.$ $$

Proof.
By Corollary 21 and a standard concentration bound on $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho(\xi)}\right]$ with sufficiently large $n$ to induce neglibile error in comaprison with the rest of the terms in the corollary, we have

$$ $\hat{\mathcal{J}}_{0}(\mu^{*}_{\beta})+\beta^{-1}\mathcal{H}(\mu^{*}_{\beta}\, |\,\gamma)-\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\rho(\xi)}} \right]\lesssim\frac{\tilde{r}_{x}}{r_{x}}\mathopen{}\mathclose{{}\left(\frac{ r_{x}\Delta}{\tilde{r}_{x}}}\right)^{\frac{-2}{k+1}}\ln\mathopen{}\mathclose{{ }\left(\frac{r_{x}\Delta}{\tilde{r}_{x}}}\right)+\frac{\lambda\Delta^{2}}{ \tilde{r}_{x}^{2}}+\frac{(c_{x}+\tilde{r}_{x})}{\sqrt{\lambda\beta}}+\frac{1}{ \kappa}.$ $$

By choosing

$$ $\Delta=\Big{(}\frac{r_{x}^{2}}{\lambda}\Big{)}^{\frac{1}{2}\cdot\frac{k+1}{k+2 }}\Big{(}\frac{\tilde{r}_{x}}{r_{x}}\Big{)}^{\frac{1}{2}\cdot\frac{3k+5}{k+2}},$ $$

and assuming $c_{x}\gtrsim\tilde{r}_{x}$,

$$ $\beta^{-1}\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)\lesssim\operatorname{\mathbb {E}}\mathopen{}\mathclose{{}\left[{\rho(\xi)}}\right]+\mathopen{}\mathclose{{} \left(\frac{\lambda}{r_{x}^{2}}}\right)^{\frac{1}{k+2}}\mathopen{}\mathclose{{ }\left(\frac{\tilde{r}_{x}}{r_{x}}}\right)^{\frac{k+1}{k+2}}\ln\mathopen{} \mathclose{{}\left(\frac{\tilde{r}_{x}r_{x}}{\lambda}}\right)+\frac{c_{x}}{ \sqrt{\lambda\beta}}+\frac{1}{\kappa}.$ $$

Note that the above choice on $\Delta$ translates to a lower bound on $\iota$ in Corollary 21, given by

$$ $\iota\gtrsim\tilde{\lambda}^{-\frac{k}{k+2}}\big{(}\frac{\tilde{r}_{x}}{r_{x}} \big{)}^{\frac{2(k+1)}{k+2}}.$ $$

By choosing $\lambda=\tilde{\lambda}r_{x}^{2}$ and using the fact that $\tilde{r}_{x}\leq\tilde{\mathcal{O}}(r_{x})$ and $\beta=\frac{c_{x}^{2}}{r_{x}^{2}\tilde{\lambda}\varepsilon^{2}}$, we have the simpification,

$$ $\beta^{-1}\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)\lesssim\operatorname{\mathbb {E}}\mathopen{}\mathclose{{}\left[{\rho(\xi)}}\right]+\tilde{\mathcal{O}}( \tilde{\lambda}^{\frac{1}{k+2}})+\varepsilon+\frac{1}{\kappa}\lesssim 1,$ $$

and,

$$ $\hat{\mathcal{J}}_{0}(\mu^{*}_{\beta})-\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\rho(\xi)}}\right]\lesssim\tilde{\mathcal{O}}(\tilde{ \lambda}^{\frac{1}{k+2}})+\varepsilon+\frac{1}{\kappa}\eqqcolon\tilde{ \varepsilon}.$ $$

Note that $\hat{\mathcal{J}}_{0}^{\varkappa}(\mu^{*}_{\beta})\leq\hat{\mathcal{J}}_{0}(
\mu^{*}_{\beta})$. Using the generalization bound of Lemma 23 with the choice of $\delta=n^{-q}$ for some constant $q>0$, we have with probability $1-\mathcal{O}(n^{-q})$,

$$ $\displaystyle\mathcal{J}_{0}^{\varkappa}(\mu^{*}_{\beta})-\hat{\mathcal{J}}_{0 }^{\varkappa}(\mu^{*}_{\beta})$ $\displaystyle\lesssim\iota\sqrt{\frac{\beta}{n}}+\varkappa\sqrt{\frac{\ln n}{n}}$ $\displaystyle\lesssim\iota\sqrt{\frac{d_{\mathrm{eff}}}{n\tilde{\lambda} \varepsilon^{2}}}+\varkappa\sqrt{\frac{\ln n}{n}}.$ (A.5) $$

Furthermore, by Lemma 24 we have

$$ $\displaystyle\mathcal{J}_{0}(\mu^{*}_{\beta})-\mathcal{J}_{0}^{\varkappa}(\mu^ {*}_{\beta})$ $\displaystyle\lesssim\iota e^{-\Omega(\varkappa^{2})}.$ $$

Combining the above with (A.5) and choosing on $\varkappa\asymp\sqrt{\ln n}$, we have

$$ $\mathcal{J}_{0}(\mu^{*}_{\beta})-\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\rho(\xi)}}\right]\lesssim\tilde{\varepsilon}+\iota\sqrt{ \frac{d_{\mathrm{eff}}}{n\tilde{\lambda}\varepsilon^{2}}}+\sqrt{\frac{\ln^{2}n }{n}},$ $$

which holds with probability at least $1-\mathcal{O}(n^{-q})$ over the randomness of $S_{n}$.
∎

###### Lemma 22 ( [ 19 , Lemma 5.5] , [ 65 , Lemma 1] ) .

###### Lemma 23 .

###### Lemma 24 .

###### Lemma 25 .

### A.4 Convergence Analysis

So far, our analysis has only proved properties of $\mu^{*}_{\beta}$. In this section, we relate these properties to $\mu^{m}_{l}$ via propagation of chaos. In particular, [] showed that for $\boldsymbol{W}\sim\mu^{m}_{l}$, $\hat{y}(\boldsymbol{x};\mu^{m}_{l})$ converges to $\hat{y}(\boldsymbol{x};\mu^{*}_{\beta})$ in a suitable sense characterized shortly, as long as the objective over $\mu^{m}_{l}$ converges to $\mathcal{F}_{\beta,\lambda}(\mu^{*}_{\beta})$. Notice that $\mu^{m}_{\ell}$ is a measure on $\mathcal{P}(\mathbb{R}^{(2d+2)m})$ instead of $\mathcal{P}(\mathbb{R}^{2d+2})$. Thus, we need to adjust the definition of objective by defining the following

$$ $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m})\coloneqq\operatorname{\mathbb{E}}_{ \boldsymbol{W}\sim\mu^{m}}\mathopen{}\mathclose{{}\left[\hat{J}_{0}( \boldsymbol{W})+\frac{\lambda}{2}R(\boldsymbol{W})}\right]+\frac{1}{m\beta} \mathcal{H}(\mu^{m}).$ (A.6) $$

We can use the same reformulation introduced earlier in (A.1) to define

$$ $\tilde{\mathcal{F}}^{m}_{\beta,\lambda}(\mu^{m})\coloneqq\operatorname{\mathbb {E}}_{\boldsymbol{W}\sim\mu^{m}}\mathopen{}\mathclose{{}\left[\hat{J}_{0}( \boldsymbol{W})}\right]+\frac{1}{m\beta}\mathcal{H}(\mu^{m}\,|\,\gamma^{ \otimes m}),$ (A.7) $$

which is equivalent to $\mathcal{F}^{m}_{\beta,\lambda}$ up to an additive constant. With these definitions, we can now control $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose
{{}\left[J_{0}(\mu^{m}_{l})}\right]$ via $\mathcal{J}_{0}(\mu^{*}_{\beta})$. The following lemma is based on [, Lemma 4], with a more careful analysis to obtain sharper constants.

###### Lemma 26 .

Let $\bar{r}_{x}\coloneqq\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}
\right\|^{1/2}\lor\tilde{r}_{x}$, and suppose $\rho$ is $C_{\rho}\lesssim 1$-Lipschitz. Then,

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose {{}\left[J_{0}(\boldsymbol{W})}\right]-\mathcal{J}_{0}(\mu^{*}_{\beta}) \lesssim\sqrt{\frac{\bar{r}_{x}^{2}W_{2}^{2}\big{(}\mu^{m}_{l},{\mu^{*}_{\beta }}^{\otimes m}\big{)}+\iota^{2}}{m}}.$ (A.8) $$

In particular, combined with [, Lemma 3], the above implies

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose {{}\left[J_{0}(\boldsymbol{W})}\right]-\mathcal{J}_{0}(\mu^{*}_{\beta}) \lesssim\sqrt{\frac{\bar{r}_{x}^{2}\beta C_{\mathrm{LSI}}}{m}\big{(}\tilde{ \mathcal{F}}^{m}_{\beta,\lambda}(\mu^{m}_{l})-\tilde{F}_{\beta,\lambda}(\mu^{* }_{\beta})\big{)}+\frac{\iota^{2}}{m}}.$ (A.9) $$

Proof.
Notice that

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}} \mathopen{}\mathclose{{}\left[J_{0}(\boldsymbol{W})}\right]$ $\displaystyle=\operatorname{\mathbb{E}}_{\boldsymbol{W}}\mathopen{}\mathclose{ {}\left[\operatorname{\mathbb{E}}_{\boldsymbol{x}}\mathopen{}\mathclose{{} \left[\rho(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})-\hat{y}(\boldsymbol{x} ;\mu^{*}_{\beta})+\hat{y}(\boldsymbol{x};\mu^{*}_{\beta})-y)}\right]}\right]$ $\displaystyle\leq\operatorname{\mathbb{E}}_{\boldsymbol{x}}\mathopen{} \mathclose{{}\left[\rho(\hat{y}(\boldsymbol{x};\mu^{*}_{\beta})-y)}\right]+C_{ \rho}\operatorname{\mathbb{E}}_{\boldsymbol{W}}\mathopen{}\mathclose{{}\left[ \operatorname{\mathbb{E}}_{\boldsymbol{x}}\mathopen{}\mathclose{{}\left[ \mathopen{}\mathclose{{}\left|{\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})- \hat{y}(\boldsymbol{x};\mu^{*}_{\beta})}}\right|}\right]}\right]$ $\displaystyle\leq\mathcal{J}_{0}(\mu^{*}_{\beta})+C_{\rho}\sqrt{\operatorname{ \mathbb{E}}_{\boldsymbol{x}}\mathopen{}\mathclose{{}\left[\operatorname{ \mathbb{E}}_{\boldsymbol{W}}\mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol {x};\mu_{\boldsymbol{W}})-\hat{y}(\boldsymbol{x};\mu^{*}_{\beta}))^{2}}\right] }\right]}$ $$

Suppose $\boldsymbol{W}=(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{m})\sim\mu^{m}_{l}$ and $\boldsymbol{W}^{\prime}=(\boldsymbol{w}^{\prime}_{1},\ldots,\boldsymbol{w}^{
\prime}_{m})\sim{\mu^{*}_{\beta}}^{\otimes m}$. Let $\Gamma$ denote the optimal $W_{2}$ coupling between $\boldsymbol{W}$ and $\boldsymbol{W}^{\prime}$, and assume $\boldsymbol{W},\boldsymbol{W}^{\prime}\sim\Gamma$. Then,

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{W}}\mathopen{}\mathclose{{ }\left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})-\hat{y}(\boldsymbol{x}; \mu^{*}))^{2}}\right]$ $\displaystyle=\operatorname{\mathbb{E}}_{\boldsymbol{W},\boldsymbol{W}^{\prime }}\mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})- \hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{\prime}})+\hat{y}(\boldsymbol{x}; \mu_{\boldsymbol{W}^{\prime}})-\hat{y}(\boldsymbol{x};\mu^{*}_{\beta}))^{2}}\right]$ $\displaystyle\leq 2\operatorname{\mathbb{E}}_{\boldsymbol{W},\boldsymbol{W}^{ \prime}}\mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol {W}})-\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{\prime}})^{2}}\right]+2 \operatorname{\mathbb{E}}_{\boldsymbol{W}^{\prime}}\mathopen{}\mathclose{{} \left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{\prime}})-\hat{y}( \boldsymbol{x};\mu^{*}_{\beta}))^{2}}\right]$ $$

Moreover, by Jensen’s inequality,

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{W},\boldsymbol{W}^{\prime} }\mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})- \hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{\prime}})^{2}}\right]$ $\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\operatorname{\mathbb{E}}_{ \boldsymbol{W},\boldsymbol{W}^{\prime}}\mathopen{}\mathclose{{}\left[(\Psi( \boldsymbol{x};\boldsymbol{w}_{i})-\Psi(\boldsymbol{x};\boldsymbol{w}^{\prime} _{i}))^{2}}\right]$ $\displaystyle\leq\frac{2}{m}\sum_{i=1}^{m}\operatorname{\mathbb{E}}_{ \boldsymbol{W},\boldsymbol{W}^{\prime}}\mathopen{}\mathclose{{}\left[\mathopen {}\mathclose{{}\left\langle{\boldsymbol{\omega}_{i1}-{\boldsymbol{\omega}^{ \prime}_{i1}}},{\tilde{\boldsymbol{x}}}}\right\rangle^{2}}\right]+\frac{2}{m} \sum_{i=1}^{m}\operatorname{\mathbb{E}}_{\boldsymbol{W},\boldsymbol{W}^{\prime }}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}_{i2}-{\boldsymbol{\omega}^{\prime}_{i2}}},{\tilde{ \boldsymbol{x}}}}\right\rangle^{2}}\right].$ $$

Hence,

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{x}}\mathopen{}\mathclose{{ }\left[\operatorname{\mathbb{E}}_{\boldsymbol{W},\boldsymbol{W}^{\prime}} \mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}})- \hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{\prime}}))^{2}}\right]}\right]$ $\displaystyle\leq\frac{2\mathopen{}\mathclose{{}\left\|{\tilde{\boldsymbol{ \Sigma}}}}\right\|}{m}\operatorname{\mathbb{E}}_{\boldsymbol{W},\boldsymbol{W} ^{\prime}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left\|{ \boldsymbol{W}-\boldsymbol{W}^{\prime}}}\right\|_{\mathrm{F}}^{2}}\right]$ $\displaystyle=\frac{2\mathopen{}\mathclose{{}\left\|{\tilde{\boldsymbol{\Sigma }}}}\right\|}{m}W_{2}^{2}\big{(}\mu^{m}_{t},{\mu^{*}_{\beta}}^{\otimes m}\big{ )}.$ $$

For the second term, notice that $\hat{y}(\boldsymbol{x};\mu^{*}_{\beta})=\operatorname{\mathbb{E}}_{\boldsymbol
{W}^{\prime}}\mathopen{}\mathclose{{}\left[\hat{y}(\boldsymbol{x};\mu_{
\boldsymbol{W}^{\prime}})}\right]=\operatorname{\mathbb{E}}_{\boldsymbol{w}^{
\prime}_{i}}\mathopen{}\mathclose{{}\left[\Psi(\boldsymbol{x};\boldsymbol{w}^{
\prime}_{i})}\right]$ for all $1\leq i\leq m$. By independence of $(\boldsymbol{w}^{\prime}_{i})$ and Jensen’s inequality, we have

$$ $\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{W}^{\prime}}\mathopen{} \mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{\prime}})-\hat {y}(\boldsymbol{x};\mu^{*}_{\beta}))^{2}}\right]$ $\displaystyle=\frac{1}{m}\operatorname{\mathbb{E}}_{\boldsymbol{w}^{\prime}} \mathopen{}\mathclose{{}\left[(\Psi(\boldsymbol{x};\boldsymbol{w}^{\prime})- \hat{y}(\boldsymbol{x};\mu^{*}))^{2}}\right]$ $\displaystyle=\frac{1}{m}\operatorname{\mathbb{E}}_{\boldsymbol{w}^{\prime}} \mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\int(\Psi( \boldsymbol{x};\boldsymbol{w}^{\prime})-\Psi(\boldsymbol{x};\boldsymbol{w})) \mathrm{d}\mu^{*}_{\beta}(\boldsymbol{w})}\right)^{2}}\right]$ $\displaystyle\lesssim\frac{\iota^{2}}{m}.$ $$

∎

Thus, the rest of this section deals with establishing convergence rates for $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})\to\mathcal{F}_{\beta,\lambda}(\mu
^{*}_{\beta})$. To use the one-step decay of optimality gap provided by [], we depend on the following assumption.

###### Assumption 5 .

Suppose there exist constants $L$, $C_{L}$, and $R$, such that

- 1.
*(Lipschitz gradients of the Gibbs potential)* For all $\mu,\mu^{\prime}\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ and $\boldsymbol{w},\boldsymbol{w}^{\prime}\in\mathbb{R}^{2d+2}$,
$\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu](
\boldsymbol{w})-\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu^{\prime}](\boldsymbol
{w}^{\prime})}}\right\|\leq L(W_{2}(\mu,\mu^{\prime})+\mathopen{}\mathclose{{}
\left\|{\boldsymbol{w}-\boldsymbol{w}^{\prime}}}\right\|),$
(A.10)
where $W_{2}$ is the $2$-Wasserstein distance.
- 2.
*(Bounded gradients of the Gibbs potential)* For all $\mu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ and $\boldsymbol{w}\in\mathbb{R}^{2d+2}$, we have $\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu](
\boldsymbol{w})}}\right\|\leq R$.
- 3.
*(Bounded second variation)* Denote the second variation of $\hat{\mathcal{J}}_{0}(\mu)$ at $\boldsymbol{w}$ via $\hat{\mathcal{J}}_{0}^{\prime\prime}[\mu](\boldsymbol{w},\boldsymbol{w}^{
\prime})$, which is defined as the first variation of $\mu\mapsto\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w})$ (see (2.6) for the definition of first variation). Then, for all $\mu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ and $\boldsymbol{w},\boldsymbol{w}^{\prime}\in\mathbb{R}^{2d+2}$,
$\mathopen{}\mathclose{{}\left|{\hat{\mathcal{J}}_{0}^{\prime\prime}[\mu](
\boldsymbol{w},\boldsymbol{w}^{\prime})}}\right|\leq L(1+C_{L}(\mathopen{}
\mathclose{{}\left\|{\boldsymbol{w}}}\right\|^{2}+\mathopen{}\mathclose{{}
\left\|{\boldsymbol{w}^{\prime}}}\right\|^{2})).$
(A.11)

We can now state the one-step bound.

###### Theorem 27 .

*[, Theorem 2]*
Suppose $\hat{\mathcal{J}}_{0}$ satisfies Assumption 5. Assume $\lambda\lesssim 1$, $\beta,L,R\gtrsim 1$, and the initialization satisfies $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left\|{\boldsymbol{w}^{i}_{0}}}\right\|^{2}}}\right]\lesssim R^{2}$ for all $1\leq i\leq m$. Then, for all $\eta\leq 1/4$,

$$ $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l+1})-\mathcal{F}_{\beta,\lambda}(\mu ^{*}_{\beta})\leq\exp\big{(}\frac{-\eta}{2\beta C_{\mathrm{LSI}}}\big{)}\big{( }\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})-\mathcal{F}_{\beta,\lambda}(\mu^ {*}_{\beta})\big{)}+\eta A_{m,\beta,\lambda,\eta},$ (A.12) $$

where

$$ $A_{m,\beta,\lambda,\eta}\coloneqq C\Bigg{(}L^{2}\big{(}d+\frac{R^{2}}{\lambda} \big{)}\big{(}\eta^{2}+\frac{\eta}{\beta}\big{)}+\frac{L}{m\beta}\Big{(}\frac{ 1}{C_{\mathrm{LSI}}}+\big{(}\frac{R^{2}}{\lambda^{2}}+\frac{d}{\lambda\beta} \big{)}\big{(}\frac{C_{L}}{C_{\mathrm{LSI}}}+\frac{L}{\beta}\big{)}\Big{)} \Bigg{)}$ (A.13) $$

for some absolute constant $C>0$.

We now focus on bounding the constants that appear in Assumption 5.

###### Lemma 28 (Lipschitzness of $\nabla\hat{\mathcal{J}}_{0}^{\prime}$ ) .

Suppose $\rho$ is either the squared error loss or is $C_{\rho}$ Lipschitz and has a $C^{\prime}_{\rho}$ Lipschitz derivative. Assume $\kappa\gtrsim 1$. Notice that for the squared error loss, $C^{\prime}_{\rho}=1$. Then, for all $\mu,\nu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ and $\boldsymbol{w},\boldsymbol{w}^{\prime}\in\mathbb{R}^{2d+2}$, we have

$$ $\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu]( \boldsymbol{w})-\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu^{\prime}](\boldsymbol {w}^{\prime})}}\right\|\lesssim\kappa C_{\rho}\mathopen{}\mathclose{{}\left\|{ \mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{ \boldsymbol{x}}^{\top}}\right]}}\right\|\mathopen{}\mathclose{{}\left\|{ \boldsymbol{w}-\boldsymbol{w}^{\prime}}}\right\|+C^{\prime}_{\rho}\mathopen{} \mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{ \boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|W_{2}(\mu,\mu^{ \prime}),$ $$

for the Lipschitz loss, and

$$ $\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu]( \boldsymbol{w})-\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu^{\prime}](\boldsymbol {w}^{\prime})}}\right\|\lesssim\kappa\sqrt{\hat{\mathcal{J}}_{0}(\mu)\mathopen {}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{ \boldsymbol{x}}^{\otimes 4}}\right]}}\right\|_{2\rightarrow 2}}\mathopen{} \mathclose{{}\left\|{\boldsymbol{w}-\boldsymbol{w}^{\prime}}}\right\|+ \mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|W_{ 2}(\mu,\mu^{\prime}),$ $$

for the squared error loss, where $\big{\|}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}
^{\otimes 4}}\right]\big{\|}_{2\rightarrow 2}\coloneqq\sup_{\mathopen{}
\mathclose{{}\left\|{\boldsymbol{v}}}\right\|\leq 1}\mathopen{}\mathclose{{}
\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{
{}\left\langle{\tilde{\boldsymbol{x}}},{\boldsymbol{v}}}\right\rangle^{2}
\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|$.

Proof.
Recall that $\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w})=\mathbb{E}_{S_{n}}
\mathopen{}\mathclose{{}\left[\rho^{\prime}(\hat{y}(\boldsymbol{x};\mu)-y)\Psi
(\boldsymbol{x};\boldsymbol{w})}\right]$, where $\Psi(\boldsymbol{x};\boldsymbol{w})=\phi_{\kappa,\iota}(\mathopen{}\mathclose{
{}\left\langle{\boldsymbol{\omega}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle
)-\phi_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}
_{2}},{\tilde{\boldsymbol{x}}}}\right\rangle)$. We start with the triangle inequality,

$$ $\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu]( \boldsymbol{w})-\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu^{\prime}](\boldsymbol {w}^{\prime})}}\right\|\leq\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal {J}}_{0}^{\prime}[\mu](\boldsymbol{w})-\nabla\hat{\mathcal{J}}_{0}^{\prime}[ \mu](\boldsymbol{w}^{\prime})}}\right\|+\mathopen{}\mathclose{{}\left\|{\nabla \hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w}^{\prime})-\nabla\hat{ \mathcal{J}}_{0}^{\prime}[\mu^{\prime}](\boldsymbol{w}^{\prime})}}\right\|.$ $$

We now focus on the first term. For the Lipschitz loss,

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\nabla_{\boldsymbol{\omega}_{1}} \hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w})-\nabla_{\boldsymbol{\omega }_{1}}\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w}^{\prime})}}\right\|$ $\displaystyle=\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{} \mathclose{{}\left[\rho^{\prime}(\hat{y}(\boldsymbol{x};\mu)-y)(\phi^{\prime}_ {\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{1}},{ \tilde{\boldsymbol{x}}}}\right\rangle)-\phi^{\prime}_{\kappa,\iota}(\mathopen{ }\mathclose{{}\left\langle{\boldsymbol{\omega}^{\prime}_{1}},{\tilde{ \boldsymbol{x}}}}\right\rangle)\tilde{\boldsymbol{x}}}\right]}}\right\|$ $\displaystyle\leq C_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[( \phi^{\prime}_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{ \omega}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle)-\phi^{\prime}_{\kappa, \iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}^{\prime}_{1}}, {\tilde{\boldsymbol{x}}}}\right\rangle))^{2}}\right]^{1/2}\mathopen{} \mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{ \boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|^{1/2}$ $\displaystyle\leq C_{\rho}\kappa\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{1}-\boldsymbol {\omega}^{\prime}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle^{2}}\right]^{1/2 }\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|^{1 /2}$ $\displaystyle\leq C_{\rho}\kappa\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_ {n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}} ^{\top}}\right]}}\right\|\mathopen{}\mathclose{{}\left\|{\boldsymbol{\omega}_{ 1}-\boldsymbol{\omega}^{\prime}_{1}}}\right\|,$ $$

where the first inequality follows from Lemma 18, and the second inequality follows from the fact that $\mathopen{}\mathclose{{}\left|{\phi^{\prime\prime}_{\kappa}}}\right|\leq\kappa$. For the squared error loss, we have

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\nabla_{\boldsymbol{\omega}_{1}} \hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w})-\nabla_{\boldsymbol{\omega }_{1}}\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w}^{\prime})}}\right\|$ $\displaystyle=\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{} \mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu)-y)(\phi^{\prime}_{\kappa,\iota }(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\tilde{\boldsymbol{x}} }}\right\rangle)-\phi^{\prime}_{\kappa,\iota}(\mathopen{}\mathclose{{}\left \langle{\boldsymbol{w}^{\prime}},{\tilde{\boldsymbol{x}}}}\right\rangle)\tilde {\boldsymbol{x}}}\right]}}\right\|$ $\displaystyle=\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\| \leq 1}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol{x} ;\mu)-y)(\phi^{\prime}_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle)-\phi^{\prime} _{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}^{ \prime}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle)\mathopen{}\mathclose{{} \left\langle{\boldsymbol{v}},{\tilde{\boldsymbol{x}}}}\right\rangle}\right]$ $\displaystyle\leq\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right \|\leq 1}\sqrt{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[(\hat{y}( \boldsymbol{x};\mu)-y)^{2}}\right]\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[(\phi^{\prime}_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle)-\phi^{\prime} _{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}^{ \prime}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle))^{2}\mathopen{}\mathclose {{}\left\langle{\boldsymbol{v}},{\tilde{\boldsymbol{x}}}}\right\rangle^{2}} \right]}$ $\displaystyle\leq\kappa\sqrt{\hat{\mathcal{J}}_{0}(\mu)\sup_{\mathopen{} \mathclose{{}\left\|{\boldsymbol{v}}}\right\|\leq 1}\mathopen{}\mathclose{{} \left\langle{\boldsymbol{v}},{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[ \mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{1}-\boldsymbol{ \omega}^{\prime}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle^{2}\tilde{ \boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]\boldsymbol{v}}}\right\rangle}$ $\displaystyle\leq\kappa\sqrt{\hat{\mathcal{J}}_{0}(\mu)\mathopen{}\mathclose{{ }\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose {{}\left\langle{\boldsymbol{\omega}_{1}-\boldsymbol{\omega}^{\prime}_{1}},{ \tilde{\boldsymbol{x}}}}\right\rangle^{2}\tilde{\boldsymbol{x}}\tilde{ \boldsymbol{x}}^{\top}}\right]}}\right\|}$ $\displaystyle\leq\kappa\sqrt{\hat{\mathcal{J}}_{0}(\mu)\mathopen{}\mathclose{{ }\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x} }^{\otimes 4}}\right]}}\right\|_{2\rightarrow 2}}\mathopen{}\mathclose{{}\left \|{\boldsymbol{\omega}_{1}-\boldsymbol{\omega}^{\prime}_{1}}}\right\|.$ $$

Similar bounds apply to the gradient with respect to $\boldsymbol{\omega}_{2}$, which completes the bound on the first term of the triangle inequality.

We now consider the second term of the triangle inequality. Here we consider Lipschitz losses and the squared error loss at the same time since both have a Lipschitz derivative.

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\nabla_{\boldsymbol{\omega}_{1}} \hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{\omega}^{\prime})-\nabla_{ \boldsymbol{\omega}_{1}}\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{\omega }^{\prime})}}\right\|$ $\displaystyle=\mathopen{}\mathclose{{}\left\|{\big{(}\rho^{\prime}(\hat{y}( \boldsymbol{x};\mu)-y)-\rho^{\prime}(\hat{y}(\boldsymbol{x};\mu^{\prime})-y) \big{)}\phi^{\prime}_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}^{\prime}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle) \tilde{\boldsymbol{x}}}}\right\|$ $\displaystyle\leq\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\big{(}\rho^{ \prime}(\hat{y}(\boldsymbol{x};\mu)-y)-\rho^{\prime}(\hat{y}(\boldsymbol{x}; \mu^{\prime})-y)\big{)}^{2}}\right]^{1/2}\mathopen{}\mathclose{{}\left\|{ \mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{ \boldsymbol{x}}^{\top}}\right]}}\right\|^{1/2}$ $\displaystyle\leq C^{\prime}_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[(\hat{y}(\boldsymbol{x};\mu)-\hat{y}(\boldsymbol{x};\mu^{\prime}))^{2}} \right]^{1/2}\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{} \mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right] }}\right\|^{1/2},$ (A.14) $$

where the first inequality follows from Lemma 18. Let $\gamma\in\mathcal{P}_{2}(\mathbb{R}^{2d+2}\times\mathbb{R}^{2d+2})$ be a coupling of $\mu$ and $\mu^{\prime}$ (i.e. the first and second marginals of $\gamma$ are equal to $\mu$ and $\mu^{\prime}$ respectively). Recall that,

$$ $\hat{y}(\boldsymbol{x};\mu)-\hat{y}(\boldsymbol{x};\mu^{\prime})=\int\big{(} \phi_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{ 1}},{\tilde{\boldsymbol{x}}}}\right\rangle)-\phi_{\kappa,\iota}(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{\omega}_{2}},{\tilde{\boldsymbol{x}}}} \right\rangle)-\phi_{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\omega}^{\prime}_{1}},{\tilde{\boldsymbol{x}}}}\right\rangle)+\phi _{\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}^{ \prime}_{2}},{\tilde{\boldsymbol{x}}}}\right\rangle\big{)}\mathrm{d}\gamma( \boldsymbol{w},\boldsymbol{w}^{\prime}).$ $$

Therefore by the triangle inequality for the $L_{2}$ norm $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[(\cdot)^{2}}\right]^{1/2}$ and Jensen’s inequality,

$$ $\displaystyle\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[(\hat{y}( \boldsymbol{x};\mu)-\hat{y}(\boldsymbol{x};\mu^{\prime}))^{2}}\right]^{1/2}\leq$ $\displaystyle\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\int\big{(}\phi_{ \kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{1}},{ \tilde{\boldsymbol{x}}}}\right\rangle)-\phi_{\kappa,\iota}(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{\omega}^{\prime}_{1}},{\tilde{ \boldsymbol{x}}}}\right\rangle)\big{)}^{2}\mathrm{d}\gamma}\right]^{1/2}$ $\displaystyle+\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\int\big{(}\phi_ {\kappa,\iota}(\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{2}},{ \tilde{\boldsymbol{x}}}}\right\rangle)-\phi_{\kappa,\iota}(\mathopen{} \mathclose{{}\left\langle{\boldsymbol{\omega}^{\prime}_{2}},{\tilde{ \boldsymbol{x}}}}\right\rangle)\big{)}^{2}\mathrm{d}\gamma}\right]^{1/2}$ $\displaystyle\leq$ $\displaystyle\int\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{} \mathclose{{}\left\langle{\boldsymbol{\omega}_{1}-\boldsymbol{\omega}^{\prime} _{1}},{\tilde{\boldsymbol{x}}}}\right\rangle^{2}}\right]^{1/2}\mathrm{d}\gamma +\int\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{} \left\langle{\boldsymbol{\omega}_{2}-\boldsymbol{\omega}^{\prime}_{2}},{\tilde {\boldsymbol{x}}}}\right\rangle^{2}}\right]^{1/2}\mathrm{d}\gamma$ $\displaystyle\leq\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{} \mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right] }}\right\|^{1/2}\int\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{} \left\|{\boldsymbol{\omega}_{1}-\boldsymbol{\omega}^{\prime}_{1}}}\right\|+ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\omega}_{2}-\boldsymbol{\omega}^{ \prime}_{2}}}\right\|}\right)\mathrm{d}\gamma(\boldsymbol{w}_{1},\boldsymbol{w }_{2})$ $\displaystyle\leq\sqrt{2\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}} \mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{ \top}}\right]}}\right\|\int\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}- \boldsymbol{w}^{\prime}}}\right\|^{2}\mathrm{d}\gamma(\boldsymbol{w}, \boldsymbol{w}^{\prime})}.$ $$

By choosing $\gamma$ whose transport cost attains (or converges to) the optimal cost, we have

$$ $\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[(\hat{y}(\boldsymbol{x};\mu)- \hat{y}(\boldsymbol{x};\mu^{\prime}))^{2}}\right]^{1/2}\leq\sqrt{2\mathopen{} \mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{ \boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|}W_{2}(\mu,\mu^{ \prime}).$ $$

Plugging the above result into (A.14), we have

$$ $\mathopen{}\mathclose{{}\left\|{\nabla_{\boldsymbol{\omega}_{1}}\hat{\mathcal{ J}}_{0}^{\prime}[\mu](\boldsymbol{\omega}^{\prime})-\nabla_{\boldsymbol{\omega }_{2}}\hat{\mathcal{J}}_{0}^{\prime}[\mu^{\prime}](\boldsymbol{\omega}^{\prime })}}\right\|\leq\sqrt{2}C^{\prime}_{\rho}\mathopen{}\mathclose{{}\left\|{ \mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{ \boldsymbol{x}}^{\top}}\right]}}\right\|W_{2}(\mu,\mu^{\prime}).$ $$

Notice that the same bound holds for gradients with respect to $\boldsymbol{\omega}_{2}$. Thus the bound of the second term in the triangle inequality and the proof is complete.
∎

###### Lemma 29 (Boundedness of $\nabla\hat{\mathcal{J}}_{0}^{\prime}$ ) .

In the same setting as Lemma 28, for all $\mu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ and $\boldsymbol{w}\in\mathbb{R}^{2d+2}$, we have

$$ $\mathopen{}\mathclose{{}\left\|{\nabla\hat{\mathcal{J}}_{0}^{\prime}[\mu]( \boldsymbol{w})}}\right\|\leq\sqrt{2}\tilde{C}_{\rho}\mathopen{}\mathclose{{} \left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}} \tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|^{1/2},$ $$

where $\tilde{C}_{\rho}=C_{\rho}$ when $\rho$ is Lipschitz and $\tilde{C}_{\rho}=\sqrt{2\hat{\mathcal{J}}_{0}(\mu)}$ when $\rho$ is the squared error loss.

Proof.
Notice that $\mathopen{}\mathclose{{}\left|{\phi^{\prime}_{\kappa,\iota}}}\right|\leq 1$. Therefore,

$$ $\displaystyle\mathopen{}\mathclose{{}\left\|{\nabla_{\boldsymbol{\omega}_{1}} \hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w})}}\right\|$ $\displaystyle=\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{} \mathclose{{}\left[\rho^{\prime}(\hat{y}-y)\phi^{\prime}_{\kappa,\iota}( \mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{1}},{\tilde{ \boldsymbol{x}}}}\right\rangle)\tilde{\boldsymbol{x}}}\right]}}\right\|$ $\displaystyle\leq\sqrt{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho^{ \prime}(\hat{y}-y)^{2}}\right]\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n }}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{ \top}}\right]}}\right\|}$ $\displaystyle\leq\tilde{C}_{\rho}\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S _{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x} }^{\top}}\right]}}\right\|^{1/2},$ $$

where the first inequality follows from Lemma 18.
∎

###### Lemma 30 (Boundedness of $\hat{\mathcal{J}}_{0}^{\prime\prime}$ ) .

In the same setting as Lemma 28, for all $\mu\in\mathcal{P}_{2}(\mathbb{R}^{2d+2})$ and $\boldsymbol{w},\boldsymbol{w}^{\prime}\in\mathbb{R}^{2d+2}$, we have

$$ $\mathopen{}\mathclose{{}\left|{\hat{\mathcal{J}}_{0}^{\prime\prime}[\mu]( \boldsymbol{w},\boldsymbol{w}^{\prime})}}\right|\leq C^{\prime}_{\rho} \mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\| \mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}} \right\|^{2}+\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}^{\prime}}}\right\| ^{2}}\right),$ $$

where we recall that $C^{\prime}_{\rho}=1$ for the squared error loss.

Proof.
Via the definition given by (2.6), it is straightforward to show that

$$ $\hat{\mathcal{J}}_{0}^{\prime\prime}[\mu](\boldsymbol{w},\boldsymbol{w}^{ \prime})=\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho^{\prime\prime}( \hat{y}(\boldsymbol{x};\mu)-y)\Psi(\boldsymbol{x};\boldsymbol{w})\Psi( \boldsymbol{x};\boldsymbol{w}^{\prime})}\right].$ $$

Then, by the Cauchy-Schwartz inequality,

$$ $\hat{\mathcal{J}}_{0}^{\prime\prime}[\mu](\boldsymbol{w},\boldsymbol{w}^{ \prime})\leq C^{\prime}_{\rho}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[ \Psi(\boldsymbol{x};\boldsymbol{w})^{2}}\right]^{1/2}\mathbb{E}_{S_{n}} \mathopen{}\mathclose{{}\left[\Psi(\boldsymbol{x};\boldsymbol{w}^{\prime})^{2} }\right]^{1/2}.$ $$

Moreover, by the Lipschitzness of $\phi_{\kappa,\iota}$,

$$ $\displaystyle\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\Psi(\boldsymbol{ x};\boldsymbol{w})^{2}}\right]^{1/2}$ $\displaystyle\leq\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\mathopen{} \mathclose{{}\left\langle{\boldsymbol{\omega}_{1}},{\tilde{\boldsymbol{x}}}} \right\rangle^{2}}\right]^{1/2}+\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\omega}_{2}},{\tilde{ \boldsymbol{x}}}}\right\rangle^{2}}\right]^{1/2}$ $\displaystyle\leq\sqrt{2}\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}} \mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{ \top}}\right]}}\right\|^{1/2}\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|$ $$

We can similarly bound the expression for $\boldsymbol{w}^{\prime}$, and arrive at the statement of the lemma via Young’s inequality,

$$ $\hat{\mathcal{J}}_{0}^{\prime\prime}[\mu](w,w^{\prime})\leq 2\mathopen{} \mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{ \boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|C^{\prime}_{\rho }\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|\mathopen{}\mathclose {{}\left\|{\boldsymbol{w}^{\prime}}}\right\|\leq\mathopen{}\mathclose{{}\left \|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\tilde{\boldsymbol{x}} \tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|\big{(}\mathopen{}\mathclose{{} \left\|{\boldsymbol{w}}}\right\|^{2}+\mathopen{}\mathclose{{}\left\|{ \boldsymbol{w}^{\prime}}}\right\|^{2}\big{)}.$ $$

∎

We collect the smoothness estimates and simplify them under the event of Lemma 16 in the following Corollary.

###### Corollary 31 .

Suppose $\rho$ and $\rho^{\prime}$ are $C_{\rho}$ and $C^{\prime}_{\rho}$ Lipschitz respectively, with $C_{\rho},C^{\prime}_{\rho}\lesssim 1$. Recall that $\boldsymbol{\Sigma}\coloneqq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}
\left[{\boldsymbol{x}\boldsymbol{x}^{\top}}}\right]$. On the event of Lemma 16, we have $\mathopen{}\mathclose{{}\left\|{\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}
\left[\tilde{\boldsymbol{x}}\tilde{\boldsymbol{x}}^{\top}}\right]}}\right\|
\lesssim\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|\lor
\tilde{r}_{x}^{2}$, and consequently, $\hat{\mathcal{J}}_{0}^{\prime}$ satisfies Assumption 5 with constants $L\lesssim\kappa(\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|
\lor\tilde{r}_{x}^{2})$, $R\lesssim\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|^{1/2}
\lor\tilde{r}_{x}$, and $C_{L}=\kappa^{-1}$.

Using the estimates above, we can present the following convergence bound $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{*}_{\beta})-\mathcal{F}_{\beta,\lambda}(
\mu^{*}_{\beta})$.

###### Proposition 32 .

Let $\bar{r}_{x}\coloneqq\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}
\right\|\lor\tilde{r}_{x}$, and for simplcity assume $C_{\mathrm{LSI}}\geq\beta$. For any $\varepsilon\lesssim 1$, suppose the step size satisfies

$$ $\eta\lesssim\frac{\varepsilon}{C_{\mathrm{LSI}}\kappa^{2}\bar{r}_{x}^{4}(d+ \bar{r}_{x}^{2}/\lambda)},$ $$

the width of the network satisfies,

$$ $m\gtrsim\frac{\kappa\bar{r}_{x}^{2}\Big{(}1+\big{(}\frac{\bar{r}_{x}^{2}}{ \lambda^{2}}+\frac{d}{\lambda\beta}\big{)}\big{(}\frac{1}{\kappa}+\frac{\kappa \bar{r}_{x}^{2}C_{\mathrm{LSI}}}{\beta}\big{)}\Big{)}}{\varepsilon},$ $$

and the number of iterations satisfies

$$ $l\gtrsim\frac{\beta C_{\mathrm{LSI}}}{\eta}\ln\big{(}\frac{\mathcal{F}^{m}_{ \beta,\lambda}(\mu^{m}_{0})-\mathcal{F}^{*}_{\beta}}{\varepsilon}\big{)}.$ $$

Then, we have $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})-\mathcal{F}_{\beta,\lambda}(\mu^{
*}_{\beta})\leq\varepsilon$.

Proof.
Throughout the proof, we will assume the event of Lemma 16 holds. Let $\mathcal{F}^{*}_{\beta,\lambda}\coloneqq\mathcal{F}_{\beta,\lambda}(\mu^{*}_{
\beta})$. Notice that by iterating the bound of Theorem 27, we have

$$ $\displaystyle\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})-\mathcal{F}^{*}_{ \beta,\lambda}$ $\displaystyle\leq\exp\big{(}\frac{-l\eta}{2\beta C_{\mathrm{LSI}}}\big{)}( \mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{0})-\mathcal{F}^{*}_{\beta,\lambda})+ \frac{\eta A_{m,\beta,\lambda,\eta}}{1-\exp\big{(}\frac{-\eta}{2\beta C_{ \mathrm{LSI}}}\big{)}}$ $\displaystyle\leq\exp\big{(}\frac{-l\eta}{2\beta C_{\mathrm{LSI}}}\big{)}( \mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{0})-\mathcal{F}^{*}_{\beta,\lambda})+ 4\beta C_{\mathrm{LSI}}A_{m,\beta,\lambda,\eta},$ $$

where the second inequality holds for $\eta\leq 2\beta C_{\mathrm{LSI}}$ since $1-e^{-x}\geq x/2$ for $x\in[0,1]$. We now bound $A_{m,\beta,\lambda,\eta}$ so that the RHS of the above is less than $\mathcal{O}(\varepsilon)$ by choosing a sufficiently large $m$ and a sufficiently small $\eta$. Recall that given constants $L$ and $R$ from Assumption 5,

$$ $A_{m,\beta,\lambda,\eta}\asymp L^{2}\big{(}d+\frac{R^{2}}{\lambda}\big{)}\big{ (}\eta^{2}+\frac{\eta}{\beta}\big{)}+\frac{L}{m\beta}\Big{(}\frac{1}{C_{ \mathrm{LSI}}}+\big{(}\frac{R^{2}}{\lambda^{2}}+\frac{d}{\lambda\beta}\big{)} \big{(}\frac{C_{L}}{C_{\mathrm{LSI}}}+\frac{L}{\beta}\big{)}\Big{)}.$ $$

From Corollary 31, $L\asymp\kappa(\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|
\lor\tilde{r}_{x}^{2})$, $R\asymp\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|^{1/2}\lor
\tilde{r}_{x}$, and $C_{L}=\kappa^{-1}$. To avoid notational clutter, let $\bar{r}_{x}^{2}\coloneqq\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}
\right\|\lor\tilde{r}_{x}^{2}$. Then, to control the terms containing $\eta$, it suffices to choose

$$ $\eta\lesssim\sqrt{\frac{\varepsilon}{\beta C_{\mathrm{LSI}}\kappa^{2}\bar{r}_{ x}^{4}(d+\bar{r}_{x}^{2}/\lambda)}}\land\frac{\varepsilon}{C_{\mathrm{LSI}} \kappa^{2}\bar{r}_{x}^{4}(d+\bar{r}_{x}^{2}/\lambda)},$ $$

for which we can simply choose

$$ $\eta\lesssim\frac{\varepsilon}{C_{\mathrm{LSI}}\kappa^{2}\bar{r}_{x}^{4}(d+ \bar{r}_{x}^{2}/\lambda)}.$ $$

Further, to control the term containing the number of particles $m$, we need

$$ $m\gtrsim\frac{\kappa\bar{r}_{x}^{2}\Big{(}1+\big{(}\frac{\bar{r}_{x}^{2}}{ \lambda^{2}}+\frac{d}{\lambda\beta}\big{)}\big{(}\frac{1}{\kappa}+\frac{\kappa \bar{r}_{x}^{2}C_{\mathrm{LSI}}}{\beta}\big{)}\Big{)}}{\varepsilon}.$ $$

To drive the suboptimality bound below $\varepsilon$, we also need to let the number of iterations $l$ satisfy

$$ $l\gtrsim\frac{\beta C_{\mathrm{LSI}}}{\eta}\ln\big{(}\frac{\mathcal{F}^{m}_{ \beta,\lambda}(\mu^{m}_{0})-\mathcal{F}^{*}_{\beta,\lambda}}{\varepsilon}\big{ )}.$ $$

With the above conditions, we can guarantee

$$ $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})-\mathcal{F}^{*}_{\beta,\lambda} \lesssim\varepsilon,$ $$

which finishes the proof.
∎

Further, we now present the proof of the LSI estimate given by Proposition 2.

Proof. [Proof of Proposition 2]
Recall that

$$ $\hat{\mathcal{J}}_{\lambda}^{\prime}[\mu_{\boldsymbol{W}^{l}}](\boldsymbol{w}) =\hat{\mathcal{J}}_{0}^{\prime}[\mu_{\boldsymbol{W}^{l}}](\boldsymbol{w})+ \frac{\lambda}{2}\mathopen{}\mathclose{{}\left\|{\boldsymbol{w}}}\right\|^{2}.$ $$

Thus we have $\nu_{\mu_{\boldsymbol{W}^{l}}}(\boldsymbol{w})\propto\gamma(\boldsymbol{w})
\exp(-\beta\hat{\mathcal{J}}_{0}^{\prime}[\mu_{\boldsymbol{W}^{l}}](
\boldsymbol{w}))$. Since $\gamma$ satisfies the LSI with constant $1/(\beta\lambda)$, by the Holley-Stroock perturbation argument [], $\nu_{\mu_{\boldsymbol{W}^{l}}}$ satifies the LSI with constant

$$ $C_{\mathrm{LSI}}\leq\frac{\exp(\beta\operatorname{osc}(\hat{\mathcal{J}}_{0}^{ \prime}[\mu_{\boldsymbol{W}^{l}}]))}{\beta\lambda}.$ $$

Additionally,

$$ $\mathopen{}\mathclose{{}\left|{\hat{\mathcal{J}}_{0}^{\prime}[\mu_{\boldsymbol {W}^{l}}](\boldsymbol{w})}}\right|=\mathopen{}\mathclose{{}\left|{\frac{1}{n} \sum_{i=1}^{n}\rho^{\prime}(\hat{y}(\boldsymbol{x};\mu_{\boldsymbol{W}^{l}})-y )\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w})}}\right|\leq 2C_{\rho}\iota,$ $$

which completes the proof.
∎

Finally, we are ready to present the proof of Theorem.

###### Lemma 26 .

###### Assumption 5 .

###### Theorem 27 .

###### Lemma 28 (Lipschitzness of ∇ 𝒥 ^ 0 ′ ∇ superscript subscript ^ 𝒥 0 ′ \nabla\hat{\mathcal{J}}_{0}^{\prime} ∇ over^ start_ARG caligraphic_J end_ARG start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ) .

###### Lemma 29 (Boundedness of ∇ 𝒥 ^ 0 ′ ∇ superscript subscript ^ 𝒥 0 ′ \nabla\hat{\mathcal{J}}_{0}^{\prime} ∇ over^ start_ARG caligraphic_J end_ARG start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ) .

###### Lemma 30 (Boundedness of 𝒥 ^ 0 ′′ superscript subscript ^ 𝒥 0 ′′ \hat{\mathcal{J}}_{0}^{\prime\prime} over^ start_ARG caligraphic_J end_ARG start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ′ ′ end_POSTSUPERSCRIPT ) .

###### Corollary 31 .

###### Proposition 32 .

### A.5 Proof of Theorem 3 and Corollary 4

Recall that $\lambda=\tilde{\lambda}r_{x}^{2}$, and let $\beta=\frac{d_{\mathrm{eff}}+\tilde{r}_{x}^{2}/r_{x}^{2}}{\varepsilon^{2}
\tilde{\lambda}}$ and $n\geq\frac{(d_{\mathrm{eff}}+\tilde{r}_{x}^{2}/r_{x}^{2})\iota^{2}}{\tilde{
\lambda}\varepsilon^{4}}$ for some $\varepsilon\lesssim 1$, where $\tilde{\varepsilon}\coloneqq\tilde{\mathcal{O}}(\tilde{\lambda}^{\frac{1}{k+2}
}+\varepsilon+\kappa^{-1})$. Then, as long as $\iota\gtrsim\frac{\tilde{r}_{x}^{2}}{\tilde{\lambda}r_{x}^{2}}$, from Lemma 25, we have $\mathcal{J}_{0}(\mu^{*}_{\beta})-\operatorname{\mathbb{E}}\mathopen{}
\mathclose{{}\left[{\rho(\xi)}}\right]\lesssim\tilde{\varepsilon}$. Note that while Lemma 25 only asks for $\iota\gtrsim\tilde{\lambda}^{-\frac{k}{k+2}}(\tilde{r}_{x}/r_{x})^{\frac{2(k+1
)}{k+2}}$, we simplify this expression in the statement of Theorem 3 so that the choice of $\iota$ does not depend on $k$.

On the other hand, given the step size $\eta$, width $m$, and number of iterations $l$ by Proposition 32, we have $\mathcal{F}^{m}_{\beta,\lambda}(\mu^{m}_{l})-\mathcal{F}_{\beta,\lambda}(\mu^{
*}_{\beta})\leq\varepsilon$. Therefore,

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose {{}\left[J_{0}(\boldsymbol{W})}\right]-\mathcal{J}_{0}(\mu^{*}_{\beta}) \lesssim\sqrt{\frac{\bar{r}_{x}^{2}\beta C_{\mathrm{LSI}}\varepsilon}{m}+\frac {\iota^{2}}{m}}.$ $$

Additionally, from Lemma 25, we have

$$ $\beta^{-1}\mathcal{H}(\mu^{*}_{\beta}\,|\,\gamma)\lesssim\operatorname{\mathbb {E}}\mathopen{}\mathclose{{}\left[{\rho(\xi)}}\right]+\tilde{\mathcal{O}}( \tilde{\lambda}^{\frac{1}{k+2}})+\varepsilon+\kappa^{-1}\lesssim 1.$ $$

Consequently, for $m\geq\frac{\bar{r}_{x}^{2}(d_{\mathrm{eff}}+\tilde{r}_{x}^{2}/r_{x}^{2})C_{
\mathrm{LSI}}}{\tilde{\lambda}\varepsilon^{3}}\lor\frac{\iota}{\varepsilon^{2}}$, we have $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose
{{}\left[J_{0}(\boldsymbol{W})}\right]-\mathcal{J}_{0}(\mu^{*}_{\beta})\leq\varepsilon$. Therefore, combining the bounds above, we have

$$ $\operatorname{\mathbb{E}}_{\boldsymbol{W}\sim\mu^{m}_{l}}\mathopen{}\mathclose {{}\left[J_{0}(\boldsymbol{W})}\right]-\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\rho(\xi)}}\right]\lesssim\tilde{\mathcal{O}}(\tilde{ \lambda}^{\frac{1}{k+2}})+\varepsilon+\kappa^{-1}.$ $$

Consequently, we can take $\tilde{\lambda}=o_{n}(1)$, $\varepsilon=o_{n}(1)$, $\kappa^{-1}=o_{n}(1)$, which finishes the proof of Theorem 3.

We finally remark that under the LSI estimate of Proposition 2 and the choice of hyperparameters in Theorem 3, the sufficient number of neurons and iterations can be bounded by

$$ $m\leq\tilde{\mathcal{O}}\Big{(}\frac{\bar{r}_{x}^{4}}{c_{x}^{4}}\big{(}\frac{d }{d_{\mathrm{eff}}}+\frac{\bar{r}_{x}^{2}}{r_{x}^{2}}\big{)}e^{\tilde{\mathcal {O}}(d_{\mathrm{eff}})}\Big{)}\leq\tilde{\mathcal{O}}\Big{(}\frac{\bar{r}_{x}^ {4}d_{\mathrm{eff}}}{c_{x}^{4}}\big{(}\frac{d}{d_{\mathrm{eff}}^{2}}+\frac{ \bar{r}_{x}^{2}}{c_{x}^{2}}\big{)}e^{\tilde{\mathcal{O}}(d_{\mathrm{eff}})} \Big{)}\leq\tilde{\mathcal{O}}\big{(}de^{\tilde{\mathcal{O}}(d_{\mathrm{eff}}) }\big{)},$ $$

and

$$ $l\leq\tilde{\mathcal{O}}\Big{(}\frac{\bar{r}_{x}^{4}d}{c_{x}^{4}}e^{\tilde{ \mathcal{O}}(d_{\mathrm{eff}})}\Big{)}\leq\tilde{\mathcal{O}}\big{(}de^{\tilde {\mathcal{O}}(d_{\mathrm{eff}})}\big{)},$ $$

which completes the proof of Corollary 4.
∎

## Appendix B Proofs of Section 4

We begin with the proof of Proposition 8.

Proof. [Proof of Proposition 8]
Note that $\hat{\mathcal{J}}_{0}(\mu^{*})=0$ by definition. Moreover, the bound on $\mathcal{H}(\mu^{*}\,|\,\tau)$ is a simple application of Jensen’s inequality, namely,

$$ $\mathcal{H}(\mu^{*}\,|\,\tau)=\int\ln\frac{e^{f}}{\int e^{f}\mathrm{d}\tau} \mathrm{d}\mu^{*}=\int f\mathrm{d}\mu^{*}-\ln\int e^{f}\mathrm{d}\tau\leq\int f (\mathrm{d}\mu^{*}-\mathrm{d}\tau).$ $$

∎

Next, using the Bakry-Émery curvature-dimension condition [], we prove the following dimension-free LSI bound.

Proof. [Proof of Proposition 9]
By the curvature-dimension condition [, Section 5.7], the Gibbs measure $\nu_{\mu}\propto\exp(-\beta\hat{\mathcal{J}}_{0}^{\prime}[\mu])$ satisfies the LSI with constant $C_{\mathrm{LSI}}\leq\alpha^{-1}$ as long as

$$ $\mathrm{Ric}_{\mathfrak{g}}+\beta\nabla^{2}\hat{\mathcal{J}}_{0}^{\prime}[\eta ](\boldsymbol{w})\geq\alpha\mathfrak{g},$ $$

for all $\boldsymbol{w}\in\mathcal{W}$ and some $\alpha>0$. By the bound on the Ricci curvature from Assumption 4, it suffices to show

$$ $\varrho d\mathfrak{g}+\beta\nabla^{2}\hat{\mathcal{J}}_{0}^{\prime}[\eta]( \boldsymbol{w})\succcurlyeq\alpha\mathfrak{g}.$ $$

Recall that

$$ $\hat{\mathcal{J}}_{0}(\mu)=\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[ \rho\mathopen{}\mathclose{{}\left(\int\Psi(\boldsymbol{x};\boldsymbol{w}) \mathrm{d}\mu(\boldsymbol{w})-y}\right)}\right].$ $$

Therefore,

$$ $\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w})=\mathbb{E}_{S_{n}} \mathopen{}\mathclose{{}\left[\rho^{\prime}(\hat{y}(\boldsymbol{x};\mu)-y)\Psi (\boldsymbol{x};\boldsymbol{w})}\right],$ $$

and

$$ $\nabla^{2}_{\boldsymbol{w}}\hat{\mathcal{J}}_{0}^{\prime}[\mu](\boldsymbol{w}) =\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho^{\prime}(\hat{y}( \boldsymbol{x};\mu)-y)\nabla^{2}_{\boldsymbol{w}}\Psi(\boldsymbol{x}; \boldsymbol{w})}\right].$ $$

Consider the case where $\rho$ is $C_{\rho}$ Lipschitz. Then,

$$ $\displaystyle\lambda_{\mathrm{min}}(\nabla^{2}_{\boldsymbol{w}}\hat{\mathcal{J }}_{0}^{\prime}[\mu](\boldsymbol{w}))$ $\displaystyle=\inf_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v}}}\right\|_{ \mathfrak{g}}\leq 1}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{}\left[\rho^{ \prime}(\hat{y}(\boldsymbol{x};\mu)-y)\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\nabla^{2}_{\boldsymbol{w}}\Psi(\boldsymbol{x};\boldsymbol{w} )\boldsymbol{w}}}\right\rangle}\right]$ $\displaystyle\geq-C_{\rho}\sup_{\mathopen{}\mathclose{{}\left\|{\boldsymbol{v} }}\right\|_{\mathfrak{g}}\leq 1}\mathbb{E}_{S_{n}}\mathopen{}\mathclose{{} \left[\mathopen{}\mathclose{{}\left|{\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{v}},{\nabla^{2}_{\boldsymbol{w}}\Psi(\boldsymbol{x};\boldsymbol{w} )\boldsymbol{v}}}\right\rangle}}\right|}\right]$ $\displaystyle=-C_{\rho}K.$ $$

∎

Before stating the proof of Theorem 10, we adapt the generalization analysis of Appendix A.3 to the Riemannian setting of this section. Recall the truncated risk functions $\mathcal{J}_{0}^{\varkappa}(\mu)=\operatorname{\mathbb{E}}\mathopen{}
\mathclose{{}\left[{\rho(\hat{y}(\boldsymbol{x};\mu)-y)\wedge\varkappa}}\right]$ and $\hat{\mathcal{J}}_{0}^{\varkappa}(\mu)=\mathbb{E}_{S_{n}}\mathopen{}\mathclose
{{}\left[\rho(\hat{y}(\boldsymbol{x};\mu)-y)\wedge\varkappa}\right]$. Then, we have the following uniform convergence bound.

###### Lemma 33 .

Under the setting of Example 7, where we recall $\mathopen{}\mathclose{{}\left|{\varphi(0)}}\right|\lesssim 1$ and $\mathopen{}\mathclose{{}\left|{\varphi^{\prime}(z)}}\right|\lesssim 1$ for all $z$, we have

$$ $\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sup_{\mu\in\mathcal{P }^{\mathrm{ac}}(\mathcal{W}):\mathcal{H}(\mu\,|\,\tau)\leq M}\mathcal{J}_{0}^{ \varkappa}(\mu)-\hat{\mathcal{J}}_{0}^{\varkappa}(\mu)}}\right]\lesssim C_{ \rho}\sqrt{\frac{M}{n}}\mathopen{}\mathclose{{}\left(1+\operatorname{\mathbb{E }}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left\|{\hat{ \boldsymbol{\Sigma}}}}\right\|^{1/2}}}\right]}\right),$ $$

where $\hat{\boldsymbol{\Sigma}}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{x}^{(i)
}{\boldsymbol{x}^{(i)}}^{\top}$. Combined with McDiarmid’s inequality, the above bound implies

$$ $\sup_{\mathcal{H}(\mu\,|\,\tau)\leq M}\mathcal{J}_{0}^{\varkappa}(\mu)-\hat{ \mathcal{J}}_{0}^{\varkappa}(\mu)\lesssim C_{\rho}\sqrt{\frac{M}{n}}\mathopen{ }\mathclose{{}\left(1+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \mathopen{}\mathclose{{}\left\|{\hat{\boldsymbol{\Sigma}}}}\right\|^{1/2}}} \right]}\right)+\varkappa\sqrt{\frac{\ln(1/\delta)}{n}},$ $$

with probability at least $1-\delta$.

Proof.
Based on the same argument as Lemma 22, for any $\alpha>0$, we have

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\sup_{ \mathcal{H}(\mu\,|\,\tau)\leq M}\mathcal{J}_{0}^{\varkappa}(\mu)-\hat{\mathcal {J}}_{0}^{\varkappa}(\mu)}}\right]$ $\displaystyle\leq 2C_{\rho}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{} \left[{\sup_{\mathcal{H}(\mu\,|\,\tau)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i} \hat{y}(\boldsymbol{x}^{(i)};\mu)}}\right]$ $$

where $(\xi_{i})$ are i.i.d. Rademacher random variables. Once again following Lemma 22, we have,

$$ $\operatorname{\mathbb{E}}_{\xi}\mathopen{}\mathclose{{}\left[\sup_{\mathcal{H} (\mu\,|\,\tau)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\hat{y}(\boldsymbol{x}^{( i)};\mu)}\right]\leq\frac{M}{\alpha}+\frac{1}{\alpha}\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\ln\int\exp\mathopen{}\mathclose{{}\left(\frac{ \alpha^{2}}{2n^{2}}\sum_{i=1}^{n}\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w})^{2} }\right)\mathrm{d}\tau(\boldsymbol{w})}}\right].$ $$

Furthermore,

$$ $\displaystyle\int\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2}}{2n^{2}} \sum_{i=1}^{n}\Psi(\boldsymbol{x}^{(i)};\boldsymbol{w})^{2}}\right)\mathrm{d} \tau(\boldsymbol{w})$ $\displaystyle\leq\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2}\varphi(0)^ {2}}{n^{2}}}\right)\int\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2} \mathopen{}\mathclose{{}\left\|{\varphi^{\prime}}}\right\|_{\infty}^{2}}{n^{2} }\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{ \boldsymbol{x}^{(i)}}}\right\rangle^{2}}\right)\mathrm{d}\tau(\boldsymbol{w})$ $\displaystyle\leq\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2}\varphi(0)^ {2}}{n}}\right)\int\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2}\mathopen {}\mathclose{{}\left\|{\varphi^{\prime}}}\right\|_{\infty}^{2}}{n}\mathopen{} \mathclose{{}\left\langle{\boldsymbol{w}},{\hat{\boldsymbol{\Sigma}} \boldsymbol{w}}}\right\rangle}\right)\mathrm{d}\tau(\boldsymbol{w})$ $\displaystyle\leq\exp\mathopen{}\mathclose{{}\left(\frac{\alpha^{2}\mathopen{} \mathclose{{}\left[\varphi(0)^{2}+\mathopen{}\mathclose{{}\left\|{\varphi^{ \prime}}}\right\|_{\infty}^{2}\mathopen{}\mathclose{{}\left\|{\hat{\boldsymbol {\Sigma}}}}\right\|}\right]}{n}}\right).$ $$

Therefore,

$$ $\operatorname{\mathbb{E}}_{\xi}\mathopen{}\mathclose{{}\left[\sup_{\mathcal{H} (\mu\,|\,\tau)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\hat{y}(\boldsymbol{x}^{( i)};\mu)}\right]\leq\frac{M}{\alpha}+\alpha\frac{\varphi(0)^{2}+\mathopen{} \mathclose{{}\left\|{\varphi^{\prime}}}\right\|_{\infty}^{2}\mathopen{} \mathclose{{}\left\|{\hat{\boldsymbol{\Sigma}}}}\right\|}{n}.$ $$

Using $\mathopen{}\mathclose{{}\left|{\varphi(0)}}\right|,\mathopen{}\mathclose{{}
\left\|{\varphi^{\prime}}}\right\|_{\infty}\lesssim 1$ and optimizing over $\alpha$ yield

$$ $\operatorname{\mathbb{E}}_{\xi}\mathopen{}\mathclose{{}\left[\sup_{\mathcal{H} (\mu\,|\,\tau)\leq M}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\hat{y}(\boldsymbol{x}^{( i)};\mu)}\right]\lesssim\sqrt{\frac{M}{n}}\mathopen{}\mathclose{{}\left(1+ \mathopen{}\mathclose{{}\left\|{\hat{\boldsymbol{\Sigma}}^{1/2}}}\right\|} \right).$ $$

Taking expectation with respect to the training set concludes the proof.
∎

We can also control the effect of truncating similar to that of Lemma 24.

###### Lemma 34 .

Under the setting of Example 7, for any $\mu\in\mathcal{P}(\mathcal{W})$, we have

$$ $\mathcal{J}_{0}(\mu)-\mathcal{J}_{0}^{\varkappa}(\mu)\leq 2C_{\rho}^{2}\cdot \frac{2\varphi(0)^{2}+2\mathopen{}\mathclose{{}\left\|{\varphi^{\prime}}} \right\|_{\infty}^{2}\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}} \right\|+\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}}\right ]}{\varkappa}.$ $$

Proof.
Similarly to the arguments in Lemma 24, by using the Cauchy-Schwartz and Markov inequalities, we have

$$ $\displaystyle\mathcal{J}_{0}(\mu)-\mathcal{J}_{0}^{\varkappa}(\mu)$ $\displaystyle\leq\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{ \mathbbm{1}(\rho(\hat{y}(\boldsymbol{x};\mu)-y)\geq\varkappa)\rho(\hat{y}( \boldsymbol{x};\mu-y))}}\right]$ $\displaystyle\leq\mathbb{P}\mathopen{}\mathclose{{}\left({\rho(\hat{y}( \boldsymbol{x};\mu)-y)\geq\varkappa}}\right)^{1/2}\operatorname{\mathbb{E}} \mathopen{}\mathclose{{}\left[{\rho(\hat{y}(\boldsymbol{x};\mu)-y)^{2}}}\right ]^{1/2}$ $\displaystyle\leq C_{\rho}\mathbb{P}\mathopen{}\mathclose{{}\left({\mathopen{} \mathclose{{}\left|{\hat{y}(\boldsymbol{x};\mu)-y}}\right|\geq\varkappa/C_{ \rho}}}\right)^{1/2}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{( \hat{y}(\boldsymbol{x};\mu)-y)^{2}}}\right]^{1/2}$ $\displaystyle\leq C_{\rho}^{2}\frac{\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{(\hat{y}(\boldsymbol{x};\mu)-y)^{2}}}\right]}{\varkappa}$ $\displaystyle\leq 2C_{\rho}^{2}\frac{\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\hat{y}(\boldsymbol{x};\mu)^{2}}}\right]+\operatorname{ \mathbb{E}}\mathopen{}\mathclose{{}\left[{y^{2}}}\right]}{\varkappa}.$ $$

Moreover, we have

$$ $\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\hat{y}( \boldsymbol{x};\mu)^{2}}}\right]\leq\operatorname{\mathbb{E}}\mathopen{} \mathclose{{}\left[{\int\Psi(\boldsymbol{x};\boldsymbol{w})^{2}\mathrm{d}\mu( \boldsymbol{w})}}\right]$ $\displaystyle\leq 2\varphi(0)^{2}+2\mathopen{}\mathclose{{}\left\|{\varphi^{ \prime}}}\right\|_{\infty}^{2}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{ }\left[{\int\mathopen{}\mathclose{{}\left\langle{\boldsymbol{w}},{\boldsymbol{ x}}}\right\rangle^{2}\mathrm{d}\mu(\boldsymbol{w})}}\right]$ $\displaystyle\leq 2\varphi(0)^{2}+2\mathopen{}\mathclose{{}\left\|{\varphi^{ \prime}}}\right\|_{\infty}^{2}\mathopen{}\mathclose{{}\left\|{\boldsymbol{ \Sigma}}}\right\|,$ $$

concluding the proof of the lemma.
∎

Finally, we can state the proof of the main theorem of this section.

Proof. [Proof of Theorem 10]
Note that given $\beta=\frac{\bar{\Delta}}{\varepsilon}$ and $d\geq 2C_{\rho}K\bar{\Delta}/(\varrho\varepsilon)$, Proposition 9 guarantees that $C_{\mathrm{LSI}}\leq 2/(\varrho d)$ along the trajectory. Consequently, by the convergence guarantee of (2.10), we have

$$ $\displaystyle\mathcal{F}_{\beta}(\mu_{T})\leq\mathcal{F}_{\beta}(\mu^{*}_{ \beta})+e^{-\frac{\varrho dT}{\beta}}(\mathcal{F}_{\beta}(\mu_{0})-\mathcal{F} _{\beta}(\mu^{*}_{\beta}))\leq\mathcal{F}_{\beta}(\mu^{*}_{\beta})+\varepsilon.$ $$

Further, by $\bar{\mu}$ of Assumption 4, we have

$$ $\mathcal{F}_{\beta}(\mu^{*}_{\beta})\leq\mathcal{F}_{\beta}(\bar{\mu})\leq\bar {\varepsilon}+\beta^{-1}\bar{\Delta}\leq\bar{\varepsilon}+\varepsilon.$ $$

As a result, $\hat{\mathcal{J}}_{0}(\mu_{T})\leq\mathcal{F}_{\beta}(\mu_{T})\leq\bar{
\varepsilon}+2\varepsilon$, and similarly $\mathcal{H}(\mu_{T}\,|\,\tau)\leq\beta(\bar{\varepsilon}+2\varepsilon)$.

Note that $\hat{\mathcal{J}}_{0}^{\varkappa}(\mu_{T})\leq\hat{\mathcal{J}}_{0}(\mu_{T})$. Using the fact that $C_{\rho},\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}}}\right\|,
\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{
{}\left|{y}}\right|^{2}}}\right]\lesssim 1$, and combining the bounds of Lemma 33 and Lemma 34, with a porbability of failure $\delta=\mathcal{O}(n^{-q})$ for some constant $q>0$, we have

$$ $\mathcal{J}_{0}(\mu_{T})-\hat{\mathcal{J}}_{0}(\mu_{T})\lesssim\sqrt{\frac{ \beta(\bar{\varepsilon}+\varepsilon)}{n}}+\varkappa\sqrt{\frac{\ln n}{n}}+ \frac{1}{\varkappa}.$ $$

Optimizing over $\varkappa$ implies

$$ $\displaystyle\mathcal{J}_{0}(\mu_{T})$ $\displaystyle\lesssim\bar{\varepsilon}+\varepsilon+\sqrt{\frac{\beta(\bar{ \varepsilon}+\varepsilon)}{n}}+\mathopen{}\mathclose{{}\left(\frac{\ln n}{n}} \right)^{1/4}$ $\displaystyle\lesssim\bar{\varepsilon}+\varepsilon+\sqrt{\frac{\bar{\Delta}(1+ \bar{\varepsilon}/\varepsilon)}{n}}+\mathopen{}\mathclose{{}\left(\frac{\ln n} {n}}\right)^{1/4}.$ $$

Choosing $n$ according to the statement of the theorem completes the proof.
∎

###### Lemma 33 .

###### Lemma 34 .

## Appendix C Comparisons with the Formulation of [ 55 ]

Here, we provide a number of comparisons with results of []. In Section C.1, we show that the statistical model (2.1) is more general than their formulation, even for parity learning problems. In Section C.2, we provide an informal comparison of their effective dimension to our setting, exhibiting the improvement in our definition of effective dimension.

### C.1 Generality of the Formulations

We begin by pointing out that the formulation of $k$-index model of (2.1) is strictly more general than that of [], even for learning $k$-sparse parities. Recall that in their setting, they consider inputs of the type $\boldsymbol{x}=\boldsymbol{\Sigma}^{1/2}\boldsymbol{z}$ for some positive definite $\boldsymbol{\Sigma}$, where $\boldsymbol{z}\sim\textnormal{Unif}(\{\pm 1\}^{d})$ (their original formulation uses $\boldsymbol{z}\sim\textnormal{Unif}(\{\pm 1/\sqrt{d}\}^{d})$, but we rescale the input to be consistent with the notation of this paper). The labels are given by

$$ $y=\mathop{\mathrm{missing}}{sign}\Big{(}\prod_{i=1}^{k}\mathopen{}\mathclose{{ }\left\langle{\tilde{\boldsymbol{u}}_{i}},{\boldsymbol{z}}}\right\rangle\Big{) }=\mathop{\mathrm{missing}}{sign}\Big{(}\prod_{i=1}^{k}\mathopen{}\mathclose{{ }\left\langle{\boldsymbol{\Sigma}^{-1/2}\tilde{\boldsymbol{u}}_{i}},{ \boldsymbol{x}}}\right\rangle\Big{)},$ (C.1) $$

where $\{\tilde{\boldsymbol{u}}_{i}\}_{i=1}^{k}$ are orthonormal vectors. Then, we can define an orthonormal set of vectors $\{\boldsymbol{u}_{i}\}_{i=1}^{k}$ such that $\operatorname{span}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{k})=
\operatorname{span}(\boldsymbol{\Sigma}^{-1/2}\tilde{\boldsymbol{u}}_{1},
\ldots,\boldsymbol{\Sigma}^{-1/2}\tilde{\boldsymbol{u}}_{k})$, and define $g$ such that

$$ $g\mathopen{}\mathclose{{}\left(\frac{\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{u}_{1}},{\boldsymbol{x}}}\right\rangle}{\sqrt{k}},\ldots,\frac{ \mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{k}},{\boldsymbol{x}}} \right\rangle}{\sqrt{k}}}\right)=g\mathopen{}\mathclose{{}\left(\frac{ \mathopen{}\mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{ 1}},{\boldsymbol{z}}}\right\rangle}{\sqrt{k}},\ldots,\frac{\mathopen{} \mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{k}},{ \boldsymbol{z}}}\right\rangle}{\sqrt{k}}}\right)=\mathop{\mathrm{missing}}{ sign}\Big{(}\prod_{i=1}^{k}\mathopen{}\mathclose{{}\left\langle{\tilde{ \boldsymbol{u}}_{i}},{\boldsymbol{z}}}\right\rangle\Big{)},$ $$

for all $\boldsymbol{z}\in\{\pm 1\}^{d}$. Therefore, the parity formulation of (C.1) can be seen as a special case of the $k$-index model (2.1). Note that $g$ is only defined on $2^{d}$ points, and we can extend it to all of $\mathbb{R}^{k}$ such that $g:\mathbb{R}^{k}\to\mathbb{R}$ is Lipschitz continuous.

In contrast, the $k$-index model can represent parity problems that cannot be represented by (C.1). Starting from an orthonormal set of vectors $\{\boldsymbol{u}_{i}\}_{i=1}^{k}$ in $\mathbb{R}^{d}$, let

$$ $y=g\mathopen{}\mathclose{{}\left(\frac{\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{u}_{1}},{\boldsymbol{x}}}\right\rangle}{\sqrt{k}},\ldots,\frac{ \mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{k}},{\boldsymbol{x}}} \right\rangle}{\sqrt{k}}}\right)=\mathop{\mathrm{missing}}{sign}\Big{(}\prod_{ i=1}^{k}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{u}_{i}},{\boldsymbol{ x}}}\right\rangle\Big{)}.$ (C.2) $$

Consider the case where $k=2$, then $y=\mathop{\mathrm{missing}}{sign}\Big{(}\mathopen{}\mathclose{{}\left\langle{
\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}},{\boldsymbol{z}}}\right\rangle
\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{
2}},{\boldsymbol{z}}}\right\rangle\Big{)}$. To be able to reformulate this to (C.1), we need to be find orthonromal $\tilde{\boldsymbol{u}}_{1},\tilde{\boldsymbol{u}}_{2}\in\mathbb{R}^{d}$ such that

$$ $\mathop{\mathrm{missing}}{sign}\Big{(}\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}},{\boldsymbol{z}}}\right\rangle \mathopen{}\mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{ 2}},{\boldsymbol{z}}}\right\rangle\Big{)}=\mathop{\mathrm{missing}}{sign}( \mathopen{}\mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_{1}},{\boldsymbol{ z}}}\right\rangle\mathopen{}\mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_{ 2}},{\boldsymbol{z}}}\right\rangle),\quad\forall z\in\{\pm 1\}^{d}.$ $$

If $\boldsymbol{\Sigma}$ has rank less than $d$ such that $\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}=\boldsymbol{\Sigma}^{1/2}
\boldsymbol{u}_{2}$, then the above implies $\mathop{\mathrm{missing}}{sign}(\mathopen{}\mathclose{{}\left\langle{\tilde{
\boldsymbol{u}}_{1}},{\boldsymbol{z}}}\right\rangle\mathopen{}\mathclose{{}
\left\langle{\tilde{\boldsymbol{u}}_{2}},{\boldsymbol{z}}}\right\rangle)\geq 0$ for all $\boldsymbol{z}\in\{\pm 1\}^{d}$. In particular, we must have some $\boldsymbol{z}$ where $\mathop{\mathrm{missing}}{sign}(\mathopen{}\mathclose{{}\left\langle{\tilde{
\boldsymbol{u}}_{1}},{\boldsymbol{z}}}\right\rangle\mathopen{}\mathclose{{}
\left\langle{\tilde{\boldsymbol{u}}_{2}},{\boldsymbol{z}}}\right\rangle)>0$, which implies that

$$ $\sum_{i=1}^{2^{d}}\mathopen{}\mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_ {1}},{\boldsymbol{z}_{i}}}\right\rangle\mathopen{}\mathclose{{}\left\langle{ \tilde{\boldsymbol{u}}_{2}},{\boldsymbol{z}_{i}}}\right\rangle=\mathopen{} \mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_{1}},{\sum_{i=1}^{2^{d}} \boldsymbol{z}_{i}\boldsymbol{z}_{i}^{\top}\tilde{\boldsymbol{u}}_{2}}}\right \rangle=2^{d}\mathopen{}\mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_{1}}, {\tilde{\boldsymbol{u}}_{2}}}\right\rangle>0,$ (C.3) $$

which is in contradiction with $\mathopen{}\mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_{1}},{\tilde{
\boldsymbol{u}}_{2}}}\right\rangle=0$. Therefore, for such $\boldsymbol{\Sigma}$, we cannot formulate (C.2) as a special case of (C.1). This argument is robust with respect to small perturbations of $\boldsymbol{\Sigma}$ which make it full-rank. Specifically, suppose $\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{2}=\boldsymbol{\Sigma}^{1/2}
\boldsymbol{u}_{1}+\boldsymbol{\delta}$. Notice that we can choose $\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}$ such that $\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{
1}},{\boldsymbol{z}}}\right\rangle^{2}\neq 0$ for all $\boldsymbol{z}\in\{\pm 1\}^{d}$, e.g. by choosing $\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}\propto\boldsymbol{e}_{1}$, i.e. the first standard basis vector. It is straightforward to construct full-rank $\boldsymbol{\Sigma}$, $\boldsymbol{u}_{1}$, and $\boldsymbol{u}_{2}$ such that $\mathopen{}\mathclose{{}\left\|{\boldsymbol{\delta}}}\right\|$ is arbitrarily small, in which case

$$ $\mathop{\mathrm{missing}}{sign}\Big{(}\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}},{\boldsymbol{z}}}\right\rangle \mathopen{}\mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{ 2}},{\boldsymbol{z}}}\right\rangle\Big{)}=\mathop{\mathrm{missing}}{sign}\Big{ (}\mathopen{}\mathclose{{}\left\langle{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u} _{1}},{\boldsymbol{z}}}\right\rangle^{2}+\mathopen{}\mathclose{{}\left\langle{ \boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{1}},{\boldsymbol{z}}}\right\rangle \mathopen{}\mathclose{{}\left\langle{\boldsymbol{\delta}},{\boldsymbol{z}}} \right\rangle\Big{)}\geq 0.$ $$

Following (C.3), once again the above would be in contradiction with $\mathopen{}\mathclose{{}\left\langle{\tilde{\boldsymbol{u}}_{1}},{\tilde{
\boldsymbol{u}}_{2}}}\right\rangle=0$.
This implies that the $k$-index model (2.1) is strictly more general than (C.1) when considering full-rank covariance matrices.

### C.2 Comparison with the Effective Dimension of [ 55 ]

A close inspection of the proofs in [] demonstrates that one can define their effective dimension in a scale invariant manner as $\tilde{d}_{\mathrm{eff}}\coloneqq\mathop{\mathrm{missing}}{tr}(\boldsymbol{
\Sigma})\mathopen{}\mathclose{{}\left\|{\sum_{i=1}^{k}\boldsymbol{\Sigma}^{-1/
2}\tilde{\boldsymbol{u}}_{i}}}\right\|^{2}$. From the previous section, we observed that to reduce their setting to ours, we need to choose a set $\{\boldsymbol{u}_{i}\}_{i=1}^{k}$ of normalized vectors that spans the set of vectors $\{\boldsymbol{\Sigma}^{-1/2}\tilde{\boldsymbol{u}}_{i}\}_{i=1}^{k}$. In particular, we can choose $\boldsymbol{u}_{i}=\frac{\boldsymbol{\Sigma}^{-1/2}\tilde{\boldsymbol{u}}_{i}}
{\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}^{-1/2}\tilde{\boldsymbol{
u}}_{i}}}\right\|}$, or equivalently write $\tilde{\boldsymbol{u}}_{i}=\frac{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{i}}{
\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{i}}}
\right\|}$. While $\{\boldsymbol{u}_{i}\}_{i=1}^{k}$ are not orthogonal, our proofs do not strictly rely on the orthogonality assumption and it is only made for simplicity.
Hence, we have

$$ $\tilde{d}_{\mathrm{eff}}=\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma}) \mathopen{}\mathclose{{}\left\|{\sum_{i=1}^{k}\frac{\boldsymbol{u}_{i}}{ \mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}^{1/2}\boldsymbol{u}_{i}}} \right\|}}}\right\|^{2}\leq k\mathop{\mathrm{missing}}{tr}(\boldsymbol{\Sigma} )\sum_{i=1}^{k}\mathopen{}\mathclose{{}\left\|{\boldsymbol{\Sigma}^{1/2} \boldsymbol{u}_{i}}}\right\|^{-2}.$ $$

Note that the above upper bound is sharp when $k=1$, and is lower bounded by our definition of effective dimension stated in Definition 1. Therefore, we use the above bound in Table 1.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: * The authors claim "the Brownian noise can help escaping from spurious local minima and saddle points" after presenting (2.3). Can you provide some reference of this statement? This is different from SGD which uses inexact oracle (stochastic gradient) leading to different randomness at each iteration. Adding Brownian motion is equivalent to adding randomness with the same magnitude at each iteration.

* In the row between 230 and 231, should the weights be $W\in\mathbb{R}^{(2d+2)\times m}$ instead of $W\in\mathbb{R}^{2d+2}$?

* What is $\mathbb{E}_{\xi}[\rho(\xi)]$ in Thm 3?

* Assumption 1 is restrictive to me. Could you provide some references which also consider this assumption on dataset? Or could you verify this assumption on some dataset? Is this assumption only for the proof? If so, why you need this assumption in your proof should be clearly stated in the main paper. It would be helpful to provide some proof sketch of Thm 3 discussing that.

* Since you establish better sample complexity under subgaussian data assumption, it would be interesting to do more simulation even with artificial mean-zero and subgaussian data for empirical comparison with other results in Table 1.
soundness: 3
strengths: * The presentation is good, which is easy to follow.
* Discussion on previous works is extensive and informative, and comparison with previous works is clear.
* This paper uses MFLA to learn multi-index model and consider the effective dimension, which is novel to me.
* This paper achieves optimal sample complexity, albeit leading to exponential dependence of $d_{eff}$ in $\mathbb{R}^d$. But the authors well explain this phenomenon and improve this dependence in Riemannian manifold under some curvature conditions.
summary: This paper explores learning multi-index models in high dimensions using a two-layer neural network trained with the mean-field Langevin algorithm (MFLA). The authors identify an "effective dimension" that can significantly reduce sample complexity by adapting to low-dimensional structures in data. While worst-case computational complexity may still grow exponentially, they propose a solution to achieve polynomial-time convergence by constraining weights to a compact manifold under specific conditions.
weaknesses: * Discussion on Assumption 1 is weak.
* Some notations are not clearly stated.
* This paper is short of some simulation.

See more details in Questions below.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See the weakness part.
soundness: 3
strengths: 1. This paper is well-written, clear, and mathematically rigorous.

2. Theoretical guarantees and insights into feature learning in deep learning are notoriously challenging, so any solid progress in this area is highly valuable. In particular, I find the paper’s second contribution quite interesting. Identifying cases where polynomial-time complexity (and thus efficient learning) can be achieved under the mean-field regime is of great importance, and this work is among the first to address this question, even if the current assumptions are somewhat restrictive.
summary: This paper examines the sample and computational complexity of learning general multi-index models in high-dimensional settings using two-layer neural networks and the mean-field Langevin algorithm. Under very mild assumptions, the authors successfully demonstrate that the sample complexity for such learning scales linearly with the effective input dimension, $d_{\text{eff}}$, which is information-theoretic optimal. However, the computational complexity typically scales exponentially with $d_{\text{eff}}$, which is also in general unavoidable. To address this, the authors explore specific conditions under which computational complexity might have a polynomial dependence on $d_{\text{eff}}$. They identify certain settings—such as particular target functions and constraints on weights to lie on the hypersphere—that allow for the desired polynomial-time convergence.
weaknesses: I feel that the result in the first part is somewhat expected (though I recognize that proving it rigorously is still a quite valuable accomplishment. For the second part, I wonder if it might be possible to establish a polynomial-time convergence guarantee for a broader class of target functions (beyond the teacher neuron setup) by furthermore just considering the case where we restrict the weights just to the sphere. In general, I am convinced that a more detailed analysis/discussion would be valuable regarding the setups in which polynomial-time convergence with optimal sample complexity can be achieved, even when the input distribution is inherently high-dimensional, such as standard normal distribution with mean zero and covariance $\Sigma = I_d$.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: See the Weakness part of the review.
soundness: 3
strengths: * Overall, the paper is well-written, and the presentation is clear. 
* Proving polynomial convergence guarantees for MFLA is an important and challenging subject. This paper makes process in 
  this direction by proving a bound that is exponential in the effective dimension. They also show that for certain 
  models, the effective dimension can be as small as $O(\mathrm{poly}\log d)$, which leads to a quasi-polynomial 
  convergence guarantee.
summary: In this work, the authors study the task of learning a general multi-index model using neural networks and the 
mean-field Langevin Algorithm (MFLA). Specifically, the authors introduce a notion of effective dimension in this context, 
which can potentially be much smaller than the ambient dimension when the input distribution is spiked the spikes 
align with the relevant subspace of the target multi-index model. Then, the author derive bounds for the sample and 
computational complexity of MFLA based the effective dimension in both Euclidean and Riemannian settings.
weaknesses: * My main concern with this paper is that the effective dimension, as defined in Definition 1, is essentially about 
  how spiked the input distribution is (and whether it aligns with the target function) and does NOT capture the potential 
  low-dimensional structure of the target function. 
  In fact, if the input distribution is isotropic, the effective dimension (as defined in Definition 1) will be
  $d$ even when the target function is a single-index model. 
  This limits the applicability of this paper's results, as it does not cover even the simplest Gaussian single-index case.
* The comparison with the information/generative exponent (Section 3.1) is misleading. The authors suggest that one 
  advantage of the MFLA analysis over the information/generative exponent analysis is that the sample complexity is 
  always $\tilde{O}(d)$ (in the isotropic case), while for SGD, (the bounds on) the sample complexity can be $\tilde{\omega}(d)$
  when the information/generative exponent is larger than $2$. However, this is not true if we are allowed to have 
  exponentially many neurons, as assumed in the setting of Corollary 4. It has been shown in the information exponent paper [1]
  that after the neuron attains a constant correlation with the ground-truth direction, the number of samples needed 
  in the final "descent" phase is $\tilde{O}(d)$ regardless the information exponent. Meanwhile, if we have 
  exponentially many neurons, we can ensure that some neuron will have a constant correlation with the ground-truth 
  direction at initialization with at least constant probability. In addition, the number of steps needed in the 
  information exponent analysis is also $\tilde{O}(d)$, which is better than the exponential bound given in Corollary 4. 
* In Sec. 4 (the Riemannian setting), the authors require the existence of a good distribution $\mu$ with a small loss 
  and $H(\mu | \tau) = o(d)$ where $\tau$ is the uniform distribution on the manifold. They justify the second condition 
  in Prop. 8 by showing that if the ground-truth distribution is given by $\mu^* \propto e^f \mathrm{d} \tau$, then we have 
  $H(\mu^* | \tau) \le \mathrm{osc}(f)$. However, this bound is vacuous if $\mu^*$ is supported only on a few points as $f$ would then take $\infty$ (or a large value if 
  we smooth $\mu^*$). This excludes models such as the single-index model and $k$-multi-index model with $k$ being small.
  To be fair, the authors do mention this limitation in the paper. I just think this assumption is too strong/unnatural. 
  It would be great if the authors could give a natural example where this condition holds. 


[1] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. 2021

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - Can we derive a LSI like in Proposition 2 in a setting where there is no explicit regularization, but instead we make a dissipativity assumption on the model? Could it be of any interest to extend the analysis beyond regularization?

 - Could you explain further the meaning of the expectation $E_\xi [\rho(\xi)]$ is Equation (3.6)?

 - Could part of the analysis be extended to more complex function classes than 2 layers neural networks?

 - Is it possible to construct explicit examples where the computational complexity becomes exponential in the effective dimension?
soundness: 4
strengths: - Both the statistical and the computational complexity are bounded in terms of a newly introduced effective dimension, which is a measure of the complexity of the learning task. It is interesting that the same quantity can be used for both notions of complexity.

 - The study of Mean-Filed Langevin Dynamics may provide important insights on the sample complexity of modern deep learning models.

 - The limitations of the paper are well-discussed.

 - The paper is well-written. Even though the subject is quite technical, good technical background and references are provided, making it sufficiently clear. The assumptions and theorems are clearly stated.
summary: This paper studies the sample and computational complexities of the mean field Langevin algorithm (MFLA). The analysis is centered aroung a newly introduced ``effective dimension'' which measures the complexity of the learning task (in terms of the data distribution and the teacher model). Under several regularity conditions and conditions on various constants, it is proven that the sample complexity and the computational complexity can both be controlled in terms of the effective dimension, which can be significantly smaller than the ambient dimension of the input space. The authors estimate (theoretically) this effective dimension on several examples. While the sample complexity bound is very satisfying and scales linearly in the effective dimension, the computational complexity may scale exponentially in the effective dimension and linearly in the ambient dimension. While this might be an issue in the general case, the authors show that this issue can be alleviate in a compact Riemannian setting. Improving the exponential dependence in the Euclidean setting remains open.
weaknesses: - The computational complexity may scale exponentially with the effective dimension (in the worst case). While the authors show that this might not be an issue in a compact Riemannian setting, the issues persists in the Euclidean setting. Additional discussion on how to go beyond this Riemanian setting could enhance the paper. In particular, what are (maybe intuitively) the conditions that could lead to non-exponential complexity?

 - As discussed in the paper, the analysis is restricted to a particular class of 2 layers neural networks. Moreover, the analysis is restricted to ``simple'' learning tasks, ie, the teacher models uses $k \ll d$ neurons. It could be interesting to further discuss what the results become when $k$ Is large.

Meta-review: The paper studies downsampling in group equivariant neural networks. The paper introduces a notion of downsampling by a factor R which is applicable to general finite groups. The idea is to form a subgroup G’ by replacing a generator s with its R power s^R, eliminating elements which are generated by s^1, s^2, \dots s^{R-1}. If R is a composite integer, this subsampling can be ``spread’’ over generators, replacing s_1 with s_1^{R_1}, s_2 with s_2^{R_2} and so forth, with R_1 R_2 … = R. The paper gives an algorithm for constructing the resulting subgroup based on the Cayley graph. The paper then develops a notion of bandlimiting and an ideal antialiasing for this downsampling operator. All of these constructions generalize standard downsampling over the cyclic group. 

The main strength of the paper is its conceptual and theoretical contributions: it gives a principled method for performing downsampling (with appropriate antialiasing) in group CNN. This is important conceptually, since ad-hoc downsample (or downsampling without antialiasing) can break equivariance. The paper demonstrates how to algorithmically determine a subgroup to downsample to, and how to construct an appropriate antialiasing filter. The initial submission demonstrated that this helps to improve equivariance in certain settings (MNIST, CFAR-10). The revision augments these results with experiments on higher resolution data (STL10).

Decision: Accept (Poster)