論文の概要: Online Stochastic Optimization with Wasserstein Based Non-stationarity
- arxiv url: http://arxiv.org/abs/2012.06961v2
- Date: Wed, 23 Dec 2020 06:24:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-09 19:43:54.593869
- Title: Online Stochastic Optimization with Wasserstein Based Non-stationarity
- Title（参考訳）: Wassersteinに基づく非定常性を用いたオンライン確率最適化
- Authors: Jiashuo Jiang, Xiaocheng Li, Jiawei Zhang
- Abstract要約: 有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
- 参考スコア（独自算出の注目度）: 12.91020811577007
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a general online stochastic optimization problem with multiple
budget constraints over a horizon of finite time periods. In each time period,
a reward function and multiple cost functions are revealed, and the decision
maker needs to specify an action from a convex and compact action set to
collect the reward and consume the budget. Each cost function corresponds to
the consumption of one budget. In each period, the reward and cost functions
are drawn from an unknown distribution, which is non-stationary across time.
The objective of the decision maker is to maximize the cumulative reward
subject to the budget constraints. This formulation captures a wide range of
applications including online linear programming and network revenue
management, among others. In this paper, we consider two settings: (i) a
data-driven setting where the true distribution is unknown but a prior estimate
(possibly inaccurate) is available; (ii) an uninformative setting where the
true distribution is completely unknown. We propose a unified
Wasserstein-distance based measure to quantify the inaccuracy of the prior
estimate in setting (i) and the non-stationarity of the system in setting (ii).
We show that the proposed measure leads to a necessary and sufficient condition
for the attainability of a sublinear regret in both settings. For setting (i),
we propose a new algorithm, which takes a primal-dual perspective and
integrates the prior information of the underlying distributions into an online
gradient descent procedure in the dual space. The algorithm also naturally
extends to the uninformative setting (ii). Under both settings, we show the
corresponding algorithm achieves a regret of optimal order. In numerical
experiments, we demonstrate how the proposed algorithms can be naturally
integrated with the re-solving technique to further boost the empirical
performance.
- Abstract（参考訳）: 有限期間の地平線上で複数の予算制約を持つ一般的なオンライン確率最適化問題を考える。
各期間において、報酬関数と複数のコスト関数が明らかにされ、意思決定者は、報酬を収集して予算を消費するために、凸及びコンパクトなアクションセットからのアクションを指定する必要がある。
各コスト関数は1つの予算の消費に対応する。
それぞれの期間において、報酬とコスト関数は未知の分布から引き出される。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理など、幅広いアプリケーションを取り込んでいる。
本稿では,次の2つの設定について考察する。 (i) 真の分布が未知であるが,事前推定(おそらく不正確な)が利用可能であるデータ駆動設定 (ii) 真の分布が完全に未知であるような非形式的設定 (uninformative setting) である。
本研究では,事前推定の不正確な設定(i)とシステムの非定常性(ii)を定量化する統一wasserstein- distance based measureを提案する。
提案手法は,両設定においてサブ線形後悔の達成に必要かつ十分な条件を導出することを示す。
i) 設定のために,本アルゴリズムは主対双対的な視点を採り,基礎となる分布の事前情報を双対空間におけるオンライン勾配降下手順に統合するアルゴリズムを提案する。
このアルゴリズムは自然に非形式的設定 (ii) にも拡張される。
どちらの設定でも、対応するアルゴリズムが最適な順序を後悔することを示す。
数値実験では,提案アルゴリズムが再解法と自然に統合され,経験的性能がさらに向上することを示した。
関連論文リスト
- Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
大規模データの爆発はシングルマシンシステムの処理能力を上回っている。
分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。
そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-30T13:22:08Z) - Online Fair Allocation of Perishable Resources [1.4952056744888913]
我々は、標準オンラインフェアアロケーション問題の事実上の動機付け型を考察する。
意思決定者は、一定回数のラウンドを割り当てるために、パーシシブルなリソースの予算を持っている。
目標は、うらやましいほど効率的で効率的なアロケーションのシーケンスを構築することです。
論文 参考訳（メタデータ） (2024-06-04T15:14:10Z) - Constrained Online Two-stage Stochastic Optimization: Algorithm with
(and without) Predictions [19.537289123577022]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳（メタデータ） (2024-01-02T07:46:33Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳（メタデータ） (2023-02-02T16:30:33Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - On Reward-Free RL with Kernel and Neural Function Approximations:
Single-Agent MDP and Markov Game [140.19656665344917]
エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。
関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。
我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
論文 参考訳（メタデータ） (2021-10-19T07:26:33Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。
様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。
我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
論文 参考訳（メタデータ） (2020-11-18T18:39:17Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。