論文の概要: Near-optimal learning with average H\"older smoothness

• arxiv url: http://arxiv.org/abs/2302.06005v3
• Date: Mon, 30 Oct 2023 09:40:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-02 03:54:26.017586
• Title: Near-optimal learning with average H\"older smoothness
• Title（参考訳）: 平均h\"older smoothnessを用いた近最適学習
• Authors: Steve Hanneke, Aryeh Kontorovich, Guy Kornowski
• Abstract要約: 平均リプシッツの滑らかさの概念をH"古い滑らかさに拡張することで一般化する。 我々の結果は任意の完全有界距離空間を持ち、その内在幾何学の観点で述べられている。
• 参考スコア（独自算出の注目度）: 29.856963741898007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We generalize the notion of average Lipschitz smoothness proposed by Ashlagi et al. (COLT 2021) by extending it to H\"older smoothness. This measure of the "effective smoothness" of a function is sensitive to the underlying distribution and can be dramatically smaller than its classic "worst-case" H\"older constant. We consider both the realizable and the agnostic (noisy) regression settings, proving upper and lower risk bounds in terms of the average H\"older smoothness; these rates improve upon both previously known rates even in the special case of average Lipschitz smoothness. Moreover, our lower bound is tight in the realizable setting up to log factors, thus we establish the minimax rate. From an algorithmic perspective, since our notion of average smoothness is defined with respect to the unknown underlying distribution, the learner does not have an explicit representation of the function class, hence is unable to execute ERM. Nevertheless, we provide distinct learning algorithms that achieve both (nearly) optimal learning rates. Our results hold in any totally bounded metric space, and are stated in terms of its intrinsic geometry. Overall, our results show that the classic worst-case notion of H\"older smoothness can be essentially replaced by its average, yielding considerably sharper guarantees.
• Abstract（参考訳）: 我々は、Ashlagi et al. (COLT 2021) によって提案された平均リプシッツの滑らかさの概念を、H\"古い滑らかさに拡張することで一般化する。 我々は, 平均H\"高齢者の滑らかさの観点から, 可逆性および非可逆性(雑音性)の回帰設定を, 平均リプシッツの滑らかさの特殊な場合においても, 既知率と既知率の両方で改善する。 さらに,我々の下限は,ログ係数に対する実現可能な設定に密着しているため,minimaxレートが確立される。 アルゴリズムの観点からは, 平均滑らか性の概念は未知の分布に対して定義されるため, 学習者は関数クラスの明示的な表現を持たないため, ERMの実行は不可能である。 それにもかかわらず、我々は(ほぼ)最適な学習率を達成する異なる学習アルゴリズムを提供する。 我々の結果は任意の完全有界距離空間を持ち、その内在幾何学の観点で述べられている。 総じて,h\"older smoothness の古典的な最悪ケース概念は,本質的に平均値に置き換えられ,よりシャープな保証が得られることを示した。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization [37.41427897807821]
  暗号非既知の正規最適化の複雑さを示す。 リプシッツ関数に作用する局所アルゴリズムは、最悪の場合、亜指数最小値の値に関して有意義な局所を与えることができない。
  論文  参考訳（メタデータ） (2024-09-16T14:35:00Z)
• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。 ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。 ゲームにおける高速収束と拡張逆最適化への応用について述べる。
  論文  参考訳（メタデータ） (2024-08-17T02:22:08Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Tight Second-Order Certificates for Randomized Smoothing [106.06908242424481]
  また、ガウス的ランダムな滑らか化のための普遍曲率的境界が存在することを示す。 この新たな証明書の正確性を証明することに加えて、SoS証明書は実現可能であり、したがって厳密であることを示す。
  論文  参考訳（メタデータ） (2020-10-20T18:03:45Z)
• Functions with average smoothness: structure, algorithms, and learning [12.362670630646804]
  各点における局所勾配を定義し、これらの値の平均として関数複雑性を測る。 平均は最大よりも劇的に小さくなるので、この複雑性測度はよりシャープな一般化境界が得られる。 私たちは定義した関数クラスにおいて驚くほどリッチで解析的な構造を発見します。
  論文  参考訳（メタデータ） (2020-07-13T10:06:58Z)

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

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