論文の概要: Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

• arxiv url: http://arxiv.org/abs/2105.01778v1
• Date: Tue, 4 May 2021 21:49:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-06 12:35:52.000062
• Title: Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
• Title（参考訳）: ボールの内部を考える:最大損失の最小最小化
• Authors: Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
• Abstract要約: オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。 非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
• 参考スコア（独自算出の注目度）: 41.17536985461902
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We characterize the complexity of minimizing $\max_{i\in[N]} f_i(x)$ for convex, Lipschitz functions $f_1,\ldots, f_N$. For non-smooth functions, existing methods require $O(N\epsilon^{-2})$ queries to a first-order oracle to compute an $\epsilon$-suboptimal point and $\tilde{O}(N\epsilon^{-1})$ queries if the $f_i$ are $O(1/\epsilon)$-smooth. We develop methods with improved complexity bounds of $\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-8/3})$ in the non-smooth case and $\tilde{O}(N\epsilon^{-2/3} + \sqrt{N}\epsilon^{-1})$ in the $O(1/\epsilon)$-smooth case. Our methods consist of a recently proposed ball optimization oracle acceleration algorithm (which we refine) and a careful implementation of said oracle for the softmax function. We also prove an oracle complexity lower bound scaling as $\Omega(N\epsilon^{-2/3})$, showing that our dependence on $N$ is optimal up to polylogarithmic factors.
• Abstract（参考訳）: 我々は、凸に対して$\max_{i\in[n]} f_i(x)$を最小化する複雑さを特徴付ける。 非スムース関数に対しては、既存のメソッドは$o(n\epsilon^{-2})$クエリを1次オラクルに要求し、$f_i$が$o(1/\epsilon)$-smoothであれば$\tilde{o}(n\epsilon^{-1})$クエリを計算する。 非滑らかな場合では$\tilde{O}(N\epsilon^{-2/3} + \epsilon^{-8/3})$と$\tilde{O}(N\epsilon^{-2/3} + \sqrt{N}\epsilon^{-1})$-smoothの場合では$O(1/\epsilon)$である。 本手法は,最近提案されたボール最適化オラクル加速アルゴリズム(精巧化)と,ソフトマックス関数に対するそのオラクルの慎重に実装とから構成される。 また、オラクルの複雑さが$\Omega(N\epsilon^{-2/3})$として低い境界スケーリングを証明し、N$への依存が多対数因子に最適であることを示す。

関連論文リスト

• Second-Order Min-Max Optimization with Lazy Hessians [17.17389531402505]
  本稿では,凸凹型最小値最適化のための2次法について検討する。 計算コストは反復的にヘッセンによって削減できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T15:30:17Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• 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)
• Faster Stochastic Algorithms for Minimax Optimization under Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
  我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。 SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
  論文  参考訳（メタデータ） (2023-07-29T02:26:31Z)
• 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)
• 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)
• 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)
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization [31.714928102950584]
  非常に滑らかな (Lipschitz $k$-thorder derivative) 関数と強い凸関数を$k$-thorder Oracleへの呼び出しによって最適化する複雑性を考える。 我々は、関数を正確に$epsilon$まで最適化するために、固定された$k$で最悪の場合のオラクルの複雑さが$leftの順序にあることを証明している。
  論文  参考訳（メタデータ） (2020-10-13T19:18:15Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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