論文の概要: Stochastic Saddle Point Problems with Decision-Dependent Distributions
- arxiv url: http://arxiv.org/abs/2201.02313v1
- Date: Fri, 7 Jan 2022 03:36:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-10 15:34:01.627689
- Title: Stochastic Saddle Point Problems with Decision-Dependent Distributions
- Title（参考訳）: 決定依存分布をもつ確率的鞍点問題
- Authors: Killian Wood and Emiliano Dall'Anese
- Abstract要約: 本稿では,静的設定と時間変化設定の両方において決定に依存するサドル点問題に焦点をあてる。
定常ミニマックス問題に対するサドル点である平衡点の概念を導入する。
原始双対アルゴリズムは、同様の方法でサドル点に収束することを示す。
- 参考スコア（独自算出の注目度）: 0.6091702876917279
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper focuses on stochastic saddle point problems with
decision-dependent distributions in both the static and time-varying settings.
These are problems whose objective is the expected value of a stochastic payoff
function, where random variables are drawn from a distribution induced by a
distributional map. For general distributional maps, the problem of finding
saddle points is in general computationally burdensome, even if the
distribution is known. To enable a tractable solution approach, we introduce
the notion of equilibrium points -- which are saddle points for the stationary
stochastic minimax problem that they induce -- and provide conditions for their
existence and uniqueness. We demonstrate that the distance between the two
classes of solutions is bounded provided that the objective has a
strongly-convex-strongly-concave payoff and Lipschitz continuous distributional
map. We develop deterministic and stochastic primal-dual algorithms and
demonstrate their convergence to the equilibrium point. In particular, by
modeling errors emerging from a stochastic gradient estimator as sub-Weibull
random variables, we provide error bounds in expectation and in high
probability that hold for each iteration; moreover, we show convergence to a
neighborhood in expectation and almost surely. Finally, we investigate a
condition on the distributional map -- which we call opposing mixture dominance
-- that ensures the objective is strongly-convex-strongly-concave. Under this
assumption, we show that primal-dual algorithms converge to the saddle points
in a similar fashion.
- Abstract（参考訳）: 本稿では,静的および時間変化の両条件における決定依存分布の確率的サドル点問題に焦点をあてる。
これらの問題は、確率的給与関数の期待値が目的であり、確率変数は分布写像によって引き起こされる分布から引き出される。
一般分布写像において、鞍点を見つける問題は、分布が分かっていても一般に計算的に負担がかかる。
移動可能な解法を実現するために, 定常確率的ミニマックス問題に対するサドルポイントである平衡点の概念を導入し, それらの存在と一意性について条件を与える。
解の2つのクラス間の距離が有界であることを示し、目的が強凸強凸ペイオフとリプシッツ連続分布写像を持つことを示した。
我々は決定論的かつ確率的原始双対アルゴリズムを開発し,それらの平衡点への収束を実証する。
特に,確率勾配推定器から生じる誤差を準weibull確率変数としてモデル化することにより,期待値と高い確率で各イテレーションに有する誤差境界を提供するとともに,期待値およびほぼ確実に近傍に収束することを示す。
最後に, 対向混合支配と呼ばれる分布写像上の条件について検討し, 目的が強凸強対流であることを確かめる。
この仮定の下で、原始双対アルゴリズムは同様の方法で鞍点に収束することを示す。
関連論文リスト
- An Inexact Halpern Iteration with Application to Distributionally Robust
Optimization [9.529117276663431]
決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。
不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
論文 参考訳（メタデータ） (2024-02-08T20:12:47Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳（メタデータ） (2023-06-27T08:15:28Z) - Robust Estimation for Nonparametric Families via Generative Adversarial
Networks [92.64483100338724]
我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。
我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。
技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
論文 参考訳（メタデータ） (2022-02-02T20:11:33Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite
Optimization [2.9112649816695204]
実バナッハ空間上の凸凹サドル点問題の第一次原始双対解法について検討する。
我々のフレームワークは一般であり、アルゴリズムにおいてブレグマンの発散を誘導するエントロピーの強い凸性を必要としない。
数値的な応用としては、エントロピー的正則化ワッサーシュタイン・バリセンタ問題や、単純体上の正則化逆問題などが挙げられる。
論文 参考訳（メタデータ） (2021-12-22T14:47:44Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical
Solution [8.465228064780748]
2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。
目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。
双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
論文 参考訳（メタデータ） (2021-03-10T18:53:59Z) - On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint
Sampling Method [18.541857410928387]
SL19]により提案されたランダム化拡散法は,連続時間ランゲヴィン・ランゲヴィンをシミュレーションするための最適離散化法として登場した。
論文 参考訳（メタデータ） (2020-11-06T03:39:23Z) - Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized
Equations [0.0]
演算子を期待値とする単調な包摂問題を考える。
分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。
本稿では,不確実性に対処する手法を提案する。
論文 参考訳（メタデータ） (2020-08-26T02:33:27Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
確率分布が未知な分布の不確実性の下でBQOについて検討する。
標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。
この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
論文 参考訳（メタデータ） (2020-01-19T12:00:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。