論文の概要: 2nd-order Updates with 1st-order Complexity
- arxiv url: http://arxiv.org/abs/2105.11439v1
- Date: Mon, 24 May 2021 17:47:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-25 16:39:49.360913
- Title: 2nd-order Updates with 1st-order Complexity
- Title（参考訳）: 1次複雑度を持つ2次更新
- Authors: Michael F. Zimmer
- Abstract要約: 関数の2次情報を効率よく計算し(f$)、数値近似を支援することが長年の目標であった。
ここでは、基礎物理学と数値近似のみを用いて、そのような情報を$cal O(N)$ complexityのコストで正確に得る方法を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It has long been a goal to efficiently compute and use second order
information on a function ($f$) to assist in numerical approximations. Here it
is shown how, using only basic physics and a numerical approximation, such
information can be accurately obtained at a cost of ${\cal O}(N)$ complexity,
where $N$ is the dimensionality of the parameter space of $f$. In this paper,
an algorithm ({\em VA-Flow}) is developed to exploit this second order
information, and pseudocode is presented. It is applied to two classes of
problems, that of inverse kinematics (IK) and gradient descent (GD). In the IK
application, the algorithm is fast and robust, and is shown to lead to smooth
behavior even near singularities. For GD the algorithm also works very well,
provided the cost function is locally well-described by a polynomial.
- Abstract（参考訳）: これは長い間、関数の二次情報(f$)を効率的に計算して数値近似を支援することを目標としてきた。
ここで、基礎物理学と数値近似のみを用いて、そのような情報は${\cal o}(n)$ のコストで正確に得られることが示され、ここでは$n$ はパラメータ空間の次元が $f$ である。
本稿では,この2次情報を利用するアルゴリズム({\em VA-Flow})を開発し,擬似コードを示す。
これは、逆キネマティクス(IK)と勾配降下(GD)の2種類の問題に適用される。
IK アプリケーションでは、アルゴリズムは高速で堅牢であり、特異点の近くでも滑らかな振る舞いをもたらすことが示されている。
gd の場合、コスト関数は多項式によって局所的に記述されるので、アルゴリズムは非常にうまく機能する。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - 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) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - 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) - Efficient Matrix-Free Approximations of Second-Order Information, with
Applications to Pruning and Optimization [16.96639526117016]
Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。
これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
論文 参考訳（メタデータ） (2021-07-07T17:01:34Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Towards an efficient approach for the nonconvex $\ell_p$ ball
projection: algorithm and analysis [3.4693390973571594]
本稿では, ベクトルのユークリッド射影を $pin(0,1)$ の $ell_p$ 球上に計算することに着目した。
我々は、再重み付けされた $ell_1$-ball 上の射影列を解いて定常点を計算する新しい数値的手法を開発した。
提案手法は穏やかな条件下で一意に収束し,最悪の場合$o(1/sqrtk)$収束率を持つ。
論文 参考訳（メタデータ） (2021-01-05T04:51:12Z) - A One-bit, Comparison-Based Gradient Estimator [29.600975900977343]
正規化勾配の頑健で信頼性の高い推定器を構築するために、1ビット圧縮センシングのツールを利用する方法を示す。
勾配降下法において,この推定器を用いたSCOBOというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-06T05:01:38Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。