論文の概要: Corner Gradient Descent

• arxiv url: http://arxiv.org/abs/2504.12519v1
• Date: Wed, 16 Apr 2025 22:39:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-18 14:35:27.977448
• Title: Corner Gradient Descent
• Title（参考訳）: Corner Gradient Descent
• Authors: Dmitry Yarotsky,
• Abstract要約: 最大$O(t-2zeta)$までのレートは、無限メモリを持つ一般化定常SGDによって達成できることを示す。 理想コーナーアルゴリズムは有限メモリアルゴリズムによって効率よく近似できることを示す。
• 参考スコア（独自算出の注目度）: 13.794391803767617
• License:
• Abstract: We consider SGD-type optimization on infinite-dimensional quadratic problems with power law spectral conditions. It is well-known that on such problems deterministic GD has loss convergence rates $L_t=O(t^{-\zeta})$, which can be improved to $L_t=O(t^{-2\zeta})$ by using Heavy Ball with a non-stationary Jacobi-based schedule (and the latter rate is optimal among fixed schedules). However, in the mini-batch Stochastic GD setting, the sampling noise causes the Jacobi HB to diverge; accordingly no $O(t^{-2\zeta})$ algorithm is known. In this paper we show that rates up to $O(t^{-2\zeta})$ can be achieved by a generalized stationary SGD with infinite memory. We start by identifying generalized (S)GD algorithms with contours in the complex plane. We then show that contours that have a corner with external angle $\theta\pi$ accelerate the plain GD rate $O(t^{-\zeta})$ to $O(t^{-\theta\zeta})$. For deterministic GD, increasing $\theta$ allows to achieve rates arbitrarily close to $O(t^{-2\zeta})$. However, in Stochastic GD, increasing $\theta$ also amplifies the sampling noise, so in general $\theta$ needs to be optimized by balancing the acceleration and noise effects. We prove that the optimal rate is given by $\theta_{\max}=\min(2,\nu,\tfrac{2}{\zeta+1/\nu})$, where $\nu,\zeta$ are the exponents appearing in the capacity and source spectral conditions. Furthermore, using fast rational approximations of the power functions, we show that ideal corner algorithms can be efficiently approximated by finite-memory algorithms, and demonstrate their practical efficiency on a synthetic problem and MNIST.
• Abstract（参考訳）: 本稿では, 無限次元2次問題に対するSGD型最適化について考察する。 このような問題に対して、決定論的GDは損失収束率$L_t=O(t^{-\zeta})$で、非定常ヤコビベースのスケジュールを持つヘビーボールを使用することで、$L_t=O(t^{-2\zeta})$に改善できる。 しかし、ミニバッチ確率GD設定ではサンプリングノイズがジャコビHBの発散を引き起こし、従って$O(t^{-2\zeta})$アルゴリズムは知られていない。 本稿では,最大$O(t^{-2\zeta})$までのレートが,無限メモリを持つ一般化定常SGDにより達成可能であることを示す。 まず、複素平面の輪郭を持つ一般化(S)GDアルゴリズムを同定することから始める。 次に、外角 $\theta\pi$ の角を持つ輪郭が、通常の GD レート $O(t^{-\zeta})$ を $O(t^{-\theta\zeta})$ に加速することを示す。 決定論的 GD に対して、$\theta$ の増加は$O(t^{-2\zeta})$ に任意に近いレートを達成することができる。 しかし、Stochastic GDでは、$\theta$の増加はサンプリングノイズを増幅するので、一般に$\theta$は加速度とノイズ効果のバランスをとることで最適化する必要がある。 最適な値は$\theta_{\max}=\min(2,\nu,\tfrac{2}{\zeta+1/\nu})$で与えられる。 さらに、パワー関数の高速な有理近似を用いて、有限メモリアルゴリズムにより理想コーナーアルゴリズムを効率よく近似できることを示し、合成問題とMNISTに対してそれらの実効性を実証する。

関連論文リスト

• Global Optimization with A Power-Transformed Objective and Gaussian Smoothing [4.275224221939364]
  我々の手法は、$f$の大域的最適点の$delta$-neighborhoodの解に収束することを示す。 収束率は$O(d2sigma4varepsilon-2)$であり、標準および単一ループホモトピー法よりも高速である。
  論文  参考訳（メタデータ） (2024-12-06T17:33:43Z)
• SGD with memory: fundamental properties and stochastic acceleration [15.25021403154845]
  非確率設定では、損失収束$L_tsim C_Lt-xiの最適指数$xi$は、平滑なGDの倍である。 メモリ1のアルゴリズムでは、安定性を維持しながら、任意に$C_L$を小さくすることができる。
  論文  参考訳（メタデータ） (2024-10-05T16:57:40Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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