論文の概要: Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness
- arxiv url: http://arxiv.org/abs/2112.01118v1
- Date: Thu, 2 Dec 2021 10:51:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-03 16:41:10.995210
- Title: Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness
- Title（参考訳）: 滑らかな全順序に対する凸最適化のための近似最適下限
- Authors: Ankit Garg, Robin Kothari, Praneeth Netrapalli and Suhail Sherif
- Abstract要約: 非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
- 参考スコア（独自算出の注目度）: 26.71898403195793
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of optimizing highly smooth convex functions. For a
positive integer $p$, we want to find an $\epsilon$-approximate minimum of a
convex function $f$, given oracle access to the function and its first $p$
derivatives, assuming that the $p$th derivative of $f$ is Lipschitz.
Recently, three independent research groups (Jiang et al., PLMR 2019;
Gasnikov et al., PLMR 2019; Bubeck et al., PLMR 2019) developed a new algorithm
that solves this problem with $\tilde{O}(1/\epsilon^{\frac{2}{3p+1}})$ oracle
calls for constant $p$. This is known to be optimal (up to log factors) for
deterministic algorithms, but known lower bounds for randomized algorithms do
not match this bound. We prove a new lower bound that matches this bound (up to
log factors), and holds not only for randomized algorithms, but also for
quantum algorithms.
- Abstract（参考訳）: 非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、oracle が関数と最初の $p$ デリバティブにアクセスし、$f$ の$p$ がリプシッツであると仮定して、凸関数 $f$ の最低値 $\epsilon$-approximate を求める。
最近、3つの独立した研究グループ (Jiang et al., PLMR 2019, Gasnikov et al., PLMR 2019, Bubeck et al., PLMR 2019) が$\tilde{O}(1/\epsilon^{\frac{2}{3p+1}})$ Oracle call for constant $p$でこの問題を解決する新しいアルゴリズムを開発した。
これは決定論的アルゴリズムの最適(対数因子まで)であることが知られているが、ランダム化アルゴリズムの既知の下限はこの境界に一致しない。
我々は、この境界(ログ係数まで)にマッチする新しい下限を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムに対しても保持する。
関連論文リスト
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
論文 参考訳（メタデータ） (2024-02-20T06:23:36Z) - Adaptive approximation of monotone functions [0.0]
GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。
おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
論文 参考訳（メタデータ） (2023-09-14T08:56:31Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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) - 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) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。