論文の概要: Do we really need the Rademacher complexities?

• arxiv url: http://arxiv.org/abs/2502.15118v1
• Date: Fri, 21 Feb 2025 00:40:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-24 16:10:26.780663
• Title: Do we really need the Rademacher complexities?
• Title（参考訳）: Rademacherの複雑さは本当に必要か?
• Authors: Daniel Bartl, Shahar Mendelson,
• Abstract要約: 凸クラスにおける2乗損失に関する学習の基本的な問題について検討する。 一般的な信念とは対照的に、最小限の仮定の下では、サンプルの複雑さはラデマッハ複雑性によって支配されないことが証明される。
• 参考スコア（独自算出の注目度）: 3.683202928838613
• License:
• Abstract: We study the fundamental problem of learning with respect to the squared loss in a convex class. The state-of-the-art sample complexity estimates in this setting rely on Rademacher complexities, which are generally difficult to control. We prove that, contrary to prevailing belief and under minimal assumptions, the sample complexity is not governed by the Rademacher complexities but rather by the behaviour of the limiting gaussian process. In particular, all such learning problems that have the same $L_2$-structure -- even those with heavy-tailed distributions -- share the same sample complexity. This constitutes the first universality result for general convex learning problems. The proof is based on a novel learning procedure, and its performance is studied by combining optimal mean estimation techniques for real-valued random variables with Talagrand's generic chaining method.
• Abstract（参考訳）: 凸クラスにおける2乗損失に関する学習の基本的な問題について検討する。 この設定における最先端のサンプルの複雑さの見積もりは、一般に制御が難しいラデマッハ複雑性に依存している。 一般的な信念に反し、最小限の仮定の下では、サンプルの複雑さはラデマッハ複雑性によって支配されるのではなく、ガウス過程の有限な振る舞いによって支配されていることを証明している。 特に、同じ$L_2$構造を持つすべての学習問題は、重い尾の分布を持つものでさえ、同じサンプル複雑性を共有している。 これは一般凸学習問題に対する最初の普遍性結果である。 この証明は、新しい学習手法に基づいており、その性能は、実数値確率変数に対する最適平均推定手法と、Talagrandのジェネリックチェイン法を組み合わせることによって研究されている。

関連論文リスト

• Simplifying Adversarially Robust PAC Learning with Tolerance [9.973499768462888]
  本稿では,Hの仮定を必要とせずに,VC次元の線形なサンプル複雑性を実現する,より単純な学習者の存在を示す。 学習者が不適切なとしても、H の仮説と「類似」な仮説を出力するという意味では「最も適切」である。 また,アルゴリズムのアイデアを用いて,トレラントな環境下で半教師付き学習者を構築する。
  論文  参考訳（メタデータ） (2025-02-11T03:48:40Z)
• Low Complexity Regularized Phase Retrieval [0.6522338519818377]
  この正規化器は、単純さや低複雑性の概念に従う解を促進することを意図している。 我々はノイズのない回復とノイズに対する安定性の両方について検討し、非常に汎用的で統一的な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2024-07-23T11:58:08Z)
• Transductive Learning Is Compact [10.168670899305232]
  一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。 不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。 我々は、無知の場合においてより大きなギャップが可能であると推測する。
  論文  参考訳（メタデータ） (2024-02-15T23:10:45Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
  長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。 長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
  論文  参考訳（メタデータ） (2020-05-01T17:56:38Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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