Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a maximum likelihood estimation technique that gives a non-asymptotic recovery guarantee of the location parameter $\lambda$ of the underlying distribution of the generated samples. The density model $f$ is assumed to be translation invariant. It is known that MLE estimated parameters converge to their true value in a limit where a number of samples n tends to infinity. MLE also achieves the Cramer-Rao lower bound of the variance which is $1/nI$ where I is the Fisher information of $f$ in the limit. With access to a finite number of samples, this paper claims to attain with a high probability the variance lower bound within (1+o(1)) factor. 

The work is quite relevant when the algorithm is not given access to an infinite number of samples, which can very well occur in real-world scenarios, where the system demands successful predictions with a high probability guarantee.

The key technique to attain the claim made by the authors is to simulate a Gaussian smooth version of the model by adding Gaussian noise $N(0,r^2)$ to each point and performing MLE corresponding to the r-smooth version of model $f$. The smoothing parameter r, which is the stdev of the added Gaussian noise, is calculated based on the targetted optimality margin. Doing MLE on the model is equivalent to finding the roots of the corresponding empirical score function $s(\hat{\lambda})$ as given by the standard definition of the score.

The paper has presented two examples of distributions where taking a finite number of samples and performing MLE leads to a high variance estimate.

1) In the first example, Gaussian with sawtooth noise, it is not clearly explained how taking $n>>1/w^2$ samples ‘aligns’ the teeth and how the variance $\Omega(1)/(\Delta^2 n)$ is obtained. Also, how does taking smaller $n$ gives a lower variance $1/n$

2) It says in line no. 57 that because of the sawtooth gradient, Fisher information $I$ increases. Does it not mean that the variance, being inverse of $I$, decreases?

3) In the second example: Gaussian with Dirac $\delta$ spike, it is not clear why the case where we don't see a point from the spike due to $n<1/\epsilon$ is not better because in the absence of an outlier point MLE is privileged to recover $\mu$ better. How does seeing a point from the spike help in estimating location?

4) The effect of adding noise to better estimate location in the second example in lines no 76-78 is not elaborate and clear enough.

The authors have presented a high probability optimal recovery guarantee of their algorithm in Theorem 1.1 and 1.2. Algorithm 1 represents Local MLE where the uncertainty region of the location parameter is provided to the algorithm. Algorithm 2 represents two-stage global MLE where the first stage is to estimate the uncertainty region from the interquartile range(IQR) of the model $f$, and the second stage is to run algorithm 1 with the obtained range.

5) In theorem 1.1, taking $\gamma$ to be ‘sufficiently large’ goes against its use in the three inequalities in line no. 99.
strengths_and_weaknesses: Please see above.
questions: Please see above.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies a classical object in statistics, the maximum likelihood estimator (MLE), in estimating the location parameter in a location family. Although the inverse Fisher information completely characterizes the optimal estimation error asymptotically, this estimation error may not be achieved in finite samples. In this paper, the authors proposed to convolute the target distribution using another Gaussian, in order to make the distribution smoother and better behaved. The benefits of doing so are two-fold: 

1. The estimation error of MLE in the convoluted model approximately achieves the inverse Fisher information, even in finite samples. 

2. The above error is also near-optimal by a complementing (two-point) minimax lower bound, which holds in finite samples as well. 

Experimental results are also included to illustrate the performance of the proposed estimator. 
strengths_and_weaknesses: This paper provides an interesting finite-sample view of the MLE, i.e. when the family of underlying distribution is very smooth, the asymptotic performance of MLE also holds in finite samples. A key feature in the result is that the authors aim to get the optimal constant, instead of a rate-optimal analysis. This paper is technically solid, and the results are sound. 

Despite my appreciation on the technical front, I am not sure of the usefulness of both the theory and methodology: 

1. On the methodology side, I am not convinced by why people should choose the smoothed MLE over the classical one. There is no formal theorem showing the failure of the MLE in finite samples, and since the smoothed Fisher information is smaller than the original one, a practitioner is actually paying a price on the variance for the guarantee on the finite sample result. Also, the authors did not comment on the computational aspect of the smoothed MLE, as the likelihood of the convolution becomes more complicated. I am wondering if the purpose of this paper is really to advocate the usage of the smoothed MLE in practice. 

