Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error
Authors: Jonah Brown-Cohen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning Theory
Convex Optimization
Robust Estimation

Abstract: The study of statistical estimation without distributional assumptions on data values, but with knowledge of data collection methods was recently introduced by Chen, Valiant and Valiant (NeurIPS 2020). In this framework, the goal is to design estimators that minimize the worst-case expected error. Here the expectation is over a known, randomized data collection process from some population, and the data values corresponding to each element of the population are assumed to be worst-case. Chen, Valiant and Valiant show that, when data values are $\ell_{\infty}$-normalized, there is a polynomial time algorithm to compute an estimator for the mean with worst-case expected error that is within a factor $\frac{\pi}{2}$ of the optimum within the natural class of semilinear estimators. However, this algorithm is based on optimizing a somewhat complex concave objective function over a constrained set of positive semidefinite matrices, and thus does not come with explicit runtime guarantees beyond being polynomial time in the input.

In this paper we design provably efficient algorithms for approximating the optimal semilinear estimator based on online convex optimization. In the setting where data values are $\ell_{\infty}$-normalized, our algorithm achieves a $\frac{\pi}{2}$-approximation by iteratively solving a sequence of standard SDPs. When data values are $\ell_2$-normalized, our algorithm iteratively computes the top eigenvector of a sequence of matrices, and does not lose any multiplicative approximation factor. Further, using experiments in settings where sample membership is correlated with data values (e.g. "importance sampling" and "snowball sampling"), we show that our $\ell_2$-normalized algorithm gives a similar advantage over standard estimators as the original $\ell_{\infty}$-normalized algorithm of Chen, Valiant and Valiant, but with much lower computational complexity. We complement these positive results by stating a simple combinatorial condition which, if satisfied by a data collection process, implies that any (not necessarily semilinear) estimator for the mean has constant worst-case expected error.

Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error
Jonah Brown-Cohen
Chalmers University of Technology j onnhibechalmers.se
Abstract
The study of statistical estimation without distributional assumptions on data values, but with knowledge of data collection methods was recently introduced by Chen, Valiant and Valiant (NeurIPS 2020). this framework, the goal is to design estimators that minimize the worst-case expected error. Here the expectation over a known, randomized data collection process from some population, and the data values corresponding to each element of the population are assumed to be worst- case. Chen, Valiant and Valiant show that, when data values are lo normalizzd, there is polynomial time algorithm to compute worst-case expected error that is within a factor z of the optimum within the natural class of semilinear estimators. However, their algorithm based on optimizing somewhat complex concave objective function over a constrained set of positive semidefinite matrices, and thus does not come with explicit runtime guarantees beyond being polynomial time in the input. In this paper we design provably efficient algorithms for approximating the optimal semilinear estimator based on online convex optimization. In the setting where data values are &o -orrmallzee our algorithm achieves a 2 -approximation by iteratively solving sequence of standard SDPs. When data values are fz-normalized, our algorithm iteratively computes the top eigenvector of sequence of matrices, and does not lose any multiplicative approximation factor. Further, using experiments in settings where sample membership correlated with data values (e.g. "importance sampling" and "snowball sampling"), we show that our fz-normalized algorithm gives similar advantage over standard estimators as the original -ormallie algorithm of Chen, Valiant and Valiant, but with much lower computational complexity. We complement these positive results by stating a simple combinatorial condition which, if satisfied by a data collection process, implies that any (not necessarily semilinear) estimator for the mean has constant worst-case expected error.
estimator for the
with
Introduction
Standard methods in statistical analysis are often based on the assumption that data values are drawn independently from some underlying distribution, and may perform poorly when this assumption violated. Methods from robust statistics often modify this assumption, for example by allowing small fraction of data values to be arbitrary outliers while the bulk of the data values remain independent samples. However, there are natural settings which data values may be strongly correlated to sample membership. so that distributional assumptions (e.g. independence of data values) can lead to inaccurate results. Furthermore, inaccuracy of predictions in such settings can have serious societal consequences-for example predictions of election outcomes the spread of contagious disease.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Recently, Chen, Valiant, and Valiant [4] introduced a framework to capture statistical estimation in such difficult settings, by assuming that the data values are worst-case, but that the estimation algorithm is able to leverage knowledge of the randomized data collection process. The framework is simple to describe. There a set (1....n) of n indices with corresponding data values x = {z1.... Fn along with probability distribution P over pairs of subsets A, B S [1....n]. Here A is called the sample set and B is called the target set. A sample (A, B3) is drawn from P' and the values A = {x, i E A} are revealed. The goal is then to estimate the value of some function g(ZB) given only A, B and a. The quality of an estimator in this framework is measured by its worst-case expected error. Here the data values are worst-case and the expectation is with respect to the distribution P.
The worst-case expected error framework captures several natural settings where data values may be correlated to sample membership. Importance sampling is the setting where the target set B is always equal to the whole population {1.... and the sample set A is chosen by independently sampling each element E {1....7) n} with probability p;- In the worst-case expected error framework, the values z; may be arbitrarily correlated to the probability p; of being sampled, In snowball sampling [12], the elements of [I,..nn correspond to the vertices of a graph (e.g. a social network). A sample set A is chosen by first picking few initial vertices. Next, each chosen vertex recruits randomly chosen subset of its neighbors into the sample, and this process is repeated until a desired sample size is reached. The target set B can be either the whole population or subset given by few additional iterations of the recruitment process. Here it is natural to assume that the data values 2; at neighboring vertices will be highly correlated. Finally, selective prediction[10 [10, 18] is a temporal sampling method where the population {1....n) corresponds to time steps, and the goal is to predict the average of future data values given the past (e.g. the average change in the stock market). The target set B is some time window {t....t t + w) and the sample A is (1....t) .t.. If the random process for choosing the starting point and length w of the time window is chosen appropriately, sub-constant error is attainable even when the n; are chosen to be worst-case values bounded by constant[10, 18).
In [4], the authors design an algorithm for computing estimators for the mean of the target set B. In particular, they restrict their attention to the class of semilinear estimators i.c. estimators which are restricted to be linear combination of the sample values ZA, but where the weights of the linear combination may depend arbitrarily on P. A, and B. In the setting where the data values are bounded, the authors design algorithm that outputs semilinear estimator with worst-case expected error at most a 2 factor larger than that of the optimal semilinear estimator. They then demonstrate that the estimator output by their algorithm has significantly lower expected error than many standard estimators in the importance sampling, snowball sampling, and selective prediction settings where data values correlated to sample membership. However, several open questions remain, even for the case of computing the optimal semilinear estimator for the mean.
First, the algorithm in [4] is concave maximization over constrained set of positive semidefinite matrices, which is solved using a general purpose convex programming solver. In particular this means that explicit bounds on the runtime of the algorithm are given beyond being polynomial in n. This leads us to ask:
Question 1: Is there a simpler algorithm to compute semilinear estimator with approximately optimal worst-case expected error that comes with explicit runtime guarantees?
Second, the choice of fox no-ommalizztion (i.e. assuming the data values are bounded) is natural for some settings such as polling or testing for infectious disease. However, fg-orrmalization (i.c. n x? < 1) is also a natural choice for settings where some data values may be much larger than others such as predicting stock prices. This motivates:
Question 2: Is there an efficient algorithm to compute semilinear estimator with approximately optimal worst-case expected error in the Ey-bounded case?
Finally, the setting of the worst-case expected error is quite challenging, and so one would expect that for many randomized data collection processes it is not possible to achieve non-trivial worst-case expected error. Thus, one might ask:
Question 3: Are there simple properties of a data collection process that ensure that estimator can achieve sub-constant worst-case expected error?
2

---

1.1 Our Results
We answer the first two questions by designing simple algorithms based on online gradient descent for approximating the optimal semilinear estimator in both the -bounddd and the Ez-bounded case. To be able to describe our algorithms we first formally define the input.
Definition 1.1 (Definition 2 in [4]). A joint sample-target distribution P Pover (1....n} is given by the uniform distribution over m pairs (A,, B,) where A., B, S nn....n].
Because any distribution P on pairs (A, B) may be approximated to arbitrary accuracy by uniform distribution this is a reasonable choice of parametrization. In many settings the m uniform pairs are obtained by sampling sufficiently many times from the known randomized data-collection process (see supplementary material for details). Thus, one should think of m as being much larger than say at least (nn"). ). Our algorithms' runtimes also depend on a parameter p which we define to be n times the worst-case expected error of the optimal semilinear estimator.
Theorem 1.2 (Informal-see Theorem 2.3). There is an algorithm based on online gradient descent for approximating the optimal semilinear estimator to within a multiplicative & and additive error for boundde values. The algorithm runs in Ogp² log p) iterations each taking O(mme=1 + n time, where w is the current matrix multiplication exponent.
Note that when there exists a semilinear estimator achieving worst-case expected error ( the algorithm requires O()) iterations. Each iteration of the algorithm requires solving a standard SDP in dimensions with n constraints (in fact the only constraints are that the diagonal entries of the psd matrix are constrained to all be equal to one).
Theorem 1.3 (Informal-see Theorem 2.4). There is an algorithm based on online gradient descent for approximating the optimal semilinear estimator to within an additive e error for lz bo-oounded values. The algorithm runs in O(p² log p) iterations each taking ((m)) time.
In addition to the improved runtime, each iteration of the algorithm for bo-uuunded values only requires computing the eigenvector corresponding to the largest eigenvalue of an n x matrix, making the algorithm practical and simple to implement. We provide the details of both algorithms in Section 2.
Recall that the SDP algorithm from [4] obtained lower expected error than several standard estimators on various synthetic datasets where data values are correlated to sample membership. To compare to these empirical results obtained for the e -bounded case, we implement our algorithm for f-- bounded values and perform experiments on the same synthetic datasets from [4]. We find that the expected error of our algorithm on these synthetic datasets matches that of the SDP algorithm from [4], while being simpler to implement and having lower computational complexity. See Section 5 for details.
Finally, in Section 4 we answer the third question by providing simple combinatorial condition for a sample-targe distribution P, which ensures that any (not necessarily semilinear) estimator has constant worst-case expected error.
1.2
Related Work
The most closely related work is [4] which defined the framework for the worst-case expected error and designed the first algorithms in this setting. The papers [10, 18] on selective prediction are also closely related as they design efficient estimators in the worst-case expected error setting for specific choice of data collection distribution.
There has been extensive recent work on the theory and practice of robust estimation in high dimen- sions, where some fraction of data values are arbitrarily corrupted and the rest remain independent samples from the distribution [5, 16, 3, 6, 7, 8]. Most closely related to our work is the recent paper of Hopkins, Li and Zhang on robust mean estimation using online convex optimization/regret minimization [13]. While that work focuses on quite different problem setting, the high-level idea of using methods in online convex optimization to design simple and efficient algorithms for robust estimation is closely connected to our work.
3

---

1.3
Preliminaries
We focus on the setting where the data values a are real numbers and the goal to estimate the mean of the target set. Since the scales linearly with the data values, it is natural assume that the values æ lie in some bounded set C IR.. For our purposes D will either be the -ball or the f2-ball.
Definition 1.4. Given a target distribution P and a bounded set S R an estimator f A, B) is a real-valued function which takes as input the data values 24 and the sample-target index sets (A, B). The worst-case expected ervor of f on given by
Σ
Bi) - mean(xB,))
max ZED 1=1
We use ||a|| to denote the l2 norm of vector v and || to denote the &e norm. For a matrix M we use ||AM]| to denote the operator norm. For a subspace W S R", we use W to denote the orthogonal complement subspace, and write 1w for the orthogonal projection onto W.
2 Algorithms for the Worst-case Expected Error
In this section we design algorithms for approximating the best semilinear estimator for the mean using tools from online convex optimization. As in [4] we focus on the class semilinear estimators which compute a linear combination of the data values JA where the weights of the linear combination can depend on the sets and B. For convenience we introduce the notation W; C R" to denote the subspace of vectors that have non-zero coordinates only on indices in A,, Then semilinear estimator takes the form f(x A A,, B,) = (as, æ) where each vector a; E W,, To further simplify notation we denote by b, R the vector which takes value [B,]] coordinates in B; and is otherwise, so that mcan B.) (b,, x². Using this notation we have:
Definition 2.1. Given a sample-targe distribution P and a set D C R" the worst-case expected error of the optimal semilinear estimator is given by
m
opt (P)
min
max RED m
Σ
(as bi, xt)²
[a,EW;)m 1m
SDP Relaxation.
The first step to approximating the best semilinear estimator is to introduce an SDP relaxation for the inner maximization Definition 2.1. To simplify notation we make the following definition.
Definition 2.2. Let a {aI.... am where a, E W; for all Define
1 ((a) m E b,) b,)
Then the inner maximization in Definition 2.1 can be written more simply as
max ZED
T M()rr
When D = {u
E
| loo < 1} the inner maximization can be relaxed to the semidefinite IR"
program
sdp (a) max (M()). X20,X,,--1
(1)
which has optimal value within a factor 7 of the true worst-case expected error shown via the rounding method of [17]. See [4] for self-contained explanation. Therefore to approximate the best semilinear estimator it suffices to approximately solve the min-man max optimization problem
min sdp (a)

