The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels

We thank the reviewer for the time and effort invested, and the kind review.

Below we answer the questions in detail.

• Technical challenge. There are three main tools for deriving lower bounds in the minimax setting: Le Cam's method, Fano's method, and Assouad's lemma. The main technical challenge in applying these known tools is coming up with an adversarial distribution pair and then also showing that the assumptions of the respective statements are all satisfied. In our case, we chose Le Cam's method and showed that its assumptions are satisfied for the parameterized Gaussian distribution (5) and its instantiations in Line 239 in the case of HSIC.
• Difference to (Zhou et al., 2019). Indeed, the rate obtained by (Zhou et al., 2019) for the covariance operator is the same as the one that we obtained for HSIC. Intuitively, one would guess that estimating the covariance operator, an element in a tensor product RKHS, is more challenging than estimating HSIC, a real number. Surprisingly, this is not the case, as our results indicate. Moreover, by an application of the reverse triangle inequality, our result allows to recover their result (see Corollary 1 and its proof). Regarding differences in the proof: The distribution pair considered by (Zhou et al., 2019) has a product structure, which, similar to (Tolstikhin et al., 2016), does not allow to obtain a lower bound for HSIC estimation.

We hope that this answers all the questions of the reviewer.

References.

Tolstikhin, I. O., Sriperumbudur, B. K., & Schölkopf, B. (2016). Minimax estimation of maximum mean discrepancy with radial kernels. Advances in Neural Information Processing Systems, 29.

Zhou, Y., Chen, D. R., & Huang, W. (2019). A class of optimal estimators for the covariance operator in reproducing kernel Hilbert spaces. Journal of Multivariate Analysis, 169, 166-178.

We thank the reviewer for the time and effort invested, and the kind review.

In the following, we answer the questions.

• Related work. The related work can be divided into lower bounding the rate of estimating (1) the kernel mean embedding, (2) maximum mean discrepancy, and (3) the covariance operator. The existing results do not permit establishing the minimax rate of HSIC estimation due to the following reasons.

1. The estimation of the mean embedding (1) concerns the estimation of an element in an RKHS, which could be more difficult than the estimation of a real-valued function of it (MMD; Tolstikhin et al., 2016, or, in our case, HSIC).
2. The proof for obtaining the lower bound of (2) relies on a distribution pair in which both distributions factorize, that is, they are independent. The corresponding HSIC value is thus zero and Le Cam's method is not applicable; hence the existing proof does not address the setting of HSIC.
3. In the case of (3), one intuitively expects that estimating the real-valued HSIC is "easier" than estimating the covariance operator, which is an element in a tensor product RKHS. Our result sheds light on a surprising phenomenon: this intuition is false. Moreover, with Corollary 1, we are able to recover the lower bound on covariance operator estimation.

These notes are also elaborated in Remark 1(c)--(e).

• Definition of HSIC. HSIC captures the dependencies of a probability measure by quantifying the discrepancy of the measure to the product of its marginals as the distance of the corresponding mean elements in an RKHS. This also corresponds to the norm of the cross-covariance operator, which (2) makes explicit; the equivalence holds for arbitrary kernel-enriched domains. In line with Line 121-122 and Theorem 1, and as correctly stated in the review, we consider $\mathcal{X} = \times_{m=1}^M \mathcal{X_m}$ with $\mathcal{X}=\mathbb{R}^d$ (for the domain of $\mathbb{P}$), $\mathcal{X}_m=\mathbb{R}^{d_m}$, i.e. one has the decomposition $d=d_1 + \cdots + d_M$, with $\mathbb P_m$-s being the corresponding marginals of $\mathbb{P}$ on $\mathbb R^{d_m}$ ($m=1,\ldots,M$). The associated kernels are $k_m:\mathbb R^{d_m} \times \mathbb R^{d_m} \to \mathbb{R}$.

We hope that this answer clarifies all the questions of the reviewer.

References.

Tolstikhin, Ilya O., Bharath K. Sriperumbudur, and Bernhard Schölkopf. "Minimax estimation of maximum mean discrepancy with radial kernels." Advances in Neural Information Processing Systems 29 (2016).

We thank the reviewer for the time and effort invested, and for the kind review.

To answer the question regarding experiments: In the minimax framework, one bounds the convergence rate from above and from below.

• The former can be validated empirically in some cases. Indeed, for HSIC, one can compute the theoretical (= population) HSIC value for a fixed (kernel, distribution)-pair---for instance, for the Gaussian kernel with the Gaussian distribution (Lemma 1)---, and verify the known (Smola et al., 2007; Theorem 2) convergence rate of the estimator w.r.t. this value.
• The latter, that is, the lower bound, can only be derived theoretically---as one must consider all possible estimators ($\inf_{\hat{F_n}}$ in (3)) and all possible probability distributions ($\sup_{P\in\mathcal{P}}$ in (3)) of the considered class ($\mathcal{P}$)---which is what we tackled in this article.

Minor note regarding the point 'existing conclusion only holds for $M=2$': We are not aware of minimax guarantees for HSIC even for $M=2$; our minimax analysis handles both the case of $M=2$ and $M>2$ in a unified fashion (for $M \ge 2$).

We hope that this settles the stated questions.

References.

Smola, A., Gretton, A., Song, L., & Schölkopf, B. (2007). A Hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory (pp. 13-31).