論文の概要: Minimax learning rates for estimating binary classifiers under margin conditions

• arxiv url: http://arxiv.org/abs/2505.10628v1
• Date: Thu, 15 May 2025 18:05:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-19 14:36:13.364674
• Title: Minimax learning rates for estimating binary classifiers under margin conditions
• Title（参考訳）: 境界条件下での二項分類器推定のための最小学習率
• Authors: Jonathan García, Philipp Petersen,
• Abstract要約: 水平関数によって決定境界を記述する二分推定器を用いた分類問題について検討する。 我々は、ルベーグノルムの有界コルモゴロフエントロピーを持つ広関数クラスに対するミニマックス学習率の上限と下限を確立する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study classification problems using binary estimators where the decision boundary is described by horizon functions and where the data distribution satisfies a geometric margin condition. We establish upper and lower bounds for the minimax learning rate over broad function classes with bounded Kolmogorov entropy in Lebesgue norms. A key novelty of our work is the derivation of lower bounds on the worst-case learning rates under a geometric margin condition -- a setting that is almost universally satisfied in practice but remains theoretically challenging. Moreover, our results deal with the noiseless setting, where lower bounds are particularly hard to establish. We apply our general results to classification problems with decision boundaries belonging to several function classes: for Barron-regular functions, and for H\"older-continuous functions with strong margins, we identify optimal rates close to the fast learning rates of $\mathcal{O}(n^{-1})$ for $n \in \mathbb{N}$ samples. Also for merely convex decision boundaries, in a strong margin case optimal rates near $\mathcal{O}(n^{-1/2})$ can be achieved.
• Abstract（参考訳）: 水平関数によって決定境界が記述され、データ分布が幾何学的マージン条件を満たす二分推定器を用いて分類問題を研究する。 我々は、ルベーグノルムの有界コルモゴロフエントロピーを持つ広関数クラスに対するミニマックス学習率の上限と下限を確立する。 私たちの研究の重要な新規性は、幾何学的マージン条件の下で最悪の場合の学習率の低い境界を導出することである。 さらに,低境界が特に確立し難いノイズレス設定についても検討した。 一般的な結果は、いくつかの関数クラスに属する決定境界を持つ分類問題に当てはまる: バロン正則関数と、強いマージンを持つH\'older-Continuous関数に対しては、$\mathcal{O}(n^{-1})$$n \in \mathbb{N}$サンプルの学習速度に近い最適な速度を同定する。 また、単に凸決定境界に対して、強いマージンの場合、$\mathcal{O}(n^{-1/2})$ に近い最適な速度が達成できる。

関連論文リスト

• High-dimensional classification problems with Barron regular boundaries under margin conditions [0.0]
  特に、強辺条件では、高次元の不連続な分類器は、低次元の滑らかな函数を近似する際にのみ達成可能な速度で近似することができる。 これらの式レートが、サンプル数である$n-1$に近い高速レートの学習境界をどのように表すかを示す。
  論文  参考訳（メタデータ） (2024-12-10T08:50:35Z)
• Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
  本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。 本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
  論文  参考訳（メタデータ） (2023-10-02T19:59:39Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Optimal learning of high-dimensional classification problems using deep neural networks [0.0]
  雑音のないトレーニングサンプルから分類関数を学習する際の問題について,決定境界が一定の規則性であることを前提として検討する。 局所バロン-正則な決定境界のクラスでは、最適推定率は本質的に基底次元とは独立である。
  論文  参考訳（メタデータ） (2021-12-23T14:15:10Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)

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

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