論文の概要: Stochastic optimization with arbitrary recurrent data sampling
- arxiv url: http://arxiv.org/abs/2401.07694v2
- Date: Sat, 20 Jul 2024 18:56:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 03:02:44.548354
- Title: Stochastic optimization with arbitrary recurrent data sampling
- Title（参考訳）: 任意の繰り返しデータサンプリングによる確率最適化
- Authors: William G. Powell, Hanbaek Lyu,
- Abstract要約: 最も一般的に使われているデータサンプリングアルゴリズムは、軽度な仮定の下にある。
特定のクラスの繰り返し最適化アルゴリズムに対して、他のプロパティは不要であることを示す。
我々は,データセットをカバーするサンプリングアルゴリズムを選択することで,収束を加速できることを示す。
- 参考スコア（独自算出の注目度）: 2.1485350418225244
- 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 Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - 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) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。