論文の概要: PAC Mode Estimation using PPR Martingale Confidence Sequences
- arxiv url: http://arxiv.org/abs/2109.05047v1
- Date: Fri, 10 Sep 2021 18:11:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-18 23:53:13.565786
- Title: PAC Mode Estimation using PPR Martingale Confidence Sequences
- Title（参考訳）: PPR Martingale Confidence Sequences を用いたPACモード推定
- Authors: Shubham Anand Jain, Sanit Gupta, Denil Mehta, Inderjeet Jayakumar
Nair, Rohan Shah, Jian Vora, Sushil Khyalia, Sourav Das, Vinay J. Ribeiro,
Shivaram Kalyanakrishnan
- Abstract要約: 離散分布 $mathcalP$ のモードを十分に高い確率で正確に同定する問題を考える。
モード推定の一般化を提案し、$mathcalP$は$K geq 2$値を取ることができる。
結果,PPR-MEと表される停止規則は,対数係数までのサンプル複雑性において最適である。
- 参考スコア（独自算出の注目度）: 5.623190096715942
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of correctly identifying the mode of a discrete
distribution $\mathcal{P}$ with sufficiently high probability by observing a
sequence of i.i.d. samples drawn according to $\mathcal{P}$. This problem
reduces to the estimation of a single parameter when $\mathcal{P}$ has a
support set of size $K = 2$. Noting the efficiency of prior-posterior-ratio
(PPR) martingale confidence sequences for handling this special case, we
propose a generalisation to mode estimation, in which $\mathcal{P}$ may take $K
\geq 2$ values. We observe that the "one-versus-one" principle yields a more
efficient generalisation than the "one-versus-rest" alternative. Our resulting
stopping rule, denoted PPR-ME, is optimal in its sample complexity up to a
logarithmic factor. Moreover, PPR-ME empirically outperforms several other
competing approaches for mode estimation. We demonstrate the gains offered by
PPR-ME in two practical applications: (1) sample-based forecasting of the
winner in indirect election systems, and (2) efficient verification of smart
contracts in permissionless blockchains.
- Abstract（参考訳）: 離散分布 $\mathcal{p}$ のモードを十分に高い確率で正しく同定する問題は、$\mathcal{p}$ に従って描かれた i.i.d. サンプルの列を観察することによって解決される。
この問題は、$\mathcal{p}$ が $k = 2$ の大きさのサポートセットを持つとき、単一のパラメータの推定に還元される。
この特別なケースを扱うために、ppr の martingale 信頼シーケンスの効率性に注目し、$\mathcal{p}$ が $k \geq 2$ の値を取るモード推定の一般化を提案する。
我々は、"one-versus-one"原則が"one-versus-rest"代替よりもより効率的な一般化をもたらすことを観察する。
結果,PPR-MEと表される停止規則は,対数係数までのサンプル複雑性において最適である。
さらに、PPR-MEは、モード推定のための他の競合するアプローチよりも経験的に優れている。
1) 間接選挙システムにおける勝者のサンプルベース予測と, (2) 許可なしブロックチェーンにおけるスマートコントラクトの効率的な検証である。
関連論文リスト
- Computing Optimal Manipulations in Cryptographic Self-Selection Proof-of-Stake Protocols [3.3139913966251227]
任意の所望の$(alpha,beta)$に対して$f(alpha,beta)$を任意の精度まで確実に釘付けする方法を開発する。
技術的課題の1つは、対象分布の平均値の自然サンプリングに基づく推定は、偏りのない推定値であるということである。
論文 参考訳（メタデータ） (2024-06-21T16:20:39Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。
本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
論文 参考訳（メタデータ） (2023-11-15T12:36:45Z) - Improved Convergence of Score-Based Diffusion Models via Prediction-Correction [15.772322871598085]
スコアベース生成モデル(SGM)は、複雑なデータ分布からサンプリングする強力なツールである。
本稿では,一般的な予測器・相関器方式のバージョンを考慮し,この問題に対処する。
まず、不正確なランゲヴィン力学を用いて最終分布を推定し、次にその過程を逆転する。
論文 参考訳（メタデータ） (2023-05-23T15:29:09Z) - 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) - Convergence for score-based generative modeling with polynomial
complexity [9.953088581242845]
我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。
以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。
予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
論文 参考訳（メタデータ） (2022-06-13T14:57:35Z) - Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。
我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-01-21T16:43:03Z) - Consistent Sufficient Explanations and Minimal Local Rules for
explaining regression and classification models [0.0]
我々は確率的十分説明(P-SE)の概念を拡張した
P-SEの要点は、同じ予測を維持する条件確率を計算することである。
我々は、$X$の分布を学ばず、予測を行うモデルも持たない非バイナリ機能に対処する。
論文 参考訳（メタデータ） (2021-11-08T17:27:52Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。