論文の概要: How to trap a gradient flow

• arxiv url: http://arxiv.org/abs/2001.02968v3
• Date: Wed, 30 Dec 2020 15:36:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-13 05:25:17.923042
• Title: How to trap a gradient flow
• Title（参考訳）: 勾配の流れを罠にかける方法
• Authors: S\'ebastien Bubeck and Dan Mikulincer
• Abstract要約: 我々は、$mathbbRd$ のコンパクト領域上の滑らかな関数の $varepsilon$-approximate 定常点を求める問題を考える。 我々の主な貢献は、勾配流トラップ法(GFT)と呼ばれるアルゴリズムと、そのオラクルの複雑さの分析である。
• 参考スコア（独自算出の注目度）: 3.198144010381572
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of finding an $\varepsilon$-approximate stationary point of a smooth function on a compact domain of $\mathbb{R}^d$. In contrast with dimension-free approaches such as gradient descent, we focus here on the case where $d$ is finite, and potentially small. This viewpoint was explored in 1993 by Vavasis, who proposed an algorithm which, for any fixed finite dimension $d$, improves upon the $O(1/\varepsilon^2)$ oracle complexity of gradient descent. For example for $d=2$, Vavasis' approach obtains the complexity $O(1/\varepsilon)$. Moreover for $d=2$ he also proved a lower bound of $\Omega(1/\sqrt{\varepsilon})$ for deterministic algorithms (we extend this result to randomized algorithms). Our main contribution is an algorithm, which we call gradient flow trapping (GFT), and the analysis of its oracle complexity. In dimension $d=2$, GFT closes the gap with Vavasis' lower bound (up to a logarithmic factor), as we show that it has complexity $O\left(\sqrt{\frac{\log(1/\varepsilon)}{\varepsilon}}\right)$. In dimension $d=3$, we show a complexity of $O\left(\frac{\log(1/\varepsilon)}{\varepsilon}\right)$, improving upon Vavasis' $O\left(1 / \varepsilon^{1.2} \right)$. In higher dimensions, GFT has the remarkable property of being a logarithmic parallel depth strategy, in stark contrast with the polynomial depth of gradient descent or Vavasis' algorithm. In this higher dimensional regime, the total work of GFT improves quadratically upon the only other known polylogarithmic depth strategy for this problem, namely naive grid search. We augment this result with another algorithm, named \emph{cut and flow} (CF), which improves upon Vavasis' algorithm in any fixed dimension.
• Abstract（参考訳）: 我々は、コンパクトな領域である $\mathbb{r}^d$ 上の滑らかな函数の1つの定常点である $\varepsilon$-approximate stationary point を見つける問題を考える。 勾配降下のような次元のないアプローチとは対照的に、ここでは$d$が有限かつ潜在的に小さい場合に焦点を当てる。 この視点は1993年にヴァヴァシスによって探求され、バヴァシスは任意の有限次元$d$に対して、勾配降下のオラクル複雑性を$O(1/\varepsilon^2)$で改善するアルゴリズムを提案した。 例えば、$d=2$の場合、vavasisのアプローチは$o(1/\varepsilon)$を得る。 さらに$d=2$で、決定論的アルゴリズムに対して$\omega(1/\sqrt{\varepsilon})$という下限を証明した(この結果をランダム化アルゴリズムに拡張する)。 我々の主な貢献は、勾配流トラップ法(GFT)と呼ばれるアルゴリズムと、そのオラクルの複雑さの分析である。 次元 $d=2$ において、GFT は Vavasis の下界(対数係数まで)とのギャップを閉じ、複雑性 $O\left(\sqrt {\frac{\log(1/\varepsilon)}{\varepsilon}}\right)$ であることを示す。 次元$d=3$では、$O\left(\frac{\log(1/\varepsilon)}{\varepsilon}\right)$を示し、Vavasisの$O\left(1 / \varepsilon^{1.2} \right)$を改善する。 高次元では、gftは勾配降下の多項式深さ(vavasis' algorithm)とは対照的に対数平行深さ戦略(logarithmic parallel depth strategy)という特徴を持つ。 この高次元状態において、GFTの総作業量は、この問題に対する既知の唯一の多対数深度戦略、すなわち単純格子探索に基づいて2次的に改善される。 我々はこの結果を,任意の固定次元におけるVavasisのアルゴリズムを改善するアルゴリズムである 'emph{cut and flow} (CF) で拡張する。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• 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)
• Escape saddle points by a simple gradient-descent based algorithm [6.7298812735467095]
  非最適化において、サドルポイントのエスケープは中心的な研究トピックである。 滑らかな関数 $fcolonmathbbRntomathbbR$ に対して、$epsilonO(log n)2/epsilon4)$ を出力する。 技術的に、我々の主な貢献は勾配のみを用いたロバストなヘッセンパワー手法の実装である。
  論文  参考訳（メタデータ） (2021-11-28T07:32:54Z)
• 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)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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