論文の概要: The Role of Randomness in Stability
- arxiv url: http://arxiv.org/abs/2502.08007v1
- Date: Tue, 11 Feb 2025 23:06:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-13 13:50:09.384337
- Title: The Role of Randomness in Stability
- Title（参考訳）: 安定性におけるランダム性の役割
- Authors: Max Hopkins, Shay Moran,
- Abstract要約: 学習における安定性という2つの重要な概念,すなわち複製可能性と差分プライバシーのランダム性複雑性について検討する。
安定に対する弱強強化定理(英語版)を証明し、タスクのランダム性複雑性は最適な複製確率によって厳しく制御される。
- 参考スコア（独自算出の注目度）: 20.718747268949112
- License:
- Abstract: Stability is a central property in learning and statistics promising the output of an algorithm $A$ does not change substantially when applied to similar datasets $S$ and $S'$. It is an elementary fact that any sufficiently stable algorithm (e.g.\ one returning the same result with high probability, satisfying privacy guarantees, etc.) must be randomized. This raises a natural question: can we quantify how much randomness is needed for algorithmic stability? We study the randomness complexity of two influential notions of stability in learning: replicability, which promises $A$ usually outputs the same result when run over samples from the same distribution (and shared random coins), and differential privacy, which promises the output distribution of $A$ remains similar under neighboring datasets. The randomness complexity of these notions was studied recently in (Dixon et al. ICML 2024) and (Cannone et al. ITCS 2024) for basic $d$-dimensional tasks (e.g. estimating the bias of $d$ coins), but little is known about the measures more generally or in complex settings like classification. Toward this end, we prove a `weak-to-strong' boosting theorem for stability: the randomness complexity of a task $M$ (either under replicability or DP) is tightly controlled by the best replication probability of any deterministic algorithm solving the task, a weak measure called `global stability' that is universally capped at $\frac{1}{2}$ (Chase et al. FOCS 2023). Using this, we characterize the randomness complexity of PAC Learning: a class has bounded randomness complexity iff it has finite Littlestone dimension, and moreover scales at worst logarithmically in the excess error of the learner. This resolves a question of (Chase et al. STOC 2024) who asked for such a characterization in the equivalent language of (error-dependent) `list-replicability'.
- Abstract（参考訳）: 安定性は、アルゴリズムの出力に$A$は、類似のデータセットに$S$と$S'$を適用すると、大きく変化しない、と約束する学習と統計における中心的な特性である。
十分に安定したアルゴリズム(例えば、同じ結果を高い確率で返却し、プライバシー保証を満たすものなど)は、基本的な事実である。
はランダム化されなければならない。
アルゴリズムの安定性にどの程度のランダム性が必要なのかを定量化できますか?
複製性は、同じ分布(および共有ランダムコイン)からサンプルを走らせるとき、通常$A$が同じ結果を出力する。
これらの概念のランダム性複雑性は、最近(Dixon et al ICML 2024)と(Cannone et al ITCS 2024)で、基本的な$d$次元のタスク(例えば$d$コインのバイアスを推定するなど)について研究されているが、より一般的には、分類のような複雑な設定で、ほとんど知られていない。
この目的に向けて、安定のための '弱強' ブースティング定理を証明している: タスクのランダム性複雑性$M$ (複製性またはDP) は、そのタスクを解く決定論的アルゴリズムの最大の複製確率によって厳密に制御される、'グローバル安定性'と呼ばれる弱測度は、$\frac{1}{2}$ (Chase et al FOCS 2023) で普遍的にカプセル化される。
クラスは、有限のリトルストーン次元を持ち、さらに、学習者の過大なエラーにおいて、最悪の対数スケールでスケールする。
これにより (Chase et al STOC 2024) は、(エラーに依存した) 'list-replicability' の同値言語でそのような特徴を要求された。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Replicability and stability in learning [16.936594801109557]
Impagliazzo氏、Lei氏、Pitassi氏、Sorrell氏(22)は先頃、マシンラーニングにおけるレプリカ性の研究を開始した。
我々は、任意のレプリカブルアルゴリズムを、任意の確率が 1 に近く同じ出力を生成するように拡張する方法を示す。
任意の確率で 1 に近い確率で達成できるように、リストの複製性を高めることができることを証明した。
論文 参考訳（メタデータ） (2023-04-07T17:52:26Z) - A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive
Noise Models [49.038420266408586]
分散の増加による変数のソートは、しばしば因果順序に近い順序になることを示す。
本稿ではR2$-SortnRegressと呼ばれる,高いR2$-sortabilityを利用する効率的なベースラインアルゴリズムを提案する。
その結果,因果発見に関連するデータ生成プロセスの仮定として,R2$-sortabilityが高額であることが判明した。
論文 参考訳（メタデータ） (2023-03-31T17:05:46Z) - Improved Sample Complexity Bounds for Distributionally Robust
Reinforcement Learning [3.222802562733787]
トレーニング環境とテスト環境のパラメータミスマッチに対して頑健な制御ポリシーを学習することの問題点を考察する。
本研究では,4つの異なる発散によって特定される不確実性集合に対して,ロバスト位相値学習(RPVL)アルゴリズムを提案する。
提案アルゴリズムは,既存の結果より一様によいサンプル複雑性を$tildemathcalO(|mathcalSmathcalA| H5)$とする。
論文 参考訳（メタデータ） (2023-03-05T21:47:08Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳（メタデータ） (2023-02-26T01:15:32Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Metric-Fair Classifier Derandomization [6.269732593554894]
機械学習における分類器のデランドマイズ問題について検討する。
事前のデランドマイズ法は, ほぼ最大値の不等式であることを示す。
我々はこれらの2つの間の魅力的なトレードオフを提供するデランドマイズ手順を考案する。
論文 参考訳（メタデータ） (2022-06-15T21:36:57Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳（メタデータ） (2022-05-12T14:40:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。