論文の概要: The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization

• arxiv url: http://arxiv.org/abs/2205.09647v1
• Date: Thu, 19 May 2022 16:04:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-20 14:34:44.469205
• Title: The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Title（参考訳）: 滑らか凸最適化における高次法の最初の最適加速
• Authors: Dmitry Kovalev, Alexander Gasnikov
• Abstract要約: 本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。 この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。 我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
• 参考スコア（独自算出の注目度）: 88.91190483500932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. Arjevani et al. (2019) established the lower bound $\Omega\left(\epsilon^{-2/(3p+1)}\right)$ on the number of the $p$-th order oracle calls required by an algorithm to find an $\epsilon$-accurate solution to the problem, where the $p$-th order oracle stands for the computation of the objective function value and the derivatives up to the order $p$. However, the existing state-of-the-art high-order methods of Gasnikov et al. (2019b); Bubeck et al. (2019); Jiang et al. (2019) achieve the oracle complexity $\mathcal{O}\left(\epsilon^{-2/(3p+1)} \log (1/\epsilon)\right)$, which does not match the lower bound. The reason for this is that these algorithms require performing a complex binary search procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $\mathcal{O}\left(\epsilon^{-2/(3p+1)}\right)$ $p$-th order oracle complexity.
• Abstract（参考訳）: 本稿では,滑らかな凸最小化問題を解くための最適高次アルゴリズムを求めるための基礎的な解法について検討する。 Arjevani et al. (2019) は、アルゴリズムが問題に対する$\epsilon$-accurate ソリューションを見つけるために必要となる$p$-thorder oracle 呼び出しの数に対して$\Omega\left(\epsilon^{-2/(3p+1)}\right) という下界の$\Omega\left(\epsilon^{-2/(3p+1)}\right) を確立した。 しかしながら、Gasnikov et al. (2019b); Bubeck et al. (2019); Jiang et al. (2019) の既存の最先端高次法は、下界と一致しないオラクル複雑性 $\mathcal{O}\left(\epsilon^{-2/(3p+1)} \log (1/\epsilon)\right)$ を達成する。 この理由は、これらのアルゴリズムが複雑な二分探索手順を必要とするため、最適でも実用でもない。 我々は、最初のアルゴリズムに$\mathcal{o}\left(\epsilon^{-2/(3p+1)}\right)$ p$-thorder oracle complexityを提供することで、この根本的な問題を解決する。

関連論文リスト

• Second-Order Min-Max Optimization with Lazy Hessians [17.17389531402505]
  本稿では,凸凹型最小値最適化のための2次法について検討する。 計算コストは反復的にヘッセンによって削減できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T15:30:17Z)
• On the Complexity of First-Order Methods in Stochastic Bilevel Optimization [9.649991673557167]
  両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。 既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。 我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
  論文  参考訳（メタデータ） (2024-02-11T04:26:35Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles [14.697733592222658]
  1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。 さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-06-26T17:07:54Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [26.71898403195793]
  非常に滑らかな凸関数を最適化する複雑性について検討する。 正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。 我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
  論文  参考訳（メタデータ） (2021-12-02T10:51:43Z)
• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
  オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。 非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
  論文  参考訳（メタデータ） (2021-05-04T21:49:15Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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