Fugu-MT 論文翻訳(概要): Computing the Newton-step faster than Hessian accumulation

論文の概要: Computing the Newton-step faster than Hessian accumulation

arxiv url: http://arxiv.org/abs/2108.01219v1
Date: Mon, 2 Aug 2021 11:22:08 GMT
ステータス: 処理完了
システム内更新日: 2021-08-04 23:40:49.443496
Title: Computing the Newton-step faster than Hessian accumulation
Title（参考訳）: ニュートンステップの計算はヘッセン累積より速い
Authors: Akshay Srinivasan, Emanuel Todorov
Abstract要約: 関数の計算グラフを考えると、この境界は$O(mtau3)$に縮めることができ、$tau, m$はグラフのツリー分解の幅と大きさである。提案アルゴリズムは,LQRに基づく非線形最適制御法を一般化し,ヘシアンが高密度である場合においても,反復複雑度において非自明なゲインを提供する。
参考スコア（独自算出の注目度）: 8.147652597876862
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Computing the Newton-step of a generic function with $N$ decision variables takes $O(N^3)$ flops. In this paper, we show that given the computational graph of the function, this bound can be reduced to $O(m\tau^3)$, where $\tau, m$ are the width and size of a tree-decomposition of the graph. The proposed algorithm generalizes nonlinear optimal-control methods based on LQR to general optimization problems and provides non-trivial gains in iteration-complexity even in cases where the Hessian is dense.
Abstract（参考訳）: N$決定変数を持つ一般関数のニュートンステップの計算は、$O(N^3)$ flopsを取る。本稿では、関数の計算グラフを考えると、この境界は$o(m\tau^3)$となり、ここで$\tau, m$ はグラフのツリー分解の幅と大きさであることを示す。提案アルゴリズムは,LQRに基づく非線形最適制御法を一般化し,ヘシアンが高密度である場合でも,反復複雑度において非自明なゲインを提供する。

関連論文リスト

Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文参考訳（メタデータ） (2024-06-18T20:14:52Z)
First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians [4.62316736194615]
我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
論文参考訳（メタデータ） (2023-09-05T17:40:54Z)
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)
Representing Additive Gaussian Processes by Sparse Matrices [18.618437338490487]
Mat'ern Gaussian Processes (GP) は、最も人気のあるスケーラブルな高次元問題の一つである。バックフィッティングアルゴリズムは、後進平均の計算時間の複雑さを$O(n3)$から$O(nlog n)$ timeに減らすことができる。後方分散と最大対数類似度を効率的に計算するためにこれらのアルゴリズムを一般化することは、未解決の問題である。
論文参考訳（メタデータ） (2023-04-29T18:53:42Z)
Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文参考訳（メタデータ） (2023-02-16T13:57:19Z)
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文参考訳（メタデータ） (2022-11-10T00:40:37Z)
Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文参考訳（メタデータ） (2020-12-22T12:59:30Z)
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)
Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文参考訳（メタデータ） (2020-06-16T17:55:46Z)
Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文参考訳（メタデータ） (2020-02-26T11:18:43Z)

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