論文の概要: Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
- arxiv url: http://arxiv.org/abs/2602.16142v1
- Date: Wed, 18 Feb 2026 02:25:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-19 15:58:30.492228
- Title: Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
- Title（参考訳）: 凸集合の比被覆と最適混合密度推定
- Authors: Spencer Compton, Gábor Lugosi, Jaouad Mourtada, Jian Qian, Nikita Zhivotovskiy,
- Abstract要約: Kullback-Leibler分散系の密度推定について検討する。
我々は,辞書サイズ,サンプルサイズ,信頼度の観点から,可能な限りの高確率保証を同定する。
- 参考スコア（独自算出の注目度）: 16.547739992791197
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density $p$, the goal is to construct an estimator $\widehat p$ such that $\mathrm{KL}(p,\widehat p)$ is small with high probability. We consider two settings involving a finite dictionary of $M$ densities: (i) model aggregation, where $p$ belongs to the dictionary, and (ii) convex aggregation (mixture density estimation), where $p$ is a mixture of densities from the dictionary. Crucially, we make no assumption on the base densities: their ratios may be unbounded and their supports may differ. For both problems, we identify the best possible high-probability guarantees in terms of the dictionary size, sample size, and confidence level. These optimal rates are higher than those achievable when density ratios are bounded by absolute constants; for mixture density estimation, they match existing lower bounds in the special case of discrete distributions. Our analysis of the mixture case hinges on two new covering results. First, we provide a sharp, distribution-free upper bound on the local Hellinger entropy of the class of mixtures of $M$ distributions. Second, we prove an optimal ratio covering theorem for convex sets: for every convex compact set $K\subset \mathbb{R}_+^d$, there exists a subset $A\subset K$ with at most $2^{8d}$ elements such that each element of $K$ is coordinate-wise dominated by an element of $A$ up to a universal constant factor. This geometric result is of independent interest; notably, it yields new cardinality estimates for $\varepsilon$-approximate Pareto sets in multi-objective optimization when the attainable set of objective vectors is convex.
- Abstract（参考訳）: 未知の密度$p$からi.d.サンプルが与えられた場合、目的は、$\mathrm{KL}(p,\widehat p)$が高い確率で小さいような推定器$\widehat p$を構築することである。
M$密度の有限辞書を含む2つの設定を考える。
(i)モデルアグリゲーション、$p$は辞書に属し、
(ii)凸集合(混合密度推定)では、$p$は辞書からの密度の混合である。
重要なことに、我々は基本密度について仮定しない:それらの比率は非有界であり、その支持は異なるかもしれない。
両問題に対して,辞書サイズ,サンプルサイズ,信頼度の観点から,可能な限りの高確率保証を実現する。
これらの最適速度は、密度比が絶対定数で有界であるときに達成可能なものよりも高く、混合密度推定では、離散分布の特別な場合において既存の下界と一致する。
混合ケースヒンジの解析は2つの新しい被覆結果に基づく。
まず、M$分布の混合のクラスの局所ヘルリンガーエントロピーに対して、鋭く分布自由な上界を与える。
第二に、凸集合に対する最適比の定理を証明している: すべての凸コンパクト集合 $K\subset \mathbb{R}_+^d$ に対して、最低でも 2^{8d}$ の要素を持つ部分集合 $A\subset K$ が存在して、K$ の各元は座標的に、普遍定数係数まで$A$ の要素に支配される。
この幾何学的な結果は独立した関心事であり、特に、達成可能な対象ベクトルの集合が凸であるとき、多目的最適化において$\varepsilon$-approximate Pareto集合に対する新しい濃度推定値が得られる。
関連論文リスト
- SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
すべての$d inmathbb N$に対して、すべての中心部分ガウス分布 $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, $d-optimal inmathbb N$, $d-optimal inmathbb N$ が成り立つような普遍定数 $C>0$ が存在することを証明している。
これは、すべてのサブガウス分布がemphS-certifiably subgaussianであることを示す。
論文 参考訳（メタデータ） (2024-10-28T16:36:58Z) - Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。
グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - Clustering Mixtures of Bounded Covariance Distributions Under Optimal
Separation [44.25945344950543]
境界共分散分布の混合に対するクラスタリング問題について検討する。
このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。
我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
論文 参考訳（メタデータ） (2023-12-19T01:01:53Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Consistent Density Estimation Under Discrete Mixture Models [20.935152220339056]
この研究は、離散混合モデルの設定において混合確率密度$f$を推定する問題を考える。
特に、すべての密度 $f$ $lim_nto infty mathbbE left[ int |f_n -f | right]=0$ の推定子 $f_n$ が存在することが示されている。
論文 参考訳（メタデータ） (2021-05-03T18:30:02Z) - Analysis of KNN Density Estimation [56.29748742084386]
kNN密度推定は、サポートセットが知られている場合、$ell_infty$と$ell_infty$の条件の両方で最小限最適である。
$ell_infty$エラーはミニマックス下限に到達しないが、カーネル密度推定よりは優れている。
論文 参考訳（メタデータ） (2020-09-30T03:33:17Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Optimal estimation of high-dimensional location Gaussian mixtures [6.947889260024788]
ワッサーシュタイン距離における混合分布を推定する最小値の値は$Theta((d/n)1/4 + n-1/(4k-2))$である。
また,混合密度はヘリンジャー距離の最適パラメトリックレート$Theta(sqrtd/n)$で推定可能であることを示す。
論文 参考訳（メタデータ） (2020-02-14T00:11:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。