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

• arxiv url: http://arxiv.org/abs/2103.12024v1
• Date: Mon, 22 Mar 2021 17:28:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-23 18:08:12.217403
• Title: Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$
• Title（参考訳）: 収束率$O(1/n)$の安定性と最適リスク境界
• Authors: Yegor Klochkov and Nikita Zhivotovskiy
• Abstract要約: 経験的リスク最小化法で有効な強く凸およびLipschitz損失に対する$O(log n/n)$の確率に拘束される高い確率過剰リスクを示す。 O(log n/n)$ 高確率過剰リスク境界が、通常の滑らかさの仮定なしで強い凸やリプシッツ損失の場合の射影勾配降下に対してどのように可能かについて論じる。
• 参考スコア（独自算出の注目度）: 4.1499725848998965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondr\'{a}k, 2018, 2019), (Bousquet, Klochkov, Zhivotovskiy, 2020) contain a generally inevitable sampling error term of order $\Theta(1/\sqrt{n})$. When applied to excess risk bounds, this leads to suboptimal results in several standard stochastic convex optimization problems. We show that if the so-called Bernstein condition is satisfied, the term $\Theta(1/\sqrt{n})$ can be avoided, and high probability excess risk bounds of order up to $O(1/n)$ are possible via uniform stability. Using this result, we show a high probability excess risk bound with the rate $O(\log n/n)$ for strongly convex and Lipschitz losses valid for \emph{any} empirical risk minimization method. This resolves a question of Shalev-Shwartz, Shamir, Srebro, and Sridharan (2009). We discuss how $O(\log n/n)$ high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.
• Abstract（参考訳）: 一様に安定なアルゴリズム(feldman, vondr\'{a}k, 2018, 2019), (bousquet, klochkov, zhivotovskiy, 2020) に対する最もシャープな高確率一般化境界は、一般的に避けられないサンプリングエラー項$\theta(1/\sqrt{n})$を含む。 過大なリスク境界に適用すると、結果としていくつかの標準確率凸最適化問題が発生する。 いわゆるバーンスタイン条件が満たされれば、$\Theta(1/\sqrt{n})$ という用語は避けられ、O(1/n)$ までの順序の高確率超過リスク境界は均一安定性によって可能であることを示す。 この結果を用いて,強い凸とリプシッツの損失に対して o(\log n/n)$ の確率に縛られた高い確率過大なリスクが \emph{any} 実験的リスク最小化法で有効であることを示した。 これはShalev-Shwartz、Shamir、Srebro、Sridharan (2009) の問題を解決する。 我々は, 通常の平滑性仮定を伴わない強凸およびリプシッツ損失の場合, 予測された勾配降下に対して, $o(\log n/n)$ high probability extra risk bounds がいかに可能であるかを考察する。

関連論文リスト

• Stability and Sharper Risk Bounds with Convergence Rate $O(1/n^2)$ [23.380477456114118]
  最も鋭い高確率過剰リスク境界は、経験的リスク最小化とアルゴリズム安定性による投射降下のために最大$Oleft(1/nright)$である。
  論文  参考訳（メタデータ） (2024-10-13T07:50:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter [14.040676498310198]
  我々は、全てのデータに対して最悪のリプシッツパラメータを持つ損失関数を持つ差分プライベート(DP)不等式最適化(SO)について検討する。 スムーズな損失関数に対して、我々は最先端の過剰リスクを持つ線形時間アルゴリズムを提供する。 また,非最適凸損失関数を扱う最初のアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2022-09-15T16:03:23Z)
• Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
  最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。 新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
  論文  参考訳（メタデータ） (2022-04-22T07:03:13Z)
• 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)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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