Fugu-MT 論文翻訳(概要): Efficient Convex Optimization Requires Superlinear Memory

論文の概要: Efficient Convex Optimization Requires Superlinear Memory

arxiv url: http://arxiv.org/abs/2203.15260v2
Date: Wed, 24 Jul 2024 11:21:47 GMT
ステータス: 処理完了
システム内更新日: 2024-07-25 20:17:42.796772
Title: Efficient Convex Optimization Requires Superlinear Memory
Title（参考訳）: 超線形メモリを必要とする効率的な凸最適化
Authors: Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant,
Abstract要約: メモリ制約付き1次アルゴリズムは, 単位球上の1/mathrmpoly(d)$精度が1/mathrmpoly(d)$で最大$d1.25 – delta$ bits of memory で最大$tildeOmega(d1 + (4/3)delta)$ 1次クエリを最小化する。
参考スコア（独自算出の注目度）: 27.11113888243391
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We show that any memory-constrained, first-order algorithm which minimizes $d$-dimensional, $1$-Lipschitz convex functions over the unit ball to $1/\mathrm{poly}(d)$ accuracy using at most $d^{1.25 - \delta}$ bits of memory must make at least $\tilde{\Omega}(d^{1 + (4/3)\delta})$ first-order queries (for any constant $\delta \in [0, 1/4]$). Consequently, the performance of such memory-constrained algorithms are a polynomial factor worse than the optimal $\tilde{O}(d)$ query bound for this problem obtained by cutting plane methods that use $\tilde{O}(d^2)$ memory. This resolves a COLT 2019 open problem of Woodworth and Srebro.
Abstract（参考訳）: メモリ制約のある1次アルゴリズムは、単位球上の1/\mathrm{poly}(d)$精度で1/\mathrm{poly}(d)$の精度で$d^{1.25 - \delta}$の精度で、少なくとも$\tilde{\Omega}(d^{1 + (4/3)\delta})$の1次クエリ(任意の定数$\delta \in [0, 1/4]$)を最小化する。したがって、そのようなメモリ制約アルゴリズムの性能は、$\tilde{O}(d)$メモリを使用する平面メソッドを切断することによって得られるこの問題に対して最適な$\tilde{O}(d)$クエリ境界よりも悪い多項式係数である。これにより、COLT 2019のWoodworthとSrebroのオープンな問題が解決される。

関連論文リスト

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)
Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文参考訳（メタデータ） (2024-02-14T13:44:16Z)
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文参考訳（メタデータ） (2023-11-17T22:07:18Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
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)
An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文参考訳（メタデータ） (2022-12-29T19:26:12Z)
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)

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