論文の概要: A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

• arxiv url: http://arxiv.org/abs/2311.10886v1
• Date: Fri, 17 Nov 2023 22:07:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-22 13:47:08.489676
• Title: A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions
• Title（参考訳）: 全く新しい球技:行列ゲームのための基本加速度法と滑らかな関数の最大最小化
• Authors: Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
• Abstract要約: 我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。 それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
• 参考スコア（独自算出の注目度）: 44.655316553524855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design algorithms for minimizing $\max_{i\in[n]} f_i(x)$ over a $d$-dimensional Euclidean or simplex domain. When each $f_i$ is $1$-Lipschitz and $1$-smooth, our method computes an $\epsilon$-approximate solution using $\widetilde{O}(n \epsilon^{-1/3} + \epsilon^{-2})$ gradient and function evaluations, and $\widetilde{O}(n \epsilon^{-4/3})$ additional runtime. For large $n$, our evaluation complexity is optimal up to polylogarithmic factors. In the special case where each $f_i$ is linear -- which corresponds to finding a near-optimal primal strategy in a matrix game -- our method finds an $\epsilon$-approximate solution in runtime $\widetilde{O}(n (d/\epsilon)^{2/3} + nd + d\epsilon^{-2})$. For $n>d$ and $\epsilon=1/\sqrt{n}$ this improves over all existing first-order methods. When additionally $d = \omega(n^{8/11})$ our runtime also improves over all known interior point methods. Our algorithm combines three novel primitives: (1) A dynamic data structure which enables efficient stochastic gradient estimation in small $\ell_2$ or $\ell_1$ balls. (2) A mirror descent algorithm tailored to our data structure implementing an oracle which minimizes the objective over these balls. (3) A simple ball oracle acceleration framework suitable for non-Euclidean geometry.
• Abstract（参考訳）: 我々は、$d$次元ユークリッドあるいはsimplexドメイン上で$\max_{i\in[n]} f_i(x)$を最小化するアルゴリズムを設計する。 f_i$ が $1$-Lipschitz と $1$-smooth のとき、我々のメソッドは $\widetilde{O}(n \epsilon^{-1/3} + \epsilon^{-2})$ 勾配と関数評価、$\widetilde{O}(n \epsilon^{-4/3})$ 追加ランタイムを使って $\epsilon$-approximate ソリューションを計算する。 大きな$n$の場合、評価の複雑さは多対数因子まで最適です。 それぞれの$f_i$ が線型である特別な場合 -- 行列ゲームにおける準最適原始戦略の発見に対応する -- では、実行時に $\epsilon$-approximate solution が $\widetilde{O}(n (d/\epsilon)^{2/3} + nd + d\epsilon^{-2})$ となる。 $n>d$と$\epsilon=1/\sqrt{n}$の場合、これは既存のすべての一階法よりも改善される。 さらに$d = \omega(n^{8/11})$のランタイムは、既知のすべてのインテリアポイントメソッドを改善します。 提案アルゴリズムは,(1)小さな$\ell_2$または$\ell_1$の球において,効率的な確率勾配推定を可能にする動的データ構造である。 (2)これらのボール上の目的を最小化するオラクルを実装するデータ構造に合わせたミラー降下アルゴリズム。 (3) 非ユークリッド幾何学に適した単純な球オラクル加速フレームワーク。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• 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)
• 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)
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical [1.2183405753834562]
  有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。 我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-02T15:59:09Z)
• 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)
• 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)
• 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)

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

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