Chebyshev polynomials, moment matching, and optimal estimation of the unseen
切比雪夫多项式、矩匹配与未观测类别的最优估计AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：研究对象是离散分布支持集大小及通用样本复杂度，不能仅因分布估计而归入分布效应。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
切比雪夫多项式、矩匹配与未观测类别的最优估计
- 研究问题
- 当离散分布的最小非零概率至少为一个已知下界时，估计包含未观测类别在内的支持集大小需要多少独立样本？
- 方法与思路
- 作者借助切比雪夫多项式及其逼近性质构造线性估计量，并研究样本复杂度与极小极大风险的界及计算开销。
- 材料陈述的贡献
- 摘要称给出了常数因子意义下的最优样本复杂度，改善既有结果对误差容忍度的依赖，并提出达到该界的快速估计量。
- 阅读关注点
- 应核对最小概率限制、误差容忍度的适用范围、矩匹配在下界中的作用，以及摘要所写成功概率至少为 0.1 的定义。
- 阅读边界
- 仅据版本未注明的 OpenAlex 摘要；未提供完整范围条件和实验细节，最优性及性能比较只能在所述采样模型与限制下理解。
原文摘要
We consider the problem of estimating the support size of a discrete distribution whose minimum nonzero mass is at least $\frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, that is, the minimal sample size to achieve an additive error of $\varepsilon k$ with probability at least 0.1 is within universal constant factors of $\frac{k}{\log k}\log^{2}\frac{1}{\varepsilon }$, which improves the state-of-the-art result of $\frac{k}{\varepsilon^{2}\log k}$ in [In Advances in Neural Information Processing Systems (2013) 2157–2165]. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in $O(n+\log^{2}k)$ time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets.