論文の概要: Replicable Composition
- arxiv url: http://arxiv.org/abs/2604.10423v1
- Date: Sun, 12 Apr 2026 02:43:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:16.006202
- Title: Replicable Composition
- Title（参考訳）: 再現可能な構成法
- Authors: Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari, Samira Goudarzi, MohammadTaghi Hajiaghayi,
- Abstract要約: そこで本研究では,複製性を維持しつつ,$widetildeO(sum_i n_i)$サンプルを共同で解決できることを述べる。
提案手法では, 各レプリカブルアルゴリズムを完全一般化アルゴリズムに変換し, プライバシスタイルの分析により構成し, 相関サンプリングによりマッピングする。
- 参考スコア（独自算出の注目度）: 35.262362690798014
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Replicability requires that algorithmic conclusions remain consistent when rerun on independently drawn data. A central structural question is composition: given $k$ problems each admitting a $ρ$-replicable algorithm with sample complexity $n$, how many samples are needed to solve all jointly while preserving replicability? The naive analysis yields $\widetilde{O}(nk^2)$ samples, and Bun et al. (STOC'23) observed that reductions through differential privacy give an alternative $\widetilde{O}(n^2k)$ bound, leaving open whether the optimal $\widetilde{O}(nk)$ scaling is achievable. We resolve this open problem and, more generally, show that problems with sample complexities $n_1,\ldots,n_k$ can be jointly solved with $\widetilde{O}(\sum_i n_i)$ samples while preserving constant replicability. Our approach converts each replicable algorithm into a perfectly generalizing one, composes them via a privacy-style analysis, and maps back via correlated sampling. This yields the first advanced composition theorem for replicability. En route, we obtain new bounds for the composition of perfectly generalizing algorithms with heterogeneous parameters. As part of our results, we provide a boosting theorem for the success probability of replicable algorithms. For a broad class of problems, the failure probability appears as a separate additive term independent of $ρ$, immediately yielding improved sample complexity bounds for several problems. Finally, we prove an $Ω(nk^2)$ lower bound for adaptive composition, establishing a quadratic separation from the non-adaptive setting. The key technique, which we call the phantom run, yields structural results of independent interest.
- Abstract（参考訳）: リプリケータビリティは、独立して描画されたデータに再実行する際にアルゴリズム的な結論が一貫していることを要求する。
1つに$ρ$-replicableアルゴリズムとサンプルの複雑さが$n$を認めると、複製性を維持しながら、全てを共同で解決するために必要なサンプルがいくつ必要か?
単純解析の結果、$\widetilde{O}(nk^2)$サンプルが得られ、Bun et al (STOC'23) は、差分プライバシーによる削減は代替の$\widetilde{O}(n^2k)$バウンドを与え、最適な$\widetilde{O}(nk)$スケーリングが達成可能かどうかを問わないままにしておくことを観察した。
より一般的には、サンプル複雑度 $n_1,\ldots,n_k$ の問題は、一定の複製性を維持しながら、$\widetilde{O}(\sum_i n_i)$ のサンプルと共同で解けることを示す。
提案手法では, 各レプリカブルアルゴリズムを完全一般化アルゴリズムに変換し, プライバシスタイルの分析により構成し, 相関サンプリングによりマッピングする。
これは、複製性に関する最初の先進的な合成定理をもたらす。
経路において、不均一なパラメータを持つ完全一般化アルゴリズムの構成のための新しい境界を得る。
この結果の一部として、レプリカブルアルゴリズムの成功確率に対するブースティング定理を提案する。
幅広い問題に対して、失敗確率は$ρ$とは独立な別個の加法項として現れ、すぐにいくつかの問題に対して改善されたサンプル複雑性境界が得られる。
最後に、適応合成に対して$Ω(nk^2)$低い境界を証明し、非適応的な設定から二次的分離を確立する。
私たちがファントムランと呼ぶ重要なテクニックは、独立した関心の構造的な結果をもたらす。
関連論文リスト
- Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity [1.655804338897892]
最適サンプリング設定を施した不条件サンプルに対して,スケールド・イテレーションが高速化されることを示す。
さらに, 最適サンプリング設定による不条件試料に対するスケールド収束が促進されることが示唆された。
論文 参考訳（メタデータ） (2026-03-31T05:20:20Z) - Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization [28.497079108813924]
データセットのサイズが$widetildeOmega(sqrtd/alphabeta3+d/epsilonalphabeta2)$である限り、$(alpha,beta)$-stationaryポイントを返すシングルパス$(epsilon,delta)$-DPアルゴリズムを提供する。
次に、サンプルの複雑さを$widetildeOmegaleft(d/beta2+d3/4/epsilonalphaに改善するマルチパス時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-08T10:15:49Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳（メタデータ） (2024-02-21T15:06:51Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - On the Sample Complexity of Privately Learning Axis-Aligned Rectangles [16.092248433189816]
有限格子上で軸-アラインド-矩形を学習する基本的な問題を再考する。
サンプルの複雑さを$tildeOleftdcdotleft(log*|X|right)1.5right$に減らす新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-24T04:06:11Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳（メタデータ） (2020-08-24T15:57:50Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。