English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The study of statistical estimation without distributional assumptions ondata values, but with knowledge of data collection methods was recentlyintroduced by Chen, Valiant and Valiant (NeurIPS 2020). In this framework, thegoal is to design estimators that minimize the worst-case expected error. Herethe expectation is over a known, randomized data collection process from somepopulation, and the data values corresponding to each element of the populationare 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 anestimator for the mean with worst-case expected error that is within a factor$\frac{\pi}{2}$ of the optimum within the natural class of semilinearestimators. However, their algorithm is based on optimizing a somewhat complexconcave objective function over a constrained set of positive semidefinitematrices, and thus does not come with explicit runtime guarantees beyond beingpolynomial time in the input.  In this paper we design provably efficient algorithms for approximating theoptimal semilinear estimator based on online convex optimization. In thesetting where data values are $\ell_{\infty}$-normalized, our algorithmachieves a $\frac{\pi}{2}$-approximation by iteratively solving a sequence ofstandard SDPs. When data values are $\ell_2$-normalized, our algorithmiteratively computes the top eigenvector of a sequence of matrices, and doesnot lose any multiplicative approximation factor. We complement these positiveresults by stating a simple combinatorial condition which, if satisfied by adata 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