論文の概要: Replicability and stability in learning
- arxiv url: http://arxiv.org/abs/2304.03757v2
- Date: Wed, 12 Apr 2023 17:10:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 17:22:50.097019
- Title: Replicability and stability in learning
- Title（参考訳）: 学習における再現性と安定性
- Authors: Zachary Chase, Shay Moran, Amir Yehudayoff
- Abstract要約: Impagliazzo氏、Lei氏、Pitassi氏、Sorrell氏(22)は先頃、マシンラーニングにおけるレプリカ性の研究を開始した。
我々は、任意のレプリカブルアルゴリズムを、任意の確率が 1 に近く同じ出力を生成するように拡張する方法を示す。
任意の確率で 1 に近い確率で達成できるように、リストの複製性を高めることができることを証明した。
- 参考スコア（独自算出の注目度）: 16.936594801109557
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Replicability is essential in science as it allows us to validate and verify
research findings. Impagliazzo, Lei, Pitassi and Sorrell (`22) recently
initiated the study of replicability in machine learning. A learning algorithm
is replicable if it typically produces the same output when applied on two
i.i.d. inputs using the same internal randomness. We study a variant of
replicability that does not involve fixing the randomness. An algorithm
satisfies this form of replicability if it typically produces the same output
when applied on two i.i.d. inputs (without fixing the internal randomness).
This variant is called global stability and was introduced by Bun, Livni and
Moran ('20) in the context of differential privacy.
Impagliazzo et al. showed how to boost any replicable algorithm so that it
produces the same output with probability arbitrarily close to 1. In contrast,
we demonstrate that for numerous learning tasks, global stability can only be
accomplished weakly, where the same output is produced only with probability
bounded away from 1. To overcome this limitation, we introduce the concept of
list replicability, which is equivalent to global stability. Moreover, we prove
that list replicability can be boosted so that it is achieved with probability
arbitrarily close to 1. We also describe basic relations between standard
learning-theoretic complexity measures and list replicable numbers. Our
results, in addition, imply that besides trivial cases, replicable algorithms
(in the sense of Impagliazzo et al.) must be randomized.
The proof of the impossibility result is based on a topological fixed-point
theorem. For every algorithm, we are able to locate a "hard input distribution"
by applying the Poincar\'{e}-Miranda theorem in a related topological setting.
The equivalence between global stability and list replicability is algorithmic.
- Abstract（参考訳）: 研究結果の検証と検証を可能にするため、科学において再現性は不可欠である。
impagliazzo, lei, pitassi, sorrell (`22)は最近、機械学習における再現性の研究を開始した。
学習アルゴリズムは、内部ランダム性を用いて2つのi.d.入力に適用した場合に通常同じ出力を生成する場合、複製可能である。
ランダム性の修正を伴わない複製可能性の変種について検討する。
アルゴリズムは、2つのi.d.入力に適用した場合(内部ランダム性を修正することなく)、通常同じ出力を生成する場合、この形式の複製性を満たす。
この変種はグローバル安定性と呼ばれ、Bun, Livni and Moran ('20) によって差分プライバシーの文脈で導入された。
Impagliazzo et al. は、任意の複製可能なアルゴリズムを、任意の確率が 1 に近く同じ出力を生成するように、どのように向上させるかを示した。
対照的に、多くの学習タスクにおいて、グローバル安定性は弱くしか達成できず、同じアウトプットが生成されるのは確率が1から外れた場合に限られる。
この制限を克服するために,地球規模の安定性に相当するリスト再現性の概念を導入する。
さらに、リストの複製性は、確率を任意に 1 に近づけることで達成できることを示す。
また,標準学習理論的複雑性尺度とレプリカブル数との基本的な関係について述べる。
さらに,自明な場合に加えて,(impagliazzoなどの意味で)レプリカブルアルゴリズムをランダム化する必要があることを示唆した。
不可能性の証明は位相的不動点定理に基づいている。
すべてのアルゴリズムに対して、関連する位相的設定でポアンカー・マランダの定理を適用することで「ハードな入力分布」を見つけることができる。
グローバル安定性とリストリプライ可能性の等価性はアルゴリズム的である。
関連論文リスト
- Replicable Online Learning [12.14234796585091]
本稿では,Impagliazzo と Ghazi が導入したアルゴリズム的複製性の概念について考察する。
本モデルでは,オンライン学習者が受信した入力シーケンスを,相手が選択した時間変化分布から生成する。
我々の目的は、2つの独立したサンプル入力シーケンス上で実行される場合、高い確率で全く同じ動作列を生成する、低レベルのオンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-11-20T22:10:37Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
多くの実世界の設計問題は、大規模で異質な観測ノイズのため、複数の実験条件を並列に評価し、各条件を複数回再現する。
本稿では,3つのアルゴリズムを含むReplicable Experimental Designフレームワークのバッチトンプソンサンプリングを提案する。
我々は,アルゴリズムの有効性を,精密農業とAutoMLの2つの実世界の応用例で示す。
論文 参考訳（メタデータ） (2023-11-02T12:46:03Z) - Replicable Reinforcement Learning [15.857503103543308]
本稿では、並列値反復のための証明可能なレプリカブルアルゴリズムと、エピソード設定における証明可能なR-maxのレプリカブルバージョンを提供する。
これらは制御問題に対する最初の公式なレプリカ化結果であり、バッチ学習設定とは異なるレプリケーションの課題を提示している。
論文 参考訳（メタデータ） (2023-05-24T16:05:15Z) - List and Certificate Complexities in Replicable Learning [0.7829352305480285]
リストの複製性と証明書の複製性という2つの実現可能な複製性について考察する。
リストと証明書の複雑さに最適な学習問題のアルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-04-05T06:05:27Z) - Stability is Stable: Connections between Replicability, Privacy, and
Adaptive Generalization [26.4468964378511]
複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。
データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。
我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
論文 参考訳（メタデータ） (2023-03-22T21:35:50Z) - $\omega$PAP Spaces: Reasoning Denotationally About Higher-Order,
Recursive Probabilistic and Differentiable Programs [64.25762042361839]
$omega$PAP 空間は表現的微分可能および確率的プログラミング言語についての推論のための空間である。
我々の意味論は、最も実践的な確率的で微分可能なプログラムに意味を割り当てるのに十分である。
確率プログラムのトレース密度関数のほぼすべての微分可能性を確立する。
論文 参考訳（メタデータ） (2023-02-21T12:50:05Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Reproducibility in Learning [8.386806623480156]
再現可能な学習アルゴリズムは、サンプルのバリエーションに耐性がある。
強い需要にもかかわらず、統計学や学習におけるいくつかの基本的な問題に対して効率的な再現可能なアルゴリズムが存在する。
論文 参考訳（メタデータ） (2022-01-20T19:59:11Z) - ReLU Regression with Massart Noise [52.10842036932169]
本稿では、ReLU回帰の基本的問題として、Rectified Linear Units(ReLU)をデータに適合させることを目標としている。
我々は自然およびよく研究された半ランダムノイズモデルであるMassartノイズモデルにおけるReLU回帰に着目した。
このモデルにおいて,パラメータの正確な回復を実現する効率的なアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-10T02:13:22Z) - Consistency of a Recurrent Language Model With Respect to Incomplete
Decoding [67.54760086239514]
逐次言語モデルから無限長のシーケンスを受信する問題について検討する。
不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
論文 参考訳（メタデータ） (2020-02-06T19:56:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。