論文の概要: Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints
- arxiv url: http://arxiv.org/abs/2405.15107v1
- Date: Thu, 23 May 2024 23:51:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-27 18:38:12.504742
- Title: Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints
- Title（参考訳）: アルゴリズム安定性はテスト可能か?計算制約下での一元化フレームワーク
- Authors: Yuetian Luo, Rina Foygel Barber,
- Abstract要約: ブラックボックスアルゴリズムの安定性をテストすることは、データが数えきれないほど無限の空間にあるような環境では不可能であることを示す。
アルゴリズム安定性テストの難易度を定量化するための統一的なフレームワークを開発し,全ての設定において,利用可能なデータが制限されている場合,網羅的探索がアルゴリズム安定性を証明するための唯一の普遍的なメカニズムであることを示す。
- 参考スコア（独自算出の注目度）: 5.68594452139461
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithmic stability is a central notion in learning theory that quantifies the sensitivity of an algorithm to small changes in the training data. If a learning algorithm satisfies certain stability properties, this leads to many important downstream implications, such as generalization, robustness, and reliable predictive inference. Verifying that stability holds for a particular algorithm is therefore an important and practical question. However, recent results establish that testing the stability of a black-box algorithm is impossible, given limited data from an unknown distribution, in settings where the data lies in an uncountably infinite space (such as real-valued data). In this work, we extend this question to examine a far broader range of settings, where the data may lie in any space -- for example, categorical data. We develop a unified framework for quantifying the hardness of testing algorithmic stability, which establishes that across all settings, if the available data is limited then exhaustive search is essentially the only universally valid mechanism for certifying algorithmic stability. Since in practice, any test of stability would naturally be subject to computational constraints, exhaustive search is impossible and so this implies fundamental limits on our ability to test the stability property for a black-box algorithm.
- Abstract（参考訳）: アルゴリズム安定性は、学習理論における中心的な概念であり、アルゴリズムの感度をトレーニングデータの小さな変化に定量化する。
学習アルゴリズムが一定の安定性特性を満たす場合、これは一般化、堅牢性、信頼性のある予測推論など、多くの重要な下流の影響をもたらす。
したがって、特定のアルゴリズムに対して安定性が成り立つことを検証することは重要かつ実践的な問題である。
しかし、近年の結果、ブラックボックスアルゴリズムの安定性をテストすることは、未知の分布から限られたデータを得ることができず、データが数えきれないほど無限の空間(実数値データなど)にあるような環境では不可能であることが証明されている。
この研究では、この質問を拡張して、任意の空間(例えばカテゴリデータ)にデータが配置されるような、より広い範囲の設定を調べます。
アルゴリズム安定性テストの難易度を定量化するための統一的なフレームワークを開発し,全ての設定において,利用可能なデータが制限されている場合,網羅的探索がアルゴリズム安定性を証明するための唯一の普遍的なメカニズムであることを示す。
実際には、安定性のテストは自然に計算上の制約を受けるため、徹底的な探索は不可能であり、ブラックボックスアルゴリズムの安定性特性をテストする能力に根本的な制限が課せられる。
関連論文リスト
- Stability is Stable: Connections between Replicability, Privacy, and
Adaptive Generalization [26.4468964378511]
複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。
データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。
我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
論文 参考訳（メタデータ） (2023-03-22T21:35:50Z) - Bagging Provides Assumption-free Stability [11.456416081243654]
バギングは、機械学習モデルを安定化するための重要なテクニックである。
本稿では,任意のモデルに対するバギングの安定性に関する有限サンプル保証を導出する。
論文 参考訳（メタデータ） (2023-01-30T01:18:05Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Provably Auditing Ordinary Least Squares in Low Dimensions [17.655785504931913]
ほとんどの測定基準は、通常最小二乗の線形回帰から導かれる結論の安定性を測定する。
最近の研究は、単純で大域的、有限サンプル安定度(英語版)を提案しており、分析の再実行が結論を覆すために取り除かなければならないサンプルの最小数である。
コ変数の数が一定であるがサンプルの数が多い低次元状態において、この計量を確実に推定する効率的なアルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-05-28T00:45:10Z) - Black box tests for algorithmic stability [10.495496415022064]
アルゴリズムの安定性特性を知ることは、多くの下流アプリケーションにとってしばしば有用である。
現在使われている多くの現代的なアルゴリズムは、その安定性の理論的解析には複雑すぎる。
論文 参考訳（メタデータ） (2021-11-30T16:36:58Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Privacy Preserving Recalibration under Domain Shift [119.21243107946555]
本稿では,差分プライバシー制約下での校正問題の性質を抽象化する枠組みを提案する。
また、新しいリカレーションアルゴリズム、精度温度スケーリングを設計し、プライベートデータセットの事前処理より優れています。
論文 参考訳（メタデータ） (2020-08-21T18:43:37Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。
目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。
提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
論文 参考訳（メタデータ） (2020-07-07T18:25:25Z) - Fine-Grained Analysis of Stability and Generalization for Stochastic
Gradient Descent [55.85456985750134]
我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。
これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。
我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
論文 参考訳（メタデータ） (2020-06-15T06:30:19Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - Interpretable Random Forests via Rule Extraction [0.0]
本稿では,ルールの短時間かつ単純なリストの形式を取り入れた,安定なルール学習アルゴリズムであるSIRUSを紹介する。
当社のR/C++ソフトウェア実装サイラスは、CRANから入手可能です。
論文 参考訳（メタデータ） (2020-04-29T08:13:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。