論文の概要: Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization

• arxiv url: http://arxiv.org/abs/2507.09823v1
• Date: Sun, 13 Jul 2025 23:07:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:24.06186
• Title: Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
• Title（参考訳）: Nesterov氏がGRAALを発見: 凸最適化のための最適かつ適応的な勾配法
• Authors: Ekaterina Borodich, Dmitry Kovalev,
• Abstract要約: GRAAL(Malitsky, 2020)を含む適応勾配法が開発されている。 我々は,このアルゴリズムがリプシッツ滑らかな関数に対する最適収束率を達成することを証明した。 既存の方法とは対照的に、複雑性において対数加法項のコストを犠牲にして、任意の、さらに極端に小さな初期段階化を行う。
• 参考スコア（独自算出の注目度）: 17.227158587717934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we focus on the problem of minimizing a continuously differentiable convex objective function $\min_x f(x)$. Recently, several adaptive gradient methods, including GRAAL (Malitsky, 2020), have been developed. These methods estimate the local curvature of the objective function to compute stepsizes, attain the standard convergence rate $\mathcal{O}(1/k)$ of fixed-stepsize gradient descent for Lipschitz-smooth functions, and do not require any line search procedures or hyperparameter tuning. However, a natural question arises: is it possible to accelerate the convergence of these algorithms to match the optimal rate $\mathcal{O}(1/k^2)$ of the accelerated gradient descent of Nesterov (1983)? Although some attempts have been made (Li and Lan, 2023), the capabilities of the existing accelerated algorithms to adapt to the curvature of the objective function are highly limited. Consequently, we provide a positive answer to this question and develop GRAAL with Nesterov acceleration. We prove that our algorithm achieves the desired optimal convergence rate for Lipschitz smooth functions. Moreover, in contrast to existing methods, it does so with an arbitrary, even excessively small, initial stepsize at the cost of a logarithmic additive term in the iteration complexity.
• Abstract（参考訳）: 本稿では、連続的に微分可能な凸対象関数 $\min_x f(x)$ を最小化する問題に焦点を当てる。 近年, GRAAL (Malitsky, 2020) などの適応勾配法が開発されている。 これらの方法では、目的関数の局所曲率を計算し、標準収束率 $\mathcal{O}(1/k)$ をリプシッツ・スムース関数の固定段数勾配勾配とし、ライン探索手順やハイパーパラメータチューニングを一切必要としない。 しかし、自然な疑問が生じる: これらのアルゴリズムの収束を加速して、Nesterov (1983) の加速勾配勾配の最適速度 $\mathcal{O}(1/k^2)$ に一致するか? いくつかの試み (Li and Lan, 2023) があるが、既存の加速アルゴリズムが目的関数の曲率に適応する能力は非常に限られている。 その結果,Nesterov 加速度を用いた GRAAL の開発に肯定的な回答が得られた。 我々は,このアルゴリズムがリプシッツ滑らかな関数に対する最適収束率を達成することを証明した。 さらに、既存の方法とは対照的に、イテレーションの複雑さにおいて対数加法項のコストを犠牲にして、任意の、さらに極端に小さな初期段階化を行う。

関連論文リスト

• Gradient-free stochastic optimization for additive models [56.42455605591779]
  本稿では,Polyak-Lojasiewicz あるいは強凸条件を満たす目的関数に対する雑音観測によるゼロ次最適化の問題に対処する。 対象関数は加法的構造を持ち、H"古い関数族によって特徴づけられる高次滑らか性特性を満たすと仮定する。
  論文  参考訳（メタデータ） (2025-03-03T23:39:08Z)
• An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
  本稿では,上層関数が非凸であり,下層関数が強凸である二層最適化問題のクラスについて検討する。 これらの問題は、非有界ネットワークを用いたテキスト分類など、データ学習に大きな応用がある。 本稿では,AccBO という新しい高速化バイレベル最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-28T02:30:44Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
  ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
  論文  参考訳（メタデータ） (2024-08-14T03:27:48Z)
• An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
  機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。 本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
  論文  参考訳（メタデータ） (2024-07-05T08:53:06Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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