論文の概要: Near-optimal learning with average H\"older smoothness
- arxiv url: http://arxiv.org/abs/2302.06005v2
- Date: Thu, 1 Jun 2023 07:27:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-03 00:24:56.585373
- Title: Near-optimal learning with average H\"older smoothness
- Title(参考訳): 平均h\"older smoothnessを用いた近最適学習
- Authors: Steve Hanneke, Aryeh Kontorovich, Guy Kornowski
- Abstract要約: 平均リプシッツの滑らかさの概念をH"古い滑らかさに拡張することで一般化する。
以上の結果から,H'older smoothness という古典的な最悪の概念は,基本的には平均値に置き換えることができることがわかった。
- 参考スコア(独自算出の注目度): 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 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 の古典的な最悪ケース概念は,本質的に平均値に置き換えられ,よりシャープな保証が得られることを示した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。