論文の概要: Quadratic Memory is Necessary for Optimal Query Complexity in Convex
Optimization: Center-of-Mass is Pareto-Optimal
- arxiv url: http://arxiv.org/abs/2302.04963v2
- Date: Fri, 19 May 2023 01:24:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 19:06:49.717817
- Title: Quadratic Memory is Necessary for Optimal Query Complexity in Convex
Optimization: Center-of-Mass is Pareto-Optimal
- Title（参考訳）: 二次記憶は凸最適化における最適クエリ複雑度に必要な:中心はパレート最適
- Authors: Mo\"ise Blanchard, Junhui Zhang and Patrick Jaillet
- Abstract要約: 本研究では,1次凸最適化に最適なオラクル複雑性を実現するためには,二次記憶が必要であることを示す。
単位球上の1ドルのLipschitz凸関数を1/d4$精度で最小化するためには、少なくともd2-delta$ビットのメモリを使用する決定論的一階述語アルゴリズムは$tildeOmega(d1+delta/3)$クエリを生成する必要がある。
- 参考スコア（独自算出の注目度）: 23.94542304111204
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give query complexity lower bounds for convex optimization and the related
feasibility problem. We show that quadratic memory is necessary to achieve the
optimal oracle complexity for first-order convex optimization. In particular,
this shows that center-of-mass cutting-planes algorithms in dimension $d$ which
use $\tilde O(d^2)$ memory and $\tilde O(d)$ queries are Pareto-optimal for
both convex optimization and the feasibility problem, up to logarithmic
factors. Precisely, we prove that to minimize $1$-Lipschitz convex functions
over the unit ball to $1/d^4$ accuracy, any deterministic first-order
algorithms using at most $d^{2-\delta}$ bits of memory must make
$\tilde\Omega(d^{1+\delta/3})$ queries, for any $\delta\in[0,1]$. For the
feasibility problem, in which an algorithm only has access to a separation
oracle, we show a stronger trade-off: for at most $d^{2-\delta}$ memory, the
number of queries required is $\tilde\Omega(d^{1+\delta})$. This resolves a
COLT 2019 open problem of Woodworth and Srebro.
- Abstract（参考訳）: 我々は、凸最適化と関連する実現可能性問題に対するクエリ複雑性の低い境界を与える。
一階の凸最適化に最適なオラクルの複雑さを達成するには二次記憶が必要であることを示す。
特にこれは、$\tilde o(d^2)$メモリと$\tilde o(d)$クエリを使用する次元$d$のマスカットプレーンズアルゴリズムが、対数因子による凸最適化と実現可能性問題の両方に対してパレート最適であることを示している。
正確には、単位球上の1ドルのリプシッツ凸関数を1/d^4$精度に最小化するためには、最大$d^{2-\delta}$ビットのメモリを使用する決定論的一階アルゴリズムは、任意の$\delta\in[0,1]$に対して$\tilde\omega(d^{1+\delta/3})$クエリを行なわなければならない。
アルゴリズムが分離オラクルにしかアクセスできない実現可能性問題に対して、我々はより強いトレードオフを示す:少なくとも$d^{2-\delta}$メモリの場合、要求されるクエリの数は$\tilde\Omega(d^{1+\delta})$である。
これにより、woodworth と srebro の colt 2019 open problem が解決される。
関連論文リスト
- Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems [0.0]
精度で実現可能な問題を解くために、決定論的アルゴリズムは$d1+delta$ bitsのメモリを使用するか、少なくとも$1/(d0.01delta epsilon2frac1-delta1+1.01 delta-o(1))$ Oracleクエリをしなければならない。
また、ランダム化アルゴリズムは$d1+delta$メモリを使用するか、少なくとも$$$$deltainに対して$1/(d2delta epsilon2(1-4delta)-o(1))$クエリを生成する。
論文 参考訳（メタデータ） (2024-04-10T04:15:50Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Memory-Query Tradeoffs for Randomized Convex Optimization [16.225462097812766]
単位球上の$d$-dimensional, $1$-Lipschitz convex関数を最小化するランダム化1次アルゴリズムは、メモリビットの$Omega(d2-delta)か、$Omega(d1+delta/6-o(1))の$クエリを使わなければならない。
論文 参考訳（メタデータ） (2023-06-21T19:48:58Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - 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) - 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) - Efficient Convex Optimization Requires Superlinear Memory [27.11113888243391]
メモリ制約付き1次アルゴリズムは, 単位球上の1/mathrmpoly(d)$精度が1/mathrmpoly(d)$で最大$d1.25 – delta$ bits of memory で最大$tildeOmega(d1 + (4/3)delta)$ 1次クエリを最小化する。
論文 参考訳（メタデータ） (2022-03-29T06:15:54Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。