論文の概要: Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

• arxiv url: http://arxiv.org/abs/2607.24827v1
• Date: Tue, 21 Jul 2026 00:40:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-29 20:50:42.530961
• Title: Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
• Title（参考訳）: 凸最適化のためのより強いメモリクエリトレードオフ:サブクワッドメモリの限界
• Authors: Michael Menart, Aleksandar Nikolov, Ohad Shamir,
• Abstract要約: メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。 まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。 決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
• 参考スコア（独自算出の注目度）: 65.64123585249297
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove two lower bounds for the first order oracle complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory. We first show that any such (possibly randomized) algorithm must make $\tildeΩ(\frac{d^2}{\sqrt{m}})$ oracle queries. For deterministic optimization algorithms, we show that $\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})$ queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of $\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})$ and $\tildeΩ(\frac{d^{5/3}}{m^{1/3}})$ for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around $m\approx d^2$, where a polylogarithmic change in memory leads to a $\mathsf{poly}(d)$ change in the number of required oracle calls. Further, when the suboptimality is polynomially small in $d$, our lower bound randomized algorithms is the first to show that $\tildeΩ(d^2)$ memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in $d$.
• Abstract（参考訳）: メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化することで、第1次オラクル複雑性に対して2つの下界を証明した。 まず、そのような(おそらくランダム化される)アルゴリズムは、$\tildeΩ(\frac{d^2}{\sqrt{m}})$ oracle query でなければならないことを示す。 決定論的最適化アルゴリズムでは、$\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})$クエリが必要である。 興味のあるすべての記憶系に対して、これらは、それぞれランダム化および決定論的アルゴリズムに対して、$\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})$と$\tildeΩ(\frac{d^{5/3}}{m^{1/3}})$の既知下界を改善する。 特に、既存の上界のため、決定論的アルゴリズムの下位境界は、まずm\approx d^2$の急激なオラクル複雑性相転移を示し、そこでは、メモリの多元対数変化によって必要となるオラクル呼び出しの数の変化が$\mathsf{poly}(d)$になる。 さらに、サブ最適性が$d$で多項式的に小さい場合、我々の下限ランダム化アルゴリズムは、メモリ制約のないアルゴリズム間の最適なクエリ複雑性にほぼ一致するために、$\tildeΩ(d^2)$メモリが必要であることを示す。 以前は、そのような結果は準最適性が$d$で半ポリノミカルに小さい体制でしか知られていなかった。

関連論文リスト

• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (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)
• 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)
• 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)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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