論文の概要: High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
- arxiv url: http://arxiv.org/abs/2010.06642v2
- Date: Wed, 28 Apr 2021 13:06:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-08 00:49:22.350708
- Title: High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
- Title（参考訳）: SmoothとStrongly Convex最適化の高次Oracle複雑度
- Authors: Guy Kornowski, Ohad Shamir
- Abstract要約: 非常に滑らかな (Lipschitz $k$-thorder derivative) 関数と強い凸関数を$k$-thorder Oracleへの呼び出しによって最適化する複雑性を考える。
我々は、関数を正確に$epsilon$まで最適化するために、固定された$k$で最悪の場合のオラクルの複雑さが$leftの順序にあることを証明している。
- 参考スコア（独自算出の注目度）: 31.714928102950584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this note, we consider the complexity of optimizing a highly smooth
(Lipschitz $k$-th order derivative) and strongly convex function, via calls to
a $k$-th order oracle which returns the value and first $k$ derivatives of the
function at a given point, and where the dimension is unrestricted. Extending
the techniques introduced in Arjevani et al. [2019], we prove that the
worst-case oracle complexity for any fixed $k$ to optimize the function up to
accuracy $\epsilon$ is on the order of $\left(\frac{\mu_k
D^{k-1}}{\lambda}\right)^{\frac{2}{3k+1}}+\log\log\left(\frac{1}{\epsilon}\right)$
(in sufficiently high dimension, and up to log factors independent of
$\epsilon$), where $\mu_k$ is the Lipschitz constant of the $k$-th derivative,
$D$ is the initial distance to the optimum, and $\lambda$ is the strong
convexity parameter.
- Abstract（参考訳）: このノートでは、非常に滑らかな(リプシッツ $k$-次微分)および強い凸関数の最適化の複雑さを、与えられた点で関数の値と最初の$k$微分を返す$k$-次オラクルを呼び出すことによって考慮する。
Arjevani et alで導入されたテクニックの拡張。
十分高い次元では、$\epsilon$ が $\mu_k d^{k-1}}{\lambda}\right)^{\frac{2}{3k+1}}+\log\log\left(\frac{1}{\epsilon}\right)$ (十分高い次元では、$\epsilon$ に依存しないログ係数まで)$ ($\mu_k$ は$k$-階微分のリプシッツ定数、$d$ は最適までの最初の距離、$\lambda$ は強凸パラメータである。
関連論文リスト
- Non-Euclidean High-Order Smooth Convex Optimization [9.940728137241214]
我々は、H"より古い連続$q$-th微分を持つ凸対象の最適化のためのアルゴリズムを、p$-normに対して開発する。
他の構造化関数も最適化できる。
論文 参考訳（メタデータ） (2024-11-13T19:22:34Z) - Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。