論文の概要: All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension

• arxiv url: http://arxiv.org/abs/2602.08350v1
• Date: Mon, 09 Feb 2026 07:33:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:25.109973
• Title: All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension
• Title（参考訳）: 全EMMは線形次元の確率凸最適化下界でフェールする
• Authors: Tal Burla, Roi Livni,
• Abstract要約: サンプルサイズが線形な場合,学習が可能であるが,経験的リスク最小化器は独特であり,過度に適合する可能性が示唆された。 グラディエント Descent は $left(sqrtT/m1.5right)$ で、ここでは $$ は学習率、$T$ は地平線、$m$ はサンプルサイズである。
• 参考スコア（独自算出の注目度）: 14.982451024975733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the sample complexity of the best-case Empirical Risk Minimizer in the setting of stochastic convex optimization. We show that there exists an instance in which the sample size is linear in the dimension, learning is possible, but the Empirical Risk Minimizer is likely to be unique and to overfit. This resolves an open question by Feldman. We also extend this to approximate ERMs. Building on our construction we also show that (constrained) Gradient Descent potentially overfits when horizon and learning rate grow w.r.t sample size. Specifically we provide a novel generalization lower bound of $Ω\left(\sqrt{ηT/m^{1.5}}\right)$ for Gradient Descent, where $η$ is the learning rate, $T$ is the horizon and $m$ is the sample size. This narrows down, exponentially, the gap between the best known upper bound of $O(ηT/m)$ and existing lower bounds from previous constructions.
• Abstract（参考訳）: 本稿では,確率的凸最適化の設定における最適事例である経験的リスク最小化器のサンプル複雑性について検討する。 サンプルサイズが線形な場合,学習が可能であるが,経験的リスク最小化器は独特であり,過度に適合する可能性が示唆された。 これはフェルドマンによるオープンな疑問を解決している。 また、これを近似ERMに拡張する。 我々の構造に基づいて構築すると、(制約された)グラディエント・ディフレッシュは水平線と学習速度がw.r.tサンプルサイズに大きくなると過度に適合する可能性があることも示される。 具体的には、Gradient Descentに対して$Ω\left(\sqrt{ηT/m^{1.5}}\right)$という新しい一般化の下界を提供し、$η$は学習率、$T$は地平線、$m$はサンプルサイズである。 これは指数関数的に、最もよく知られた$O(ηT/m)$の上限と、以前の構成から既存の下限の間のギャップを狭める。

関連論文リスト

• Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization [10.913566070767596]
  差分プライバシー(DP)モデルにおける最小値最適化の問題について検討する。 経験的リスク関数の Descent $l$-norm が $tO(n)(n)$ で上界となる推定器を得ることが可能である。
  論文  参考訳（メタデータ） (2025-03-24T03:51:27Z)
• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization [14.268363583731848]
  フルバッチ勾配 Descent の一般化誤差は $tilde Theta(d/m + 1/sqrtm)$ であり、$d$ は次元、$m$ は標本サイズである。 これは、Emphworst型経験的リスク最小化器のサンプル複雑さと一致する。
  論文  参考訳（メタデータ） (2024-04-07T12:07:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization [30.26365073195728]
  基本凸最適化設定における勾配法の一般化性能について検討する。 同様の構成手法を適用すると、SGDのサンプル複雑性に対して同様の$Omega(sqrtd)$ローバウンドが得られ、非自明な経験的誤差に達することが示される。
  論文  参考訳（メタデータ） (2024-01-22T15:50:32Z)
• Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization [9.019243171993553]
  トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。 まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。 近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
  論文  参考訳（メタデータ） (2023-03-19T20:24:33Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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