論文の概要: The Sample Complexity of Approximate Rejection Sampling with
Applications to Smoothed Online Learning
- arxiv url: http://arxiv.org/abs/2302.04658v3
- Date: Fri, 23 Feb 2024 19:35:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 19:47:49.503594
- Title: The Sample Complexity of Approximate Rejection Sampling with
Applications to Smoothed Online Learning
- Title（参考訳）: 平滑化オンライン学習への応用による近似拒絶サンプリングのサンプル複雑性
- Authors: Adam Block and Yury Polyanskiy
- Abstract要約: n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。
次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
- 参考スコア（独自算出の注目度）: 29.44582058149344
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Suppose we are given access to $n$ independent samples from distribution
$\mu$ and we wish to output one of them with the goal of making the output
distributed as close as possible to a target distribution $\nu$. In this work
we show that the optimal total variation distance as a function of $n$ is given
by $\tilde\Theta(\frac{D}{f'(n)})$ over the class of all pairs $\nu,\mu$ with a
bounded $f$-divergence $D_f(\nu\|\mu)\leq D$. Previously, this question was
studied only for the case when the Radon-Nikodym derivative of $\nu$ with
respect to $\mu$ is uniformly bounded. We then consider an application in the
seemingly very different field of smoothed online learning, where we show that
recent results on the minimax regret and the regret of oracle-efficient
algorithms still hold even under relaxed constraints on the adversary (to have
bounded $f$-divergence, as opposed to bounded Radon-Nikodym derivative).
Finally, we also study efficacy of importance sampling for mean estimates
uniform over a function class and compare importance sampling with rejection
sampling.
- Abstract（参考訳）: 分布$\mu$から$n$独立サンプルにアクセスでき、出力をターゲットディストリビューション$\nu$に可能な限り近いものにすることを目標に、その中の1つを出力したいとします。
この研究において、n$ の関数としての最適な全変動距離は、すべての対のクラスに対して$\nu,\mu$ で与えられ、有界な $f$-divergence $d_f(\nu\|\mu)\leq d$ が与えられる。
以前は、この問題は、$\mu$に対する$\nu$のラドン・ニコディム微分が一様有界である場合にのみ研究された。
次に、一見全く異なるスムーズなオンライン学習分野の応用を考えると、ミニマックスの後悔とオラクル効率アルゴリズムの後悔は、(ラドン-ニコディムの有界な微分とは対照的に、$f$-divergenceを有界とする)敵のゆるい制約の下でも保たれていることを示す。
最後に,関数クラス全体に対する平均推定値に対する重要サンプリングの有効性について検討し,また,重要サンプリングと拒絶サンプリングを比較した。
関連論文リスト
- Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。
我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
論文 参考訳（メタデータ） (2024-07-18T15:58:04Z) - Weighted least-squares approximation with determinantal point processes and generalized volume sampling [33.33724208084121]
与えられた$m$-次元空間$V_m$の要素によって、函数を$L2$から近似する問題を考える。
近似は、ほぼ確実に$H$-normで測定された最高の近似誤差によって境界づけられていることを示す。
論文 参考訳（メタデータ） (2023-12-21T17:34:18Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Optimistic Posterior Sampling for Reinforcement Learning with Few
Samples and Tight Guarantees [43.13918072870693]
強化学習(OPSRL)のための楽観的後部サンプリングアルゴリズムを提案する。
殆どの$widetildemathcalO(sqrtH3SAT)$ ignoring $textpolylog(HSAT)$ termsにおいて、高い確率で再帰的な順序境界を保証する。
我々の境界は位数$Omega(sqrtH3SAT)$の下位境界と一致し、Agrawal と Jia が提起した開問題に答える。
論文 参考訳（メタデータ） (2022-09-28T20:49:34Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。