Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the conditional mean embedding and provides learning rate for the ridge regression based estimator of the CME.
strengths_and_weaknesses: This is a very technical paper and as such I have not verified all the details. Despite being technical the paper does a great job in being clear and precise about the statements.

Conditional mean embeddings (CME), although used frequently in machine learning, have only recently been defined and studied rigorously. This paper is part of that literature and it makes some valuable contributions. The most important of them is using interpolation space theory to study an estimator for the CME operator and provide optimal learning rates.
questions: -
limitations: Not relevant
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The work focuses on estimation of the kernel conditional embedding operator in the so-called mis specified case. The recently proposed idea of interpolation spaces between H_X and L_2 is leveraged to define CME operator with milder conditions (depending on interpolant parameter \beta). 

The key contribution is theorem 4, where an upper bound on estimation error of the CME operator is presented (mis specified case). Though the derivation is technical, the final bound is insightful and depends on the interplay between \beta, \apha (smoothness parameter) and p (eigen value decay parameter). For larger \beta (i.e., less mis specification), in particular, \alpha\le\beta, which is shown to be optimal via theorem 5 that provides a matching lower bound. The upper bound however can be very loose when \beta is tiny.


strengths_and_weaknesses: Overall the paper is well-written and organized. Though technical, enough details are provided to be self-contained. The upper bound is interesting as it explicilty involves the mis-specification parameter. The lower bound on learning rate is also seems to fill a gap in existing literature.


questions: Please verify minor typos:
Consider five equations between eqn(14) and line 479. The fourth equation misses a C_YX term. But it is minor because it is back in the next equation.
limitations: Limitations have been discussed (case of low \beta).
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents novel theoretical results on learning empirical approximations of conditional mean embeddings (CMEs) from samples. The derivations focus on the misspecified case, where the true CME operator does not satisfy the usually strict assumptions found in the literature, but only milder ones which are more plausible in practical settings. The theoretical analysis show that the true CME can be approximated via an interpolation space between the reproducing kernel Hilbert space $\mathcal{H}_X$ of functions over the conditioning inputs $X$ and the Hilbert space $L_2(\pi)$ of square-integrable functions under the inputs marginal distribution $X \sim \pi$.The derived results present an optimal learning rate for the empirical CME approximation, which leads to a vanishing error bound with respect to the true CME operator.
strengths_and_weaknesses: Strengths:
- The theoretical analysis is rigorous and improves on the understanding of CME learning in misspecified settings.
- Assumptions are milder and seem easier to satisfy than the ones found in existing theoretical analyses in the literature.
- The first lower bound on the learning rate for the CME estimator is derived.

Weaknesses:
- The derived results do not hold for the case of the constant function, i.e., when $Y$ is independent of $X$, which is a problem in the case of radial basis function and other characteristic kernels popular in kernel embeddings applications.
- The paper is quite dense at some points and a few details get lost.
questions: * I've missed some important details:
 - It is not specified whether the samples in the dataset for learning CME estimator need to be independent and identically distributed (i.i.d.) w.r.t. the joint the distribution of $X, Y$ or not. Would the results hold for a non-i.i.d. case?
- The statement of Theorem 2 is a bit confusing regarding $\alpha$. Does Thm. 2 hold for any $\alpha > 0$? Or does it imply there is an $alpha > 0$ such that its result holds?
- It is not clear to me how to get to the formulation of $C_{XX}$ in terms of $(\mu_i)_i$ and $(e_i)_i$ in line 135.

* Minor details:
 - In the proof sketch after Theorem 4, are we missing an identity operator next to $\lambda$ in the definition of $F_{Y|X,\lambda}$?

limitations: Most limitations are discussed in the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers estimating the conditional mean embedding (CME). The authors propose an estimation of CME using an approximation in interpolation space.  Consistency and convergence rates are also established for the CME estimator in the misspecified setting.

strengths_and_weaknesses: [Strengths]
1. The presentation of the paper is clear, and estimating the CME is an important problem.
2. The authors provide an operator-theoretic definition of the CME in the misspecified case where the target CME can be well approximated by Hilbert-Schmidt operators.
3. A lower bound on the learning rate is established, which reveals that when the target CME operator is smooth, the obtained upper bound is optimal.

[Weaknesses]
1. It seems that most of the results follow from [8, 39] as well as direct adaption of the interpolation spaces. The background section could be reduced.
2. I am not convinced about the advantages of adapting the interpolation space for approximation. How does the proposed approach compare with related work [39]?
3. While most of the work is theoretical, it could be useful to provide numerical results to demonstrate the performance on real-life data.


questions: See the main comments.
limitations: N/A
review_title: null

Meta-review: metareview: There is a wide consensus among reviewers, after the discussion period, that this submission has strong and novel results where a clear minimax optimality is established for the conditional mean embedding problem.

For the camera ready version, the authors are strongly encouraged to clearly implement all revisions mentioned in the discussion related to the correctness of the lower bound. 
confidence: Certain
Decision: Accept