論文の概要: Replicability in High Dimensional Statistics
- arxiv url: http://arxiv.org/abs/2406.02628v1
- Date: Tue, 4 Jun 2024 00:06:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 23:29:51.861062
- Title: Replicability in High Dimensional Statistics
- Title（参考訳）: 高次元統計学における再現性
- Authors: Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye,
- Abstract要約: 本稿では,いくつかの基本的高次元統計課題に対する再現性の計算的および統計的コストについて検討する。
我々の主な貢献は、最適なレプリカブルアルゴリズムと高次元等尺波の計算的および統計的等価性を確立することである。
- 参考スコア（独自算出の注目度）: 18.543059748500358
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
- Abstract（参考訳）: レプリカ化の危機は、統計学におけるレプリカ化の正式な研究を呼びかけ、実証科学のほぼすべての領域で大きな問題となっている。
この文脈で動機づけられた [Impagliazzo, Lei, Pitassi, Sorrell STOC 2022] は、複製可能な学習アルゴリズムの概念を導入し、統計的クエリを含む1ドルでのタスクの基本的な手順を与えた。
本研究では,複数次元の統計的タスクの再現性に関する計算的・統計的コストについて検討する。
我々の主な貢献は、最適なレプリカブルアルゴリズムと高次元等尺タイリングの計算的および統計的等価性を確立することである。
その結果,有界共分散を持つ分布を推定し, [Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, and Sorrell, STOC2023] および$N$-Coin問題に対して, [Karbasi, Velegkas, Yang, and Zhou, NeurIPS2023] の開問題をログファクターまで解いた。
我々の等価性は計算であり、最もよく知られた効率的なアルゴリズムからサンプルの複雑さのログファクターを削ることができるが、効率的な等尺タイリングは知られていない。
これを回避するために, 前処理, 適応性, 近似複製性など, サンプリングおよび計算効率のよいアルゴリズムを実現する, 緩和されたパラダイムをいくつか導入する。
これらのケースでは、平均推定とコイン問題に最もよく知られたサンプルの複雑さをマッチングまたはビートするアルゴリズムが提供され、その中には、複製可能性の標準的な2次オーバーヘッドを期待値の線形化に還元する一般的な手順が含まれる。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Geometry-Aware Approaches for Balancing Performance and Theoretical
Guarantees in Linear Bandits [6.907555940790131]
トンプソンサンプリングとグリーディは有望な経験的性能を示したが、これは悲観的な理論的後悔の境界とは対照的である。
本研究では不確実楕円体の幾何学的特性を追跡する新しいデータ駆動手法を提案する。
ベースアルゴリズムが不十分な問題インスタンスを特定し,コース修正する。
論文 参考訳（メタデータ） (2023-06-26T17:38:45Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Replicable Reinforcement Learning [15.857503103543308]
本稿では、並列値反復のための証明可能なレプリカブルアルゴリズムと、エピソード設定における証明可能なR-maxのレプリカブルバージョンを提供する。
これらは制御問題に対する最初の公式なレプリカ化結果であり、バッチ学習設定とは異なるレプリケーションの課題を提示している。
論文 参考訳（メタデータ） (2023-05-24T16:05:15Z) - Stability is Stable: Connections between Replicability, Privacy, and
Adaptive Generalization [26.4468964378511]
複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。
データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。
我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
論文 参考訳（メタデータ） (2023-03-22T21:35:50Z) - Best Subset Selection in Reduced Rank Regression [1.4699455652461724]
提案アルゴリズムは,有意な確率でランク推定を行うことができることを示す。
がん研究における数値的研究と応用は、有効性と拡張性を示している。
論文 参考訳（メタデータ） (2022-11-29T02:51:15Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - Statistically Guided Divide-and-Conquer for Sparse Factorization of
Large Matrix [2.345015036605934]
統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。
第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。
第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
論文 参考訳（メタデータ） (2020-03-17T19:12:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。