Learning Minimax Estimators via Online Learning
- URL: http://arxiv.org/abs/2006.11430v1
- Date: Fri, 19 Jun 2020 22:49:42 GMT
- Title: Learning Minimax Estimators via Online Learning
- Authors: Kartik Gupta, Arun Sai Suggala, Adarsh Prasad, Praneeth Netrapalli,
Pradeep Ravikumar
- Abstract summary: We consider the problem of designing minimax estimators for estimating parameters of a probability distribution.
We construct an algorithm for finding a mixed-case Nash equilibrium.
- Score: 55.92459567732491
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of designing minimax estimators for estimating the
parameters of a probability distribution. Unlike classical approaches such as
the MLE and minimum distance estimators, we consider an algorithmic approach
for constructing such estimators. We view the problem of designing minimax
estimators as finding a mixed strategy Nash equilibrium of a zero-sum game. By
leveraging recent results in online learning with non-convex losses, we provide
a general algorithm for finding a mixed-strategy Nash equilibrium of general
non-convex non-concave zero-sum games. Our algorithm requires access to two
subroutines: (a) one which outputs a Bayes estimator corresponding to a given
prior probability distribution, and (b) one which computes the worst-case risk
of any given estimator. Given access to these two subroutines, we show that our
algorithm outputs both a minimax estimator and a least favorable prior. To
demonstrate the power of this approach, we use it to construct provably minimax
estimators for classical problems such as estimation in the finite Gaussian
sequence model, and linear regression.
Related papers
- Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds [3.9041951045689305]
Schmidt-Hieber ( 2020) proved the minimax optimality of deep neural networks with ReLu activation for least-square regression estimation.
We study a more general class of machine learning problems, which includes least-square and logistic regression.
We establish a similar lower bound for classification with the logistic loss, and prove that the proposed DNN estimator is optimal in the minimax sense.
arXiv Detail & Related papers (2024-10-29T03:37:02Z) - Smoothed Analysis of Sequential Probability Assignment [16.090378928208885]
We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle.
Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning.
arXiv Detail & Related papers (2023-03-08T19:25:57Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space.
We establish non-asymptotic bounds for both the operator defect and the estimation error.
arXiv Detail & Related papers (2022-01-21T02:46:57Z) - Learning to Estimate Without Bias [57.82628598276623]
Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models.
In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints.
A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
arXiv Detail & Related papers (2021-10-24T10:23:51Z) - Near-optimal inference in adaptive linear regression [60.08422051718195]
Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner.
We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation.
We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
arXiv Detail & Related papers (2021-07-05T21:05:11Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation.
Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle.
We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
arXiv Detail & Related papers (2020-11-05T08:04:34Z) - Distributionally Robust Parametric Maximum Likelihood Estimation [13.09499764232737]
We propose a distributionally robust maximum likelihood estimator that minimizes the worst-case expected log-loss uniformly over a parametric nominal distribution.
Our novel robust estimator also enjoys statistical consistency and delivers promising empirical results in both regression and classification tasks.
arXiv Detail & Related papers (2020-10-11T19:05:49Z) - Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares
using Random Projections [37.27708297562079]
We derive an improved estimator for the least squares solution using the Gaussian sketch.
Empirically, this estimator achieves smaller error on simulated and real datasets.
arXiv Detail & Related papers (2020-06-15T06:42:18Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator)
We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$.
We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
arXiv Detail & Related papers (2020-05-26T17:53:18Z)
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.