Filters

2006 - 200912010 - 20202

More filters

2019 - 201912020 - 20222
Reset filters

Settings

Publisher: Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik × Subject: complexity ×

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Semi-tractability of optimal stopping problems via a weighted stochastic mesh algorithm
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2019) Belomestny, Denis; Kaledin, Maxim; Schoenmakers, John G.M.
    In this article we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete and continuous time optimal stopping problems. It is shown that in the discrete time case the WSM algorithm leads to semi-tractability of the corresponding optimal stopping problem in the sense that its complexity is bounded in order by $varepsilon^-4log^d+2(1/varepsilon)$ with $d$ being the dimension of the underlying Markov chain. Furthermore we study the WSM approach in the context of continuous time optimal stopping problems and derive the corresponding complexity bounds. Although we can not prove semi-tractability in this case, our bounds turn out to be the tightest ones among the complexity bounds known in the literature. We illustrate our theoretical findings by a numerical example.
  • Thumbnail Image
    Item
    On the optimal combination of tensor optimization methods
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2020) Kamzolov, Dmitry; Gasnikov, Alexander; Dvurechensky, Pavel
    We consider the minimization problem of a sum of a number of functions having Lipshitz p -th order derivatives with different Lipschitz constants. In this case, to accelerate optimization, we propose a general framework allowing to obtain near-optimal oracle complexity for each function in the sum separately, meaning, in particular, that the oracle for a function with lower Lipschitz constant is called a smaller number of times. As a building block, we extend the current theory of tensor methods and show how to generalize near-optimal tensor methods to work with inexact tensor step. Further, we investigate the situation when the functions in the sum have Lipschitz derivatives of a different order. For this situation, we propose a generic way to separate the oracle complexity between the parts of the sum. Our method is not optimal, which leads to an open problem of the optimal combination of oracles of a different order.
  • Thumbnail Image
    Item
    Simple Monte Carlo and the metropolis algorithm
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2006) Mathé, Peter; Novak, Erich
    We study the integration of functions with respect to an unknown density. Information is available as oracle calls to the integrand and to the non-normalized density function. We are interested in analyzing the integration error of optimal algorithms (or the complexity of the problem) with emphasis on the variability of the weight function. For a corresponding large class of problem instances we show that the complexity grows linearly in the variability, and the simple Monte Carlo method provides an almost optimal algorithm. Under additional geometric restrictions (mainly log-concavity) for the density functions, we establish that a suitable adaptive local Metropolis algorithm is almost optimal and outperforms any non-adaptive algorithm.