論文の概要: Learning multivariate Gaussians with imperfect advice

• arxiv url: http://arxiv.org/abs/2411.12700v1
• Date: Tue, 19 Nov 2024 18:08:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:37:19.470789
• Title: Learning multivariate Gaussians with imperfect advice
• Title（参考訳）: 不完全なアドバイスによる多変量ガウスの学習
• Authors: Arnab Bhattacharyya, Davin Choo, Philips George John, Themis Gouleakis,
• Abstract要約: 学習強化アルゴリズムの枠組みにおける分布学習の問題を再考する。 我々の目的は、アドバイスの質が向上するにつれて、サンプルの複雑さが減少する学習アルゴリズムを開発することである。
• 参考スコア（独自算出の注目度）: 14.459107410136486
• License:
• Abstract: We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is provided as potentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases as the quality of the advice improves, thereby surpassing standard learning lower bounds when the advice is sufficiently accurate. Specifically, we demonstrate that this outcome is achievable for the problem of learning a multivariate Gaussian distribution $N(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ in the PAC learning setting. Classically, in the advice-free setting, $\tilde{\Theta}(d^2/\varepsilon^2)$ samples are sufficient and worst case necessary to learn $d$-dimensional Gaussians up to TV distance $\varepsilon$ with constant probability. When we are additionally given a parameter $\tilde{\boldsymbol{\Sigma}}$ as advice, we show that $\tilde{O}(d^{2-\beta}/\varepsilon^2)$ samples suffices whenever $\| \tilde{\boldsymbol{\Sigma}}^{-1/2} \boldsymbol{\Sigma} \tilde{\boldsymbol{\Sigma}}^{-1/2} - \boldsymbol{I_d} \|_1 \leq \varepsilon d^{1-\beta}$ (where $\|\cdot\|_1$ denotes the entrywise $\ell_1$ norm) for any $\beta > 0$, yielding a polynomial improvement over the advice-free setting.
• Abstract（参考訳）: 学習強化アルゴリズムの枠組みにおける分布学習の問題を再考する。 本稿では,確率分布が真の未知分布に対する潜在的不正確なアドバイスとして提供されるシナリオを考察する。 本研究の目的は,アドバイスの質が向上するにつれて,サンプルの複雑さが減少する学習アルゴリズムを開発することである。 具体的には、この結果は多変量ガウス分布を学習する問題に対して、PAC学習条件において$N(\boldsymbol{\mu}, \boldsymbol{\Sigma})$で達成可能であることを示す。 古典的には、アドバイスのない環境では、$\tilde{\Theta}(d^2/\varepsilon^2)$サンプルは、一定の確率でテレビ距離まで$d$次元ガウスアンを学ぶのに必要な十分かつ最悪のケースである。 パラメータ $\tilde{\boldsymbol{\Sigma}}$ をアドバイスとして与えられると、$\tilde{O}(d^{2-\beta}/\varepsilon^2)$ サンプルサッフィス if $\| \tilde{\boldsymbol{\Sigma}}^{-1/2} \boldsymbol{\Sigma} \tilde{\boldsymbol{\Sigma}}^{-1/2} - \boldsymbol{I_d} \|_1 \leq \varepsilon d^{1-\beta}$ (ここで $\|\cdot\|_1$ は、任意の$\beta > 0 に対するエントリワイド $\ell_1$ のノルムを表す) が、多項式よりも改善される。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
  論文  参考訳（メタデータ） (2024-10-02T15:21:07Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions [8.40077201352607]
  我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。 我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
  論文  参考訳（メタデータ） (2023-01-28T16:57:46Z)
• Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians [3.5788754401889014]
  強い$varepsilon$-contaminationモデルでは、元のガウスサンプルのベクトルの$varepsilon$分を他のベクトルに置き換えたと仮定する。 我々は、少なくとも1-デルタの確率で満足するコフラ行列 $Sigma の推定器 $widehat Sigma を構築する。
  論文  参考訳（メタデータ） (2023-01-21T23:28:55Z)
• Memory-Sample Lower Bounds for Learning Parity with Noise [2.724141845301679]
  ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。 我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
  論文  参考訳（メタデータ） (2021-07-05T23:34:39Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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