Sharp regret bounds for empirical Bayes and compound decision problems

• URL: http://arxiv.org/abs/2109.03943v2
• Date: Fri, 10 Sep 2021 15:25:37 GMT
• Title: Sharp regret bounds for empirical Bayes and compound decision problems
• Authors: Yury Polyanskiy and Yihong Wu
• Abstract summary: In a Bayes setting the optimal estimator is given by the prior-dependent conditional mean. We show that for the Poisson model with compactly supported and subexponential priors, the optimal regret scales as $Theta(fraclog nloglog n)2)$ and $Theta(log3 n)$.
• Score: 42.397889421982555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the classical problems of estimating the mean of an $n$-dimensional normally (with identity covariance matrix) or Poisson distributed vector under the squared loss. In a Bayesian setting the optimal estimator is given by the prior-dependent conditional mean. In a frequentist setting various shrinkage methods were developed over the last century. The framework of empirical Bayes, put forth by Robbins (1956), combines Bayesian and frequentist mindsets by postulating that the parameters are independent but with an unknown prior and aims to use a fully data-driven estimator to compete with the Bayesian oracle that knows the true prior. The central figure of merit is the regret, namely, the total excess risk over the Bayes risk in the worst case (over the priors). Although this paradigm was introduced more than 60 years ago, little is known about the asymptotic scaling of the optimal regret in the nonparametric setting. We show that for the Poisson model with compactly supported and subexponential priors, the optimal regret scales as $\Theta((\frac{\log n}{\log\log n})^2)$ and $\Theta(\log^3 n)$, respectively, both attained by the original estimator of Robbins. For the normal mean model, the regret is shown to be at least $\Omega((\frac{\log n}{\log\log n})^2)$ and $\Omega(\log^2 n)$ for compactly supported and subgaussian priors, respectively, the former of which resolves the conjecture of Singh (1979) on the impossibility of achieving bounded regret; before this work, the best regret lower bound was $\Omega(1)$. In addition to the empirical Bayes setting, these results are shown to hold in the compound setting where the parameters are deterministic. As a side application, the construction in this paper also leads to improved or new lower bounds for density estimation of Gaussian and Poisson mixtures.

Related papers

• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate. We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Better and Simpler Lower Bounds for Differentially Private Statistical Estimation [7.693388437377614]
  We prove that for any $alpha le O(1)$, estimating the covariance of a Gaussian up to spectral error $alpha$ requires $tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$ samples. Next, we prove that estimating the mean of a heavy-tailed distribution with bounded $k$th moments requires $tildeOmegaleft(fracdalphak/(k-1) varepsilon +
  arXiv  Detail & Related papers  (2023-10-10T04:02:43Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework [22.846260353176614]
  We propose an Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that can efficiently accommodate bandit problems. We show that EBUCB can achieve the optimal regret order $O(log T)$ if the inference error measured by two different $alpha$-divergences is less than a constant. Our study provides the first theoretical regret bound that is better than $o(T)$ in the setting of constant approximate inference error.
  arXiv  Detail & Related papers  (2022-01-31T01:36:15Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
  We develop machinery to design efficiently computable and consistent estimators. For sparse regression, we achieve consistency for optimal sample size $ngsim (klog d)/alpha2$. In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix.
  arXiv  Detail & Related papers  (2021-11-04T15:59:44Z)
• Super fast rates in structured prediction [88.99819200562784]
  We show how we can leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in $n-1/4$ to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem.
  arXiv  Detail & Related papers  (2021-02-01T10:50:04Z)
• Regret-Optimal Filtering [57.51328978669528]
  We consider the problem of filtering in linear state-space models through the lens of regret optimization. We formulate a novel criterion for filter design based on the concept of regret between the estimation error energy of a clairvoyant estimator. We show that the regret-optimal estimator can be easily implemented by solving three Riccati equations and a single Lyapunov equation.
  arXiv  Detail & Related papers  (2021-01-25T19:06:52Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  We present a novel estimator with sub-Gaussian convergence. Our estimator does not require prior knowledge of the variance. Our estimator construction and analysis gives a framework generalizable to other problems.
  arXiv  Detail & Related papers  (2020-11-17T02:47:24Z)
• Computationally and Statistically Efficient Truncated Regression [36.3677715543994]
  We provide a computationally and statistically efficient estimator for the classical problem of truncated linear regression. Our estimator uses Projected Descent Gradient (PSGD) without replacement on the negative log-likelihood of the truncated sample. As a corollary, we show that SGD learns the parameters of single-layer neural networks with noisy activation functions.
  arXiv  Detail & Related papers  (2020-10-22T19:31:30Z)

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.