2. On the theory side, even if this should be purely treated as a theoretical paper, the authors should make more comparisons of their results and treatments with the statistical literature. The finite sample analysis of the MLE is not new; there is a well-known result using the empirical process theory which could upper bound the finite-sample performance of the MLE in terms of the Dudley integral of the Hellinger metric entropy. A nice reference is the following book: 

Sara A van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.

This line of research seems to be overlooked in this paper. Although the above only provides rate analysis, it would be great to see the connections. For example, when the location family formed by Gaussian convolution, would the empirical process theory lead to similar finite sample results in terms of the Fisher information? 

Other comments: 

If the authors are mainly investigating theories of MLE, I would actually suggest the authors to tell the story in another way, i.e. establish a nice finite-sample result for the MLE when the distribution is smooth (i.e. a Gaussian convolution), rather than advocating an artificial convolution of another Gaussian distribution. I think this is still a nice storyline of the theory while avoids controversies on the practical front. 

Lemma 3.1 is a direct consequence of the following inequality on the Fisher information by Stam: for independent X and Y, 1/I(X+Y) >= 1/I(X) + 1/I(Y). 

Lemma C.2: conditions 5 and 6 cover conditions 3 and 4 by choosing k = 2. 

Post rebuttal: Thanks to the authors for the clarification and I am willing to increase my score to 7. 
questions: I am looking forward to the authors' responses to my above points. 
limitations: The authors have adequately discussed the limitations in the future direction section.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper explore the limits of the Maximum likelihood estimator (MLE) when the density is not smooth. Usually, the Fisher information gives the optimal deviations for the MLE, however there are a number of cases where the Fisher information is infinite or very large and it can't be used anymore to derive deviation bounds. In such cases, the authors propose to use the Fisher information of a smoothed version of $f$ instead. Using this, the authors give among other things a way to construct a robust location estimator for a given (non smooth) distribution.
strengths_and_weaknesses: Strengths: the paper is clear, the proofs are clear. Some of the results and proof techniques are of independent interest. The guarentees are given with high probability for results that usually hold only asymptotically.

Weaknesses: the paper is poorly motivated, there are some mention of examples in which the technique could be useful but these examples are not developed enough to compare to the state of the art.
questions: - My main concern is the choice of the optimal value of $r^*$ to apply the results when one only wants to estimate the location parameter. In Theorem 5.1, a loose lower bound is given for $r^*$ even though $I_{r^*}$ can change a lot with $r^*$. A wrong choice of $r^*$ would entail an unneeded multiplicative error that renders the $(1+o(1))$ guarantees useless. This comment also applies to Theorem 1.3. Could the authors comment on that ?

- Is it possible to quantify what we loose by considering $I_{r}$ instead of $I$ ? For instance, if the data come from a distribution that is smooth, is the value of $I_r$ very different from $I$ ? 

- The authors talk about the robust context, how the article could be used in the case of Gaussian with a Dirac spike. Would it be possible to state an estimator and theoretical guarantees that suppose only knowledge of some inlier distribution and allow for an unknown outlier distribution that render the problem non-smooth ? To compare to state of the art results in robust theory. 

- In the experimental results of Section 7, the authors use a simplified version of the Algorithm proved in practice. Would the algorithm originally proposed work in practice ? How does the efficiency compare between the algorithm used in Section 7 and Algorithm 1 ?

- Could the authors include the median in the experiments ? The median is known to handle non-smoothness when estimating location parameters. It would be interesting to compare with the proposed estimators.

- Could the authors explain Lemma 3.2 ? This Lemma does not seem to be true when $r$ goes to $0$. Could the authors detail the coupling argument used here ?

limitations: Suggestion of improvements are included in the questions. In particular, the practical applications and  motivations should be developed a bit more.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies finite-sample location estimation: for a known distribution X with pdf f, given n samples from X+lambda, estimate lambda. In the large-sample limit n -> infty, it's known that maximum likelihood estimation is the best unbiased estimator with asymptotic variance 1/(n I), where I is the Fisher information of f. However, for a finite number of samples, there are pathological examples where the MLE variance is much larger than 1/(nI) until n hits some distribution-dependent threshold, and there are also examples where the MLE is suboptimal for small n.

