論文の概要: Learning and Covering Sums of Independent Random Variables with Unbounded Support

• arxiv url: http://arxiv.org/abs/2210.13313v1
• Date: Mon, 24 Oct 2022 15:03:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-25 22:19:29.291066
• Title: Learning and Covering Sums of Independent Random Variables with Unbounded Support
• Title（参考訳）: 非有界サポートを持つ独立確率変数の学習と総和
• Authors: Alkis Kalavasis, Konstantinos Stavropoulos, Manolis Zampetakis
• Abstract要約: 独立整数値確率変数の和 $X = X_1 + cdots + X_n$ を非有界、あるいは無限なサポートでカバーし、学習する問題について検討する。 我々は、$X_i$sの集合的サポートの最大値が、必ずしも$X$を学習する際のサンプルの複雑さに現れることを示した。
• 参考スコア（独自算出の注目度）: 4.458210211781738
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of covering and learning sums $X = X_1 + \cdots + X_n$ of independent integer-valued random variables $X_i$ (SIIRVs) with unbounded, or even infinite, support. De et al. at FOCS 2018, showed that the maximum value of the collective support of $X_i$'s necessarily appears in the sample complexity of learning $X$. In this work, we address two questions: (i) Are there general families of SIIRVs with unbounded support that can be learned with sample complexity independent of both $n$ and the maximal element of the support? (ii) Are there general families of SIIRVs with unbounded support that admit proper sparse covers in total variation distance? As for question (i), we provide a set of simple conditions that allow the unbounded SIIRV to be learned with complexity $\text{poly}(1/\epsilon)$ bypassing the aforementioned lower bound. We further address question (ii) in the general setting where each variable $X_i$ has unimodal probability mass function and is a different member of some, possibly multi-parameter, exponential family $\mathcal{E}$ that satisfies some structural properties. These properties allow $\mathcal{E}$ to contain heavy tailed and non log-concave distributions. Moreover, we show that for every $\epsilon > 0$, and every $k$-parameter family $\mathcal{E}$ that satisfies some structural assumptions, there exists an algorithm with $\tilde{O}(k) \cdot \text{poly}(1/\epsilon)$ samples that learns a sum of $n$ arbitrary members of $\mathcal{E}$ within $\epsilon$ in TV distance. The output of the learning algorithm is also a sum of random variables whose distribution lies in the family $\mathcal{E}$. En route, we prove that any discrete unimodal exponential family with bounded constant-degree central moments can be approximated by the family corresponding to a bounded subset of the initial (unbounded) parameter space.
• Abstract（参考訳）: 独立整数値確率変数の和 $X = X_1 + \cdots + X_n$ を非有界あるいは無限なサポート付きでカバーし学習する問題について検討する。 de et al. は、focs 2018で、$x_i$'s の集団的サポートの最大値は、必ず $x$ の学習のサンプル複雑さに現れることを示した。 この作品では2つの疑問に答えます (i)$n$ とサポートの最大要素の両方に依存しないサンプル複雑性で学べる、無制限のサポートを持つsiirvの一般的なファミリーは存在するか? (ii)全変動距離において適切なスパースカバーを許容する非有界なサポートを持つsiirvの一般ファミリーは存在するか? 質問として i) 上述した下界をバイパスする複雑性$\text{poly}(1/\epsilon)$ で、非有界な SIIRV を学習できる一連の単純な条件を提供する。 我々はさらに疑問に答える (ii) 各変数 $x_i$ がユニモーダル確率質量関数を持ち、いくつかの構造的性質を満たす、おそらくは多パラメータの指数関数族 $\mathcal{e}$ の異なるメンバーである一般設定において。 これらの性質により、$\mathcal{E}$ は重い尾と非対数分布を含むことができる。 さらに、$\epsilon > 0$ および $k$-parameter family $\mathcal{E}$ がいくつかの構造的仮定を満たす場合、$\tilde{O}(k) \cdot \text{poly}(1/\epsilon)$ のサンプルを持つアルゴリズムが存在し、$\mathcal{E}$ の任意のメンバーの$n$の和をTV距離で学習する。 学習アルゴリズムの出力は、分布が $\mathcal{e}$ に属する確率変数の和でもある。 経路において、定数度中央モーメントが有界な任意の離散単項指数族は、初期(非有界)パラメータ空間の有界部分集合に対応する族によって近似できることを示す。

関連論文リスト

• The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
  単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。 この問題は、$alpha = beta$ (prior-free) または $alpha = 1/2$ (Bayesian) でのみ研究されている。
  論文  参考訳（メタデータ） (2024-03-25T17:42:32Z)
• Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
  1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。 目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
  論文  参考訳（メタデータ） (2024-03-14T15:04:45Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。 具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。 本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
  論文  参考訳（メタデータ） (2023-11-22T04:34:09Z)
• Learning linear dynamical systems under convex constraints [4.4351901934764975]
  線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。 A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
  論文  参考訳（メタデータ） (2023-03-27T11:49:40Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。 我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
  論文  参考訳（メタデータ） (2020-08-16T21:26:46Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。