The replicability crisis is a major issue across nearly all areas of
empirical science, calling for the formal study of replicability in statistics.
Motivated in this context, [Impagliazzo, Lei, Pitassi, and Sorrell STOC 2022]
introduced the notion of replicable learning algorithms, and gave basic
procedures for $1$-dimensional tasks including statistical queries. In this
work, we study the computational and statistical cost of replicability for
several fundamental high dimensional statistical tasks, including
multi-hypothesis testing and mean estimation.
Our main contribution establishes a computational and statistical equivalence
between optimal replicable algorithms and high dimensional isoperimetric
tilings. As a consequence, we obtain matching sample complexity upper and lower
bounds for replicable mean estimation of distributions with bounded covariance,
resolving an open problem of [Bun, Gaboardi, Hopkins, Impagliazzo, Lei,
Pitassi, Sivakumar, and Sorrell, STOC2023] and for the $N$-Coin Problem,
resolving a problem of [Karbasi, Velegkas, Yang, and Zhou, NeurIPS2023] up to
log factors.
While our equivalence is computational, allowing us to shave log factors in
sample complexity from the best known efficient algorithms, efficient
isoperimetric tilings are not known. To circumvent this, we introduce several
relaxed paradigms that do allow for sample and computationally efficient
algorithms, including allowing pre-processing, adaptivity, and approximate
replicability. In these cases we give efficient algorithms matching or beating
the best known sample complexity for mean estimation and the coin problem,
including a generic procedure that reduces the standard quadratic overhead of
replicability to linear in expectation.

研究了可复制性的计算和统计等价性以及高维统计任务中的样本复杂度，并提出了解决分布有有界协方差和 N-Coin 问题中的开放问题的有效算法。

高维统计中的可复制性

Replicability in High Dimensional Statistics

The replicability crisis in the social, behavioral, and data sciences has led
to the formulation of algorithm frameworks for replicability -- i.e., a
requirement that an algorithm produce identical outputs (with high probability)
when run on two different samples from the same underlying distribution. While
still in its infancy, provably replicable algorithms have been developed for
many fundamental tasks in machine learning and statistics, including
statistical query learning, the heavy hitters problem, and distribution
testing. In this work we initiate the study of replicable reinforcement
learning, providing a provably replicable algorithm for parallel value
iteration, and a provably replicable version of R-max in the episodic setting.
These are the first formal replicability results for control problems, which
present different challenges for replication than batch learning settings.

本篇文章探索了在机器学习中的可复制性问题，提出了一个可复制的算法架构和针对不同领域的可复制性解决方案，包括针对控制问题和批量学习设置的评估模型。