概要: 再現性とは、独立に抽出されたデータ上で再実行しても、アルゴリズムによる結論が一貫していることを要求する。中心となる構造的な問いは合成である。すなわち、
ho-再現可能（replicable）なアルゴリズムが各々の問題に対してサンプル計算量 n をもつとき、再現性を保ったまま、k 個の問題をすべて同時に解くには何個のサンプルが必要なのか？素朴な解析では frac{O}(nk^2) のサンプルが必要という結果が得られる。Bun ら（STOC'23）は、差分プライバシーによる還元によって別の frac{O}(n^2k) の上界が得られることを観察し、最適な frac{O}(nk) スケーリングが達成可能かどうかが未解決のまま残っていた。我々はこの未解決問題を解決し、さらに一般に、サンプル計算量が n_1, である問題は、一定の再現性（constant replicability）を保ちながら、
\ldots,n_kfrac{O}(\sum_i n_i) 個のサンプルで同時に解けることを示す。我々の手法は、各再現可能アルゴリズムを完全に汎化する（perfectly generalizing）アルゴリズムへと変換し、プライバシー風の解析でそれらを合成し、相関サンプリング（correlated sampling）によって元に戻す。これにより、再現性のための最初の高度な合成定理（advanced composition theorem）が得られる。途上で、異種パラメータをもつ完全に汎化するアルゴリズムの合成に対する新しい上界も得る。
我々の結果の一部として、再現可能アルゴリズムの成功確率に対するブースティング定理も提示する。問題の広いクラスにおいて、失敗確率は
ho に依存しない別個の加法項として現れるため、いくつかの問題について改良されたサンプル計算量の上界が直ちに導かれる。
最後に、適応的合成（adaptive composition）に対して Omega(nk^2) の下界を証明し、非適応的設定（non-adaptive setting）との間に二次の分離（quadratic separation）があることを確立する。主要な技術は、我々がファントムラン（phantom run）と呼ぶものであり、独立して興味のある構造的結果を与える。
再現可能な構成
arXiv cs.LG / 2026/4/14
📰 ニュースSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、複数の「再現可能（独立にサンプリングされたデータ上で一貫性がある）」アルゴリズムを、再現可能性を保ったままどのように合成できるかを研究し、そのために必要な同時サンプル複雑度に焦点を当てる。
- 各問題が個別に必要とするサンプル複雑度が n である k 個の問題を、全体としてほぼ 2(nk) のスケーリング（より一般には 2(\sum_i n_i)）で同時に解けることを示し、未解決問題を解決する。これにより、従来の 2(nk^2) や 2(n^2k) の上界を改善する。
- 手法は、各再現可能なアルゴリズムを完全に汎化するものへ変換し、それらをプライバシー流の議論で合成した後、相関サンプリングによって元に戻すことで機能する。
- 著者らは、失敗確率を再現可能性パラメータ \rho から切り離すブースティング定理を提示し、複数の問題に対して改善されたサンプル複雑度の境界を与える。
- さらに、新しい技術「phantom run（ファントム実行）」を用いて、適応的な合成に対する \Omega(nk^2) の下界も証明しており、適応設定と非適応設定の間に二次的なギャップがあることを示す。
