Fugu-MT 論文翻訳(概要): Stability and Sharper Risk Bounds with Convergence Rate $O(1/n^2)$

論文の概要: Stability and Sharper Risk Bounds with Convergence Rate $O(1/n^2)$

arxiv url: http://arxiv.org/abs/2410.09766v1
Date: Sun, 13 Oct 2024 07:50:47 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-30 05:02:48.418487
Title: Stability and Sharper Risk Bounds with Convergence Rate $O(1/n^2)$
Title（参考訳）: 収束率$O(1/n^2)$の安定性とシャーパリスク境界
Authors: Bowei Zhu, Shaojie Li, Yong Liu,
Abstract要約: 最も鋭い高確率過剰リスク境界は、経験的リスク最小化とアルゴリズム安定性による投射降下のために最大$Oleft(1/nright)$である。
参考スコア（独自算出の注目度）: 23.380477456114118
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The sharpest known high probability excess risk bounds are up to $O\left( 1/n \right)$ for empirical risk minimization and projected gradient descent via algorithmic stability (Klochkov \& Zhivotovskiy, 2021). In this paper, we show that high probability excess risk bounds of order up to $O\left( 1/n^2 \right)$ are possible. We discuss how high probability excess risk bounds reach $O\left( 1/n^2 \right)$ under strongly convexity, smoothness and Lipschitz continuity assumptions for empirical risk minimization, projected gradient descent and stochastic gradient descent. Besides, to the best of our knowledge, our high probability results on the generalization gap measured by gradients for nonconvex problems are also the sharpest.
Abstract（参考訳）: 最も周知な高確率過剰リスク境界は、経験的リスク最小化とアルゴリズム安定性による勾配勾配降下のために最大$O\left(1/n \right)$である(Klochkov \& Zhivotovskiy, 2021)。本稿では,高い確率過剰リスク境界が$O\left(1/n^2 \right)$まで可能であることを示す。実験的リスク最小化, 射影勾配降下, 確率勾配降下に対する強い凸性, 滑らか性, リプシッツ連続性仮定の下で, 高確率過剰リスク境界が$O\left(1/n^2 \right)$にどの程度達するかを論じる。さらに、我々の知る限り、非凸問題に対する勾配によって測定される一般化ギャップに関する高い確率も最も鋭い。

関連論文リスト

Analysis of Schedule-Free Nonconvex Optimization [0.0]
大規模学習アルゴリズムの根底にある一階法であるが、その収束性は慎重にスケジュールされたステップのヒンジを保証し、前例のないスケジュール自由地平線に依存する。我々の$Oレートが$O(log T)$に束縛されていることを示す。我々の研究はSFの地平線を拡張し、最適な非滑らかな速度で将来の方向をグラフ化する。
論文参考訳（メタデータ） (2025-08-08T22:54:35Z)
Super-fast rates of convergence for Neural Networks Classifiers under the Hard Margin Condition [9.993044620455338]
DNNは二乗損失代理と$ell_p$ペナルティによる経験的リスクを最小限に抑えることができ、ハードマージン条件下では、任意の大きさの$alpha>0$に対して$mathcalOleft(n-alpharight)$の有限サンプル超過リスクを達成できることを示す。この証明は、独立した利害関係にある可能性のある過剰リスクの新たな分解に依存している。
論文参考訳（メタデータ） (2025-05-13T06:26:04Z)
Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文参考訳（メタデータ） (2025-02-11T19:54:11Z)
Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文参考訳（メタデータ） (2025-02-09T22:14:45Z)
Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文参考訳（メタデータ） (2023-11-07T17:39:17Z)
Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression [19.31269916674961]
実現可能な場合、即時仮定では、$O(d)$サンプルはターゲットを正確に回復するのに十分であることを示す。この結果は、 (1, 2)$) の場合、最小化子におけるリスクのヘッセンの存在を保証する穏やかな仮定の下で、$p in (1, 2)$ に拡張する。
論文参考訳（メタデータ） (2023-10-19T03:21:28Z)
Risk Estimation in a Markov Cost Process: Lower and Upper Bounds [3.1484174280822845]
我々はマルコフコストプロセスにおいて、無限水平割引コストのリスク対策を推定する問題に取り組む。私たちが調査するリスク尺度には、分散、バリュー・アット・リスク(VaR)、条件付きバリュー・アット・リスク(CVaR)がある。
論文参考訳（メタデータ） (2023-10-17T16:35:39Z)
Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk [22.843623578307707]
我々は,多武装バンディット問題における後悔分布の予測とテールリスクのトレードオフについて検討した。予測された後悔の順序が、最悪のケースとインスタンスに依存したシナリオの両方において、後悔の尾確率の減衰率にどのように影響するかを示す。
論文参考訳（メタデータ） (2023-04-10T01:00:18Z)
Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。 2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文参考訳（メタデータ） (2022-11-29T18:38:40Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文参考訳（メタデータ） (2022-08-19T18:00:34Z)
Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文参考訳（メタデータ） (2022-06-17T06:10:20Z)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文参考訳（メタデータ） (2021-06-28T00:17:01Z)
Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data [13.465471169118974]
差分プライバシーの制約の下で,重み付きデータを用いた凸最適化について検討した。我々は、純粋な差分プライバシーの制約の下で、ほぼ一致する低い境界を証明し、我々の境界が厳密であることを示す強力な証拠を与える。
論文参考訳（メタデータ） (2021-06-02T17:45:47Z)
Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$ [4.1499725848998965]
経験的リスク最小化法で有効な強く凸およびLipschitz損失に対する$O(log n/n)$の確率に拘束される高い確率過剰リスクを示す。 O(log n/n)$ 高確率過剰リスク境界が、通常の滑らかさの仮定なしで強い凸やリプシッツ損失の場合の射影勾配降下に対してどのように可能かについて論じる。
論文参考訳（メタデータ） (2021-03-22T17:28:40Z)
Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文参考訳（メタデータ） (2020-06-29T21:06:52Z)
Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret [115.85354306623368]
本研究では,未知の遷移カーネルを持つマルコフ決定過程におけるリスク感応性強化学習について検討する。確率的に効率的なモデルレスアルゴリズムとして、リスク感性価値反復(RSVI)とリスク感性Q-ラーニング(RSQ)を提案する。 RSVIが $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big) に達したことを証明しています。
論文参考訳（メタデータ） (2020-06-22T19:28:26Z)
A Brief Prehistory of Double Descent [75.37825440319975]
Belkin et al. は、現代の複雑度学習者の文脈におけるリスク曲線の形状を説明し、議論する。 N$が増加すると、リスクは最初減少し、最小値に達した後、N$が$n$に等しいまで増加し、トレーニングデータが完全に適合する。
論文参考訳（メタデータ） (2020-04-07T09:41:24Z)

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