{
  "id": "1712.03843",
  "version": "v1",
  "published": "2017-12-11T15:42:57.000Z",
  "updated": "2017-12-11T15:42:57.000Z",
  "title": "Breaking the Curse for Uniform Approximation in Hilbert Spaces via Monte Carlo Methods",
  "authors": [
    "Robert J. Kunsch"
  ],
  "comment": "1 figure. Based on a chapter of the author's PhD thesis arXiv:1704.08213, yet with improved results in some settings",
  "categories": [
    "math.NA"
  ],
  "abstract": "We study the $L_{\\infty}$-approximation of $d$-variate functions from Hilbert spaces via linear functionals as information. It is a common phenomenon in tractability studies that unweighted problems (with each dimension being equally important) suffer from the curse of dimensionality in the deterministic setting, that is, the number $n(\\varepsilon,d)$ of information needed in order to solve a problem to within a given accuracy $\\varepsilon > 0$ grows exponentially in $d$. We show that for certain approximation problems in periodic tensor product spaces, in particular Korobov spaces with smoothness $r > 1/2$, switching to the randomized setting can break the curse of dimensionality, now having polynomial tractability, namely $n(\\varepsilon,d) \\preceq \\varepsilon^{-2} \\, d \\, (1 + \\log d)$. Similar benefits of Monte Carlo methods in terms of tractability have only been known for integration problems so far.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-12-11T15:42:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "41A25",
      "41A45",
      "41A63",
      "41A65",
      "65C05",
      "65J05"
    ],
    "keywords": [
      "monte carlo methods",
      "hilbert spaces",
      "uniform approximation",
      "periodic tensor product spaces",
      "tractability studies"
    ],
    "tags": [
      "dissertation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}