論文の概要: Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization

• arxiv url: http://arxiv.org/abs/2506.09730v1
• Date: Wed, 11 Jun 2025 13:37:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 06:35:03.00879
• Title: Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization
• Title（参考訳）: 滑らか凸最適化における長期・加速法の実証的・コンピュータ支援ロバストネス解析
• Authors: Pierre Vernimmen, François Glineur,
• Abstract要約: 本研究は, 勾配計算における相対的不完全性を考慮した一階最適化手法のロバスト性を評価する。 相対的不正確性は、少ない情報ビットを用いて勾配を圧縮する際に起こる。 どちらの加速法も予想よりもはるかに頑健であり, 短縮係数が長ステップ法に大きく寄与することが観察された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work assesses both empirically and theoretically, using the performance estimation methodology, how robust different first-order optimization methods are when subject to relative inexactness in their gradient computations. Relative inexactness occurs, for example, when compressing the gradient using fewer bits of information, which happens when dealing with large-scale problems on GPUs. Three major families of methods are analyzed: constant step gradient descent, long-step methods, and accelerated methods. The latter two are first shown to be theoretically not robust to inexactness. Then, a semi-heuristic shortening factor is introduced to improve their theoretical guarantees. All methods are subsequently tested on a concrete inexact problem, with two different types of relative inexactness, and it is observed that both accelerated methods are much more robust than expected, and that the shortening factor significantly helps the long-step methods. In the end, all shortened methods appear to be promising, even in this inexact setting.
• Abstract（参考訳）: 本研究は, 性能推定手法を用いて, 勾配計算における相対的不完全性を考慮した一階最適化手法がいかに頑健であるかを実証的および理論的に評価する。 相対的不正確性は、例えば、GPU上の大規模な問題に対処する際に発生する、少ない情報のビットを使用して勾配を圧縮する際に起こる。 定段勾配降下法, 長段法, 加速法という3種類の手法を解析した。 後者の2つは、理論上不完全性に対して堅牢でないことが最初に示されている。 そして、理論的保証を改善するために半ヒューリスティック短縮係数を導入する。 いずれの手法も, 2種類の相対的不連続性を持つ具体的な不正確な問題に対して試験を行い, いずれの手法も予想よりもはるかに頑健であり, 短縮係数が長ステップ法に大きく寄与することが観察された。 結局のところ、この不正確な設定であっても、すべての短縮メソッドは有望であるように見える。

関連論文リスト

• Natural Gradient Methods: Perspectives, Efficient-Scalable Approximations, and Analysis [0.0]
  Natural Gradient Descentは、情報幾何学によって動機付けられた2次最適化手法である。 一般的に使用されるヘッセン語の代わりにフィッシャー情報マトリックスを使用している。 2階法であることは、膨大な数のパラメータとデータを扱う問題で直接使用されることが不可能である。
  論文  参考訳（メタデータ） (2023-03-06T04:03:56Z)
• Toward Efficient Gradient-Based Value Estimation [4.365720395124051]
  強化学習における値推定の勾配に基づく手法は、時間差(TD)学習法よりも典型的にはるかに遅い。 この速度の根本原因について検討し,メアン・スクエア・ベルマン・エラー(MSBE)がヘッセンの条件数が大きいという意味で不条件損失関数であることを示す。 本稿では,ガウス・ニュートン方向をほぼ追従し,パラメータ化に頑健な,低複雑性なバッチフリー近似法を提案する。 RANSと呼ばれる本アルゴリズムは, ほぼ同一でありながら, 残留勾配法よりもかなり高速であるという意味で, 効率的である。
  論文  参考訳（メタデータ） (2023-01-31T16:45:49Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Stochastic Gradient Methods with Preconditioned Updates [47.23741709751474]
  このような問題に対するアルゴリズムはいくつかあるが、既存の手法は、スケールが悪く、あるいは条件が悪ければ、しばしばうまく機能しない。 ここではハッチンソンの対角ヘッセン近似のアプローチに基づく前提条件を含む。 我々は滑らかさとPL条件が仮定されるときの収束性を証明する。
  論文  参考訳（メタデータ） (2022-06-01T07:38:08Z)
• Acceleration Methods [57.202881673406324]
  まず2次最適化問題を用いて加速法を2つ導入する。 我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。 我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
  論文  参考訳（メタデータ） (2021-01-23T17:58:25Z)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。 我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。 一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
  論文  参考訳（メタデータ） (2020-09-23T20:02:00Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)

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

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