論文の概要: Average-case Acceleration Through Spectral Density Estimation
- arxiv url: http://arxiv.org/abs/2002.04756v6
- Date: Wed, 15 Dec 2021 13:18:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 20:30:41.313056
- Title: Average-case Acceleration Through Spectral Density Estimation
- Title(参考訳): スペクトル密度推定による平均ケース加速度
- Authors: Fabian Pedregosa, Damien Scieur
- Abstract要約: ランダム2次問題の平均ケース解析のためのフレームワークを開発する。
この分析で最適なアルゴリズムを導出する。
我々は, 均一性, マルテンコ・パストゥル, 指数分布の明示的アルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 35.01931431231649
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a framework for the average-case analysis of random quadratic
problems and derive algorithms that are optimal under this analysis. This
yields a new class of methods that achieve acceleration given a model of the
Hessian's eigenvalue distribution. We develop explicit algorithms for the
uniform, Marchenko-Pastur, and exponential distributions. These methods are
momentum-based algorithms, whose hyper-parameters can be estimated without
knowledge of the Hessian's smallest singular value, in contrast with classical
accelerated methods like Nesterov acceleration and Polyak momentum. Through
empirical benchmarks on quadratic and logistic regression problems, we identify
regimes in which the the proposed methods improve over classical (worst-case)
accelerated methods.
- Abstract(参考訳): 本研究では,この解析で最適となる確率2次問題と導出アルゴリズムの平均ケース解析のためのフレームワークを開発する。
これにより、ヘッセンの固有値分布のモデルが与えられたとき、加速度を達成する新しいクラスの方法が得られる。
我々は, 均一性, マルテンコ・パストゥル, 指数分布の明示的アルゴリズムを開発した。
これらの方法は運動量に基づくアルゴリズムであり、その超パラメータはヘッセンの最小特異値を知ることなく推定できるが、ネステロフ加速やポリア運動量のような古典的加速法とは対照的である。
二次回帰問題およびロジスティック回帰問題に関する経験的ベンチマークを通じて,提案手法が古典的(ワーストケース)加速法よりも向上するレジームを同定する。
関連論文リスト
- Momentum Particle Maximum Likelihood [2.6831773062745863]
パラメータと確率分布の拡張空間上の自由エネルギー関数を最小化するための類似システムに基づくアプローチを提案する。
適切な仮定の下では、提案された系を連続時間における一意的な一意の最小化器に定量的に収束させる。
そこで本研究では,潜在変数モデルにおけるパラメータ推定に適用可能な数値的な離散化を提案する。
論文 参考訳(メタデータ) (2023-12-12T14:53:18Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T18:54:54Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳(メタデータ) (2021-11-29T15:10:09Z) - The Last-Iterate Convergence Rate of Optimistic Mirror Descent in
Stochastic Variational Inequalities [29.0058976973771]
本稿では,アルゴリズムの収束率とBregman関数によって誘導される局所幾何学との複雑な関係を示す。
この指数はアルゴリズムの最適ステップサイズポリシーと得られた最適レートの両方を決定する。
論文 参考訳(メタデータ) (2021-07-05T09:54:47Z) - A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
最適化のための異なる手法を導出できる変分法を導入する。
我々は1対1の対応において最適化手法の2つのファミリを導出する。
自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
論文 参考訳(メタデータ) (2021-06-04T20:21:53Z) - Acceleration Methods [87.07695512525717]
まず,二次最適化問題を用いて,モメンタムとネスト正則性最適化スキームという2つの主要な手法を導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
次に、emphCatalystとemphAccelerated Hybrid Proximal Extragradientフレームワークの中心にある加速度技術をカバーする。
論文 参考訳(メタデータ) (2021-01-23T17:58:25Z) - Differentially Private Accelerated Optimization Algorithms [0.7874708385247353]
微分プライベート最適化アルゴリズムの2つのクラスを示す。
最初のアルゴリズムはPolyakのヘビーボール法にインスパイアされている。
アルゴリズムの第2のクラスは、ネステロフの加速勾配法に基づいている。
論文 参考訳(メタデータ) (2020-08-05T08:23:01Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳(メタデータ) (2020-06-11T18:49:06Z) - Interpolation Technique to Speed Up Gradients Propagation in Neural ODEs [71.26657499537366]
本稿では,ニューラルネットワークモデルにおける勾配の効率的な近似法を提案する。
我々は、分類、密度推定、推論近似タスクにおいて、ニューラルODEをトレーニングするリバースダイナミック手法と比較する。
論文 参考訳(メタデータ) (2020-03-11T13:15:57Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳(メタデータ) (2020-03-06T16:17:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。