Finite-Sample Maximum Likelihood Estimation of Location
Authors: Shivam Gupta
Jasper C.H. Lee
Eric Price
Paul Valiant
Venue: NeurIPS 2022 Accept (2022)

Abstract: We consider 1-dimensional location estimation, where we estimate a parameter $\lambda$ from $n$ samples $\lambda + \eta_i$, with each $\eta_i$ drawn i.i.d. from a known distribution $f$. For fixed $f$ the maximum-likelihood estimate (MLE) is well-known to be optimal in the limit as $n \to \infty$: it is asymptotically normal with variance matching the Cramer-Rao lower bound of $\frac{1}{n\mathcal{I}}$, where $\mathcal{I}$ is the Fisher information of $f$. However, this bound does not hold for finite $n$, or when $f$ varies with $n$. We show for arbitrary $f$ and $n$ that one can recover a similar theory based on the Fisher information of a smoothed version of $f$, where the smoothing radius decays with $n$.

Finite-Sample Maximum Likelihood Estimation of Location
Shivam Gupta
Jasper C.H. Lee
The University of Texas at Austin shivanguttauutexss.. edu
University of Wisconsin-Madison jasper leeewiee. edu
Eric Price
Paul Valiant Purdue University pvaliant@gmail.co com
The University of Texas at Austin ecpriceccs utw.us.eecccm edu
Abstract
We consider 1-dimensional location estimation, where we estimate a parameter À from n samples À + Tk. with each 77, drawn i.i.d. from known distribution f. For fixed the maximum likellhood estimate (MLE) is well- to be optimal in the limit as n + oc: it is asymptotically normal with variance matching the Cramér-Rao lower bound of 77. where I is the Fisher information of However, this bound does not hold for finite n. or when f varies with n. We show for arbitrary f and n that one recover similar theory based on the Fisher information of smoothed version of f. where the smoothing radius decays with n.
Introduction
We revisit fundamental problem in statistics: consider translation- iinettiionnnnviannttt parametric model {f²) JOER of distributions, where (z) = f(x - 0). Suppose there is an arbitrarily chosen unknown true parameter X, and we get i..d. samples from f^. The task is to accurately estimate from the samples. This problem is known location parameter estimation in the statistics literature.
Location estimation a well-studied and general model, including as a special case the important setting of Gaussian mean estimation. In contrast to general mean estimation (where we want to estimate the mean of distribution given minimal assumptions such as moment conditions), in location estimation we are given the shape of the distribution up to shift. This advantage lets us handle some distributions where mean estimation impossible (e.g., the mean may not exist), and lets us aim for higher accuracy than is possible without knowing the distribution.
The classic theory of location estimation is asymptotic, see [vdV00] for detailed background. On the algorithmic side, it is well-known that the maximum likelihood estimator (MLE) is asymptotically normal. Specifically, as the number of samples n tends infinity, the distribution of the MLE converges to a Gaussian centered at the true parameter with variance 1/ 1/(nZ), where I is the Fisher information of the distribution f:
I = / (f(())) f(x)
log log )
dz dr=
E z-f Oz
Conversely, the celebrated Cramér-Ras Rao bound states that the variance of any unbiased estimator must be at least 1/(nZ), meaning that the MLE has mean-squared error that is asymptotically at least as good as any unbiased estimator.
In the last few decades, motivated by an increasing dependence on data high-stakes applications, the statistics and computer science communities have shifted focus towards santee and high
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

