論文の概要: High Probability Guarantees for Random Reshuffling

• arxiv url: http://arxiv.org/abs/2311.11841v3
• Date: Fri, 14 Mar 2025 09:45:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-17 13:03:02.343613
• Title: High Probability Guarantees for Random Reshuffling
• Title（参考訳）: ランダムリシャッフルのための高い確率保証
• Authors: Hengxu Yu, Xiao Li,
• Abstract要約: 最適化問題に対処するためにランダムリシャッフル(mathsfRR$)の勾配法を検討する。 本手法の1次複雑性保証を行う。 我々は、$mathsfp$-$mathsfRR$provably escapes strict point and a high tail.
• 参考スコア（独自算出の注目度）: 4.794366598086316
• License:
• Abstract: We consider the stochastic gradient method with random reshuffling ($\mathsf{RR}$) for tackling smooth nonconvex optimization problems. $\mathsf{RR}$ finds broad applications in practice, notably in training neural networks. In this work, we provide high probability first-order and second-order complexity guarantees for this method. First, we establish a high probability first-order sample complexity result for driving the Euclidean norm of the gradient (without taking expectation) below $\varepsilon$. Our derived complexity matches the best existing in-expectation one up to a logarithmic term while imposing no additional assumptions nor changing $\mathsf{RR}$'s updating rule. We then propose a simple and computable stopping criterion for $\mathsf{RR}$ (denoted as $\mathsf{RR}$-$\mathsf{sc}$). This criterion is guaranteed to be triggered after a finite number of iterations, enabling us to prove a high probability first-order complexity guarantee for the last iterate. Second, building on the proposed stopping criterion, we design a perturbed random reshuffling method ($\mathsf{p}$-$\mathsf{RR}$) that involves an additional randomized perturbation procedure near stationary points. We derive that $\mathsf{p}$-$\mathsf{RR}$ provably escapes strict saddle points and establish a high probability second-order complexity result, without requiring any sub-Gaussian tail-type assumptions on the stochastic gradient errors. The fundamental ingredient in deriving the aforementioned results is the new concentration property for sampling without replacement in $\mathsf{RR}$, which could be of independent interest. Finally, we conduct numerical experiments on neural network training to support our theoretical findings.
• Abstract（参考訳）: 滑らかな非凸最適化問題に対処するために,ランダムリシャッフル(\mathsf{RR}$)を用いた確率勾配法を考える。 $\mathsf{RR}$は、特にニューラルネットワークのトレーニングにおいて、実際に広く使われているアプリケーションを見つける。 本研究では,この手法に対して高い確率の1次・2次複雑性保証を提供する。 まず、勾配のユークリッドノルムを(期待せずに)$\varepsilon$以下に駆動する確率の高い一階サンプル複雑性結果を確立する。 我々の導出した複雑性は、対数項に最も近い既存の不変項と一致するが、追加の仮定や$\mathsf{RR}$の更新規則の変更は含まない。 次に、$\mathsf{RR}$($\mathsf{RR}$-$\mathsf{sc}$)に対する単純で計算可能な停止基準を提案する。 この基準は、有限反復の後にトリガーされることが保証され、最後の反復に対して高い確率の1次複雑性を保証することができる。 第二に、提案した停止基準に基づいて、定常点付近に乱数化を施した乱数化法(\mathsf{p}$-$\mathsf{RR}$)を設計する。 確率勾配誤差に対して準ガウス的尾型仮定を必要とせず、厳密なサドル点から確実に脱却し、高い確率の2階複雑性結果を確立することを導出する。 上記の結果を得るための基本的な要素は、$\mathsf{RR}$で置き換えることなくサンプリングを行うための新しい濃度特性である。 最後に、ニューラルネットワークトレーニングに関する数値実験を行い、理論的な知見を裏付ける。

関連論文リスト

• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
  重み付き雑音下での最初の収束を提供するが、切断はしない。 また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
  論文  参考訳（メタデータ） (2024-12-27T08:46:46Z)
• Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
  非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。 階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
  論文  参考訳（メタデータ） (2023-05-11T16:07:47Z)
• Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [43.0867217287089]
  ガウス分布の下で半空間を不可知的に学習する作業について検討する。 この課題に対して,ほぼ最適計算硬度を証明した。
  論文  参考訳（メタデータ） (2023-02-13T16:46:23Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• 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)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
  本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。 この方法はこの問題でよく知られている。
  論文  参考訳（メタデータ） (2020-01-11T09:05:03Z)

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

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