論文の概要: Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes
- arxiv url: http://arxiv.org/abs/2103.12243v1
- Date: Tue, 23 Mar 2021 00:28:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-24 14:02:52.026897
- Title: Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes
- Title（参考訳）: ステップサイズ削減による有限サム最適化とサンプリングのための適応的重要度サンプリング
- Authors: Ayoub El Hanchi, David A. Stephens
- Abstract要約: ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。
標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
- 参考スコア（独自算出の注目度）: 4.355567556995855
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reducing the variance of the gradient estimator is known to improve the
convergence rate of stochastic gradient-based optimization and sampling
algorithms. One way of achieving variance reduction is to design importance
sampling strategies. Recently, the problem of designing such schemes was
formulated as an online learning problem with bandit feedback, and algorithms
with sub-linear static regret were designed. In this work, we build on this
framework and propose Avare, a simple and efficient algorithm for adaptive
importance sampling for finite-sum optimization and sampling with decreasing
step-sizes. Under standard technical conditions, we show that Avare achieves
$\mathcal{O}(T^{2/3})$ and $\mathcal{O}(T^{5/6})$ dynamic regret for SGD and
SGLD respectively when run with $\mathcal{O}(1/t)$ step sizes. We achieve this
dynamic regret bound by leveraging our knowledge of the dynamics defined by the
algorithm, and combining ideas from online learning and variance-reduced
stochastic optimization. We validate empirically the performance of our
algorithm and identify settings in which it leads to significant improvements.
- Abstract（参考訳）: 勾配推定器の分散を減少させることは、確率的勾配に基づく最適化およびサンプリングアルゴリズムの収束率を改善することが知られている。
分散還元を達成する一つの方法は、重要なサンプリング戦略を設計することである。
近年,このようなスキームの設計問題は,バンディットフィードバックを伴うオンライン学習問題として定式化され,サブリニアな静的後悔を伴うアルゴリズムが設計されている。
そこで本研究では,有限サム最適化のための適応的重要度サンプリングアルゴリズムであるAvareを提案し,ステップサイズを小さくしたサンプリングを行う。
標準的な技術的条件下では、Avare は $\mathcal{O}(T^{2/3})$ と $\mathcal{O}(T^{5/6})$ を、それぞれ $\mathcal{O}(1/t)$ のステップサイズで実行するときに、SGD と SGLD の動的後悔を達成する。
我々は,アルゴリズムが定義する力学の知識を活用し,オンライン学習と分散還元確率最適化のアイデアを組み合わせることで,この動的後悔を克服する。
我々は,アルゴリズムの性能を実証的に検証し,それが大きな改善をもたらす設定を特定する。
関連論文リスト
- Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization [0.0]
雑音のない微分自由最適化のための球平滑化法とガウス平滑化法を拡張した新しいアルゴリズムを提案する。
アルゴリズムはスムーズなカーネルの形状を動的に適応させ、局所最適関数の Hessian を近似する。
論文 参考訳（メタデータ） (2024-05-02T21:04:20Z) - Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。
適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。
決定集合の低次元構造を高次元問題に活用する。
論文 参考訳（メタデータ） (2022-11-21T18:31:43Z) - Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
ゼロ階エントロピー合成目的のためのアルゴリズムを解析し,次元依存性に着目した。
これは、ミラー降下法と推定類似関数を用いて、決定セットの低次元構造を利用して達成される。
勾配を改善するため、Rademacherに基づく古典的なサンプリング法を置き換え、ミニバッチ法が非ユークリ幾何学に対処することを示す。
論文 参考訳（メタデータ） (2022-08-09T07:36:25Z) - A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [21.67411847762289]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAが$O(frac1T)$収束率を持つことを示す。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Asymptotic study of stochastic adaptive algorithm in non-convex
landscape [2.1320960069210484]
本稿では、最適化や機械学習に広く用いられる適応アルゴリズムの仮定特性について検討する。
このうちAdagradとRmspropは、ブラックボックスのディープラーニングアルゴリズムの大部分に関与している。
論文 参考訳（メタデータ） (2020-12-10T12:54:45Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
我々は、バリエーションのホストが、我々が提案する統一されたフレームワークでカバー可能であることを示す。
本稿では,この手法の収束性を証明し,ResNet,LSTM,Transformer上での経験的性能を厳格に評価する。
論文 参考訳（メタデータ） (2020-06-10T08:22:41Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。