probability theories: 1) asymptotic theories assume access to an infinite amount of data, and can in certain cases fail to predict the performance of an algorithm with only a finite number of samples-see the next section for bad examples for the MILE 2) in high-stakes applications where failure can be catastrophic, is crucial for predictions to hold except with exponentially small probability. Yet, classic results bounding the variance or mean-squared error of estimators, such as the Cramér-Rao bound, do not readily translate to (tight) high probability bounds.
The goal of this paper is to establish finite-sample and high probability theory for the location estima- tion problem, in both the algorithmic bound and the estimation lower bound. Our algorithmic theory includes a simple yet crucial modification of perturbing samples by Gaussian noise-correspone corresponding to drawing samples from Gaussian saoothhed version of the underlying distribution beaute per- forming MLE. We show that this smoothed MLE has finite-n high bogh-probability performance analogous to the Gaussian tail in the classic asymptotic theory, but replacing the usual Fisher information with a smoothed Fisher information. The amount of smoothing required decreases with n.
Complementing our upper bound result, we prove a high probability version of the Cramér-Rao bound for Gaussian-smoothed distributions, showing that for these instances our sub-Gaussian accuracy bound, with variance determined by the Fisher information, is optimal to within 1 + o[) factor.
1.1 Obstacles to a Finite Sample Theory
Before discussing our results in detail, we examine two simple distributions where the asymptotic theory predictions for the MLE do not hold in finite samples. The first example highlights an cnformationntthorrete barrier, that no algorithm can attain the performance predicted by the Gaussian with variance 1/I. The second example, on the other hand, demonstrates how the MLE can be "tricked" by the distribution, and how an algorithmic remedy is needed to improve its accuracy.
Gaussian with sawtooth noise Our first example takes a standard Gaussian, and adds fine- grained sawtooth perturbation to it over a bounded region at the center of the Gaussian, as shown in Figure la. The fine-grat -ra-grained sawtooth has slope either +A -A, alternating over "teeth" of width w. for A > and w < 1/A. This sawtooth perturbation barely changes the pdf. but significantly changes its derivatives, so the Fisher information J' / grows from 1 to (
Essentially, the sawtooth perturbation makes the distribution easier to align within tooth, but not across teeth. The asymptotic analysis reflects that: for >> 1/w² where we can align the teeth correctly, the MLE much more accurate on the perturbed distribution. But for n & 1/w2, no algorithm can do better on the perturbed distribution than on a regular Gaussian." Thus, the normalized estimation accuracy depends on n: for large enough n, it has variance e(1) but for smaller n has variance J. n. Our finite sample theory should reflect this.
A formal statement of the above reasoning is as follows, with a proof sketch in Appendix A. Proposition 1.1. The Gaussian+ sawtooth model, with "teeth" of width w and slope & has Fisher information 2 >> 1 but no location estimator can have error o(1 /n) with constant probability over n samples, unless n > 0.01 0.01/w².
This holds for arbitrarily large A and small w. By contrast, the asymptotic theory predicts error O(L/(A/n)) which only holds for n Z 1/w².
Gaussian with a Dirac å spike Our next example adds an even simpler noise to the standard Gaussian: Dirac ô spike with minimal mass E, placed sufficiently far away from the Gaussian mean 0 (Figure lb). This distribution has infinite Fisher information, reflecting that for >> 1/E, we will probably see the spike multiple times, identify and get zero estimation error. But for n < 1/e, we probably will not see the spike, so our error bound will not reflect the overall Fisher information.
Moreover, the MLE performs remarkably badly when sampled, yet the Dirac has infinite density, and so the MLE will match a Gaussian sample to the spike to get maximium likelihood solution. As the spike is placed far from the true mean, this leads to much higher error than (say) the empirical mean.
1/e. Most likely the Dirac 8 is not
The reasoning in the above two paragraphs can be formally summarized as follows.
This can be shown by the KL divergence from shifting integer number of teeth of distance about 1/Vn.

---

Exammpe
Dienaity
(a) Sawtooth example
(b) Dirac & example
Figure 1: Bad examples for MLE
Proposition 1.2. Consider the spiked Gaussian example (1 (1-T) + Tôr where dy is Dirac 5 at location x T. The Fisher information is infinite, but for < 1/(100r), every estimation algorithm has median error at least 0.6/ vn. Moreover, with 98% probubility the MLE has error at least T - O( /og n.), which can be arbitrarily large.
We also note that, while we present the hardness result in terms mixing a Gaussian with Dirac spike for conceptual simplicity, milder but similar effect occurs when the spike is narrow but not infinite.
Fortunately, there is simple modification to the MLE that solves this issue almost completely: we add a small amount of Gaussian noise to the distribution. This means we convolve the PDF with a small Gaussian, and add independent Gaussian noise each individual sample effectively draw from the convolved PDF The crucial effect of this Gaussian smoothing that the density of the Dirac 5 will be reduced from infinity down to some constant, and hence MLE will longer "fit it at any cost". On the other hand, the smoothing increases the variance of the distribution and decreases the Fisher information. This raises the question of determining the best amount of smoothing, which address in this paper.
1.2 Our Results and Approach
Based the discussion of the spiked Gaussian model in the previous section, propose finite sample theory for MLE that uses Gaussian smoothing. As we described, the algorithmic approach is simple: we perturb all the samples by independent Gaussian noise of variance y2, and convolve the known model f by the same Gaussian to yield the model fr. before performing MLE.
We state below the basic MLE algorithm (Algorithm 1) in this paper, which adopts the above approach. Algorithm is a local algorithm, in that assumes as input an initial uncertainty region guaranteed to contain the true parameter X, and performs MLE only attempts only to find local optimum in the likelihood: it computes the derivative of the log likelihood function, also known the score function, and returns any root of the score function.
this domain. Furthermore, Algorithm 1
Algorithm Local MLE for known parametric model
Input Parameters: Description of distribution smoothing parameter r, samples r 1.J.d. fA, uncertainty region [e, u] containing the unknown X
1. Let sy)() be the score function of fr. the r-smoothed version of f.
2. For each sample F,, compute a perturbed sample x = + (0, r?) where all the Gaussian noise are drawn independently across all the samples.
3. Compute À that is root of the empirical score function s(Å) the domain [f, uj. root should exist and picking any root is sufficient.
Σi= sr Å) inside
4. Return Å.
Theorem 1.3 states our guarantees on Algorithm 1. Locally around the true parameter- -tht is, within r/2 for the r-smoothed iistributioon-an root of the score function (i.e., local optimum of likelihood) must be very close to the true parameter À with high probability over the samples. In particular, the

