論文の概要: Near-optimal learning with average H\"older smoothness
- arxiv url: http://arxiv.org/abs/2302.06005v1
- Date: Sun, 12 Feb 2023 21:19:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 17:09:37.941629
- Title: Near-optimal learning with average H\"older smoothness
- Title(参考訳): 平均h\"older smoothnessを用いた近最適学習
- Authors: Steve Hanneke, Aryeh Kontorovich, Guy Kornowski
- Abstract要約: 我々は, 平均H"高齢者の滑らかさの観点から, ほぼ厳密なリスク境界と低いリスク境界を証明した。
我々の結果は任意の完全有界距離空間を持ち、その内在幾何学の観点で述べられている。
- 参考スコア(独自算出の注目度): 18.152972568358507
- 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 prove nearly tight upper and lower risk bounds in terms
of the average H\"older smoothness, establishing the minimax rate in the
realizable regression setting up to log factors; this was not previously known
even in the special case of average Lipschitz smoothness. From an algorithmic
perspective, since our notion of average smoothness is defined with respect to
the unknown sampling distribution, the learner does not have an explicit
representation of the function class, hence is unable to execute ERM.
Nevertheless, we provide a learning algorithm that achieves the (nearly)
optimal learning rate. 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\"older smoothness に拡張することで一般化する。
函数の「有効滑らかさ」のこの測度は、下層の分布に敏感であり、古典的な ``worst-case'' H\"older constant よりも劇的に小さい。
我々は, 平均H\"高齢者の滑らか度の観点から, 平均リプシッツ・スムースネスの特殊な場合においても, ログファクタに設定された再現可能な回帰設定において, 最小値の値を確立することによって, 平均H\"高齢者のスムースネスにおいて, ほぼ厳密な上限と低いリスク境界を証明した。
アルゴリズムの観点からは, 平均滑らか性の概念は未知のサンプリング分布に対して定義されるため, 学習者は関数クラスの明示的な表現を持たないため, ERMの実行は不可能である。
それにもかかわらず、我々は(ほぼ)最適学習率を達成する学習アルゴリズムを提供する。
我々の結果は任意の完全有界距離空間を持ち、その内在幾何学の観点で述べられている。
総じて,h\"older smoothness の古典的な最悪ケース概念は,本質的に平均値に置き換えられ,よりシャープな保証が得られることを示した。
関連論文リスト
- Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳(メタデータ) (2023-11-21T18:50:38Z) - Towards More Robust Interpretation via Local Gradient Alignment [37.464250451280336]
任意の非負の同質ニューラルネットワークに対して、勾配に対する単純な$ell$-robust criterionは、テクスティノ正規化不変量であることを示す。
我々は,局所勾配の整合性を両立させるために,$ell$とcosine distance-based criteriaを正則化項として組み合わせることを提案する。
我々は,CIFAR-10 と ImageNet-100 でトレーニングしたモデルにより,より堅牢な解釈が得られたことを実験的に示す。
論文 参考訳(メタデータ) (2022-11-29T03:38:28Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Learning to Estimate Without Bias [57.82628598276623]
ガウスの定理は、重み付き最小二乗推定器は線形モデルにおける線形最小分散アンバイアスド推定(MVUE)であると述べている。
本稿では、バイアス制約のあるディープラーニングを用いて、この結果を非線形設定に拡張する第一歩を踏み出す。
BCEの第二の動機は、同じ未知の複数の推定値が平均化されてパフォーマンスが向上するアプリケーションにおいてである。
論文 参考訳(メタデータ) (2021-10-24T10:23:51Z) - 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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。