論文の概要: Stochastic optimization with arbitrary recurrent data sampling
- arxiv url: http://arxiv.org/abs/2401.07694v1
- Date: Mon, 15 Jan 2024 14:04:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-17 16:57:17.576416
- Title: Stochastic optimization with arbitrary recurrent data sampling
- Title（参考訳）: 任意再帰データサンプリングによる確率的最適化
- Authors: William G. Powell and Hanbaek Lyu
- Abstract要約: 最も一般的に使われているデータサンプリングアルゴリズムは、軽度な仮定の下にある。
特定のクラスの繰り返し最適化アルゴリズムに対して、他のプロパティは不要であることを示す。
我々は,データセットをカバーするサンプリングアルゴリズムを選択することで,収束を加速できることを示す。
- 参考スコア（独自算出の注目度）: 2.5382095320488673
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For obtaining optimal first-order convergence guarantee for stochastic
optimization, it is necessary to use a recurrent data sampling algorithm that
samples every data point with sufficient frequency. Most commonly used data
sampling algorithms (e.g., i.i.d., MCMC, random reshuffling) are indeed
recurrent under mild assumptions. In this work, we show that for a particular
class of stochastic optimization algorithms, we do not need any other property
(e.g., independence, exponential mixing, and reshuffling) than recurrence in
data sampling algorithms to guarantee the optimal rate of first-order
convergence. Namely, using regularized versions of Minimization by Incremental
Surrogate Optimization (MISO), we show that for non-convex and possibly
non-smooth objective functions, the expected optimality gap converges at an
optimal rate $O(n^{-1/2})$ under general recurrent sampling schemes.
Furthermore, the implied constant depends explicitly on the `speed of
recurrence', measured by the expected amount of time to visit a given data
point either averaged (`target time') or supremized (`hitting time') over the
current location. We demonstrate theoretically and empirically that convergence
can be accelerated by selecting sampling algorithms that cover the data set
most effectively. We discuss applications of our general framework to
decentralized optimization and distributed non-negative matrix factorization.
- Abstract（参考訳）: 確率最適化のための最適な一階収束保証を得るには、全てのデータポイントを十分な周波数でサンプリングするリカレントデータサンプリングアルゴリズムを使う必要がある。
最もよく使われるデータサンプリングアルゴリズム(例えば、MCMC、ランダムリシャッフル)は、実際は穏やかな仮定の下で繰り返される。
本研究では,特定の確率的最適化アルゴリズムに対して,データサンプリングアルゴリズムにおける再帰性以外の特性(独立性,指数混合性,再シャッフル性など)を必要とせず,一階収束の最適性を保証する。
すなわち、インクリメンタルサロゲート最適化(MISO)による最小化の正規化バージョンを用いて、非凸およびおそらく非滑らかな目的関数に対して、期待される最適性ギャップは、一般的な再帰サンプリングスキームの下での最適速度$O(n^{-1/2})$で収束することを示す。
さらに、インプリート定数は、現在の位置上で平均値(「ターゲット時間」)または上限値(「ハイティング時間」)を訪問する所望の時間量によって測定される「再発速度」に明示的に依存する。
我々は,データセットを効率的にカバーするサンプリングアルゴリズムを選択することにより,収束を加速できることを示す。
分散最適化と分散非負行列分解への一般フレームワークの適用について論じる。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳（メタデータ） (2022-06-22T17:58:23Z) - Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax
Optimization [12.794526174053134]
滑らかな有限サム最小値最適化のための勾配アルゴリズムの収束速度を解析する。
このようなアルゴリズムの多くは、置換のないサンプリングポイントが、置換したサンプリングよりも高速な収束をもたらすことを示している。
論文 参考訳（メタデータ） (2022-06-07T00:37:37Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory [6.696267547013535]
そこで本研究では,データ駆動基準によりパラメータ選択された,近接する隣人の数がパラメータとなる分散適応型NN分類器を提案する。
有限標本性能を向上する最適チューニングパラメータを探索する際,早期停止規則を提案する。
特に、サブサンプルサイズが十分に大きい場合、提案した分類器がほぼ最適な収束率を達成することを示す。
論文 参考訳（メタデータ） (2021-05-20T14:38:41Z) - On the Comparison between Cyclic Sampling and Random Reshuffling [27.27774034428748]
周期的なサンプリングは、サンプルを周期的に再シャッフルするよりも頑丈でない、固定された循環的な順序でサンプルを引き出す。
既存の研究は、循環サンプリングにおける最悪のケース収束率を確立しており、一般にランダムリシャフリングよりも悪い。
本論文では,リシャッフルよりも一定の周期順序の方がはるかに早く,低コストで発見できることを発見した。
論文 参考訳（メタデータ） (2021-04-25T09:29:43Z) - Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。
提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
論文 参考訳（メタデータ） (2020-12-07T14:58:16Z) - 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) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。