論文の概要: Stochastic-Constrained Stochastic Optimization with Markovian Data

• arxiv url: http://arxiv.org/abs/2312.04312v1
• Date: Thu, 7 Dec 2023 14:09:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-08 14:57:20.273870
• Title: Stochastic-Constrained Stochastic Optimization with Markovian Data
• Title（参考訳）: マルコフデータを用いた確率制約付き確率最適化
• Authors: Yeongjong Kim, Dabeen Lee
• Abstract要約: マルコフ連鎖からデータサンプルが引き出され、したがって独立性がなく、同一に分布しないような環境について検討する。 ドリフト・プラス・ペナルティの2つの変種を提案する。ひとつは、基礎となるマルコフ鎖の混合時間を知る場合である。 我々のアルゴリズムは、制約関数列がマルコフ連鎖に従うような制約付きオンライン凸最適化のより一般的な設定に適用できる。
• 参考スコア（独自算出の注目度）: 2.1756081703276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers stochastic-constrained stochastic optimization where the stochastic constraint is to satisfy that the expectation of a random function is below a certain threshold. In particular, we study the setting where data samples are drawn from a Markov chain and thus are not independent and identically distributed. We generalize the drift-plus-penalty framework, a primal-dual stochastic gradient method developed for the i.i.d. case, to the Markov chain sampling setting. We propose two variants of drift-plus-penalty; one is for the case when the mixing time of the underlying Markov chain is known while the other is for the case of unknown mixing time. In fact, our algorithms apply to a more general setting of constrained online convex optimization where the sequence of constraint functions follows a Markov chain. Both algorithms are adaptive in that the first works without knowledge of the time horizon while the second uses AdaGrad-style algorithm parameters, which is of independent interest. We demonstrate the effectiveness of our proposed methods through numerical experiments on classification with fairness constraints.
• Abstract（参考訳）: 本稿では,確率的制約がランダム関数の期待値が一定のしきい値以下であることを示す確率的拘束型確率的最適化を考える。 特に,マルコフ連鎖からデータサンプルを抽出し,独立性を持たず,同一に分布する環境について検討する。 我々は,i.i.d.ケース用に開発された初回-双次確率勾配法であるドリフト-プラス-ペナルティフレームワークをマルコフ連鎖サンプリング設定に一般化する。 我々はドリフトプラスペナルティの2つの変種を提案する。1つはマルコフ鎖の混合時間が知られ、もう1つは未知の混合時間の場合である。 実際、我々のアルゴリズムは制約付きオンライン凸最適化のより一般的な設定に適用され、制約関数の列はマルコフ連鎖に従う。 どちらのアルゴリズムも適応的であり、第1のアルゴリズムは時間軸の知識なしに動作し、第2のアルゴリズムはAdaGradスタイルのアルゴリズムパラメータを使用する。 フェアネス制約付き分類における数値実験により提案手法の有効性を実証する。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
  マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配勾配の変動について検討する。 我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
  論文  参考訳（メタデータ） (2023-02-28T09:18:00Z)
• Adapting to Mixing Time in Stochastic Optimization with Markovian Data [12.709177728330399]
  マルコフ連鎖からデータを引き出す際の最適化問題を考える。 この設定の既存の方法は、チェーンの混合時間を知ることに依存する。 本手法は,適応学習法とともに,マルチレベルモンテカルロ勾配推定(ML)の新たな組み合わせに依存する。
  論文  参考訳（メタデータ） (2022-02-09T12:43:11Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise [2.0305676256390934]
  2つの連結非線形作用素の根を探すためのシミュレーションベースアプローチである,いわゆる2時間スケール近似について検討する。 特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。 演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を 0 に特徴づける公式を提供する。
  論文  参考訳（メタデータ） (2021-04-04T15:19:19Z)
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance [0.0]
  本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。 この回避は、非自明な常微分方程式のノイズ離散化として研究される。
  論文  参考訳（メタデータ） (2020-12-07T19:14:49Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。