論文の概要: Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
- arxiv url: http://arxiv.org/abs/2404.06720v1
- Date: Wed, 10 Apr 2024 04:15:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-11 15:39:25.669656
- Title: Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
- Title（参考訳）: Oracleの複雑さと実現可能性問題に対するメモリトレードオフにおいて、グラディエントDescentは最適である
- Authors: Moise Blanchard,
- Abstract要約: 精度で実現可能な問題を解くために、決定論的アルゴリズムは$d1+delta$ bitsのメモリを使用するか、少なくとも$1/(d0.01delta epsilon2frac1-delta1+1.01 delta-o(1))$ Oracleクエリをしなければならない。
また、ランダム化アルゴリズムは$d1+delta$メモリを使用するか、少なくとも$$$$deltainに対して$1/(d2delta epsilon2(1-4delta)-o(1))$クエリを生成する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we provide oracle complexity lower bounds for finding a point in a given set using a memory-constrained algorithm that has access to a separation oracle. We assume that the set is contained within the unit $d$-dimensional ball and contains a ball of known radius $\epsilon>0$. This setup is commonly referred to as the feasibility problem. We show that to solve feasibility problems with accuracy $\epsilon \geq e^{-d^{o(1)}}$, any deterministic algorithm either uses $d^{1+\delta}$ bits of memory or must make at least $1/(d^{0.01\delta }\epsilon^{2\frac{1-\delta}{1+1.01 \delta}-o(1)})$ oracle queries, for any $\delta\in[0,1]$. Additionally, we show that randomized algorithms either use $d^{1+\delta}$ memory or make at least $1/(d^{2\delta} \epsilon^{2(1-4\delta)-o(1)})$ queries for any $\delta\in[0,\frac{1}{4}]$. Because gradient descent only uses linear memory $\mathcal O(d\ln 1/\epsilon)$ but makes $\Omega(1/\epsilon^2)$ queries, our results imply that it is Pareto-optimal in the oracle complexity/memory tradeoff. Further, our results show that the oracle complexity for deterministic algorithms is always polynomial in $1/\epsilon$ if the algorithm has less than quadratic memory in $d$. This reveals a sharp phase transition since with quadratic $\mathcal O(d^2 \ln1/\epsilon)$ memory, cutting plane methods only require $\mathcal O(d\ln 1/\epsilon)$ queries.
- Abstract（参考訳）: 本稿では, 分離オラクルにアクセスできるメモリ制約アルゴリズムを用いて, 与えられた集合の点を求めるために, オラクル複雑性の低い境界を提供する。
集合は単位$d$-次元球の中に含まれ、既知の半径$\epsilon>0$の球を含むと仮定する。
この設定は一般に実現可能性問題と呼ばれる。
精度$\epsilon \geq e^{-d^{o(1)}}$で実現可能な問題を解決するために、任意の決定論的アルゴリズムは、$d^{1+\delta}$ bits of memoryを使用するか、少なくとも$1/(d^{0.01\delta }\epsilon^{2\frac{1-\delta}{1+1.01 \delta}-o(1)})$ oracle query, for any $\delta\in[0,1]$とする。
さらに、ランダム化されたアルゴリズムは、$d^{1+\delta}$メモリを使用するか、少なくとも$1/(d^{2\delta} \epsilon^{2(1-4\delta)-o(1)})$クエリを$\delta\in[0,\frac{1}{4}]$にします。
勾配降下は線形メモリ$\mathcal O(d\ln 1/\epsilon)$のみを使用するが、$\Omega(1/\epsilon^2)$クエリを生成するので、オラクルの複雑性/メモリトレードオフではPareto-Optimalであることが示唆される。
さらに,決定論的アルゴリズムのオラクル複雑性が1/\epsilon$の多項式であることを示す。
これは、二次的な$\mathcal O(d^2 \ln1/\epsilon)$メモリで、カットプレーンメソッドは$\mathcal O(d\ln 1/\epsilon)$クエリしか必要としないため、鋭い位相遷移が明らかになる。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Quadratic Memory is Necessary for Optimal Query Complexity in Convex
Optimization: Center-of-Mass is Pareto-Optimal [23.94542304111204]
本研究では,1次凸最適化に最適なオラクル複雑性を実現するためには,二次記憶が必要であることを示す。
単位球上の1ドルのLipschitz凸関数を1/d4$精度で最小化するためには、少なくともd2-delta$ビットのメモリを使用する決定論的一階述語アルゴリズムは$tildeOmega(d1+delta/3)$クエリを生成する必要がある。
論文 参考訳（メタデータ） (2023-02-09T22:37:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。