Minimax-Optimal Location Estimation
Authors: Shivam Gupta
Jasper C.H. Lee
Eric Price
Paul Valiant
Venue: NeurIPS 2023 poster (2023)
Keywords: location estimation
minimax estimation

Abstract: Location estimation is one of the most basic questions in parametric statistics. 
Suppose we have a known distribution density $f$, and we get $n$ i.i.d. samples from $f(x-\mu)$ for some unknown shift $\mu$.
The task is to estimate $\mu$ to high accuracy with high probability.
The maximum likelihood estimator (MLE) is known to be asymptotically optimal as $n \to \infty$, but what is possible for finite $n$?
In this paper, we give two location estimators that are optimal under different criteria: 1) an estimator that has minimax-optimal estimation error subject to succeeding with probability $1-\delta$ and 2) a confidence interval estimator which, subject to its output interval containing $\mu$ with probability at least $1-\delta$, has the minimum expected squared interval width among all shift-invariant estimators.
The latter construction can be generalized to minimizing the expectation of any loss function on the interval width.

Minimax-Optimal Location Estimation
Shivam Gupta
Jasper C.H. Lee University of -isconsin-Madison jasper bee@wisccedu
The University of Texas at Austin shivanuutaauttexa.cco edu
Eric Price
Paul Valiant
The University of Texas at Austin ecpricelcs www.usttaa...m edu
Purdue University pvaliant@gmail.cmm com
Abstract
Location estimation one of the most basic questions in parametric statistics. Suppose we have known distribution density f. and we get n i.idd samples from f(r - μ³ for some unknown shift μ. The task is estimate μ high accuracy with high probability. The maximum likelihood estimator (MLE) is known to be asymptotically optimal as + oc, but what is possible for finite n? In this paper, we give two location estimators that are optimal under different criteria: an estimator that has minimax- contimal-pptiml estimation error subject to succeeding with probability 1 - 5 and 2) confidence interval estimator which, subject output interval containing f4 with probability at least 6, has the minimum expected squared interval width among all shift-invariant estimators. The latter construction can be generalized to minimizing the expectation of any loss function the interval width.
Introduction
We revisit one of the most basic questions in parametric statistics: location estimation. Suppose there is a shift-invariant parametric model {f(() YOER, namely that f()) f(r 0) for some distribution f, and we get i.i.d. samples from f(u) for some unknown parameter The task is to estimate μ as accurately as possible, succeeding with probability at least 8. This problem includes Gaussian mean estimation as a special case. Compared to general mean estimation, where we know nothing about the distribution beyond mild moment assumptions, here we are given the shape the distribution, and only the shift is unknown. This allows us aim for better performance than in mean estimation, and even handle cases where the mean of the distribution does not exist.
The problem has been widely studied as special case of parametric estimation. In particular, the classic asymptotic theory [Vaa00] recommends using the maximum likelihood estimator (MLE), which, when fix distribution + (O, 1/ 1/(Z)) for any parameter μ. Here, the variance of the asymptotic Gaussian is 1/(nZ), where I is the Fisher information of the distribution f. defined by I = (f))))))) dz. It standard fact that 1/I < o² for any v distribution, meaning that the asymptotic performance of the MLE is always at least as good as the sample mean. Conversely, the well-known Cramér-Rao theorem states that, for any shift-equivariant estimator ù,, its variance must be least 1/(nZ) as well.
(()) and take the number of samples
co, satisfies (MLE
However, the classic asymptotic guarantee can be misleading, since the convergence to the asymp- totic Gaussian may be arbitrarily slow in the number samples, depending on the underlying distri- bution f. Indeed, recent work by Gupta et al. [GLPV22] showed that the issue is in fact information-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Cumulative Density
1.0
MSE Estimator
Interval MLE
p(xx)
0.5
0.0
3
Interval Width
(a) The input distribution has a rare but very infor- mative spike
(b) The minimax interval estimator from 10 sam- ples finds the smallest possible worst-case interval, but at the cost of much worse typical interval size.
Figure I: Example comparing our algorithms
theoretic, that no estimator can converge to the Fisher information rate a distribution-indeeendenn manner n - They [GLPV22; GLP23] also studied the finite sample algorithmic theory of location estimation, with the goal of yielding samiee estimation error tight to within a + o(1) multiplicative factor. To circumvent the impossibility of converging the Fisher informa- tion a distribution distribution-indeeendeni finite-sample manner, they instcad proposed a theory based on the smoothed Fisher information I,. That is, the Fisher information of the distribution after convoly- ing with N (0, 2 They showed that applying the MLE to perturbed samples and the smoothed dis- tribution will yield estimation error that converges N (0, 1/(nI,)) in instribution-indepennne fashion, for some smoothing radius that vanishes as n + co.
The key issue with the above theory, however, is that the Fisher information can be extremely sensi- tive to smoothing, As simple example, a Dirac-ó spike has infinite Fisher information, yet smooth- ing by NN r²) reduces its Fisher information to 1/r². Thus, to get 1 + o(1) tightness in esti- mation error, one would also need to also completely optimize away the smoothing. This is highly challenging and not yet achieved by these prior works on distribution- sisiooon----iiee diditiiiibttion basis.
In this work, we instead directly construct minimax minimax-optimall location estimators, under two different criteria. The first construction is point estimator ý which, for a given failure probability 8*, attains the minimum estimation error e such that [á μ S e with probability at least 8* The second construction is a confidence interval estimator [uc, /r]. Consider loss function the size of the output interval L(ur- - (e) that is monotonically increasing. The second estimator one such that, subject to the "correctness" constraint that the true parameter lies in the output interval [ie, pr] with probability at least 8", the estimator minimizes the mean loss.
The distinction is whether we want to minimize the worst-case or the average confidence interval. For example, consider the distribution (1 -1,n)N + N + n, r²) for r х (see Figure 1). There is about 1/c chance that you don't 't sample the narrow spike, in which case your uncertainty effectively the Gaussian N(0, }): but if you do sample the spike > times, it gives
much more precise (00, =²) uncertainty. That is, some observed samples could give very precise estimates, while other observed x cannot. The second algorithm gives worse worst-case behavior in behavior.
exchange for much better average
Our first algorithm only cares about the maximum size confidence interval returns. That will be dominated by the 1/e chance the narrow spike isn't sampled; so to get 95% confidence inter- val, will always return essentially (1 S )confiidence interval for the N(0 4) error, which
1.49
v 1.491 Our second algorithm could instead think: by returning the slightly larger inter-
val
in the cases where the narrow spike is not sampled, can return much smaller (r) size intervals when the spike is seen. It will optimize this tradeoff according to the given loss function; for square loss, this will be with Orrylog n) in the (more common!) "good" case, and
1.50
Va V
1 + 1/ (nly(n) factor worse than optimal interval in the "bad" case.

---

1.1 Our results and techniques
Minimax-optimal point estimation the first setting we consider in this paper: Given a point estimator ü. for given failure probability 8*, we measure its estimation error e0,8* by its worst-case emoor over parameters μs, namely
inf
sup
Pr Floeth (a (I((T))..., En) -a| S 8
Our first main contribution is that the estimator defined in Algorithm 2 achieves (essentially) mini- mal estimation error
Theorem 1.1. For any small k > 0, the estimator defined in Algorithm 2 has estimation error within a (1 x) factor of minimax optimal.
In order to construct this estimator, solve the dual problem: fixing estimation accuracy find an estimator that minimizes the failure probability 6. The optimal estimator for this dual problem can be defined as the limit of family of Bayes-optimal estimators. Specifically, fixing estimation error the estimator A, defined in Algorithm attains the minimum failure probability when the true parameter μ is drawn from the prior Unif[-t, t]. The following theorem shows that the estimator in the limit as f + oo, Aos, attains the minimax-optimat failure probability.
Theorem 1.2. The algorithm Axc (limit of Algorithm as t - oo) is minimax-optimal with respect the 0-1 loss [(p, 11) 11í
c). namely, with respect the failure probability.
The estimator Ace induces function of the failure probability 5 in terms of the estimation error Thus, given a desired a failure probability 8", the 8(c) function can be inverted to define the optimal estimator in Algorithm 2 in Section 3.2. Since d(c) is monotonic, we can use binary search approximately compute the optimal The binary search is explicitly given and analyzed in Appendix A.I.
Minimax-optimal confidence-interval estimation The second setting we consider this paper concerns confidence-interval estimators. Suppose are given increasing loss function L R. + R4+ mapping an interval width to a loss, and given an estimator A whose output interval we denote by [ue prl, we measure its mean loss by
sup PER #1 flo [L(,, -me)l
E
Our main result for this second setting that the estimator defined in Algorithm 4 achieves minimax- optimal mean loss, subject to the constraint that for all parameters μ E IR, the probability that μ [ue, [r]] is at least 8* for given failure probability 8*.
Theorem 1.3. Consider the set Algs- of estimators A whose output we denote by [pesHy], such that for all parameters p.
Pr fftt)
(u E [pt, 1-
Consider the estimator defined in Algorithm using failure probability 8*, and denote its mean loss by R. Then,
RS inf sup E [L(rr -pr)
AEAlgs NER Zi...,
The construction of Algorithm and proof of Theorem 1.3 come in two parts. First, show in Section 4.1 that Algorithm is minimax-optimal among equivariant estimators. That is, estimators which, the probability (density) of the estimator outputting the interval [ue, Mr] on input (Z1...., .. x,,) equal to the probability of the estimator outputting [it + 0, pr + 0 on input (x1 +0. (0....,2,, Hn, 0). Second, show in Section 4.2 that, for any estimator, equivariant arbitrarily well-approximated by an equivariant estimator. Together, this shows Theorem 1.3, that Algorithm is minimax optimal.
not, its performance can be
The bulk of the technical work comes from the first step, constructing Algorithm 4 and showing that it is minimax-optimal among equivariant estimators. The challenge is that we need to optimize the

---

mean loss of an estimator subject to the constraint on its probability of success, which is the event that its output interval does in fact include the true parameter.
Our approach is to use convex optimization techniques: for each equivariant estimator A, we con- sider its mean loss R and its failure probability 6,4. both of which independent of the true parameter due to the equivariance of A. It is easy to check that the set {RR, d2) over equivari- ant estimators A is convex set. We give Algorithm 3, which, for any angle p 722) is an cquivariant estimator which attains the minimum possible RA cos p + 5. sin among equivariant estimators. We also show the optimality of Algorithm 3 in Theorem 4.3. This estimator thus defines a failure probability 6p and a supporting hyperplane of angle for the {(RA, 5,) set. Noting that 6p monotonic in p. this again means we can binary search on P to yield the desired failure probability 8". Appendix 1.1 gives the explicit binary search algorithm and its correctness guarantees.
2
Related work
Location estimation, special case of parametric estimation, has well-established asymptotic theory [Vaa00] concerning the MIE, whose asymptotic performance captured by the Fisher in- formation. There have also been works on the finite-sample performance of the MLE, see for exam- ple [Spol1; 1in17; Van00; Mial0]. However, these works impose strong regularity conditions on the parametric model, and lose at least constant multiplicative factors in their error guarantees.
More recently, Gupta et al. [GLPV22; GLP23] focused on location estimation, and aimed to charac- terize the finite-sample theory to within 1 - o(1) ttighttssss in the estimation error. They proposed a theory in terms of the smoothed Fisher information. Yet, there are examples of distributions whose Fisher information decrease significantly even after little smoothing, meaning that their theory does not always capture the optimal finite-sample bounds up to a + o11)-factor. By contrast, in this work, we directly construct minimax-opting estimators.
The related problem of mean estimation has also seen renewed interest in its finite-sample theory, also with the aim of yielding 1 + o(1) (tighthtssssss in the estimation error. Catoni [Cat12] showed in his seminal work that, if the variance of the underlying distribution is known, then is possible to achieve 1 + (ti)tt estimation error. Catoni [Cat12] and Devroye et al. [DLLO16] also showed that, as long as the kurtosis (normalized central 4th moment) is bounded, knowledge of the variance is unnecessary. Recently, Lee and Valiant [LV22] proposed an estimator also yielding ++ o(1)-tight error, but removing the knowledge assumption on the variance entirely, and instead assuming only its existence and finiteness.
3 Minimax-optimal point estimator
The goal of this section is to construct point minimax-optimal estimation error, where error for
estimator
á that yields i is measured by
inf {+ > 0 sup,, Pf.t... (1ā(11........ x.) 1l S e) 2 8
Section 3.1 first gives and analyzes an algorithm which takes as input an estimation accuracy e and returns an estimate á whose failure probability Pr(lă μ4| > e) is minimax-optimal Section 3.2 then uses binary search to construct an estimator that instead takes in desired failure probability, and outputs an estimation that (almost) optimally minimizes the estimation error.
3.1 Estimator with minimax failure probability
The goal of this section is construct an algorithm that takes in a desired estimation accuracy and optimizes for the failure probability 8. The key intuition is that, since we do not know what the true parameter 9 is, we might as well start by constructing an estimator that is Bayes optimal with respect to the uniform prior over the real line (R). However, there is no such thing as uniform prior over the real line. So instead, Algorithm below is constructed to be Bayes optimal with respect to the prior Unif[-1, f]. and we take the limit of ( - to get a translation-equivarian estimator, whose risk (failure probability) independent of the underlying parameter O. We then use standard tools to relate Bayes optimality to minimax optimality, under such translation equivariance.

---

Algorithm The algorithm A, for a fixed estimation accuracy
Input: Distribution shape f, samples , and estimation accuracy
1. Let (0) be the likelihood of f(() yielding the observed samples 21,...;; -n-
2. Return j arg maxgel-tte,teeeeee Je- (0) d0
As mentioned earlier, the optimal algorithm we propose is the limit Ace namely, in Step of Algorithm 1, the arg max on 0 is over the entire real line. Note, as basic observation, that A is an equivariant estimator.
To show that A minimax optimal in failure probability, we will use the standard technique of relating it to (a sequence) of Bayes-optimal estimators for some (sequence of) Bayesian priors.
Let us define the relevant notation here.
Definition 3.1. Throughout this section, we consider the 0-1 loss function L(p. pb) 111 pl > cl
for some fixed The failure probubility of an n-sample estimator i with respect parameter can then be re-expressed as the risk R(H,, (b) Be.........ff [[u,, (.(I,,...; [in]].
Consider a prior x on the parameter μl over R. We denote the Bayes risk of an estimator jo with respect to prior πI as R(T,p)) pJ) Euown [R p)], under the usual abuse of notation.
To show that given estimator jú has minimax optimal risk (namely, failure probability), the follow- ing standard fact states that suffices to demonstrate sequence of priors, such that the worst-case risk of is the limit of the optimal Bayes risk of these priors. We prove this fact in Appendix A.
Given an nasalple estimator j., suppose there exists sequence of priors { such that the worst-case risk of fu is equal to the limit of optimal Bayes risk of Tú, namely
Fact 3.2.
sup R(p, (b) lim inf R(T,, P') WER
11000 P
Then is minimax optimal.
To show the minimax optimality of Asc. we will consider the sequence of priors गe Unif([-t, tJ). The first step is to characterize the Bayes-optimal estimators for the prior Me.
Lemma 3.3. The algorithum Ar is Bayes-optimal for the prior Tt.
Proof. Given the samples 2i...., Tn, the likelihood function (0) constructed in Step 1 of As, limited the range t]. equal to the posterior distribution of 0 given æ up to a normalization factor. Thus, by construction, Step finds the f that maximizes the posterior success probability, or equivalently, that minimizes the expected posterior loss (the posterior failure probability) given r. Hence A, is Bayes-optimal estimator.
With Fact 3.2 and Lemma 3.3, we can now state and prove that the algorithm Aso (Algorithm 1) is minimax-optin optimal with respect to the 0-1 loss, namely that it has minimax ootimalllpalallaaaa failure probability.
Theorem 1.2. The algorithm Age (limit of Algorithm I as - oo) is minimax-optime with respect the 0-1 loss L(p, H) 1llA pl el, namely, with respect the failure probability.
Proof. Fact 3.2 implies that, it suffices for us to show
sup Aoo) inf R(T... + 0 Ar
as i - 00. Since Asc equivariant, the risk R(μ, Abc) is independent of μ. Also, recall by Lemma 3.3 that A, is Bayes-optimal for the prior गт. The above claim is thus equivalent to
((T.A)))) - R(T,, A:) +
00.
5

---

Since A, is Bayes-optimal for xg, the left hand side is always positive. Also observe that the left hand side is upper bounded by the probability that Axo has different output from A, We will show that such probability, explicitly, Pr P, (a) * (.))), tends to 0 as i + co.
We first claim that, fixing distribution shape f. for any small probability sufficiently large such that, if the true parameter 0 E [-i+ Vi,i vi, then there is at most a/2 probability that Axx has different output from A, when given i.i.d. samples from ((w), This is easy to see, since A&e outputting differently from A, implies the output of Axc is outside of (-i+6,i-0 Furthermore, since Asc is equivariant, have
0, there exists
Pr I Tluet t flo) (Axc (ar) [M 1, 1))
as - 0o for any fixed J.. For μ E [-i+ Vi Vil, the locations -i + c and - c are at least t = ((vi) away from Thus we can set sufficiently large such that As outputs outside of t- - E) with probability at most k/2, for any fixed μ E [-i ii vij.
Further observe that, under prior T4, there is only 2/vī probability that the parameter p is sampled be to outside of [-i+ Vi - vil. By setting sufficiently large, this probability is at most 6/2, for any given K.
In summary, for any given small probability K, there exists a sufficiently large such that A outputs differently from A, under prior n; with probability at most K. We have thus shown that
A2o; - A,)
as + oo, completing the proof.
3.2 Estimator with (almost) optimal estimation error
In Section 3.1, we presented an algorithm which, when given the distribution shape / and a fixed estimation error e, finds an estimate which minimizes the failure probability 6. Observing that is a monotonic function in e, we can also interpret as a monotonic function of 6. Thus, if we are given fixed d (and distribution f), there is an infimum over achievable e. Algorithm I therefore also induces an optimal algorithm that optimizes for e when given 8, as follows.
Algorithm 2. Consider the optimal failure probability d as function of the estimation accuracy Given desired failure probability 8*, define e" inf(e > 0 ö(e) S }*.. Using Algorithm with estimation accuracy (1+ x)E" for results an estimator whose failure probability by
definition at most 8*, By construction, this estimator has accuracy that is within a (1 + k)) factor of minimax optimality.
The optimal estimation error ex can be computed using binary search. We defer the details to Ap- pendix A.I.
4 Minimax-optimal confidence-interval estimator
Recall the second problem setting of this paper concerning confidence-inteed inntrrvvee estimators. Fix a loss function L IR, + I4, mapping an interval width to loss, and assume it is increasing, Given an estimator whose output interval we call [Me, Mr), its mean loss is the worst-case expected loss
E E R1 R f(a) [L[,, -me)l
sup
8". That is, for all Consider the set Algs- of estimators A that are "correct" with probability 1 -- parameters μa,
Pr (n E [pe, (.)) 2 8 E1.... f(t
Then, the goal this section is to find an estimator in Algg- that minimizes its mean loss, for any desired failure probability 8* (0, 1].
Section 4.1 shows how to define the optimal equivariant estimator subject to the 8* probability correctness constraint. Appendix B.1 gives binary search procedure for approximately computing this optimal equivariant estimator. Finally, Section 4.2 shows that the optimal equivariant estimator is also optimal across all estimators.

---

Average loss Ry
Ag 4
Ag
(*(5)
8y --coniidenee level
Figure 2: Illustration of the feasible set F, Definition 4.1, and Algorithm and Algorithm
4.1
Optimality among equivariant estimators
We use convex optimization techniques to find the best equivariant estimator. do so, consider the following feasible set of estimator performances, where for each equívariant estimator A, we consider the pair (RA,,6A) 6A) which respectively its mean loss and its failure probability. This set always convex.
Definition 4.1. Fix a distribution I f(0), Given (potentialy) randomized equivariant n- sample estimator A with output [p,, we say that A achieves the performance pair (R 5.)) if F pp))²] & RA and Pra & (ue, S 6
Define the feasible set for distribution f to be the set
Fi {(RA. A achieved by some an equivariant n-sample estimator A}
See Figure 2 for a pictorial illustration of the set.
Fact 4.2. Given an arbitrary distribution f. the feasible set F3 is convex. As corollary, the boundary R (6) inf [RA (RA, 8) E F3} a non-increasing convex function.
Proof. Given two algorithms Ao and A₁ achieving (RAo, dAa) and (RAi SA.)) respectively, con- sider new randomized algorithm which runs Ao with probability À and Ai otherwise, for an arbitrary À E j0, 1]. The new algorithm achieves (ARA, + A)R Ad + - A) Thus, Fy is a convex set.
Since Fy is a convex set, the boundary R is also a convex function. The definition of Fy also directly implies that R is non-increasing.
Our goal then to define the equivariant algorithm arg m RA the boundary R" being inf is actually achievable. The key idea is consider the (sub- bub-)derivvative (or just "slope", from now on) of the boundary function R (8), which is always non- non-positive and also increasing as function of 5, since R is non-increasing and convex. We will first show how, given a slope, we can find an estimator whose (R,,, d.A) pair lies on the boundary of Fr and has supporting hyperplane with the desired slope (see "Generic Alg 3" in Figure 2). Having defined this estimator, its failure probability 5 can be evaluated. Since the failure probability is an increasing function of the slope, we will then do a binary search on the value of the slope to yield the correct value of 6A 8 (see "Alg 4" in Figure 2).
(RA.0) E Fy). that fact,
Specifically, will parameterize the slope by its angle p E [0, T m/2 Given angle p, will define an estimator AA in arg min(RA cos + 5 sin p (RA, 5A) E Fy)- Additionally, since the arg min may contain many estimators, we will also have the choice to additionally find the algorithm in the arg min with the minimum 8 (equivalently, maximizing RA)) or the largest 8
As we see in the following theorem, the quantity ||Z/|| in Step 3 above is in fact the probability (den- sity) of observing any shifted versions of , and hence exists and finite. Thus the normalization step well-defined.

---

Algorithm 3 Estimator minimizing RA cos + d sin p for a given angle p E [0,
1. Input: samples 21.....22, En. distribution Boolean flag smallestDelta indicating whether we ticbreak for the smallest 5д or the largest 5A
2. Compute the likelihood function (=(0) of f()) yielding the observed sample 21,...,
3. Normalize lg into the distribution (0) 1=(6)/||4<111
4. For each interval jīg, frl, define its risk Rij..ū.] as (jr, ie)?. and its corresponding O[pespe] the probability 1 pelie, Ør] under the distribution pz.
5. Return juce Pr)] that minimizes Riue cos p + (eeme) sin p. and tiebreak according to the input Boolean flag smallestDelta.
The following theorem shows that Algorithm 3 is indeed an optimal estimator that minimizes RA cos p + A sin p among all equivariant estimators.
Theorem 4.3 (Correctness of Algorithm 3). Suppose Algorithm 3 with angle and flag smallest-
Delta set to true achieves the pair AR A) Then, for an arbitrary equivariant estimator A whose performance is (R 0.)), ) we have that
RA cos p + 8 sin p Rí cos Rosospp
A sin
Furthermore, if RA p d sin RA co8 p + A sin then A S 6
The analogous statement holds for Algorithm with the flag smallesiDelta set to false.
Moreover, as a corollary, we have R (6 = RA by the convexity of Fj-
Proof. For the rest of the proof, use the notation for the unit vector (cos p; sin p)-
On the set of n-tuples samples (namely IR"), define the equivalence relation if two n-tuples are shifts of each other, that is, E = (#1,.... _n) is in the same class as y7 (U vn.) if and only 1/1 1 = equivalence class. We will also abuse notation and use [ to denote unique representative chosen for that equivalence class, and use
Yn In. Given a tuple V. we use the notation [z]] to denote the corresponding
to denote scalar shift between ő and the representative
[X] of its equivalence class.
Then, for an equivariant algorithm A whose output is denoted by [ne, prl, we can write RA as
[[ pell
R
meaning that there are three levels of randomness: first draw an equivalence class [a]] (according to the distribution = f())), then draw a random shift according to the conditional distribution [ then finally, the algorithm A can itself be random conditioned on its input
Similarly, we can write A as
0
E
E
I A|F
1 og (egine.a.))
Given that the goal of Algorithm 3 is to optimize ग (RA, AA, linearity implies that it suffices to optimize, for each equivalence class [7]. the inner product
T E
E 21 A
we)]
LAIZ
To that Algorithm optimizes the above inner product among all equivariant algorithms, first ob- serve that by linearity, it suffices to consider deterministic algorithms A which output a deterministic interval given input n-tulle of samples.
Moreover, observe that the conditional distribution / [7]] is, up to translation, equal to the normal- ized likelihood (110//1l for any n-tuple ÿj E [T.. This is because ||/l| is exactly the probability

---

(density) of the equivalence class [æ]. Therefore, in Step 4 of Algorithm 3, the probability Sjpe.ü..] is equal to the probability, under the conditional distribution 전 [z], that an equivariant algorithm whose output jāte ( fr (7 [d-[ under input [3] fails to output an interval that contains the parameter O. That is, ō..... = Ea|sa]] [1 [og where [pg, [rr] is the output of a deterministic
equívariant algorithm that outputs lite ( (. - (H [=]]] under input [+]]
To conclude, then, Algorithm by construction chooses deterministic interval to output so as to minimize the inner product
FLE - pe)l
E
E LAE
E -|
LA
among all equivariant algorithms. The same reasoning also shows that the tiebreaking per input n- tuple sample i implies tiebreaking on أA which is an expectation over the distribution of the n-tuple sample input.
Given Algorithm 3, we can now define the optimal estimator for a given confidence parameter 6. which is by construction optimal given Theorem 4.3,
Algorithm (Minimax-optimal confidence-interv interval estimator). Fix a distribution f. For an angle p. let de(p) be the failure probability of Algorithm 3 with the flag smalles/Delta set to true, denote this estimator by Ae(p), and 8u(p) be the failure probability of Algorithm 3 with the flag set to false, similarly denoting this estimator by Ap).. Given a failure probability 8", by the supporting hyperplane theorem there exists an angle value p (e.g. the arctangent of a sub-derivative of R (6) be 6p)p).. Let 8* =dd((p) + (1 ()) Then, define the
at 8 8*) such that 6" E [de(p), optimal MSE estimator for failure probability to be the randomized algorithm which runs Ae(p)
with probability X and runs (p) otherwise. By definition, this estimator achieves (R* (6*))
The optimal slope angle p can be approximately computed using binary search. We give the details in Appendix B.1.
4.2 Minimax optimality of Algorithm 4
In Section 4.1, we showed that Algorithm 4 is optimal among equivariant estimators. We now show that is in fact optimality among all estimators.
We first extend Definition 4.1 to cover also non-equivariant estimators.
Definition 4.4. Given a (potentially) randomized n-sample estimator A. whose output interval we denote by Prl. we say that A achieves its (RA, 5.)) pair if. for all parameters μ I, E. [[ -me) S RA and Pr PT (11 &f luc, prl) S 8AA
The key step in the proof of minimax optimality of Algorithm is to show that the performance of any estimator can be well-approximated by equivariant estimator.
Proposition 4.5. Fix an arbitrary distribution f and an arbitrarily small approximation parameter b E (0, 5). Suppose there is an estimator A (not necessarily equivariant) achieving (RA, A.) then there exists an equivariant estimator A' that achieves ((1 + A,, 8 2b).
We prove Proposition 4.5 in Appendix B. The main idea for constructing A'' from A is that, on input an n-tuple of samples (z) "......;20 )n,) whose sample median is s, we shift the samples by a random shift drawn from Unif[-t-s, s, - s) for sufficiently large f, 2) call AA on the shifted samples and 3) output the returned interval and subtract off the random shift we made to the samples. This estimator is equivariant by construction, and we relate its execution with high probability to applying A to samples drawn according to the prior [n, This allows us to bound the performance guarantees of A' by those of A.
With Proposition 4.5, we can then show that Algorithm 4 is in fact minimax optimal among all estimators, not just cquivariant ones.
Theorem 4.6. Fix distribution f. Recall the definition of Rd (8) from Fact 4.2, which is the infimum of all achievable (RA. 5) over all equivariant estimator A. Now consider an arbitrary (potentially non-equivariant) estimator A'. If A' achieves (Rar, d, then R R² (ō.Ar)
As result, since (R" (8*), 5*) is achievable by Theorem 4.3 and Algorithm 4 for any 8* > 0, we have that Algorithm 4 is in fact minimax optimal among all estimators.

---

CDF of Error
0,0008
0.0006
Coanalervo Density
0.8-
Oviginal Distrintiion Sunoorlued Distriutton (r-0.3)
0.0004
MSE Estiimator
0.4-
MLE
1,1002
Smoothhe MLE
1-d
Intersal MLE
0,0000
20
1.0
1.5
Brror
(a) Distribution f
(b) Point Error
MSE Estimator Interval Radins
fer Interval MLF
Cunalalive Deasity
0.5-
0.4-
0.2-
0.9
0.4
10.6
01.
1.0
1.2
(c) Interval radius
Figure Example distribution and CDF of confidence interval widths
The proof is in Appendix B.
5 Experimental results
We compare various location estimation methods on synthetic data from a fairly simple, but irregu- lar, piecewise linear distribution (Figure 3())). We set 10 and aim for 90% confidence intervals. In Figure 3(b), we plot the CDF of the point error produced by the MLE, the 0.3-smoothed MLE, and our two algorithms (Algorithm and Algorithm 4). We find that algorithms get 25% smaller error than the MLEE at the target 90% error rate. The smoothed MLE and Algorithm 4 error distri- butions both dominate the MLE, with Algorithm 4 having better performance close to its target and smoothed MLE better further away. Algorithm does 2% better than Algorithm at the target 90%, but worse most of the range.
In Figure 3(c), we compare the confidence intervals produced by our algorithms. Algorithm uses fixed interval radius regardless of the samples it sees, while Algorithm 4 has distribution over interval widths that is usually smaller but occasionally bigger.
Acknowledgements
We thank the anonymous reviewers for insightful comments and suggestions this work. Shivam Gupta and Eric Price are supported by NSF awards CCF-2008868, CCF-1751040 (CAREER). and the NSF AI Institute for Foundations of Machine Learning (IFML). Jasper C.H. Lee supported in part by the generous funding of a Croucher Fellowship for Postdoctoral Research, NSF award DMS- 2023239, NSF Medium Award CCF-2107079 and NSF AiTF Award CCF-2006206. Paul Valiant is supported by NSF award CCF-2127806.
10

---

References
[Cat12]
Olivier Catoni. "Challenging the empirical mean and empirical variance: A devia- tion study". In: Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 48, .44 (2012), pp. 1148-1185. DOI: 10. 10214/11-AIHH
[DLLO16] Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto Oliveira. "Sub-Gaussian mean estimators". In: Ann. Stat 44.6 (2016), pp. 2695-2725.
[GLP23] Shivam Gupta, Jasper C.H. Lee, and Eric Price. "Hiigh-iimensional Location Estima- tion via Norm Concentration for Subgamma Vectors", In: ICML. 2023.
[GLPV22] Shivam Gupta, Jasper C.H. Lee, Eric Price, and Paul Valiant. "Finite-Sample Maxi- mum Likelihood Estimation of Location". In: NeurlPS. 2022.
[LV22]
Jasper C.H. Lee and Paul Valiant. "Optimal Lub-Gaussian Mean Estimation in R". In: Proc. FOCS'21, 2022, pp. 672-683.
[Mia10]
Miao. "Concentration incquality of maximum likelihood estimator". In: Applied Mathematics Letters 23.10 (2010), pp. 1305-1309. ISSN: 0893-9659. DOI: https:
(aoii.rr//.... 3tg//00.016// aml 2010.0000000 .6.066..001 019.
[Pin17]
Iosif Pinelis. "Optmallorder uniform and nonuniform bounds on the rate of conver- gence normality for maximum likelihood estimators". Statistics 11.1 (2017), 1160-1179. DOI:
In: Electronic Journal of
[Spol1]
Vladimir Spokoiny. "Parametric estimation. Finite sample theory". In: The Annals of Statistics 40.6 (201 1), pp. 2877-2909. DOr: 10. 10l.1121112AAS111111
[Vaa00]
A.W. van der Vaart. Asymptotic Statistics. Cambridge University Press, 2000. ISBN:
9780521784500
[Van00]
Sara Van de Geer. Empirical Processes in M-estimation. Vol. 6. Cambridge univer- sity press, 2000.

---

A Missing details from Section
Fact 3.2. Given an n-sample estimator jt, suppose there exists a sequence of priors {Ti) such that the worst-case risk of Pt is equal to the limit of optimal Bayes risk of Tú namely
sup R(u. (2) lim inf R( p²) PER
1-000 1
Then ji is minimax optimal.
Proof. Consider any other estimator 0.
Then
sup R(0, 0) 2 R( 0) 2 inf R(T,, 8')
0'
for all xy. meaning that
sup R(0,0) 2
lim inf R(T,, 0') = sup R(0,0) 1000
A.1 Binary search for approximately computing the optimal point estimator
In this section, we address the (approximate) computation of the optimal e* when given desired failure probability 8", using binary search. We explicitly give the (straightforward) binary search below in Algorithm which accounts for the error in computing d(e) for a given value of e. We also state the guarantees of Algorithm 5 here in Theorem A. and prove the theorem in Appendix A.
Algorithm Approximately computing e" from 8* using binary search
Assume: Oracle for estimating 6(e) to additive error & for any given e. Call this oracle 6(e).
Input:
Distribution f f()), desired failure probablity 8*
1. 6max 1
2. While 8(Emax) + & 8", double Emax
3. Gmin +
4. While émax Emin 1]
(a) émid f- (Emax + Emin)
(b) If (f + < 8*, then Cmax f- Emid
(c) Otherwise, Emin Emid
5. Return Emax
Theorem A.1. Fix a distribution shape f. which implicitly defines a function (8) mapping a failure probability 8 an optimal estimation error E" (6)). Algorithm on input a failure probability 8* and the distribution shape f, takes poly(? 1 [log c0 - E) fog 2. log (() many executions Aro and returns ē E [ee [e"()*), e8 - + v) with probability 1 1
Proof. For now we analyze Algorithm 5 assuming the oracle. We will discuss the time complexity of the oracle and success probability of the whole algorithm the end of the proof.
Given the guarantee that 1 8 < &, at the end of Step
have emax 2 6"
Due to the one-sided test Step 4(b), by induction, we have that Emin S e" (5* - {) throughout the
iterations of Step 4. Since we return max in Step 5, when Caax Cmin 17, we can guarantee that the returned value of is at most e (8* - {)
The above analysis assumes the success of every call to the oracle 8. Observe that a failure probability, namely that it is the expectation of Bernoulli coin. We can estimate å via running A.e
12

---

using phantom samples we generate from fu. Via the standard Hoeffding bound, to yield an estimate of Ó(E) to within additive error Ç with probability 1 т, we need O log ( samples, namely that many independent runs of A Since we make many calls the oracle throughout Algorithm 5, suffices for us to upper bound the number of oracle calls, and multiplicatively adjust appropriately such that the total failure probability is T by union bound, across all the oracle calls.
For Step 2, we can upper bound the number of iterations by log max [1 c" {)), since we always terminate whenever émax 2 (6* - {) by the guarantee that å 2 d - ç.
Step 4 is just binary search, halving the interval [émin Emax] every time, from size max(1, e (0" {)) down to 17, thus requiring log(max(1,, c (6 - ())/)) many iterations. Note also that log(max(L, e (8* E))/n)= S log (6" E)] + log ((88-()
"
The runtime claim of Theorem A.1 thus follows.
B Missing details from Section 4
Proposition 4.5. Fix an arbitrary distribution f and an arbitrarily small approximation parameter b E (0, 2) Suppose there is estimator A (not necessarily equivariant) achieving (RA, 6.), then there exists equivariant estimator A' that achieves b,, 2b).
Proof. Given the estimator AA first construct an intermediate estimator À such that, if AA outputs an interval of length at most - then A outputs an identical output, otherwise Á outputs an arbitrary interval of length at most L ' (Ra/b). The claim is that A achieves (RA, + 6). It is immediate that A achieves mean loss at most RA for any parameter by construction. As for its failure probability. for an arbitrary parameter ja, the probability that AA outputs an interval [ue, prl of length > L, (Ra( is at most b, since the mean loss is at most R for parameter μ.. Thus, the failure probability of Á on parameter μ is at most A + 6. which holds true for any μ.
We now construct the equivariant estimator A'. On input n-tuple H. let the sample median be s. Sample number w ~ Unif[-t- - 8, s] for some fixed parameter i chosen later, where depends only on b and the distribution f. and is independent of F. Then, A' calls À on input Z + (w...., and obtains an output interval [ū,, j.... Finally, A' outputs lie w. jr,- w).
Observe that the new estimator AA' is by construction equivariant. remains to choose the parameter t as a function of b (and the underlying distribution f). Consider drawing n samples from f = f()) then there must exist some distance Smax such that the sample median is within Smax of the origin with probability at least - b²/ /2. We will choose the above parameter t as = smax/b?.
Now we need to upper bound RA and & in terms of R R and و respectively. Specifically, we claim that there is 1 - 6² probability coupling between the execution of A' on parameter μ 0 to the process of 1) drawing a parameter j Uni t). 2) drawing an n-tuple of samples 7 from f(w), 3) running À on z to get interval jūe, (rr] and outputting jit: - pt, fr - n4]. We note that the 0.
latter process achieves iR 2) with respect to parameter
To show this, observe that with probability at least 1 - 02/2, drawing an n-tuple of samples F from f = (0) will yield a sample median of s S 8max. by definition of 8max. Then, observe that since I Smmxm00 /b2 the total variation distance between Unif[ 8, [-8] and Unif[-(, (] is 8/ //21 < 12 12/2. /2. Thus, with probability at least b22 the execution of A'' on input samples drawn from f(0) is equal to a version of A' where the "shift" w is instead always drawn from Unif[-t, t). However, this variant of A' is exactly equivalent to the aforementioned process of 1) drawing parameter Un, 2) running A on samples drawn from f(w) and 3) outputting the interval after correcting for the w shift.
Therefore, given this coupling, conclude that S S 2 S 66+6+62 < 6 as 6 2-
As for RAy, since Á always returns intervals whose loss is at most Ra/b, the probability S 12 part of the coupling when the two processes behave differently, the contribution to the expected loss
of A' is at most 1 Ra/b h = bRA, Thus we can bound RA by R₁ + bRa S (1 + b) R. as desired.
13

---

Theorem 4.6. Fix a distribution f. Recall the definition of R R*) (6) from Fact 4.2, which is the infimum of all achievable A == over all equivariant estimator A. Now consider an arbitrary (potentially non non-equivarian)) estimator A'. If A' achieves (R , 6.).,, then R 2 R (6.)))
),88 8*) is achievable by Theorem 4.3 and Algorithm 4 for any 8 As result, since (R" ), have that Algorithm 4 is in fact minimax optimal among all estimators.
Proof of Theorem 4.6. Suppose for the sake contradiction that R < (6x)). By the support- ing hyperplane theorem, there exists angle p E [0, //2 such that for all equivariant estimators A, we have A cos p + RA sin 2 å cos + R (6 sin p. However, by Proposition 4.5, for all b E (0, 2). there is equivariant estimator As that achieves ((1 + Ra.- A 2b). Consider value of < min(;, (It (6 (2 cos p + Rx sin p)), noting that the upper bound is positive by our contradiction assumption. Then, it is straightforward to check that A, violates the supporting hyperplane dA cos p+ R.A, sin p 2 ó cos p R (6.r) sin p. Thus, must be the case that R (6x)).
B.1 Compute an optimal slope angle
In order to apply the construction of Algorithm 4, when given a distribution f and a desired failure probability 8", we need compute optimal slope angle value p aT x/ use for Algorithm 3. Since the failure probability is monotonic function of p. the obvious strategy here is to again use binary search. Algorithm 6 returns an (approximately) optimal value of p for Algorithm 3, well as probability for randomly setting the flag smallestDelta to true or false.
Algorithm Binary search for the optimal estimator through the slope angle p
Assume: Oracle for computing the failure probability of Algorithm 3 to additive error & for any given angle and Boolcan value for the smallestDelta flag. We will use de(p) to denote the oracle approximation for Algorithm with smallestDelta set to true, and 8/((p) for smallestDelta set to false.
1. Input: distribution failure probability 8*
2. Set Pmin O, Pmax + πT/2 7/2.
3. Repeat until (e(pmin) - 8, (Pmax) S VE - 48:
(a) Set Pmid < (Pmin + Pmax)//2 //2.
(b) Use the oracle to evaluate the failure probabilities be de (Pmia) and (Pmia) for Algo- rithm 3.
(c) If 8* < de(Piia)) + E. Pini Pmid-
(d) 8* > 8, (Pmia) + E, Pmmx +- Pmiid-
(c) If 8* E (ōe(Pmia)) E, (pmil)) + +]
(Pmia) - (p S VE 46, terminate and return the algorithm that runs Algorithm 3 with p Punid and flag smallestDelta
true always.
ii Otherwise, terminate and return the algorithm that runs Algorithm with p Pmid and flag smallestDelta set to true with probability (1 (6) + E (-)/(6((Pmia) (e(mii))).
4. Return the algorithm that runs Algorithm 3 with p Pmax and setting smallestDelta to be false always.
The following theorem captures the correctness of Algorithm 6.
Theorem B.1. Fix an arbitrary distribution I and failure probability 8*. If. for parameter E smaller than some absolute constant, all the oracle culls in Algorithm 6 are correct, then, upon termination of Algorithm 6, the returned algorithm achieves a mean loss of RA E [R" (8*), -((EE)) and succeeds with probability at least 1 8*.
14

---

Proof. For this proof, denote 5t (p) by the actual failure probability of Algorithm 3 using slope value P and setting smallestDelta true, and similarly for (p).
First, by induction, throughout the execution of the algorithm, we have that 5 E (Pmmaax),
+ 2g]. This can be checked straightforwardly by Steps 3(c,d) and the fact that 8(0) is within additive & error of 8()) by assumption.
There are two ways the algorithm terminates, either in Step 4 or in Step 3(e).
We first analyze the termination condition in Step 4. Since, from the above paragraph. have 8 ( (g(miin) + 2g]. For the returned estimator from Step 4, its failure probability is by definition 5, (Pmax). In order to reach Step 4, it must be the case that (e(pmin)- - (pmax) < V - 45. which implies (P(mi))) 5, (Pmaa) Fact 4.2, we conclude that RA E [R* R - -V)].
VE. Therefore, we have (p 10" VE,8*) By
Next, we analyze the two possible termination conditions in Step 3(e). We know that 8 (pm(a)))) E, (Pmia) + c), which implies 8* E (5 5, (Pmia) + 26].
If terminate according to Step 3(e) i., then we know that 8 (Priid) (e(Piid) S -V--55 46. This implies 6/((mia) (e(iii)) S V - 2Ç. Combining with the last paragraph, we get óe(Piia)) E 18" -VE, VE.6"] Also note that the returned estimator has failure probability 6e(Pmia) by definition. Again using Fact 4.2, we conclude that the returned estimator satisfies RA E [Rt* (6*), (8 - VE)I-
Lastly, we check the case if we terminate according to Step 3(e) ii. The failure probability of the returned algorithm is
(1 (8m E -8) 5e(Peni)) + (1- 3 (6 + - 8 (Pmia)
8, (Pmia) - 8e(Piia)
8 (Pridd) 8e(Pmid)
We will show that this failure probability is between 8" O(VE) and o", which (again, by Fact 4.2)
lets us conclude that RA E (8*),, (6 O(VE)))
To show that the failure probability is most 8", observe that 8, (Pmia) - S 8 (Pmia)
Se(Puid) + 2 S (1 + 3VEE (Pmiia) - de (Pmia)) since (Punid) 8e(Pmia) 2 V - 4 by the condition in Step 3(e) ii. Furthermore, (pmia) + --- 8' 2 8, (Pmia) - 8 Thus,
(1 + ( + - 8, (Pmid) - (Pmia))
8p(pmid) - 8" 8r (Pmid) 8e(Pmid
implying that the failure probability most 8*.
Finally we need to show that the failure probability is at least d" - -O(VE). To see this, we upper bound
(1 + (6 -
(pmia)) - 8e(mia))
(1 + (6 (Pmid) - 80 + +2E)
8, (Pmia) (Pmia) 2
(1 + (5, (Pmiia) - 8" + +EE
<
(since 8 (pmia) - 8e(pmia) 2 V -g)
8r (Pmid) (emid)
Therefore, the failure probability is lower bounded by
(1 (1+0( (6
8" + 2E)
6e(mmtt) + (1- (1 (5 - 5" + 2E) 8, (Pmia)
8r (Pmiaa) - de (e(ia)))
8, (P(indd) de (e(prna))
8* - (6 - +2) (1 (L+O(VE))22
2 8" - O(VE) since & is sufficiently small
Since the failure probability 8 is not a Lipschitz function of the slope angle cannot in theory bound the runtime of Algorithm 6. However, we can nonetheless implement the probability esti- mation oracle and ensure total failure probability of most 1 т. As in Scction 3.2, in order
15

---

to estimate the failure probability of an algorithm to accuracy & with probability 1 - it suffices to use Ollog / executions of Algorithm over simulated samples (say, from f()), In order to make sure that all oracle calls are correct, with total failure probability of most т, we simply decrease the failure probability of each subsequent oracle call by factor of 2. That is, the first call allowed fail with probability т, then the second call r/2 and on, which sums a total failure probability of strictly less than т.
We emphasize again that these executions of Algorithm 3 only "simulated" samples that generate ourselves from a known distribution with a known shift, and not "real" samples we get for the estimation task.
16


Reviews:
[{"review_id": "suLxX6EXaC", "reviewer": "Reviewer_cZWD", "summary": "This paper is about location estimation from sampling. That is, given n samples from a known probability distribution f, which is shifted by an unknown value $\\mu$, the goal is to estimate that shift. Gaussian mean estimation is a special case of this parametric estimation type of problem. The paper describes two minimax optimal algorithms with respect to the failure probability and the accuracy, which output a confidence interval for $\\mu$. The first algorithm achieves this in a worst-case sense. That is, it is trying to output as small confidence interval as possible in the worst case instance. However, the second one is minimax optimal with respect to the mean loss, which is the expected value of a loss function which is increasing with respect to the length of the confidence interval. \nThe authors motivate the use of mean loss by constructing a mixture of two gaussians consisting of one with high mass and high variance and a second one with very small mass and small variance, so that the existence of samples from the second Gaussian is rare, but provides much more information about the shift $\\mu$ when it occurs. \n", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper gives optimal results on a very fundamental problem of location estimation in the finite sample setting. The paper is also quite well written, while highly non-trivial techniques are used.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive appreciation of our results."}, {"review_id": "X6gJURMtOR", "reviewer": "Reviewer_ng2F", "summary": "\nThis paper considers the problem of estimating an unknown shift given samples from a known density. The authors provide two estimators for this problem” a point estimator and an output interval, and they demonstrate these estimators are minimax optimal in slightly different ways. They provide an empirical evaluation of their estimators as well.", "questions": "See above\n", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall I found the paper well written and the authors did a good job motivating their constructions and the results they provided. Section 1.1 provided a solid summary that made getting through the rest of the paper easier.", "weaknesses": "\nThere were several places where I believe the paper could be improved or I struggled with the paper.\n\nMajor comments:\n1. Significance: The authors mention that this question is a fundamental one in parametric statistics, but I totally failed to understand why. I understand it’s a theory paper - but regardless, Some more motivation would help the reader understand why having better methods is important. \n2. More motivation around what algorithm 1 is accomplishing - perhaps on an example, similar to the mixture discussed in the introduction would help. I didn’t really understand why the algorithm was natural without reading the proof. \n3. Algorithm 1/3 are very much designed with the goal of being optimal with the loss function  defined in 3.1 How does that objective compare to the guarantee of previous works (i.e. the smoothed mle). In particular, those results seem a bit stronger since they guarantee convergence inference on mu through asymptotic convergence in distribution. Can the authors remark on whether a Bayes optimal estimator will have similarly strong properties?\n4. Following up on this, it would have been nice if the experimental section had been more flushed out. It was unclear what the take away was and only one example was provided. Are there regimes where the estimators of these papers perform better/worse than other estimators? Where should I expect the estimator to perform well?\n\nMinor Comments:\n1. I found the proof of Theorem 1.2 reasonably straightforward to follow however the proof of 4.3 was more challenging. I think having a picture to demonstrate the underlying geometry of the 2d Pareto front would have helped significantly. Also, the discussion in lines 284-290 was quite tricky - I still don’t fully understand what is the conditional distribution being discussed. \n2. Note that the risk function R being used in section 3.1 is overloaded in notation. You have R(hat mu, mu) vs R (pi, mu). This is not a huge problem, but I did find it a bit confusing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions and suggestions.\n\n(1) The goal of our (long-term) project is to build a finite-sample minimax theory of parametric statistics.  Classical theory is asymptotic, without finite-sample guarantees; location estimation is a simple setting to start building this theory, so we start there and already find interesting behavior.\n\n(2) See the general response: Algorithm 1 is essentially the Bayes optimal algorithm (fixing estimation error $\\epsilon$ and optimizing over failure probability $\\delta$) for $\\theta$ drawn from a uniform prior over the real line.  (This isn't an actual prior, but it's the limiting behavior).\n\n(3) Under smoothness assumptions, our estimator will also be asymptotically normal: it's an interval version of MLE, where the interval length goes to 0 as $n \\to 0$.  Without smoothness assumptions, we're not sure -- but as far as we know, it's not even known if the standard MLE is asymptotically normal under zero assumptions.\n\n(To be clear, the above is discussing asymptotic normality of $\\sqrt{n}$ times the error.  For distributions with infinite Fisher information, like the uniform distribution, the error rate is $\\ll 1/\\sqrt{n}$.  The error of our estimator then does *not* look normal at its intrinsic scale, but when scaled by $\\sqrt{n}$ it is essentially zero and hence $N(0, 0)$.)\n\n(4) The minimax estimators are, by construction, optimal. So Algorithm 1/2 (Interval MLE) will never perform worse than any other estimator, at the specified confidence level; but it may be significantly worse for other confidence levels. \nThe takeaway of the experiment is to confirm this, and to compare the overall behavior of Interval MLE vs the minimax-optimal interval estimator (Algorithm 3/4, MSE Estimator). The experiment shows that, while the MSE estimator performs slightly worse at the specified (90\\%) confidence than Interval MLE, its average case behavior is (much) better.\n\n\nMinor comment 1: We included a figure of the 2d Pareto front in the rebuttal pdf that we'll include in the final paper. Do you have any comments on it?"}, {"review_id": "vJLQmsPR1B", "reviewer": "Reviewer_b2QA", "summary": "This paper studies the problem of location estimation. We obtain n i.i.d. samples from a distribution f(x-u*) where f is known and u* is fixed but unknown. The goal is to estimate u* as accurately as possible. This is a generalization of Gaussian mean estimation though it's not as difficult of the general mean estimation because f is known. Note that for large n, maximum likelihood estimator gives asymptotically optimal performance, so the focus is on small n.\n\nThe authors present two algorithms for optimal \"average case\" and \"worst case\" behavior.\n1) Minimize estimation error |u - u*| with failure probability \\delta.\n2) Minimize length of an interval [u_l, u_r] which contains u* with probability 1-\\delta. This algorithm can be generalized to any loss function of the length of the interval, L(u_r - u_l).", "questions": "See weaknesses", "limitations": "See above", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Essentially optimal error guarantees for small n in both \"worst case\" and \"average case\" scenarios.", "weaknesses": "W1. Does not discuss running times.\nW2. Fig 2b shows that the landscape of performance is different for smaller error (and success probabilities). Is this because of how epsilon is chosen, or is it inherent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Running times.** One challenge in expressing the running time is it depends on how the distribution is represented as an input.  If it's just given as a density discretized to $N$ bins, then Algorithm 1 can be done in $O(N \\log N)$ time by an FFT convolution to compute the likelihoods.  Algorithm 2 just runs Algorithm 1 inside a binary search, so multiplies the time by log of the precision desired.\nAlgorithm 3 takes $O(N^2)$ time, and Algorithm 4 adds another logarithmic factor from binary search.\n\n**Landscape of performance.** Our algorithms depend on the desired confidence level $1-\\delta$, for which they optimize the max/average confidence interval size.  By contrast, the MLE/smoothed MLE do not depend on the desired confidence level. In Figure 2b, we asked our algorithms to optimize for 90\\% coverage.\n\nThey quite correctly outperform the competing methods at 90\\% coverage, but there is a cost: worse performance in significantly different regimes (e.g., worse median error than smoothed MLE).\nThis tradeoff is inherent to optimizing 90\\% coverage."}, {"review_id": "qSqu5Tm0Fy", "reviewer": "Reviewer_j3jn", "summary": "This work revisits one of the most basic questions in parametric statistics: location estimation. Two location estimators are proposed and proved to be optimal under different criteria.\n\nFrom the reviewer's point of view, overall this paper is well-written and easy to understand. The problem is well-motivated, and the mathematical derivation seems rigorous. I only have some minor comments.\n\n1. is it possible to provide some motivation before presenting Algorithm 1 and 2？ So readers can have a better understanding of it.\n\n2. Whether the theoretical results of classical MLE can be established under these different criteria？\n\n3. I understand due to the page limit, only one pdf is considered. Maybe some classical pdf like Gaussian can also be considered to better compare MLE and the proposed methods.\n\n4. Is it possible to put Figure 2 after Section 5. The current location is a little bit weird.", "questions": "Please see summary.", "limitations": "Please see summary.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Please see summary.", "weaknesses": "Please see summary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestions and comments.\n\nQ1: We will provide more motivation before Algorithm 1, as discussed in the overall response.\n\nQ2: There are prior works studying the finite-sample guarantees of MLE for point estimation (see [Spo11, Pin17, VdG00, Mia10]), but they tend to lose constants (at least) or make strong assumptions. We can augment the MLE into an interval estimate simply by using an interval of size equal to the estimation error guarantees in these other works, but naturally the guarantees are rather sub-optimal compared to what we show for Algorithm 3 (which is optimal).\n\n[Spo11] Vladimir Spokoiny. Parametric estimation. finite sample theory. The Annals of Statistics, 40(6):2877--2909, 2011.\n\n[Pin17] Iosif Pinelis. Optimal-order uniform and nonuniform bounds on the rate of convergence to normality for maximum likelihood estimators. Electronic Journal of Statistics, 11(1):1160--1179, 2017.\n\n[VdG00] Sara A Van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.\n\n[Mia10] Yu Miao. Concentration inequality of maximum likelihood estimator. Applied Mathematics Letters, 23(10):1305–1309, 2010.\n\nQ3:  A Gaussian pdf wouldn't be very interesting, because the empirical mean is optimal for every confidence level, and basically every method will output it.  (In the Bayesian interpretation, the posterior is Gaussian, which is symmetric.)  But we might show a Laplacian, depending on space."}]

Author rebuttal:
We thank the reviewers for the positive reviews of our work. In particular, it is encouraging that the reviewers find our work 1) tackling an important problem (reviewers cZWD, j3jn), with 2) strong motivations (reviewers ng2F, j3jn) as well as 3) using highly non-trivial techniques (reviewer cZWD) to give optimal error guarantees.
We will respond to the individual reviews.
In this overall response, we only wish to address the question of technically motivating the construction of Algorithm 1, since it was raised by both reviewers ng2F and j3jn.

Recall that Algorithm 1 is the point estimator which, fixing an estimation accuracy $\epsilon$, attains the minimax-optimal failure probability.
The key intuition is that, since we don't know what the true parameter $\theta$ is, we might as well start by constructing an estimator that is Bayes optimal with respect to the uniform prior over the real line $\theta \sim \mathrm{Unif}(\mathbb{R})$.
But, there is no such thing as a uniform prior over the real line.
So instead, Algorithm 1 is constructed to be Bayes optimal with respect to the prior $\theta \sim \mathrm{Unif}[-t,t]$, and we take the limit of $t \to \infty$ to get a translation-equivariant estimator, whose risk (failure probability) is independent of the underlying parameter $\theta$.
We then use standard tools to relate Bayes optimality to minimax optimality, under such translation equivariance.

Meta-review: The paper focuses on location estimation from samples, aiming to estimate an unknown shift $\mu$ in a probability distribution $f$ based on n samples. It covers Gaussian mean estimation as a special case. Two minimax optimal algorithms are introduced: one for minimizing failure probability by generating tight confidence intervals, and another for minimizing mean loss by considering the expected value of a length-increasing loss function. The latter is motivated by a mixture of two Gaussians, emphasizing the importance of rare samples from a low-mass, low-variance Gaussian for accurate estimation of $\mu$.
Decision: Accept (poster)