The study of statistical estimation without distributional assumptions on\ndata values, but with knowledge of data collection methods was recently\nintroduced by Chen, Valiant and Valiant (NeurIPS 2020). In this framework, the\ngoal is to design estimators that minimize the worst-case expected error. Here\nthe expectation is over a known, randomized data collection process from some\npopulation, and the data values corresponding to each element of the population\nare assumed to be worst-case.\n Chen, Valiant and Valiant show that, when data values are\n$\\ell_{\\infty}$-normalized, there is a polynomial time algorithm to compute an\nestimator for the mean with worst-case expected error that is within a factor\n$\\frac{\\pi}{2}$ of the optimum within the natural class of semilinear\nestimators. However, their algorithm is based on optimizing a somewhat complex\nconcave objective function over a constrained set of positive semidefinite\nmatrices, and thus does not come with explicit runtime guarantees beyond being\npolynomial time in the input.\n In this paper we design provably efficient algorithms for approximating the\noptimal semilinear estimator based on online convex optimization. In the\nsetting where data values are $\\ell_{\\infty}$-normalized, our algorithm\nachieves a $\\frac{\\pi}{2}$-approximation by iteratively solving a sequence of\nstandard SDPs. When data values are $\\ell_2$-normalized, our algorithm\niteratively computes the top eigenvector of a sequence of matrices, and does\nnot lose any multiplicative approximation factor. We complement these positive\nresults by stating a simple combinatorial condition which, if satisfied by a\ndata collection process, implies that any (not necessarily semilinear)\nestimator for the mean has constant worst-case expected error.\n