A fundamental notion of distance between train and test distributions from
the field of domain adaptation is discrepancy distance. While in general hard
to compute, here we provide the first set of provably efficient algorithms for
testing localized discrepancy distance, where discrepancy is computed with
respect to a fixed output classifier. These results imply a broad set of new,
efficient learning algorithms in the recently introduced model of Testable
Learning with Distribution Shift (TDS learning) due to Klivans et al. (2023).
Our approach generalizes and improves all prior work on TDS learning: (1) we
obtain universal learners that succeed simultaneously for large classes of test
distributions, (2) achieve near-optimal error rates, and (3) give exponential
improvements for constant depth circuits. Our methods further extend to
semi-parametric settings and imply the first positive results for
low-dimensional convex sets. Additionally, we separate learning and testing
phases and obtain algorithms that run in fully polynomial time at test time.

提供了可靠与高效的算法来测试本地化的差异距离，进一步扩展了 TDS 学习模型并改进了之前相关的工作，同时提供了针对常数深度电路的指数级改进，与低维凸集的首个正面结果。

学习中的分布偏移的高效差异性测试

Efficient Discrepancy Testing for Learning with Distribution Shift

Linear Quadratic Regulators (LQR) achieve enormous successful real-world
applications. Very recently, people have been focusing on efficient learning
algorithms for LQRs when their dynamics are unknown. Existing results
effectively learn to control the unknown system using number of episodes
depending polynomially on the system parameters, including the ambient
dimension of the states. These traditional approaches, however, become
inefficient in common scenarios, e.g., when the states are high-resolution
images. In this paper, we propose an algorithm that utilizes the intrinsic
system low-rank structure for efficient learning. For problems of rank-$m$, our
algorithm achieves a $K$-episode regret bound of order $\widetilde{O}(m^{3/2}
K^{1/2})$. Consequently, the sample complexity of our algorithm only depends on
the rank, $m$, rather than the ambient dimension, $d$, which can be
orders-of-magnitude larger.

本篇论文提出一种基于系统内在低秩结构进行高效学习的算法，使样本复杂度只依赖于秩而非环境维度，同时获得了关于 K 的次线性复杂度，在 LQR 问题的应用中取得了较好效果。