---

Algorithm via Online Gradient Descent. Our first theorem states that we can approximately minimize sd (a) with an application of online gradient descent.
Theorem 2.3. Let P be sample-target distribution, P opt(P), and e > 0. There is algorithm which computes a set of m vectors a' {ai.... dm such that
so (a') S min sd +
The algorithm runs in O ( Tog.P
(gigge
iterations, and 10 (omm + n log(1/c)) time, where
w the current matrix multiplication exponent.
Note that the parameter p depends on the optimal value of the worst-case expected error. In particular, the optimal worst-case expected error is O(2) then p = O(1), and the iteration count of the algorithm ( ). The algorithm is an application of online gradient descent where in each step we solve instance of so a) and use the solution convex cost function. The analysis is based on standard regret bounds for online gradient descent.
Algorithm 1: Online gradient descent for minimizing (d)
Input: A sample-target distribution P, accuracy parameter e, upper bound optimum p. Output: A sequence of m vectors {[1,... with E W; for all i.
Let r / mmp
2 Let B = Ei=1 [ 11.
(1) - LA, for all i.
Let a;
for t.from to 36
do
Let (t) = {al ..... (1) ). and let 1/t
(6)
n/t
Let (4) be a (1+ + 1o approxximate solution to sdp (a
a; (t+1) < di
w. (1()))) - b;) for all i.
7
m
Set A(t) min 1,
1 Er la nw, 1P
+1 I( bi return (t)) where 1" argmin, (M(al)) X(O).
(++1) < a (++1)
We now give the analysis of the algorithm using standard regret bounds for online gradient descent (see the text [11]). See the supplementary material for the referenced lemmas.
Proof. The main observation is that the algorithm is precisely online gradient descent where the convex cost function observed each step is given by fi (M (()).. Indeed viewing a as a vector in nm dimensions (one for each a;) the component of the gradient fí((a) corresponding to a, is 2 Uw, (1) (a. b.). Using the positive semidefinite Grothendieck inequality, one can show
that for the optimal solution a" lies B,, (b), the balball of radius y' at b = {b....., bm (Lemmaa A.1). Thus given an upper bound 2 opt(P) it is sufficient to limit the search to (b) for = v /=me, The last lines of the loop are just projection onto this ball (Lemma A.3). Finally, for a in (b),, straightforward calculation (Lemma A.2) gives [[V (a)]l
opt(P) centered
2
< 2nr
m
Thus the algorithm is online gradient descent with feasible set diameter 2r and gradients bounded by G 2nr Thus by the textbook analysis of online gradient descent [11] we have
min (b) T Σ ())
1 T t=1
Σ fe(a')
<
3GD T
3rmp
VT
Letting a" = argmin, sdp (a) (which we know is contained in (b)))) we have
Σ ()) - Σ Je(a") <
3xnp
VT
5

---

Noting that f((a") = (M(a"), x - <ddp (a*) yields
T Σ f((a sd (a") 3rmp
vT I sdpo
where the last line follows from the choice of T 36x n have
For t, argmin, fe(a!!) therefore
(M(al")) x(1)) = f((alt)) I sdp (a') (
Since the value of sdp (a*) bounded, the fact that x is multiplicative (1 1 approximation implies that x((*) is an additive 5-approximation to (alt)) (see Lemma A.4). Thus we conclude that
max (M (3 x) (((a(()))xx11 + s sdp (a") te adpx(aal)) X
L.c. (!")) is an
of mina sd
To analyze the runtime note that each iteration requires approximately solving instance of (a!"), multiplying the solution (() by each vector a!" ((()) and then rescaling by (() First, the matrix M (a) can be constructed in time O(mn"~1) by grouping the vectors a;
(t) 6, into
blocks of size n x n,, and using fast matrix multiplication for each block. Next, using the fact that ((a)
is positive semi- cenineefiitee the approximate solution (() can be computed in time Onn using the interior point SDP solver of [14] (see Lemma A.4 for details). Finally, we can group the vectors a ( columnwise into matrices of size n x n, and then use fast matrix multiplication to compute the product of each matrix with ((). This results in runtime of 01mm²~1) where is the current matrix multiplication exponent. Finally, (+) can be computed in O(m)) time. Putting all together there are O Q(='n" iterations each of which takes Ö(mm~~1 1 + n 7/2 log(1/e)) time, given upper bound p 2 opt(P). We can find an upper bound that is at most 2 opt((P) (P) by starting with nn and repeatedly doubling at most log(n (pt(())))) O(log p) times. This yields the final iteration count of l)
22-norm Bounded Values. We now turn to the setting where the data values are bounded in f--mrrm ie. when = {a E R" |||||| S vn). In this case the inner maximization in Definition 2.1 is equal to times the maximum eigenvalue of (a)
sdpz(a) = max T
The choice of normalization is such that the second moment is one i.e. =3= = 1. A subtle difference in the bg-bounded setting is that opt(P) may not be bounded by constant for certain pathological examples. This is unlike the f bounded setting where choosing a to be the all zeros vector immediately gives upper bound of opt(P) < 1. However, if the target distribution is the full population mean (i.e. by = for all i), then setting a to all zeros and applying Cauchy-Seti Cauchy-Schwarz yields
opt S max
1
Σ
m
(be,
x)
1
|
m
m
n
More generally, only makes sense to compute estimators approximating the worst-case expected error when the achievable error goes to zero with n i.e. opt(P)= o(1). Therefore, for the fz-bounded setting we make the additional assumption that opt (P) < We now state our main theorem for the lz-bounded setting.
Theorem 2.4. Let P be sample-target distribution with opt. $ p= n opt(P), and > 0. There an algorithm which computes a set of m vectors a' ........ amm such that
sdpz(a') < min sdpz (a) te.
The algorithm runs in logg
iterations and takes ( (215emm)) time.

---

If the optimal worst-case expected error is opt(P) = 0( then O(2²) iterations suffices, and each iteration takes ( mm) time. The algorithm for the & fz-bounded case is also an application of online gradient descent, where in each step we solve an instance of sdp, (a) and use it as convex cost function. However, the fact that sdp, (a) corresponds to computing the maximum eigenvalue of an x matrix leads to the improved runtime per iteration of O (m)))
Algorithm 2: Online gradient descent for minimizing sdp2(a).
Input: A sample-target distribution P. accuracy parameter e, upper bound on optimum p. Output: A sequence of m vectors a = {a1,...am) with 0z E W; for all i.
Let
/mp
Let B
D i- [ W. 6111?. 1 LA, for all
Let a;
A.l
36 do
for t f.from 1 to
<²
Let (t)) {a1 (1)
a and let 7). nvt
Let (11) =x.. where 2n is + 1o) approximate solution sdp2 (a()
(1+1) c =a!" T1I I.. X (a (1) b;) for all i.
dj
2 &PP Set ((1) min 1, V Ee
Mw, bi- 10 return (t") where = argmin ( (M(al)), X(0).
(+++) a10 (++1) (1
To summarize briefly, the fz-bounded algorithm can be essentially obtained by modifying Algorithm 1 by letting (() _ where ze is an 2 aadditive-approximate eigenvector of M (a)). The improved rumning time follows from two points. First, the classical power method can compute the required eigenvector in mm time. Second, computing the gradient requires multiplying (a -b,) for all i, just as in Algorithm 1. However, since in the 62-bounded case X = ou" is rank one, each multiplication can be carried out in (n) time, for total cost of O(m)). The full details of the analysis can be found in Section B in the supplementary material.
3 The algorithm of Chen, Valiant and Valiant
At this point it is instructive to compare Algorithm I with the original SDP-based algorithm of [4]. In Appendix C of [4] the authors show how to approximate any sample-target distribution P by drawing at most m poly(? (2) samples. Thus should be generally thought of as large polynomial in n. The approach taken in [4] to approximate the optimal semilinear estimator is based on first replacing the inner maximization in Definition 2.1 with (a). This only incurs error of at most a factor of 2. and additionally means that the problem is convex in a = {ai.... am and linear in X. Thus the min-max theorem applies and the min and max be exchanged, resulting in inner minimization over a which can be solved explicitly. This gives rise to a somewhat complicated semidefinite program where the objective is concave maximization depending on the inverse of the variable matrix.
The authors note that this SDP can be converted to more standard SDP by using the Schur comple- ment to re-express the matrix inverse. However this conversion increases the number constraints in the SDP to at least m. The best known interior point solver [14] has runtime O(Vnnmmn2 m + +*))) for general SDP with an n dimensional PSD matrix variable and constraints. The dominant term in our setting is Ö(Vrum"). For example, in [4] is Ón where we have used the fact that the current matrix multiplication exponent is approximately
On²2) then the runtime for the general SDP solver
2.37. The runtime of Algorithm in this setting is O Depending the achievable worst-case expected error, p can range from O(1) to O(n). so the runtime of Algorithm ranges from 4n773 6.377 all of which are faster than O(n7.61) for [4].
To summarize, after making the appropriate reductions, the algorithm of [4] requires solving an SDP with (m) constraints. In contrast, the SDP solved in each iteration of Algorithm has exactly
7

---

constraints. Therefore, given that SDP solvers have runtimes polynomial in the number of constraints, and that in our setting we should think of m > n. Algorithm 1 will tend have faster runtime even though it solves an SDP in each iteration.
4 A constant lower bound
In this section we identify simple combinatorial condition that ensures the worst-case expected error of any estimator for the mean is at least a constant. Of course is possible to construct trivial examples of sample-target distributions P for which constant lower bound holds. For example, nt consider a distribution P where the samples A, S (1, T and B, C 1 + 1,...n) n) for all In this case, given any estimator A A, B), worst-case adversary is free to set the data values 2j for
j 2 arbitrarily in order to maximize (f A, A,, B,) mean ( ))², these values never appear as imput to Indeed, since the estimator has zero probability of ever observing one of the data values ry for j 7, there is hope of estimating the mean of these values under worst-case assumptions.
To go beyond the trivial case it makes sense to require that every data value has some non negligibbe probability under P of being included in sample set A. We will show that even in this case, the worst-case expected error can be constant. In fact, the condition we identify can hold for distributions P where each coordinate i is equally likely to be included in A.
Definition 4.1. Let a be constant. sample-target distribution P is a-non-expanding if there exists subset C n.) such that for an a-fraction of the pairs (A,, B,) exactly one of the following holds:
A S S and B, n S
2. A, A and B, S
For example, the definition is satisfied with a 1 by the distribution which half the time picks uniform random subset A from the first half of indices and B from the second half, and half the time does the opposite. More subtle examples are possible where the subset S is arbitrary and a < so that a constant fraction of sample and target sets can have arbitrary intersection with S.
Theorem 4.2. Let P be e-poon-xpanding tarpee- distribution. For any estimator A,
1 =1 TI Σ A, ))
Proof. Let be the subset provided by Definition 4.1. Without loss of generality we may assume that A, C S and B, S at least for least _ fraction of pairs (A,, B.). Otherwise could just switch the roles of S and S. Let be the median of f(1 Ary A,, B,) on this fraction. If is positive let E be the at least & fraction of indices for which f[1A, A;, B,) 2 if is negative let E be the least e fraction of indices for which f(1 Ag A., B;) c. Set xj 1 for all j E S and
sign(c) for all j & S. Since A; C S and B, n = @ for all i E we have
272
(f(AA, A, me)n(
Σ (f(=A, B,) mean(z;,))
m
VEE
Σ (f(1,, A,: A,, B₂) sign()))
YEE
(c si))
IV
where the final inequality follows from the fact |c+ sign(c)) for all R.
5
Experimental Results
In this section we empirically evaluate Algorithm 2 in settings where data values are correlated to inclusion in sample. In [4] the authors show that solutions to argmin,, sdp (a) clearly outperform

---

standard choices for estimators in such settings, However, their algorithm requires using the general purpose convex programming solver MOSEK [2] via the CVXPY package [9, 1]. which can be quite slow and memory intensive. We implement Algorithm 2 in Python, and run the algorithm on the same synthetic datasets as those in [4]. For the algorithm of [4] we use the publicly available code at https://// thub. com/justc2//e /ttuusccccossttteeeeeeeeesssssst wtts:/ootttttttteeeeoo case- r y col-ccceeeeee We find that Algorithm 2 has comparable empirical performance to the original algorithm of [4], while being simpler and more computationally efficient. For more details of the experiments please see the supplementary material.
Importance Sampling Importance sampling, where elements are sampled independently but with different probabilities, is one of the simplest examples where data values may be correlated with sample membership. In this experiment the population size is = 50 and the element i is included in the sample with probability 0.1 for i ك 25 and probability 0.5 for > 25. We compare both Algorithm 2 and the sd -based algorithm from [4] with two standard estimators for this setting. The first estimator is reweighting which computes the weighted mean of the Z;, where the weight of each xi is the reciproeal of the probability that x; is included in the sample. The second is subgroup estimation which computes the sample means of zy for S 25 and I; for > 25 separately, and then averages these two sample means.
We evaluate the results on three synthetic datasets: (1) Constant where x; = 1 for all i. (2) Intergroup variance where 2; = 1 for i S 25 and z; -1 for > 25. (3) Intragroup variance where r; 1 for odd indices and z; = - for even i. We also report worst-case fo and Eg error by solving sdp, (a) and sdpy(a) for each estimator. The expected squared errors for each estimator and dataset in this experiment appear in Table 1. Note that on the three synthetic datasets the sdp, algorithm from [4] and Algorithm have essentially identical expected error, while the former has lower sdp error and the latter has lower sdp, error as one might expect. Furthermore, the error on the synthetic datasets is consistently low for Algorithm 2, while the standard estimators each have large error for least. one setting where data values are correlated to sample membership.
Data Values
Reweighting
Subgroup Estimation
sdp Alg. [4]
Algorithm 2
Constant (r: 1)
0.100
0.018
0.051
0.052
Intergroup Variance
0.100
0.018
0.053
0.052
Intragroup Variance
0.100
0.121
0.052
0.053
Worst Case sdp
0.101
0.122
0.053
0.062
Worst Case sdp,
0.181
0.222
0.088
0.078
Table I: Expected squared error for importance sampling experiment
Snowball Sampling In our snowball sampling experiment we randomly draw n 50 points in the two dimensional unit square to be the population and let the target set B be the entire population. We construct a sample by first picking a random starting point, and then iteratively adding to the sample two of the five nearest neighbors of each point added so far, until & = 25 points are included in the sample. We compare Algorithm and the sdp...bbaee -based algorithm from [4] with the estimator that simply computes the sample mean. We evaluate these estimators on dataset of spatially correlated values by setting x, equal to the sum of the two coordinates of the point in the unit square corresponding to element i. We also report worst-case &oo and & error by solving sdp (a) and sdpz(a) for each estimator. The expected squared errors for each estimator and dataset in this experiment appear in Table 2. As in the previous example, we see that the sdp.c algorithm and Algorithm have equal error on the synthetic dataset (both clearly outperforming the sample mean estimator), and each algorithm does better than the other the worst-case data values it was designed to optimize.
Data Values
Sample Mean
sdp Alg. [4]
Algorithm 2
Spatially Correlate Values
0.082
0.032
0.032
Worst Case sdp
0.690
0.135
0.153
Worst Case sdp,
0.747
0.327
0.326
Table 2: Expected squared error for snowball sampling experiment

---

Selective Prediction In the selective prediction experiment the population consists of n = 32 timesteps, and the goal is predict some future target time window {t.....* t + w) given the sample consisting of the past {1,... 4). Here < n is chosen uniformly at random, and w is chosen uniformly from {1, 2, 4, 8, 16). In this setring we compare the sdp algorithm from [4] and Algorithm 2 with the selective prediction estimator of [10, 18). The selective prediction estimator simply computes the mean of the final w elements of the sample {L....6 I., and is known to achieve expected worst-case error O I ). We evaluate the worst-case &o and 6g error of these by solving sdp (a) and sapz(a) and report the results in Table 3. As in the previous cases both the sdp algorithm from [4] and Algorithm 2 outperform the selective prediction estimator, and each of the two algorithms outperforms the other the worst-case data values of the appropriate type.
Data Values
Selective Prediction
sdp Alg. [4] Algorithm 2
Worst Case sdp
1.208
0,498
0.620
Worst Case sdp,
1.371
0.746
0.686
Table 3: Expected squared error for selective prediction experiment.
Funding Disclosure
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
References
[1] AGRAWAL, A., VERSCHUEREN, R., DIAMOND, S., AND BOYD, S. A rewriting system for
convex optimization problems. Journal of Control and Decision 5, I (2018), 42-60.
[2] APS, M. The MOSEK Optimizer API for Python 90., 2019.
[3] BALAKRISHNAN, S., DU, S. S., LI, J., AND SINGH, A. Computationally efficient robust sparse estimation in high dimensions. In Proceedings the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017 (2017), Kale and O. Shamir, Eds., vol. 65 of Proceedings of Machine Learning Research. PMLR, pp. 169-212.
[4] CHEN, J. Y., VALIANT, G., AND VALIANT, P. Worst-case analysis for randomly collected data. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual (2020), H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds.
[5] DIAKONIKOLAS, I., KAMATH, G., KANE, D., LI, J., MOITRA, A., AND STEWART, A. Robust estimators in high-dimensions without the computational intractability. SIAM J. Comput.
48, 2 (2019), 742 864.
[6] DIAKONIKOLAS, I., KAMATH, G., KANE, D. M., J., MOITRA, A., AND STEWART, A. Being robust (in high dimensions) can be practical. In Proceedings the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 (2017), D. Precup and Y. W. Teh, Eds., vol. of Proceedings of Machine Learning Research, PMLR, pp. 999-1008.
[7] DIAKONIKOLAS, I., KAMATH, G., KANE, D. M., LI, MOITRA, A., AND STEWART, A. Robustly learning a gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (USA, 2018), SODA '8, Society for Industrial and Applied Mathematics. p. 2683-2702.
[8] DIAKONIKOLAS, I., KANE, D. M., AND STEWART, A. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA, 2018), STOC 2018, Association for Computing Machinery, p. 1047-1060.
[9] DIAMOND, S., AND BOYD, S. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research 17, 83 (2016), 1-5.
[10] DRUCKER, A. High-confidence predictions under adversarial uncertainty.
10

---

[11] HAZAN, E. Introduction to online convex optimization, Found. Trends Optim. 3-4 (2016), 157-325.
[12] HECKATHORN, D. D. Respondent-driven sampling ii: Deriving valid population estimates from chain-referral samples of hidden populations. Social Problems 49, (2002), 11-34.
[13] HOPKINS, S. B., LI, J., AND ZHANG, F. Robust and heavy-tailed mean estimation made simple, via regret minimization. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual (2020), H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds.
[14] JIANG, H., KATHURIA, T., LEE, Y. T., PADMANABHAN, S., AND SONG, 7. A faster interior point method for semidefinite programming. In 6 IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16- 2020 (2020), IEEE, pp. 910-918.
[15] KUCZYNSKI, J., AND WOŻNIAKOWSKI, Estimating the largest eigenvalue by the power and lanczos algorithms with random start, SIAM Journal on Matrix Analysis and Applications 13, 4 (1992), 1094-112)
[16] LAI, K. A., RAO, A. B., AND VEMPALA, S. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (2016), pp. 665-674.
[17] NESTEROV, Y. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software 9, 1-3 (1998), 141-160.
[18] QIAO, M., AND VALIANT, G. theory of selective prediction. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA (2019), A. Beygelzimer and D. Hsu, Eds., vol. 99 of Proceedings of Machine Learning Research, PMLR, pp. 2580-280002 2594..


Reviews:
[{"review_id": "y6fuD_w0XGB", "reviewer": "Reviewer_52Vh", "summary": "The authors build on the work of Chen, Valiant and Valiant from NeurIPS 2020 on estimators minimizing the worst-case expected error by providing two new algorithms for the same problem formulation, but with explicit runtime guarantees. The first algorithm uses a standard semidefinite program within a gradient descent loop to arrive at a runtime that is (with some abusive simplification) $\\tilde O(mn^5 \\log n/\\epsilon^6)$. The second relaxes the setting so that data values are bounded in $\\ell_2$ norm (rather than $\\ell_\\infty$), and uses this new setting to reduce the runtime to $O(mn^3 \\log n/\\epsilon^3)$. As far as I can tell, these algorithms don't offer any guarantees on sample complexity, but the newly explicit runtime guarantee is (subject to questions below) an improvement. As an impossibility result, the authors provide a combinatorial condition on the sample-target distribution under which the worst-case expected error for all estimators is at least a constant. Finally, the authors verify their new algorithm experimentally, showing comparable performance to [4] but faster runtime.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Clarity:** I thought the description of the framework from [4] and this work's intended contributions are very clear and the authors deserve credit and appreciation for this. There is perhaps some lack of clarity about certain points of differentiation, which I ask more about below and potentially suggest that the authors address in the main paper (rather than only supplementary). But the general thrust of the work is clear. The authors choose notation judiciously to aid communication and succinctness. The algorithms as written are mostly clear. The proofs, without the supplementary material, give a good understanding of the tools used to arrive at the results. The authors also articulate well how Algorithm 2 differs from Algorithm 1, and what about the additional structure leads to the improvements.\n\n**Quality:** I checked the first and last paragraphs of the proof of Theorem 2.3, which is what I would consider to be the main result of this paper. I did not thoroughly check lines 194–201, nor did I peruse the lemmas in the supplementary material, or [16] (which was cited for the SDP solver, see questions below). Otherwise, the proof seemed reasonable to me and I did not detect any errors or problems with it. I felt that the understanding from this result carried over comfortably to Theorem 2.4. I also felt that the result in Theorem 3.2 was probably sound, but I did have one sticking point to clarify:\n\n_Clarification in the proof of Theorem 3.2._ I couldn't quite follow the second-to-last step of the proof of Theorem 3.2 (line 264). I would have assumed that this follows directly from the definition of $c$ as $f(\\mathbf{1} _ {A_i}, A_i, B_i) \\ge c$. But I couldn't see how this would work when the median $c$ happens to be negative, since then $|f(\\mathbf{1} _ {A_i}, A_i, B_i)|$ might be less than $|c|$.\n\nAs a counterexample for this step, imagine that $m = 8$ and $\\alpha = 1$, so there are 4 samples in the category of interest, and consider $f(\\mathbf{1}_{A_i}, A_i, B_i) = -i$ for $i = 1, \\dots, 4$. Then I get $c = \\frac{-5}{2}$ and\n\n$$\\frac18 \\sum_{i \\in E} [f(\\mathbf{1}_{A_i}, A_i, B_i) + \\mathrm{sign}(c)]^2 = \\frac{13}{8} < \\frac{49}{16} = \\frac14 [c + \\mathrm{sign}(c)]^2.$$\n\nThis probably doesn't disprove the theorem—if I'm not mistaken, I imagine this is probably quite easily resolved with some trivial definition swaps?\n\n**Originality/Significance:** I hadn't come across [4] before reviewing this paper, so couldn't claim any knowledge of the area sufficient to fully assess originality and significance. However, it seems like [4] was the (or at least an) original work in this area, in which case this work seems clearly novel. I think the results, if the questions in this review are resolved, are very likely to be of interest to this community, because they make some promising headway into the open questions left by [4].\n\nI'm not 100% sure on the following remark, but my understanding of this paper is that the authors claim that using online gradient descent can reduce the complexity of the SDP that is required to be solved as part of these algorithms (see questions below). If this is true, that seems like a significant insight and I would expect similarly interested researchers to build on these contributions.\n\n**Questions about relationship with Chen, Valiant and Valient (2020) [4]:** I spent some time trying to understand precisely what the claimed improvements and sacrifices are relative to the algorithm provided in [4]. The description in Section C of the supplementary material was very helpful for this and I was a little surprised it didn't feature in the main paper. But a few questions remain that I hope the authors can address, perhaps by making minor revisions to the paper.\n\n1. Since [4] made a claim about sample complexity, I tried to understand how the algorithms in this paper fare in terms of sample complexity. The authors didn't address this in the main paper, but argue in Section C that since Appendix C of [4] offers an approximation drawing $m = \\mathrm{poly}(n, 1/\\epsilon)$ samples (lines 472–473):\n  >Thus $m$ should be generally thought of as a large polynomial in $n$. In contrast, both of our algorithms never use more than $O(mn)$ space […]\n\n    Wouldn't, at a minimum, a similar argument that $m = \\mathrm{poly}(n, 1/\\epsilon)$ samples are necessary also apply to this work, in cases where $m$ _samples_ are taken, rather than just being the support size of $P$? What is it allows this work to treat $m$ as something less than $\\mathrm{poly}(n, 1/\\epsilon)$?\n\n    Otherwise, my comment was going to be that I think it's fine for the authors not to offer sample complexity guarantees in this work (or to simply require that the entire sample-target distribution $P$ be specified, as [4] did in Theorem 3), but it should be mentioned explicitly as a limitation, trade-off or open question.\n\n2. If I understood correctly, the algorithm in [4] is basically an SDP, [4] doesn't really address its runtime beyond saying it runs in polynomial time. In this work, the more explicit runtime guarantees are great, but the algorithm incorporates an SDP solver run once per iteration, for which they cite the runtime complexity provided by [16]. Why could this same solver from [16] and Lemma A.4 not be used on the SDP on which [4] relies?\n\n    Again, Section C was of some assistance here. But the discussion merely suggested that the SDP in [4] is \"somewhat complicated\", and that the Schur complement conversion suggested in [4] requires $O(mn^2)$ memory. But memory use wasn't really discussed in the main paper, and I was still lost what this means in terms of runtime.\n\n    Perhaps I'm asking the wrong question, but I think I was hoping for a discussion of why the SDP solver suggested in this work would not have worked as a much more straightforward improvement to [4]. That would have then offered some insight into why wrapping the SDP in online gradient descent can be an improvement over the single-shot SDP strategy of [4].\n\nDepending on what the answers are to these questions, I may suggest addressing them in the main paper (even if only briefly) rather than only in supplementary material.\n\n**Summary:** In summary, my assessment of this paper is generally positive, but conditioned on an understanding of the paper's core claims that I'm not totally certain about, and therefore dependent on the authors' assistance in addressing my questions above. I thank the authors in advance for their attention.\n\n--------------------------\n\n**Minor potential typos:** (for authors, not part of assessment)\n- Line 188, is that meant to say $\\frac{2}{m} \\Pi_{W_i} X^{(t)} (a_i - b_i)$ rather than $\\frac{2}{m} \\Pi_{W_i} X^{(t)} a_i$?\n- Line 207, was \"sdp\" meant to be capitalized?\n- In the first two display math lines of line 264 (proof of Theorem 3.2), should the top limit in the summation sign $\\sum_{i \\in E}^m$ be removed, so that it's just $\\sum_{i \\in E}$?\n\n--------------------------------\n_Edit 02 Sep 2021: Fix whitespace/indentation, and change $\\mathrm{poly}(n/\\epsilon)$ to $\\mathrm{poly}(n, 1/\\epsilon)$._", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is almost entirely theoretical in nature and I don't foresee any direct societal impact as a result of this work.\n\nI felt some (non-social) limitations of this work were not addressed in this paper as well as they could have been, most notably the one about sample complexity I mentioned in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "mpV9etQ72-U", "reviewer": "Reviewer_Lwob", "summary": "This paper studies the recently introduced *worst-case expected error* framework of Chen-Valiant-Valiant [4]. In this setting the data values are worst case, but the statistician has knowledge of the data-generating process. The authors provide new efficient algorithms based on alternating minimization-maximization for estimating the mean in worst-case under the previously studied $\\ell_\\infty$ assumption [4] on the dataset as well as under a new $\\ell_2$ assumption. The authors also provide a simple combinatorial condition denoting when the worst-case error is $\\Omega(1)$, and thus consistent estimation is not possible in this setting. Experiments compare their $\\ell_2$ algorithm with the algorithm proposed by [4]  on synthetic data in the settings of importance sampling, snowball sampling, and selective prediction. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Originality**: The authors make an interesting connection between the worst-case expected error objective and online optimization that enables them to introduce efficient algorithms with explicit run-time bounds. The authors also introduce a new $\\ell_2$ assumption on the data that may be useful in some applications. The constant lower bounds are also new and shed further light on the degree of pessimism of this framework; in addition they apply to *any* estimator, not just the semilinear ones that were originally studied. One weakness along these lines is that there are no new examples given where this framework can be applied; the three examples studied were already introduced in [4]. The existing literature is well-described. \n\n**Quality**: I have not checked the details in the appendix, but the arguments in the main text appear to be correct and use standard tools (albeit with clever application). The results are all interesting and provide a better understanding of this estimation framework as well as improved and explicit computational guarantees, improving on [4] where the bounds are polynomial-time but not explicit. I was a bit disappointed that Algorithm 1 was not evaluated empirically against the algorithm in [4]. This makes me concerned that the explicit bounds are still quite large (requiring $\\varepsilon^{-8}$ iterations) and do not necessarily imply that Algorithm 1 is more computationally efficient than [4]. It would strengthen the paper to clarify this. On the other hand, it is interesting how the $\\ell_2$ algorithm performs similarly to the algorithm from [4] in most cases.\n\n**Clarity**: The paper is well-written and enjoyable.\n\n**Significance**: The worst-case error framework is interesting, new, and still not yet well-studied, so this line of results is a welcome contribution that could inspire further study. Along these lines, it would benefit the paper to have some discussion of open problems and future directions for studying this framework.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Minor issues and typos:\n- p2 Line 73: replace \"minimization\" with \"maximization\"\n- p3 Line 101: replace \"say at least $O(n^2)$\" with \"say $\\Omega(n^2)$\"\n- p3 Theorem 1.2: I found the informal statement hard to parse because of the confusing phrase \"within a multiplicative $\\pi/2$ and additive $\\varepsilon$ error\". Please rephrase this\n- p5 Line 188: I believe that the gradient (without projection) is actually $\\frac{2}{m} X^{(t)} (a_i - b_i)$ and that the update in Line 7 of Algorithm 1 represents the projection of this gradient onto $W_i$ (*ie* back onto the feasible set). Is that correct? There is a similar statement in the Appendix for the $\\ell_2$ that should also be fixed if so. \n- p7 Definition 3.1: Very minor, but the term \"$\\alpha$-non-expanding\" is a bit unwieldy. I suggest the terminology \"$\\alpha$-separated\".\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "a3Mzdk8Nq0j", "reviewer": "Reviewer_R91w", "summary": "This work builds on a recent statistical estimation framework of Chen, Valiant,\nand Valiant [NeurIPS`20] that leverages knowledge about how samples are\ncollected but makes no distributional assumptions on the data values. The\nauthors explore three important questions in this space:\n\n(1) Is is possible to compute a semilinear estimator for the $\\ell_\\infty$ case\nthat achieves the same approximation quality as that of Chen-Valiant-Valiant,\nwhile also emitting explicit running time bounds?\n\n(2) Is there an algorithm to compute a high-quality semilinear estimator in the\n$\\ell_2$-bounded case?\n\n(3) Are there simple properties of a data collection process that guarantees no\nestimator can achieve sub-constant worst-case expected error?\n\nThe results answer all three questions affirmatively. The authors show that\nonline gradient descent can be used to design simpler SDP-based algorithms,\nanswering (1) and (2). They also quantify a combinatorial property of joint\nsample-target distributions that, for any estimator, necessarily incur at least\na constant error. The paper then presents experiments based on those in\n[Chen-Valiant-Valiant, NeurIPS`20] to demonstrate the effectiveness of their\ngradient descent-based approach.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "*Originality.* This work builds on a fairly new problem introduced by Chen,\nValiant, and Valiant in NeurIPS`20, whose aim is to study statistical\nestimation when data values are correlated with sample membership. The\nalgorithms proposed in this paper consider an SDP relaxation of the objective\nfunction and then use traditional online gradient descent-based methods to\nachieve the same approximation factor as Chen-Valiant-Valiant for the\n$\\ell_\\infty$ case, but with an explicit bound on the running time. The\nmultiplicative approximation factor in both cases is the result of the SDP\nrelaxation. The extension to the $\\ell_2$ case, together with the simple but\nnovel constant lower bound in Section 3, are nice contributions towards the\noriginality of this work.\n\n*Quality.* Overall, this work is a nice extension of Chen-Valiant-Valiant. The\nmain results are incremental in some sense, but the approach is cleaner and\nallow for further generalization (e.g., the $\\ell_2$-bounded case). The\nexperiments do not really stand out, but they also don't detract from the\nquality of the paper.\n\n*Clarity.* The paper is written pretty well. The introduction could do a better\njob motivating the model, but the message that it generalizes importance\nsampling, snowball sampling, selective prediction, etc. comes across well\nenough. The algorithms and analysis are quite clear, but the paper could\nbenefit from setting up the joint sample-target distribution definition in more\ndetail.\n\n*Significance.* The least compelling part of the paper, in my opinion, is the\nmodel itself (introduced in previous works). Given the problem, the algorithms\npresented seem like good approaches, even though they are mostly theoretical\nand rely on solving SDPs.\n\n*Typos / Suggestions*\n- [41] Missing a ',' in the set of data values.\n- [57] Missing space in \"selective prediction[10, 17]\"\n- [95] Even though Definition 1 references [4], the definition is initially\n  somewhat unclear / ambiguous to me. A small example would be helpful, or an\n  explicit definition.\n- [110] Typo: \"psd\" --> \"PSD\"\n- [118] Nit: \"Recall that the SDP algorithm...\" -- the reader might never have\n  read [4], and hence can't recall. I suggest just saying that \"The SDP algorithm...\"\n- [207] Typo: \"sdp\" --> \"SDP\"\n- [249] Suggestion: Italicize \\alpha-non-expanding since its the term being defined.\n- [347] Journal is missing for Drucker reference [10]", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6ki7LuIMMrg", "reviewer": "Reviewer_FKv3", "summary": "This paper studies the _worst-case expected error framework_ of statistical estimation proposed by Chen, Valiant, and Valiant, where data values are worst-case, but the estimation algorithm exploits randomness in the data collection process.\nIn this worst-case expected error framework, there are $n$ data values $x_1$ to $x_n$ and a probability distribution $P$ over pairs of subsets $A, B \\subseteq {1, \\ldots, n}$, where the variables $x_A$ over the sample set $A$ are revealed, and we want to estimate the value of some fixed function $g(X_B)$ of the variables $x_B$ over the target set $B$.\nRestricting attention to _semilinear_ estimators, which are linear combinations of the sample values whose weights could depend on the sample-target distribution $P$ or the indices $x_A$ and $x_B$ of the sample and target variables, Chen, Valiant, and Valiant gave a complicated semilinear estimator for the mean of the target set $B$ which is at most $\\pi/2$ factor larger than the optimal semilinear estimator, when the data values are $\\ell_\\infty$-bounded.\n\nThis paper presents the following three results:\n1. a simpler algorithm to compute a semilinear estimator within a multiplicative $\\pi/2$ factor and an additive $\\epsilon$ factor for $\\ell_\\infty$-bounded values, with explicit efficient runtime guarantees.\n2. an efficient algorithm to compute a semilinear estimator within an additive $\\epsilon$ error for $\\ell_2$-bounded values.\n3. a family of lower bound instances where all estimators (not necessarily semilinear) must have at least constant error, which generalizes the trivial lower bounds of disjoint $A$ and $B$.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "1. The main idea in the algorithms is to apply online gradient descent to solve an SDP relaxation arising from optimizing semilinear estimators.\n2. This reader would appreciate more motivation of studying the generalized lower bounds, given that there are trivial lower bounds.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This theoretical-inclined paper does not discuss societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper continues a line of investigation initiated by Chen, Valiant, and Valiant in NeurIPS'20. That work proposed a new model of statistical estimation for worst-case data that is randomly collected and gave a polynomial time algorithm minimizes the expected error. The current work provides a significantly faster algorithm for this problem, matching the guarantees of the previous work, when the data is bounded in $\ell_{\infty}$-norm. Moreover, additional (new) results are obtained in the current work, e.g., for the setting that the data is bounded in $\ell_2$-norm. At the technical level, the proposed algorithms rely on some version of online gradient descent, as opposed to black-box convex optimization in the previous work. With the exception of one reviewer (who was unconvinced about the model itself, i.e., the prior NeurIPS'20 work), the reviewers ranked this paper above the acceptance threshold.
Decision: Accept (Poster)