Extrapolating the profile of a finite population
- URL: http://arxiv.org/abs/2005.10561v1
- Date: Thu, 21 May 2020 10:39:41 GMT
- Title: Extrapolating the profile of a finite population
- Authors: Soham Jana, Yury Polyanskiy and Yihong Wu
- Abstract summary: We study a prototypical problem in empirical Bayes. Namely, consider a population consisting of $k$ individuals each belonging to one of $k$ types.
We show that in the sublinear regime of $m =omega(k/log k)$, it is possible to consistently estimate in total variation the emphprofile of the population.
- Score: 35.69057741775438
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a prototypical problem in empirical Bayes. Namely, consider a
population consisting of $k$ individuals each belonging to one of $k$ types
(some types can be empty). Without any structural restrictions, it is
impossible to learn the composition of the full population having observed only
a small (random) subsample of size $m = o(k)$. Nevertheless, we show that in
the sublinear regime of $m =\omega(k/\log k)$, it is possible to consistently
estimate in total variation the \emph{profile} of the population, defined as
the empirical distribution of the sizes of each type, which determines many
symmetric properties of the population. We also prove that in the linear regime
of $m=c k$ for any constant $c$ the optimal rate is $\Theta(1/\log k)$. Our
estimator is based on Wolfowitz's minimum distance method, which entails
solving a linear program (LP) of size $k$. We show that there is a single
infinite-dimensional LP whose value simultaneously characterizes the risk of
the minimum distance estimator and certifies its minimax optimality. The sharp
convergence rate is obtained by evaluating this LP using complex-analytic
techniques.
Related papers
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
We show that for a broad class of data structures their bounds cannot be significantly improved.
This is a novel emphstatistical-computational trade-off for density estimation.
arXiv Detail & Related papers (2024-10-30T15:03:33Z) - Precise Asymptotics of Bagging Regularized M-estimators [5.165142221427928]
We characterize the squared prediction risk of ensemble estimators obtained through subagging (subsample bootstrap aggregating) regularized M-estimators.
Key to our analysis is a new result on the joint behavior of correlations between the estimator and residual errors on overlapping subsamples.
Joint optimization of subsample size, ensemble size, and regularization can significantly outperform regularizer optimization alone on the full data.
arXiv Detail & Related papers (2024-09-23T17:48:28Z) - Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity [8.28720658988688]
We identify a class of ReLU multilayer perceptions (MLPs) that are optimal function approximators and are statistically well-behaved.
We achieve this by avoiding the standard approach to constructing optimal ReLU approximators, which sacrifices by relying on small spikes.
arXiv Detail & Related papers (2024-09-18T22:05:07Z) - Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
We study person-level differentially private mean estimation in the case where each person holds multiple samples.
We give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP.
arXiv Detail & Related papers (2024-05-30T18:20:35Z) - On Computationally Efficient Learning of Exponential Family
Distributions [33.229944519289795]
We focus on the setting where the support as well as the natural parameters are appropriately bounded.
Our method achives the order-optimal sample complexity of $O(sf log(k)/alpha2)$ when tailored for node-wise-sparse random fields.
arXiv Detail & Related papers (2023-09-12T17:25:32Z) - Robust Sparse Mean Estimation via Incremental Learning [15.536082641659423]
In this paper, we study the problem of robust mean estimation, where the goal is to estimate a $k$-sparse mean from a collection of partially corrupted samples.
We present a simple mean estimator that overcomes both challenges under moderate conditions.
Our method does not need any prior knowledge of the sparsity level $k$.
arXiv Detail & Related papers (2023-05-24T16:02:28Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP)
We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
arXiv Detail & Related papers (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model.
The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
We consider the problem of learning the best-fitting single neuron as measured by the expected square loss.
For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
arXiv Detail & Related papers (2020-05-29T07:20:35Z) - Locally Private Hypothesis Selection [96.06118559817057]
We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution.
We show that the constraint of local differential privacy incurs an exponential increase in cost.
Our algorithms result in exponential improvements on the round complexity of previous methods.
arXiv Detail & Related papers (2020-02-21T18:30:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.