In the misspecified kernel ridge regression problem, researchers usually
assume the underground true function $f_{\rho}^{*} \in [\mathcal{H}]^{s}$, a
less-smooth interpolation space of a reproducing kernel Hilbert space (RKHS)
$\mathcal{H}$ for some $s\in (0,1)$. The existing minimax optimal results
require $\|f_{\rho}^{*}\|_{L^{\infty}}<\infty$ which implicitly requires $s >
\alpha_{0}$ where $\alpha_{0}\in (0,1)$ is the embedding index, a constant
depending on $\mathcal{H}$. Whether the KRR is optimal for all $s\in (0,1)$ is
an outstanding problem lasting for years. In this paper, we show that KRR is
minimax optimal for any $s\in (0,1)$ when the $\mathcal{H}$ is a Sobolev RKHS.

本论文证明了当 H 是一个 Sobolev RKHS 时，对于任何 0 < s < 1，KRR 都是极小化最优的，解决了长期存在的问题。

关于错配核岭回归的最优性

On the Optimality of Misspecified Kernel Ridge Regression

Embedding index that enables fast approximate nearest neighbor(ANN) search,
serves as an indispensable component for state-of-the-art deep retrieval
systems. Traditional approaches, often separating the two steps of embedding
learning and index building, incur additional indexing time and decayed
retrieval accuracy. In this paper, we propose a novel method called Poeem,
which stands for product quantization based embedding index jointly trained
with deep retrieval model, to unify the two separate steps within an end-to-end
training, by utilizing a few techniques including the gradient straight-through
estimator, warm start strategy, optimal space decomposition and Givens
rotation. Extensive experimental results show that the proposed method not only
improves retrieval accuracy significantly but also reduces the indexing time to
almost none. We have open sourced our approach for the sake of comparison and
reproducibility.

本文提出了一种称为 Poeem 的新方法，它采用了产品量化嵌入索引与深度检索模型联合训练的方法，将嵌入学习和索引构建两个步骤统一起来，从而提高了检索准确率，减少了索引时间，并公开了我们的方法以便于比较和重现。