Search for: All records

Abstract Estimating the mean of a probability distribution using i.i.d. samples is a classical problem in statistics, wherein finite-sample optimal estimators are sought under various distributional assumptions. In this paper, we consider the problem of mean estimation when independent samples are drawn from $$d$$-dimensional non-identical distributions possessing a common mean. When the distributions are radially symmetric and unimodal, we propose a novel estimator, which is a hybrid of the modal interval, shorth and median estimators and whose performance adapts to the level of heterogeneity in the data. We show that our estimator is near optimal when data are i.i.d. and when the fraction of ‘low-noise’ distributions is as small as $$\varOmega \left (\frac{d \log n}{n}\right )$$, where $$n$$ is the number of samples. We also derive minimax lower bounds on the expected error of any estimator that is agnostic to the scales of individual data points. Finally, we extend our theory to linear regression. In both the mean estimation and regression settings, we present computationally feasible versions of our estimators that run in time polynomial in the number of data points. 

We investigate a simple model for social learning with two agents: a teacher and a student. The teacher’s goal is to teach the student the state of the world Theta, however, the teacher herself is not certain about Theta and needs to simultaneously learn it and teach it to the student. We model the teacher’s and the student’s uncertainty via binary symmetric channels, and employ a simple heuristic decoder at the student’s end. We focus on two teaching strategies: a "low effort" strategy of simply forwarding information, and a "high effort" strategy of communicating the teacher’s current best estimate of Theta at each time instant. Using tools from large deviation theory, we calculate the exact learning rates for these strategies and demonstrate regimes where the low effort strategy outperforms the high effort strategy. Our primary technical contribution is a detailed analysis of the large deviation properties of the sign of a transient Markov random walk on the integers.