論文の概要: Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes
- arxiv url: http://arxiv.org/abs/2306.10096v1
- Date: Fri, 16 Jun 2023 17:00:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-22 00:13:13.061512
- Title: Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes
- Title（参考訳）: Recursive Cutting-Planesによる凸最適化のためのメモリ制約アルゴリズム
- Authors: Mo\"ise Blanchard, Junhui Zhang, Patrick Jaillet
- Abstract要約: 勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
- 参考スコア（独自算出の注目度）: 23.94542304111204
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a family of recursive cutting-plane algorithms to solve
feasibility problems with constrained memory, which can also be used for
first-order convex optimization. Precisely, in order to find a point within a
ball of radius $\epsilon$ with a separation oracle in dimension $d$ -- or to
minimize $1$-Lipschitz convex functions to accuracy $\epsilon$ over the unit
ball -- our algorithms use $\mathcal O(\frac{d^2}{p}\ln \frac{1}{\epsilon})$
bits of memory, and make $\mathcal O((C\frac{d}{p}\ln \frac{1}{\epsilon})^p)$
oracle calls, for some universal constant $C \geq 1$. The family is
parametrized by $p\in[d]$ and provides an oracle-complexity/memory trade-off in
the sub-polynomial regime $\ln\frac{1}{\epsilon}\gg\ln d$. While several works
gave lower-bound trade-offs (impossibility results) -- we explicit here their
dependence with $\ln\frac{1}{\epsilon}$, showing that these also hold in any
sub-polynomial regime -- to the best of our knowledge this is the first class
of algorithms that provides a positive trade-off between gradient descent and
cutting-plane methods in any regime with $\epsilon\leq 1/\sqrt d$. The
algorithms divide the $d$ variables into $p$ blocks and optimize over blocks
sequentially, with approximate separation vectors constructed using a variant
of Vaidya's method. In the regime $\epsilon \leq d^{-\Omega(d)}$, our algorithm
with $p=d$ achieves the information-theoretic optimal memory usage and improves
the oracle-complexity of gradient descent.
- Abstract（参考訳）: 本論文では,一階の凸最適化にも使用可能な制約付きメモリを用いた再帰的切削平面アルゴリズムのファミリーを提案する。
正確には、半径 $\epsilon$ のボール内の点を見つけるために、次元 $d$ の分離オラクルを持つか、単位球上の 1$-Lipschitz 凸関数を最小化するために $\epsilon$ -- アルゴリズムは、$\mathcal O(\frac{d^2}{p}\ln \frac{1}{\epsilon})$ ビットメモリを使用し、$\mathcal O((C\frac{d}{p}\ln \frac{1}{\epsilon})^p)$ oracle コール、ある普遍定数 $C \geq 1$ に対して$ oracle コールする。
このファミリーは$p\in[d]$でパラメータ化され、サブポリノマルレジーム$\ln\frac{1}{\epsilon}\gg\ln d$でoracle-complexity/memoryのトレードオフを提供する。
いくつかの研究が低いバウンドのトレードオフ(具体的結果)を与えたが、ここでは $\ln\frac{1}{\epsilon}$ への依存を明示し、これらがどんなサブポリノミカルな体制でも成り立つことを示しており、私たちの知る限り、これは $\epsilon\leq 1/\sqrt d$ を持つ任意のレシエーションにおける勾配降下法と切断平面法の間の正のトレードオフを提供するアルゴリズムの第一級である。
アルゴリズムは$d$変数を$p$ブロックに分割し、Vaidyaの方法の変種を用いて近似分離ベクトルを構築し、ブロックを順次最適化する。
規則 $\epsilon \leq d^{-\Omega(d)}$ では、$p=d$ のアルゴリズムは情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
関連論文リスト
- 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) - 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) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - 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) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。