The sample mean is often used to aggregate different unbiased estimates of a parameter, producing a final estimate that is unbiased but possibly high-variance. This paper introduces the Bayesian median of means, an aggregation rule that roughly interpolates between the sample mean and median, resulting in estimates with much smaller variance at the expense of bias. While the procedure is non-parametric, its squared bias is asymptotically negligible relative to the variance, similar to maximum likelihood estimators. The Bayesian median of means is consistent, and concentration bounds for the estimator's bias and @math error are derived, as well as a fast non-randomized approximating algorithm. The performances of both the exact and the approximate procedures match that of the sample mean in low-variance settings, and exhibit much better results in high-variance scenarios. The empirical performances are examined in real and simulated data, and in applications such as importance sampling, cross-validation and bagging.
Unfortunately, however, there are practical challenges in using the median of means estimator. First, there is little guidance in how to pick the number of groups, which essentially amounts to the estimator's willingness to trade off bias for variance. Furthermore, in spite of its theoretical properties, the median of means underutilizes the data available by only using each datapoint once. This guarantees independence between blocks, but limits the number of means one can obtain in a given dataset. This requirement can be relaxed to a degree, but not completely (see @cite_21 ). The estimator considered here has no such restrictions, and can be viewed as a smoothed version of the median of means. Besides, the randomness introduced in sampling the blocks allow for probabilistic analyses and parameter choices conditional on the realized datapoints. A further benefit is that, unlike the median of means, its smoothed counterpart does not depend on the order of the datapoints while still being computationally tractable.
@cite_21
2435502378 2014689751 2494296723 2468801653
We revisit the classic problem of estimating the population mean of an unknown single-dimensional distribution from samples, taking a game-theoretic viewpoint. In our setting, samples are supplied by strategic agents, who wish to pull the estimate as close as possible to their own value. In this setting, the sample mean gives rise to manipulation opportunities, whereas the sample median does not. Our key question is whether the sample median is the best (in terms of mean squared error) truthful estimator of the population mean. We show that when the underlying distribution is symmetric, there are truthful estimators that dominate the median. Our main result is a characterization of worst-case optimal truthful estimators, which provably outperform the median, for possibly asymmetric distributions with bounded support. The method of stable random projections is popular in data stream computations, data mining, information retrieval, and machine learning, for efficiently computing the lα (0 We propose algorithms based on (1) the geometric mean estimator, for all 0 • The general sample complexity bound for α ≠ 1,2. For α = 1, [27] provided a nice argument based on the inverse of Cauchy density about the median, leading to a sample complexity bound, although they did not provide the constants and their proof restricted e to be "small enough." For general α ≠ 1, 2, however, the task becomes much more difficult. [27] provided the "conceptual promise" that the sample complexity bound similar to that for α = 1 should exist for general α, if a "non-uniform algorithm based on t-quantile" could be implemented. Such a conceptual algorithm was only for supporting the arguments in [27], not a real implementation. We consider this is one of the main problems left open in [27]. In this study, we propose a practical algorithm based on the geometric mean estimator and derive the sample complexity bound for all 0 • The practical and optimal algorithm for α = 0+ The l0 norm is an important case. Stable random projections can provide an approximation to the l0 norm using α → 0+. We provide an algorithm based on the harmonic mean estimator, which is simple and statistically optimal. Its tail bounds are sharper than the bounds derived based on the geometric mean. We also discover a (possibly surprising) fact: in boolean data, stable random projections using α = 0+ with the harmonic mean estimator will be about twice as accurate as (l2) normal random projections. Because high-dimensional boolean data are common, we expect this fact will be practically quite useful. • The precise theoretical analysis and practical implications We provide the precise constants in the tail bounds for both the geometric mean and harmonic mean estimators. We also provide the variances (either exact or asymptotic) for the proposed estimators. These results can assist practitioners to choose sample sizes accurately. In some statistical non-parametric models the mean of the random variable y has to satisfy specific constraints. We consider the case where the set defined by the constraints is a closed polyhedral cone K in Rk. For example, when the mean is required to be concave in x, the set of acceptable means is a closed convex cone defined by k-2 linear inequalities in Rk. The least squares estimate of the mean is then the projection of the data point y on the cone K. In this paper, we present an algorithm to find the least square estimate of the mean in a finite number of steps. Other algorithms to solve this problem have been given before. The successive approximations in such algorithms are usually points on the faces of K. The solution here is reached by following a fixed line joining an abitrary but suitably chosen initial point y0 to the data point y. The 1- dimensional subspace spanned by the generators of the cone K is divided into 2' regions which can be described as the set of points with non-negative coordinates in mixed primal-dual bases relative to the cone K. Any point y belongs to one and only one of these regions SJ with corresponding basis 3j. The projection of y on K is immediately obtained from the expression of y in Oj by dropping the dual component of y. The sample mean is one of the most fundamental concepts in statistics. Properties of the sample mean that are well-defined in Euclidean spaces become unclear in graph spaces. This paper proposes conditions under which the following properties are valid: existence, uniqueness, and consistency of means, the midpoint property, necessary conditions of optimality, and convergence results of mean algorithms. The theoretical results address common misconceptions about the graph mean in graph edit distance spaces, serve as a first step towards a statistical analysis of graph spaces, and result in a theoretically well-founded mean algorithm that outperformed six other mean algorithms with respect to solution quality on different graph datasets representing images and molecules. HighlightsA first step towards a theory of statistical graph space analysis is proposed.MMM-algorithm is proposed that outperformed six other mean algorithms.Necessary conditions of optimality are proved.Convergence of MMM-algorithm is shown.Basic statistical and geometrical properties are shown.