論文の概要: How to Shrink Confidence Sets for Many Equivalent Discrete Distributions?
- arxiv url: http://arxiv.org/abs/2407.15662v1
- Date: Mon, 22 Jul 2024 14:19:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-23 14:40:28.533552
- Title: How to Shrink Confidence Sets for Many Equivalent Discrete Distributions?
- Title（参考訳）: 多くの等価離散分布に対する信頼セットの縮小法
- Authors: Odalric-Ambrym Maillard, Mohammad Sadegh Talebi,
- Abstract要約: 機械学習問題における置換等価性を利用する。
信頼集合のサイズは$O/sqrtn_k)$と$O/max_kin K n_k)$で縮小することを示す。
- 参考スコア（独自算出の注目度）: 17.52590726972374
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the situation when a learner faces a set of unknown discrete distributions $(p_k)_{k\in \mathcal K}$ defined over a common alphabet $\mathcal X$, and can build for each distribution $p_k$ an individual high-probability confidence set thanks to $n_k$ observations sampled from $p_k$. The set $(p_k)_{k\in \mathcal K}$ is structured: each distribution $p_k$ is obtained from the same common, but unknown, distribution q via applying an unknown permutation to $\mathcal X$. We call this \emph{permutation-equivalence}. The goal is to build refined confidence sets \emph{exploiting} this structural property. Like other popular notions of structure (Lipschitz smoothness, Linearity, etc.) permutation-equivalence naturally appears in machine learning problems, and to benefit from its potential gain calls for a specific approach. We present a strategy to effectively exploit permutation-equivalence, and provide a finite-time high-probability bound on the size of the refined confidence sets output by the strategy. Since a refinement is not possible for too few observations in general, under mild technical assumptions, our finite-time analysis establish when the number of observations $(n_k)_{k\in \mathcal K}$ are large enough so that the output confidence sets improve over initial individual sets. We carefully characterize this event and the corresponding improvement. Further, our result implies that the size of confidence sets shrink at asymptotic rates of $O(1/\sqrt{\sum_{k\in \mathcal K} n_k})$ and $O(1/\max_{k\in K} n_{k})$, respectively for elements inside and outside the support of q, when the size of each individual confidence set shrinks at respective rates of $O(1/\sqrt{n_k})$ and $O(1/n_k)$. We illustrate the practical benefit of exploiting permutation equivalence on a reinforcement learning task.
- Abstract（参考訳）: 学習者が未知の離散分布の集合である$(p_k)_{k\in \mathcal K}$を共通アルファベット$\mathcal X$で定義し、各分布に対して$p_k$を構築できる状況を考える。
集合 $(p_k)_{k\in \mathcal K}$ は構成される: 各分布 $p_k$ は同じ共通であるが未知の分布 q から、未知の置換を $\mathcal X$ に適用することで得られる。
これをemph{permutation-equivalence}と呼ぶ。
目標は、この構造的特性を改良された信頼セット \emph{exploiting} を構築することである。
他の一般的な構造概念(Lipschitz smoothness、Linearityなど)と同様に、置換等価性は機械学習問題に自然に現れ、特定のアプローチに対する潜在的なゲインコールの恩恵を受ける。
本稿では,置換等価性を効果的に活用する戦略を提案し,その戦略によって出力される改良された信頼セットのサイズに依存する有限時間高確率を与える。
改良は一般にあまり観測できないため、穏やかな技術的仮定の下では、観測数$(n_k)_{k\in \mathcal K}$が十分大きいときに有限時間解析が成立し、出力信頼セットが初期個々の集合よりも改善される。
我々はこの出来事とそれに対応する改善を慎重に特徴づける。
さらに、各信頼集合のサイズがそれぞれ$O(1/\sqrt{n_k})$と$O(1/\max_{k\in \mathcal K} n_k})$と$O(1/\max_{k\in K} n_k})$の漸近速度で縮小することを示す。
本稿では,強化学習課題における置換等価性を利用した実践的メリットについて述べる。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Transfer Operators from Batches of Unpaired Points via Entropic
Transport Kernels [3.099885205621181]
そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。
我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
論文 参考訳（メタデータ） (2024-02-13T12:52:41Z) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳（メタデータ） (2023-09-25T09:50:15Z) - Learning and Covering Sums of Independent Random Variables with
Unbounded Support [4.458210211781738]
独立整数値確率変数の和 $X = X_1 + cdots + X_n$ を非有界、あるいは無限なサポートでカバーし、学習する問題について検討する。
我々は、$X_i$sの集合的サポートの最大値が、必ずしも$X$を学習する際のサンプルの複雑さに現れることを示した。
論文 参考訳（メタデータ） (2022-10-24T15:03:55Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Metric-Fair Classifier Derandomization [6.269732593554894]
機械学習における分類器のデランドマイズ問題について検討する。
事前のデランドマイズ法は, ほぼ最大値の不等式であることを示す。
我々はこれらの2つの間の魅力的なトレードオフを提供するデランドマイズ手順を考案する。
論文 参考訳（メタデータ） (2022-06-15T21:36:57Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。