---

estimation enror is within 1 + ((1) factor of the Gaussian deviation with variance 1 and failure probability 8, where I, is the Fisher information of fr.
nI,
Theorem 1.3 (Local Convergence). Suppose we have a known model Jr that is the result of r- smoothing, with Fisher information I,, and a given width parameter Emax and failure probability Further suppose that satisfies r 2 22 max and there is a parameter ", where is larger than some universal constant, such that 1) x2 VIr Z 76 2) (log f)/n t and 3) log L/(TVIrr)r S log 8 flog log 3-
Then, with probability least - 6, for all & E (1-)
log nZ, Smax 8(2 E) is strictly
negative and a(A +) is strictly positive.
In the scenario where we do have an initial uncertainty region for the true parameter A, we would use Theorem 1.3 to compute the minimal smoothing amount satisfying the assumptions in the theorem, then use Algorithm with this parameter r, to obtain an accurate estimate of X.
In general, however, we may not have initial uncertainty region for X. In Section 5, we present Algorithm 2, a global two-stage MLE algorithm, which first infers an initial uncertainty region by using quantile information from the distribution before invoking Algorithm 1, the local MLE algorithm. The guarantees Algorithm are summarized here.
Theorem 1.4 (Global MIE guarantees, informal version Theorem 5.1). Given model f. let the r-smoothed Fisher information of a distribution f be I,, and let IQR be the interquartile range of When >> log >> 1, there exists an r* o(IQR) such that, with probability at least 8, the output of Algorithm 2 satisfies
2 log 3 ndpp
J - AI (1+
In addition to the theoretical framework, Section 7 gives experimental evidence demonstrating that r-smoothed Fisher information does capture the empirical performance of (smoothed) MLE.
We also prove new estimation lower bounds for the location estimation problem for r-smoothed distributions. The lower bound statement below (Theorem 1.5) shows that the estimation error
(1 + o()) V /2log ! nT,,
optimal to within a + o(1) factor.
Theorem 1.5. Suppose fo is an r-smoothed distribution with Fisher information I, Givenfaalure probability and sample size n, no algorithm can distinguish Se and f? with probability
where & = (1-)(11) log / (nII). Here, the o(1) term tends to as 5 > and log /// -
for a fixed ITI
This lower bound is the standard "two- statement that, with samples, it is statistically impossible to distinguish between the distributions ff and f shifted by a small error (in the z-axis) with probability 1 8. Even though there are known standard inequalities distribution distances and divergences for proving lower bounds of this form, the technical challenge is that they generally yield estimation lower bounds that only tight to within constant factors, instead of the + o(1) tightness we desire. This paper presents new analysis to derive + o(1)-tight lower bound, which may be of independent interest.
1.3 Notations
We denote the shift-invariant model we consider by the distribution f. and the distribution with parameter by f*(x) f(x A). Denote by Z, the Gaussian with mean O and variance r², The r-smoothed model for is denoted by fr (and similarly, for parameter X, fA) which is distributed as Y Z, + X where X + independently from the Gaussian perturbation Z,..
The log-like -ogliikeldood function of f is denoted by 1 log f. The score function is the derivative of i, denoted by s = f'/s. We use the notation 8, to denote the score function of f,. The Fisher Infor- mation of f is denoted by 1 = Es-//s²² (xx)) Similarly, the Fisher Information of fr is denoted by I,..

---

2 Related Work
Location estimation and MLE in general has been extensively studied under the lens of asymp- totic statistics. See [vdV00] for an in-depth treatment. The MLE has also been studied under the finite-sample setting [Spo11, Pin17, VdGOO, Mial0], but these prior works impose restrictive regularity conditions and also loses (at least) multiplicative constants in the estimation accuracy.
Specifically, [Spo1]] l] assumes that the parametric family f satisfies D (f || ( 2 Q - 0'))) for every pair of parameters 0, 0', where is the Fisher information of the parametric family. This is a global distance property that does not always hold in our general setting. for example in the Gaussian with sawtooth example in Section I.I, where can be arbitrarily large yet the density is arbitrarily close to the standard Gaussian. Our work handles the lack of global distance property by instead proposing a two-stage final algorithm (Algorithm 2 in Section 5). [Pin 17] also assumes a global distance property, similar to [Spol1]. but in Hellinger distance instead of KL divergence. [VdG00] again assumes a somewhat similar global distance property, and further characterizes convergence of the recovered distribution in Hellinger distance to the true distribution, instead of directly bounding estimation error in the parameter space. [Mia10] on the other hand requires Lipschitzness in the score, whereas for Gaussian-smoother distributions we only have 1-sided L Lipschitzness (Lemma B.2). Moreover, the [Mial0] results quantify the error not in terms of the Fisher information (the variance of the score), but in terms of the maximum magnitude of the score.
In contrast to these prior works, our work modifies the MLE to include smoothing. Without smoothing. these prior works do not apply even in simple cases like a standard Laplace distribution: [Spol]] 1] because the KL divergence between shifted versions of the Laplace distribution is not locally quadratic in the shift- parameter space, and [Pin17] because of this reason and their further assumption that the score function is smooth, which is not true at the origin for the Laplace distribution. On the other hand, by introducing smoothing to the MIE, we can take arbitrary distribution and extract meaningful finite-sample guarantee, which is tight to within 1 + o(1) factors conditioned on such smoothing.
There has also been a flurry of recent interest in the related mean estimation problem, in the finite- sample and high-probability setting. Recall that mean estimation does not assume knowledge of the shape of the distribution, but instead imposes mild moment conditions, for example the finiteness of the variance. Catoni [Cat12] initiated line of work studying the statistical limits of univariate mean estimation to within a 1 + (1) factor, ending recently with the work of Lee and Valiant [LV22]. which proposed and analyzed estimator with accuracy optimal to within 1 + o(1) factor for all distri- butions with finite variance. See also the recent work of Minsker [Min22] for an alternative solution.
Beyond the differences in assumptions, the main distinction between location and mean estimation lies in their statistical limits. In mean estimation, the optimal accuracy is captured by the variance of the underlying distribution, scaling linearly with the standard deviation. On the other hand, the classic asymptotic theory suggests that the Fisher information captures the optimal accuracy for location estimation, scaling with the reciprocal of the square root of the Fisher information. It is a well-known fact that the Fisher information is always lower bounded by the reciprocal of the variance [SV11], which shows that location estimation is always easier than mean estimation in the infinite-sample regime. In this work, we refine this understanding, showing that in finite samples, the optimal accuracy for location estimation is instead given by the r-smoothed Fisher information in place of the unsmoothed Fisher information.
3 Tails and boundedness of r-smoothed score and Fisher information
Recall that given a distribution f, its r-smoothed version fr is distributed as Y X + Z, where X f and Z, ~ (N( and X, Z, are independent.
Both algorithmic and lower bound theories are centered around r-smoothed distributions. There- fore, we state here basic concentration and boundedness properties of r-smoothed score function and Fisher information, which we use in the rest of the paper. We prove all these lemmas in Appendix B.
First, we show that the r-smoothed Fisher information I, is upper bounded by 1/r² and can be lower bounded using the interquartile range of f.
Lemma 3.1. Let I, be the Fisher information of an r-smoothed distribution f.. Then, I, S 1/72.
5

---

Lemma 3.2. Let I, be the Fisher information for fr. the r-smoothed version of distribution f. Let IQR be the interquartile range of f. Then, I, 2 1/QQR + +r² Here, the hidden constant universal one independent of the distribution f and independent of
Next, we show that, fixing a point close to the true parameter X, the empirical score function evaluated at that point will concentrate around its expectation for smoothed distributions.
Corollary 3.3. Let f be an arbitrary distribution and let fr be the r-smoothed version of f. That is,
[a(x)) = Eay 1 (= Suppose we take i.i.d. samples yl, y1..... Un f7. and consider the empirical score function mapping a candidate parameter À (1 2), where 8y the score function of fr-
x)
2n 3 Consider the parametric family of distributions (2)x) = fr X).
Then, for any |els r/2,
|s(x - =)]l max((En [s](x E)], Ix)
log
15 log 2/2
(((A+)) - ze
+
8
n
nr
Finite Sample Analysis of r-smoothed Local MLE
In this section, analyze Algorithm 1, which is our version of local MLE with r-smoothing applied. Algorithm takes an initial uncertainty region that the true parameter is guaranteed to lie in, and uses the model and the initial interval to refine the estimate to high accuracy. We first present simpler and easier-to-intee ionterrettterrrret version of our result, Theorem 1.3, which we stated in Section 1.2.
Recall that Algorithm 1 computes the empirical score function, and returns any of its roots. The theorem thus states that, with high probability, for any point X e with |e] too large, the empirical score function must be non-zero and thus X + will not returned as the estimate. More precisely, given an initial interval of length max as well as the failure probability ò, the theorem assumes that the smoothing parameter is sufficiently large (conditions I and 3 in the theorem) and that the sample size n is sufficiently large, and guarantees an estimation error that within a + o(1) factor of the error predicted by the Gaussian with variance 1/Ir, where I, is the Fisher information of fr.
Theorem 1.3 (Local Convergence). Suppose we have a known model fr that is the result of r- smoothing, with Fisher information I,, and given width parameter Emax and failure probability Further suppose that satisfies r 2 2m and there is a parameter ", where y is larger than some universal constant, such that 1) r2 VI, 7Emaxx 2) (log f)/n t and 3) log (/(rVI,)) /log log 3-
log boog/
Then, with probubility at least - 6, for all e (1=
2 log ni,
max 8(2 - E) is strictly
negative and s(A + is strictly positive.
Theorem 1.3 follows from Theorem 4.1 below, which makes the "o(1)" term (the 0(1/7) term) in the theorem explicit. Assumptions 2 and 3 in the theorem statement essentially bounds various multiplicative terms in the estimation eиror and makes sure that they "1 + o(1)" terms. In Appendix C, we give the formal proof of Theorem 1.3 using Theorem 4.1.
Theorem 4.1. Suppose we have known model fo that is the result of r-smoothing, and given parameter Euax Let B and be the hidden multiplicative constants in Lemmas C.2 and C.3. Further suppose that satisfies mm and 2 II, 2 "Emaax for some parameter 7 3.
Now define the notation P. by
4 4log
2 2
WE +
15
-TI, 23
1 Pr
2
n

---

Then, for sufficiently small 8
0, with probability at least 1 6, for all E
log 4logg $ 12,,111 7)
(1+ log
log niz Emax
8(A - 8) < and 8(A + e>> >0
log
To prove Theorem 4.1, suffices to show the following lemma. The theorem follows directly by reparameterizing 6 and choosing & to be 1/log 8.
Lemma 4.2. Suppose we have a known model fr that is the result of r-smoothing with Fisher information I,, and a given parameter maax- Let B and nj be the hidden multiplicative constants in Lemmas C.2 and C.3. Further suppose that r satisfies r 2 max and y² V'r, 2 "/E for some
parameter 2 B. Also define the notation P (a "o(1)" term) by
1+ 1+ AVEE
15
2 2log 1
+
2/7
n2
(P for all e E Then, for every & < 1, with probability at least -
(1 1+0 1-2 V
2 log 1 ni, Emax| ) 8(2 e) is strictly negative and 8(A + 8) strictly positive.
We prove Lemma 4.2 in Appendix C, and here we give a proof sketch.
Proof sketch for Lemma 4.2. First, recall that Corollary 3.3 from Section 3 shows that fixing candidate input value À + e for some small E, the value of the empirical score function at À + is well-concentrated around its expectation. In Lemmas C.2 and C.3, we calculate and bound the expectation and second moment of the empirical score function at X + & for all sufficiently small e. This allows to derive tail bounds for the empirical score function at each point À + E, to show that is bounded away from O. Next, we need to show that with high probability, the empirical score function is simultaneously bounded away from for all with magnitude greater than the desired estimation accuracy. We achieve this via straightforward net argument, crucially utilizing the fact that the expectation of the empirical score function is bounded away from 0 by essentially linear function e, and that the variance is essentially constant e. This means that the probability for to hit is decreasing exponentially in which allows to
the empirical score function complete the net argument.
Global Two-Stage MLE Algorithm
Algorithm 1, which we stated in the introduction and analyzed in Section 4, is local algorithm that assumes we have knowledge of a non-triee non-trivially small uncertainty region containing the true parameter A. The smoothing parameter can then be computed from the assumptions of Theorems 4.1 or 1.3, and we run Algorithm to obtain an accurate estimate of the true parameter X, with accuracy predicted by the r-smoothed Fisher information I,..
However, in general, we might not have a-priori knowledge of where the true parameter lies. In this section, we propose global maximum likelihood algorithm (Algorithm 2) which first estimates a preliminary interval containing X, before choosing the smoothing parameter r" using an easily calculable expression that is o(1) times smaller than the interquartile range of the distribution, and finally applies the local MILE algorithm (Algorithm 1) to obtain final estimate, Theorem 5. states that the accuracy of Algorithm 2 is always within 1 + o(1) times the accuracy predicted by the r" -mmotthedd Fisher information I,...
Theorem 5.1 (Global MLE Theorem). Given model f. let the r-smoothed Fisher information of distribution f be I,, and let TQR be the interquartile range of J. Fix the failure probability be 8.
Choose p" = Q(max(( log 1/8,,8 200 Olv/o0 F))RQ Then, with probability at least 1 - 8. the output À of Algorithm 2 satisfies
log 1
$
1
2 log 1 nII.-
i A/5 1+0
+0
5
Voog
7

---

Algorithm 2 Global MLE for known parametric model
Input Parameters: Failure probability 8, description of distribution f. i.i.d. samples drawn from I for some unknown
1. Compute an a E ly 222lo 4 3/n, 2 //m] such that the interval defined by the 22 //n and a + /2log //n quantiles of f is the smallest.
2. By standard Cherooff bounds, with probability at least 1 z. the sample a-quantile 4a
will be such that &a À is within the a / log //n and a + 2 / quantiles of f. Based on this, compute an initial confidence interval [e, u] for
3. Let M(max(( (lo ) 2 (00((/ Oly f) IQQR.
4. Run Algorithm on the interval [e, u). using r' -moothing and failure probability 8/2. returning the final estimate Å.
The total failure probability of the steps is at most 6. Thus, in this proof condition on the success of Algorithm in all probabilistic steps.
Proof.
By the minimality condition in the definition of the length Emax of the interval [e, u] from Step 2 is at most (Voog /n)IQR.
Further, recall by Lemma 3.2 that I, 2 2(1/(TQR + r)2). Picking r"
((max(( Ing ) ///8,,28 200 +) IIR and 71 O log 1/4 and 72 Olv log }), we check
that the following conditions are satisfied:
log 1. (r") (T*) + +r") Q
1 7mx
n
2. log \ 0
Olylog log /n) 1/7/.
3. log1/((r V/-)"VII- & O(log (/1// 2)) = 0 0 log t).
Further note that log log }/ /log S 11// log oogg 0(1 (2)/
Thus, using Theorem 1.3, Step returns an estimate satisfying
A - Aaا ( 1+ O
- +
) 122
2 2 1
nII,-
which is equivalent to the theorem statement.
6 High Probability Cramér-Rao Bound
Complementing our algorithmic results, we also give new results on lower bounding the estimation error in the location parameter model. The celebrated Cramér-Re bound lower bounds the variance of estimators, which does not readily translate to (tight) lower bounds estimation error. In this section, we show that is possible to derive high probability version of the Cramér-Rao lower bound for r-smoothed distributions, where, given failure probability we lower bound the estimation error to within 1 + o(1)-factor of the error predicted by the asymptotic normality of the standard maximum likelihood algorithm, namely the Gaussian with the true parameter as the mean, and variance 1/(nIz) for estimation using n samples.
the distribution tail of
Theorem 1.5. Suppose fo an r-soohhedd distribution with Fisher information I,. Given failure probability 8 and sample size algorithm can distinguish fo and f2s with probability 1 8.

---

where & = (1 o(1))) (1- log //2 (/I,)) Here, the o(1) term tends to 0 as 6 - 0 and log g/nn - 0. for a fixed I"
We prove Theorem 1.5 in Appendix D. The high-level technique we use is a standard one, showing that, it is statistically impossible to distinguish two slightly shifted copies of fr with probability 1 using n samples. The shift corresponds to (twice) the estimation accuracy lower bound. The difficulty lies in getting the right constant.
Standard inequalities for showing indistinguishabiliy results rely on calculating either the squared Hellinger distance [BY0 or the KL--divergence [BH79] between the two distributions. While these inequalities are straightforward to apply, given the calculated bounds on these statistical distances/divergenness, the inequalities only yield constant-factor tightness in the estimation accuracy lower bound. On the other hand, in this work, we aim to give accuracy upper and lower bounds that are matching strongly, to within 1 1+ (1) factors. As such, our proof of Theorem 1.5 involves delicate and non-standard bounding techniques which may be of independent interest. The proof techniques are currently slightly ad-hoc, and for future work, we hope to improve on these techniques to make them more general and more usable.
7 Experimental Results
In this section, we give experimental evidence supporting our proposed algorithmic theory. Our goals are to demonstrate that 1) r-smoothing is beneficial pre-processing to the MLE, that r-smoothed Fisher information does capture the algorithmic performance in location estimation and 2) r-smoothed MLE can outperform the standard MLE, as well as standard mean estimation algorithms which do not leverage information about the distribution shape.
The version of smoothed MLE we use for experimentation is even simpler than Algorithm 1: use Gaussian smoothing before performing actual maximum likelihood finding over the entire real line, instead of returning a root of the empirical score function. This is closest to what statisticians would do in practice, and further does not require any initial uncertainty region on the true parameter X.
We use the Gaussian-spiked Laplace model for experiments, with Laplace distribution of density proportional to e-1x1, and Gaussian of mass 0.001 and width roughly 0.002 (the discretization granularity) added at x = 4. The reason we choose the Laplace over the Gaussian as the "body" of the distribution is because, fixing the variance of the distribution, the Laplace has twice the Fisher information as the Gaussian. Given that standard mean estimation algorithms only aim to achieve sub-Gaussian concentration, choosing the Laplace as the core distribution lets demonstrate that the smoothed MLE can outperform mean estimation algorithms even in finite samples. We also note that this example is crucially different from the Dirac d-spiked example in Section 1. The Dirac d spike has infinity density, whereas the narrow Gaussian spike only has somewhat large, but finite density. Given the finite and not too large density in the spike, our experiments, the basic MLE algorithm will not "fit it at any cost", and instead has a smoother error distribution whenever we do not observe samples from the Gaussian spike. Nonetheless, even in this milder setting, we demonstrate that our smoothed MLE algorithm performs better than the original MLE.
Figure 2a is heat map of the mean squared error of the smoothed MLE. The æ-axii varies the number of samples n from 50 to 5000, and the y-axis varies the smoothing parameter r from 0.001 to I in log scale. Lighter color indicates smaller mean squared error. The line overlaid on the heat map indicates, for each value of n, the value of r with the smallest mean squared error. As n increases, the optimal value of r decreases, as predicted by our theory.
For small values of belbwww about 1000- the mean squared error first decreases then increases again as we increase the smoothing parameter r. This confirms the theory in the paper: for small n, it is unlikely that we see any samples from the spike, in which case too small values for r cause MLE to overfit. On the other hand, too large values of r simply add too much noise, and also yields sub-optimal mean squared error. The optimal value of r is thus somewhere in between.
The situation changes when > 1000, which is over the mass of the spike. In this case, we expect to typically see samples from the spike, which allows us to estimate the mean highly accurately. Any smoothing just adds noise, and hence the optimal value of is close to 0.

---

15
10
17
134
Estimation
Essimtionn
(a) Heat map of mean squared er- for
(h) Estimation error distribution,
Estimation error distribution,
= 500
n = 3000
Figure 2: Experimental results Spiked Laplace model
Figure 2b picks 500 and compares the distribution of estimation errors across different algorithms: unsmoothed MLE (blue). omot-smo MLE (orange), empirical mean (yellow), Lee- Valiant (LV) estimator (purple) using 8 = e -5 With only 500 samples, the unsmoothed MLE occasionally sees sample from the spike, and attains high accuracy, but otherwise has large variance in error, compared with the empirical and LV estimators (which have essentially identical performance, so yellow is overlapped by purple on the plot). With just 0.05-mmotthing. MLE outperforms all other estimators.
Figure 2c picks n 3000 and compares the same algorithms. The unsmoothed MLE sees samples from the spike most of the time, and attains high accuracy, vastly outperforming the empirical and LV estimators (again, yellow is overlapped by purple). The 0.05-smoothed MLE performs worse than the unsmoothed MLE in the typical case, but has better tail behavior. This plot suggests that the optimal smoothing parameter r in the high probability regime depends on the desired failure probability 8.
8 Future Directions
One natural goal is to extend these techniques to estimate the mean of unknown distributions by means of kernel density estimate (KDE), with accuracy dependent on the true distribution's 's Fisher information. In general this cannot work, a bias independent of the Fisher information is unavoidable. but for symmetric distributions the bias is zero and one can hope for good results. An asymptotic version of this was shown by Stone [Sto75], and we believe our techniques could get finite-sample guarantee here.
A second direction is to investigate ways to generalize and simplify our lower bound analysis techniques. Recall that, while standard "indistinguishability" bounds based squared Hellinger distance and KL-divergence are relatively straightforward to apply, they generally lose constant factors. Our analysis tight within 1 + o(l)-factor, but requires analyzing several different parameters of the distribution. One can hope to extend and generalize these techniques to yield new casy-to-apply bound, similar to those based on Hellinger distance and KL-divergence, that gives 1 + o(1) f-fcto tightness.
Acknowledgements
We thank the anonymous reviewers for insightful comments and suggestions on this work. Shivam Gupta and Eric Price are supported by NSF awards CCF-2008868, CCF-1751044 (CAREER), and the NSF AI Institute for Foundations of Machine Learning (IFML), Jasper C.H. Lee is supported in part by the generous funding Croucher Fellowship for Postdoctoral Research, NSF award DMS-2023239, NSF Medium Award CCF-2107079 and NSF AITF Award CCF-2006206. Part of this work was done while Jasper C.H. Lee was a visitor at the Simons Institute for the Theory of Computing. Paul Valiant is supported by NSF award CCF-2127806.
10

---

Bibliography
[BH79] Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wehhschheilicckeeissheeee und verwandte Gebiete, 47(2):119-137, 1979.
[BMM33] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[BY02] Ziv Bar- Yossef. The complexity of massive data set computations. University of California, Berkeley, 2002.
[Cat12] Olivier Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de I'Institul Henri Poincaré, Probabilités et Statistiques, 48(4): 1185, 2012.
[LV22] Jasper C.H. Lee and Paul Valiant. Optimal sub-gaussian mean estimation in I. In Proc. FOCS'21, pages 672-683. 683, 2022.
[Mia10] Yu Miao. Concentration inequaltty of maximum likelihood estimator. Applied Mathematics Letters, 23(10):1305-1309 2010.
[Min22] S. Minsker. U-statistics of growing order and sub- sabb-aassian mean estimators with sharp constants. arXiv preprint arXiv:2202. 1842, 2022.
[Pin17] Iosif Pinelis. Optimal-order uniform and nonuniform bounds on the rate of convergence to normality for maximum likelihood estimators. Electronic Journal of Stafistics, 11(1):1160 -179, 2017.
[Spo1]] 1] Vladimir Spokoiny. Parametric estimation. finite sample theory. The Annals of Statistics,
20(6):8877-2909, 2011.
[Sto75] Charles Stone. Adaptive maximum likelihood estimators of location parameter. The Annals of Statistics, 3(2):267-284, 1975.
[SV11] G.L. Shevlyakov and N.O. Vilchevski. Robustness in Data Analysis: Criteria and Methods. Modern Probability and Statistics. De Gruyter, 2011.
[VdGO0] Sara A Van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
[vdV00] A. van der Vaart. Asymptotic Statistics. Cambridge University Press, 2000.


Reviews:
[{"review_id": "q1cXDCOHXS3", "reviewer": "Reviewer_6bYV", "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.\n\nThis 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:\n1) 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\n2) 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.\n3) 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.\n", "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?\n2) 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?\n3) 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?\n4) 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", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe 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).\n\nI 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.\n\nThe 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.\n\nI 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YebiS08cmtM", "reviewer": "Reviewer_dJ3A", "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: \n\n1. The estimation error of MLE in the convoluted model approximately achieves the inverse Fisher information, even in finite samples. \n\n2. The above error is also near-optimal by a complementing (two-point) minimax lower bound, which holds in finite samples as well. \n\nExperimental results are also included to illustrate the performance of the proposed estimator. ", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nDespite my appreciation on the technical front, I am not sure of the usefulness of both the theory and methodology: \n\n1. 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. \n\n2. 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: \n\nSara A van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.\n\nThis 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? \n\nOther comments: \n\nIf 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. \n\nLemma 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). \n\nLemma C.2: conditions 5 and 6 cover conditions 3 and 4 by choosing k = 2. \n\nPost rebuttal: Thanks to the authors for the clarification and I am willing to increase my score to 7. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J4kykQOGXUM", "reviewer": "Reviewer_hCp9", "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. \n\nThe 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.\n\nThe 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.\n\nThe paper has presented two examples of distributions where taking a finite number of samples and performing MLE leads to a high variance estimate.\n\n1) 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$\n\n2) 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?\n\n3) 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?\n\n4) The effect of adding noise to better estimate location in the second example in lines no 76-78 is not elaborate and clear enough.\n\nThe 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.\n\n5) In theorem 1.1, taking $\\gamma$ to be ‘sufficiently large’ goes against its use in the three inequalities in line no. 99.", "questions": "Please see above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Please see above.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EUM_bGcoPFL", "reviewer": "Reviewer_64zQ", "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.", "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 ?\n\n- 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$ ? \n\n- 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. \n\n- 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 ?\n\n- 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.\n\n- 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 ?\n", "limitations": "Suggestion of improvements are included in the questions. In particular, the practical applications and  motivations should be developed a bit more.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWeaknesses: 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept