論文の概要: Data-driven optimal stopping: A pure exploration analysis
- arxiv url: http://arxiv.org/abs/2312.05880v1
- Date: Sun, 10 Dec 2023 13:16:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-12 18:15:45.636732
- Title: Data-driven optimal stopping: A pure exploration analysis
- Title(参考訳): データ駆動型最適停止:純粋な探索分析
- Authors: S\"oren Christensen, Niklas Dexheimer, Claudia Strauch
- Abstract要約: 最小限の最適性は、単純な後悔に対する下界を一致させて上界結果を完成させることによって検証される。
本研究は, 具体的な探査・探査戦略について, 簡単な後悔から累積後悔への移動について検討した。
- 参考スコア(独自算出の注目度): 1.0742675209112622
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The standard theory of optimal stopping is based on the idealised assumption
that the underlying process is essentially known. In this paper, we drop this
restriction and study data-driven optimal stopping for a general diffusion
process, focusing on investigating the statistical performance of the proposed
estimator of the optimal stopping barrier. More specifically, we derive
non-asymptotic upper bounds on the simple regret, along with uniform and
non-asymptotic PAC bounds. Minimax optimality is verified by completing the
upper bound results with matching lower bounds on the simple regret. All
results are shown both under general conditions on the payoff functions and
under more refined assumptions that mimic the margin condition used in binary
classification, leading to an improved rate of convergence. Additionally, we
investigate how our results on the simple regret transfer to the cumulative
regret for a specific exploration-exploitation strategy, both with respect to
lower bounds and upper bounds.
- Abstract(参考訳): 最適停止の標準理論は、基礎となる過程が本質的に知られているという理想化された仮定に基づいている。
本稿では, この制約を取り除き, 一般的な拡散過程におけるデータ駆動型最適停止について検討し, 最適停止障壁推定器の統計的性能について検討する。
より具体的には、単純後悔に対する非漸近上界と、一様および非漸近性PAC境界を導出する。
最小限の最適性は、単純な後悔に対する下界を一致させて上界結果を完成させることによって検証される。
すべての結果は、給与関数の一般的な条件と、バイナリ分類で使われるマージン条件を模倣したより洗練された仮定の両方で示され、収束率の向上に繋がる。
さらに,我々は,下限と上限の両方において,特定の探査・探査戦略の累積的後悔に単純な後悔を移す結果について検討した。
関連論文リスト
- Regret Optimality of GP-UCB [12.323109084902228]
ガウス過程 上信頼境界 (GP-UCB) は、ノイズの多い観測でブラックボックス関数を最適化する最も一般的な方法の1つである。
GP-UCB の単純かつ累積的後悔の両面に新たな上限を確立する。
同じレベルの探索で、GP-UCBは単純かつ累積的後悔の両方において、同時に最適性を達成することができる。
論文 参考訳(メタデータ) (2023-12-03T13:20:08Z) - Off-policy estimation of linear functionals: Non-asymptotic theory for
semi-parametric efficiency [59.48096489854697]
観測データに基づいて線形汎関数を推定する問題は、因果推論と包帯文献の両方において標準的である。
このような手順の平均二乗誤差に対して非漸近上界を証明した。
非漸近的局所ミニマックス下限をマッチングすることにより、有限標本のインスタンス依存最適性を確立する。
論文 参考訳(メタデータ) (2022-09-26T23:50:55Z) - Sharp Bounds for Federated Averaging (Local SGD) and Continuous
Perspective [49.17352150219212]
Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。
微分方程式(SDE)の観点から、この量を解析する方法を示す。
論文 参考訳(メタデータ) (2021-11-05T22:16:11Z) - Minimax Optimal Quantile and Semi-Adversarial Regret via
Root-Logarithmic Regularizers [31.102181563065844]
量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。
最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。
我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
論文 参考訳(メタデータ) (2021-10-27T22:38:52Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum
Optimization [1.6973426830397942]
平滑な非有限和最適化における高階法の下限を証明する。
pth-order regularized method は有限和の目的から利益を得ることができないことを示す。
新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
論文 参考訳(メタデータ) (2021-03-08T23:33:58Z) - Finite Sample Analysis of Minimax Offline Reinforcement Learning:
Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
強化学習におけるオフ・ポリティィ・アセスメント(OPE)の理論的特徴について述べる。
ミニマックス法により、重みと品質関数の高速収束を実現することができることを示す。
非タブラル環境における1次効率を持つ最初の有限サンプル結果を示す。
論文 参考訳(メタデータ) (2021-02-05T03:20:39Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳(メタデータ) (2020-08-20T03:48:14Z) - Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via
Root-Entropic Regularization [16.536558038560695]
我々は、未知の制約セット内でデータを任意に生成する場合、専門家のアドバイスで予測する。
Hedgeアルゴリズムは、最近、i.d.データに対して同時にミニマックス最適であることが示されている。
我々は,すべてのレベルにおいてミニマックス後悔の上限と下限を一致させ,決定論的学習率を持つヘッジが極端外において最適以下であることを示し,すべてのレベルにおいてミニマックス後悔を適応的に得ることを証明した。
論文 参考訳(メタデータ) (2020-07-13T17:54:34Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳(メタデータ) (2020-06-12T00:32:21Z) - On Low-rank Trace Regression under General Sampling Distribution [9.699586426043885]
クロスバリデード推定器は一般仮定でほぼ最適誤差境界を満たすことを示す。
また, クロスバリデーション推定器はパラメータ選択理論に着想を得た手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2019-04-18T02:56:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。