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

• arxiv url: http://arxiv.org/abs/2507.09823v2
• Date: Fri, 29 Aug 2025 15:15:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-01 15:42:25.901074
• Title: Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
• Title（参考訳）: Nesterov氏がGRAALを発見: 凸最適化のための最適かつ適応的な勾配法
• Authors: Ekaterina Borodich, Dmitry Kovalev,
• Abstract要約: 最近、Malitsky (2020), Alacaoglu et al.(2023) は適応的な一階法 GRAAL を開発した。 我々は,Nesterov 加速度を用いた GRAAL を開発した。これは,非加速 GRAAL と同様に局所曲率を幾何的,あるいは線形で,局所的な曲率に順応することができる。
• 参考スコア（独自算出の注目度）: 9.98884634301032
• 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, Malitsky (2020); Alacaoglu et al.(2023) developed an adaptive first-order method, GRAAL. This algorithm computes stepsizes by estimating the local curvature of the objective function without any line search procedures or hyperparameter tuning, and attains the standard iteration complexity $\mathcal{O}(L\lVert x_0-x^*\rVert^2/\epsilon)$ of fixed-stepsize gradient descent for $L$-smooth functions. However, a natural question arises: is it possible to accelerate the convergence of GRAAL to match the optimal complexity $\mathcal{O}(\sqrt{L\lVert x_0-x^*\rVert^2/\epsilon})$ of the accelerated gradient descent of Nesterov (1983)? Although some attempts have been made by Li and Lan (2025); Suh and Ma (2025), the ability of existing accelerated algorithms to adapt to the local curvature of the objective function is highly limited. We resolve this issue and develop GRAAL with Nesterov acceleration, which can adapt its stepsize to the local curvature at a geometric, or linear, rate just like non-accelerated GRAAL. We demonstrate the adaptive capabilities of our algorithm by proving that it achieves near-optimal iteration complexities for $L$-smooth functions, as well as under a more general $(L_0,L_1)$-smoothness assumption (Zhang et al., 2019).
• Abstract（参考訳）: 本稿では,連続的に微分可能な凸対象関数,$\min_x f(x)$ を最小化する問題に焦点をあてる。 最近、Malitsky (2020)、Alacaoglu et al (2023) は適応的な一階法、GRAALを開発した。 このアルゴリズムは、行探索手順やハイパーパラメータチューニングを使わずに目的関数の局所曲率を推定し、標準反復複雑性を$\mathcal{O}(L\lVert x_0-x^*\rVert^2/\epsilon)$L$-smooth関数に対して固定ステップ勾配を求める。 しかし、自然の疑問が生じる: GRAAL の収束を加速して、最適複雑性 $\mathcal{O}(\sqrt{L\lVert x_0-x^*\rVert^2/\epsilon})$ をネステロフの加速勾配勾配(1983)と一致させることができるか? いくつかの試みはLi と Lan (2025)、Suh と Ma (2025) によって行われたが、既存の加速アルゴリズムが目的関数の局所曲率に適応する能力は非常に制限されている。 我々はこの問題を解決し,Nesterov 加速度を用いた GRAAL を開発した。 より一般的な$(L_0,L_1)$-smoothnessの仮定 (Zhang et al , 2019) の下で,$L$-smooth関数のほぼ最適反復複雑性を達成できることを証明し,アルゴリズムの適応性を示す。

関連論文リスト

• 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)

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

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