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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We give a polynomial time approximation scheme (PTAS) for computing thesupremum of a Gaussian process. That is, given a finite set of vectors$V\subseteq\mathbb{R}^d$, we compute a $(1+\varepsilon)$-factor approximationto $\mathop {\mathbb{E}}_{X\leftarrow\mathcal{N}^d}[\sup_{v\in V}|\langlev,X\rangle|]$ deterministically in time $\operatorname{poly}(d)\cdot|V|^{O_{\varepsilon}(1)}$. Previously, only a constant factordeterministic polynomial time approximation algorithm was known due to the workof Ding, Lee and Peres [Ann. of Math. (2) 175 (2012) 1409-1471]. This answersan open question of Lee (2010) and Ding [Ann. Probab. 42 (2014) 464-496]. Thestudy of supremum of Gaussian processes is of considerable importance inprobability with applications in functional analysis, convex geometry, and inlight of the recent breakthrough work of Ding, Lee and Peres [Ann. of Math. (2)175 (2012) 1409-1471], to random walks on finite graphs. As such our resultcould be of use elsewhere. In particular, combining with the work of Ding [Ann.Probab. 42 (2014) 464-496], our result yields a PTAS for computing the covertime of bounded-degree graphs. Previously, such algorithms were known only fortrees. Along the way, we also give an explicit oblivious estimator forsemi-norms in Gaussian space with optimal query complexity. Our algorithm andits analysis are elementary in nature, using two classical comparisoninequalities, Slepian's lemma and Kanter's lemma.

A polynomial time approximation scheme for computing the supremum of Gaussian processes