論文の概要: Stability and List-Replicability for Agnostic Learners

• arxiv url: http://arxiv.org/abs/2501.05333v1
• Date: Thu, 09 Jan 2025 15:59:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-10 13:58:32.798828
• Title: Stability and List-Replicability for Agnostic Learners
• Title（参考訳）: 学習者の安定度とリスト再現性
• Authors: Ari Blonda, Shan Gao, Hamed Hatami, Pooya Hatami,
• Abstract要約: 無限のリトルストーン次元を持つクラスは、過大な誤差に依存する安定性パラメータを許容しても、安定してPACを学習できないことを証明している。 また、人口減少の少ない分布に非依存的な設定を限定しても、有限仮説クラスのみがグローバルに安定に学習可能であることも証明した。
• 参考スコア（独自算出の注目度）: 2.061173670995696
• License:
• Abstract: Two seminal papers--Alon, Livni, Malliaris, Moran (STOC 2019) and Bun, Livni, and Moran (FOCS 2020)--established the equivalence between online learnability and globally stable PAC learnability in binary classification. However, Chase, Chornomaz, Moran, and Yehudayoff (STOC 2024) recently showed that this equivalence does not hold in the agnostic setting. Specifically, they proved that in the agnostic setting, only finite hypothesis classes are globally stable learnable. Therefore, agnostic global stability is too restrictive to capture interesting hypothesis classes. To address this limitation, Chase \emph{et al.} introduced two relaxations of agnostic global stability. In this paper, we characterize the classes that are learnable under their proposed relaxed conditions, resolving the two open problems raised in their work. First, we prove that in the setting where the stability parameter can depend on the excess error (the gap between the learner's error and the best achievable error by the hypothesis class), agnostic stability is fully characterized by the Littlestone dimension. Consequently, as in the realizable case, this form of learnability is equivalent to online learnability. As part of the proof of this theorem, we strengthen the celebrated result of Bun et al. by showing that classes with infinite Littlestone dimension are not stably PAC learnable, even if we allow the stability parameter to depend on the excess error. For the second relaxation proposed by Chase et al., we prove that only finite hypothesis classes are globally stable learnable even if we restrict the agnostic setting to distributions with small population loss.
• Abstract（参考訳）: Alon, Livni, Malliaris, Moran (STOC 2019) と Bun, Livni, Moran (FOCS 2020) の2つの学術論文は、オンライン学習可能性とバイナリ分類におけるグローバルに安定したPAC学習可能性の等価性を確立した。 しかし、Chase, Chornomaz, Moran, and Yehudayoff (STOC 2024) は近年、この同値性は不可知的条件では成り立たないことを示した。 具体的には、非依存的な条件下では、有限仮説クラスのみがグローバルに安定に学習可能であることを証明した。 したがって、非依存的大域的安定性は、興味深い仮説クラスを捉えるには制限的すぎる。 この制限に対処するため、Chase \emph{et al } は2つの非依存的大域安定性の緩和を導入した。 本稿では,提案した緩和条件下で学習可能なクラスを特徴付ける。 まず,安定性パラメータが過大な誤差(学習者の誤りと仮説クラスによる最高の達成可能な誤りとのギャップ)に依存することができるような場合,非依存的安定性はリトルストーン次元によって完全に特徴づけられることを示す。 したがって、実現可能な場合と同様に、このような学習可能性の形式はオンライン学習可能性と等価である。 この定理の証明の一部として、無限小ストーン次元のクラスが安定にPACを学習できないことを示し、たとえ安定性パラメータが過大な誤差に依存することを許すとしても、 Bun et al の有望な結果を強化する。 チェイスらによって提案された第二の緩和について、人口損失の少ない分布に非依存的な設定を限定しても、有限仮説類のみがグローバルに安定に学習可能であることを証明した。

関連論文リスト

• Stabilizing Extreme Q-learning by Maclaurin Expansion [51.041889588036895]
  XQL(Extreme Q-learning)は、ベルマン誤差がガムベル分布に従うという仮定に基づいて損失関数を用いる。 オフラインとオンラインの強化学習環境では、強力なパフォーマンスを示している。 安定度を高めるため,Maclaurin Expanded Extreme Q-learningを提案する。
  論文  参考訳（メタデータ） (2024-06-07T12:43:17Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent(GD)は、現代の機械学習の強力な仕事場である。 GDが局所最小値を見つける能力は、リプシッツ勾配の損失に対してのみ保証される。 この研究は、2段階の勾配更新の分析を通じて、単純だが代表的でありながら、学習上の問題に焦点をあてる。
  論文  参考訳（メタデータ） (2022-06-08T21:32:50Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• Multi-fidelity Stability for Graph Representation Learning [38.31487722188051]
  エンフルティ忠実度安定性(英語版)と呼ばれるより弱い一様一般化を導入し、その例を示す。 2種類の安定性の相違点について,多相性設計を正当化する下界を提示する。
  論文  参考訳（メタデータ） (2021-11-25T01:33:41Z)
• Super-Convergence with an Unstable Learning Rate [20.13887962999915]
  従来の知恵は、学習率が安定的な体制にあるべきであり、勾配に基づくアルゴリズムが爆発しないようにしている。 ここでは、不安定な学習率スキームが超高速収束をもたらす単純なシナリオを紹介する。 我々は周期的に大きな不安定なステップといくつかの小さな安定ステップを取り、不安定さを補うサイクル学習率を用いている。
  論文  参考訳（メタデータ） (2021-02-22T02:05:47Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  より弱い仮定として, 2$-adjacency faithfulness を提案します。 より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:04:08Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。 これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。 我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
  論文  参考訳（メタデータ） (2020-06-15T06:30:19Z)
• The Curse of Performance Instability in Analysis Datasets: Consequences, Source, and Suggestions [93.62888099134028]
  自然言語推論(NLI)および読み込み(RC)解析/ストレスセットにおける最先端モデルの性能は極めて不安定であることがわかった。 このことは、(1)不安定さがこれらの分析セットに基づいて引き出された結論の信頼性にどのように影響するかという3つの疑問を提起する。 不安定の原因に関する理論的説明と実証的証拠の両方を提示する。
  論文  参考訳（メタデータ） (2020-04-28T15:41:12Z)
• An Equivalence Between Private Classification and Online Prediction [43.37646702577754]
  有限リトルストーン次元を持つすべての概念クラスは、(近似)微分プライベートアルゴリズムによって学習可能であることを証明している。 我々は「グローバル安定性」と呼ばれる新しい安定性の概念を導入し、これは我々の証明に不可欠であり、独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2020-03-01T19:20:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。