論文の概要: Higher Order Generalization Error for First Order Discretization of Langevin Diffusion

• arxiv url: http://arxiv.org/abs/2102.06229v1
• Date: Thu, 11 Feb 2021 19:16:03 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-15 22:38:33.259955
• Title: Higher Order Generalization Error for First Order Discretization of Langevin Diffusion
• Title（参考訳）: ランゲビン拡散の第一次離散に対する高次一般化誤差
• Authors: Mufan Bill Li, Maxime Gazeau
• Abstract要約: 本稿では,ランジュバン拡散の離散化に対する一般化誤差を分析する新しい手法を提案する。 さらなる平滑性仮定により、ファーストオーダーメソッドでさえ任意に実行時の複雑さを達成できることを示した。
• 参考スコア（独自算出の注目度）: 3.04585143845864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a novel approach to analyze generalization error for discretizations of Langevin diffusion, such as the stochastic gradient Langevin dynamics (SGLD). For an $\epsilon$ tolerance of expected generalization error, it is known that a first order discretization can reach this target if we run $\Omega(\epsilon^{-1} \log (\epsilon^{-1}) )$ iterations with $\Omega(\epsilon^{-1})$ samples. In this article, we show that with additional smoothness assumptions, even first order methods can achieve arbitrarily runtime complexity. More precisely, for each $N>0$, we provide a sufficient smoothness condition on the loss function such that a first order discretization can reach $\epsilon$ expected generalization error given $\Omega( \epsilon^{-1/N} \log (\epsilon^{-1}) )$ iterations with $\Omega(\epsilon^{-1})$ samples.
• Abstract（参考訳）: 本稿では,確率勾配ランゲヴィンダイナミクス (SGLD) など,ランゲヴィン拡散の離散化に対する一般化誤差の解析手法を提案する。 予想される一般化誤差の $\epsilon$ 許容値に対して、$\Omega(\epsilon^{-1} \log (\epsilon^{-1}) )$ の反復を $\Omega(\epsilon^{-1})$ サンプルで実行すると、第一次離散がこのターゲットに達することが知られている。 本稿では,さらにスムーズな仮定を加えることで,一階法でも任意の実行時複雑性を実現することができることを示す。 より正確には、各$N>0$に対して、第1次離散化が$\epsilon$期待一般化誤差に$\Omega( \epsilon^{-1/N} \log (\epsilon^{-1}) )$反復が$\Omega(\epsilon^{-1})$サンプルを満たすような損失関数上の十分滑らかな条件を提供する。

関連論文リスト

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。 そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:29:14Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。 この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。 しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
  論文  参考訳（メタデータ） (2022-02-27T09:41:43Z)
• Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo [24.00911089902082]
  これは$mathdで$pi exp(-V)$を見つけるためのサンプリングイテレーションである。 多数の拡張応用について論じ、特に非凹凸サンプリングの一般理論への第一歩である。
  論文  参考訳（メタデータ） (2022-02-10T18:20:55Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。 特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
  論文  参考訳（メタデータ） (2020-07-22T18:18:28Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)

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

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