This paper proposes smoothing each sample with independent additive Gaussian noise of some variance r^2, before applying MLE ("r-smoothed MLE"). The results are as follows:
1) r-smoothed MLE (with some additional algorithmic details) achieves, with probability 1-delta, deviations bounded by (1 + o(1))sqrt(2 log(1/delta) / (n I_r)), where I_r is the Fisher information of the smoothed distribution, where r = o(1) can be computed algorithmically
2) For sufficiently small delta and sufficiently large n, no algorithm given r-smoothed samples can perform location estimation with deviations bounded by (1-o(1))sqrt(2 log (1/delta) / (n I_r)) with probability 1-delta.
3) Experimentally, on a Laplace distribution with a Dirac delta spike, the smoothed MLE can outperform unsmoothed MLE and mean estimation algorithms when the number of samples n is small.

strengths_and_weaknesses: 
The paper studies an original problem (finite-sample location estimation) and is technically clear. As far as correctness, I did not go through all the proofs but the technical lemmas I checked seemed correct. However, the intended conceptual message is unclear to me. There are two issues at hand, which are both discussed in the introduction: (A) performing location estimation with near-optimal rates in the finite-sample regime; (B) predicting the performance of (any particular) algorithm (e.g. high-probability confidence intervals).

I think this paper makes an interesting theoretical contribution in Direction (B). Essentially, the theory in this paper shows that under a particular regularity condition (that the distribution can be obtained by convolving with a variance-r^2 Gaussian), the Fisher information governs the optimal estimation rates even with finite samples, and MLE obtains this optimal rate. If there is a way to estimate this smoothed Fisher information, then this seems to give a way to compute finite-sample confidence intervals. However, the theoretical contribution in direction (A) is more limited: it only shows that if the true distribution is already r-smoothed, then MLE is near-optimal in finite samples. For arbitrary distributions, the lower bound is not applicable.

The experiments are also somewhat limited; all they show is that for some pathological distributions, smoothed MLE can outperform MLE (which is already fairly clear from the paper's introduction). It's not immediately obvious to me why we would even care about location estimation for distributions with Dirac delta spikes (without knowing a priori where the spikes are). Also, there are no experiments validating that the theory leads to accurate confidence intervals for smoothed MLE.

I would weakly accept this paper on the strength of the insights that smoothing can (A) sometimes enable better location estimation (albeit demonstrated in pathological cases), and (B) allow for finite-sample error bounds. However, the paper would be significantly strengthened by (1) a clearer conceptual message supported by the theory and experiments, (2) lower bounds showing that (perhaps) smoothed MLE is optimal when the number of samples is finite, (3) more practically motivated distributions on which smoothing can be useful in practice, or (4) practical evidence that the theory provides tight confidence intervals.
questions: 1) The lower bound is only against algorithms that receive the smoothed samples. Thus, it gives no evidence that "smoothed MLE" is optimal when we are given the original samples. Indeed, given the pathological examples with Dirac delta spikes, it seems that an optimal algorithm may require examining the pdf in a more fundamental way?
2) The examples where the asymptotic behavior breaks down for finite-samples seem rather contrived. Certainly Dirac delta spikes may arise in practice (e.g. special 0s, or truncation) but I'm not sure why we would need location estimation in these settings. Is there some motivation for location estimation of pathological distributions where (a) regularity conditions of prior work fail, or (b) smoothing could be helpful?
3) It's noted that prior work on finite-sample bounds for MLE impose restrictive regularity conditions and lose multiplicative factors. I can't argue with the latter, but for the former I'm curious: does the smoothed PDF f_r not satisfy whatever regularity conditions are needed by the prior work, or if not what is the obstacle?
4) Is there some more explicit regularity condition under which the theory of this paper for the smoothed distribution f_r holds more generally (i.e. more explicit than the condition "this distribution is the convolution of some distribution with N(0,r^2)")?
limitations: Yes
review_title: null

Meta-review: metareview: This paper considers the problem of parameter estimation using smoothed observations: indeed, after smoothing although the asymptotic variance may increase we also have finite sample guarantees for the MLE. Although it is not clear how useful this methodology would be for high-dimensional applications, I am impressed by this neat observation and the solid writing. 
confidence: Less certain
Decision: Accept