5 results
Search Results
Now showing 1 - 5 of 5
- ItemSemitractability of optimal stopping problems via a weighted stochastic mesh algorithm(Oxford [u.a.] : Wiley-Blackwell, 2020) Belomestny, Denis; Kaledin, Maxim; Schoenmakers, JohnIn this paper, we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete- and continuous-time optimal stopping problems. In this context, we consider tractability of such problems via a useful notion of semitractability and the introduction of a tractability index for a particular numerical solution algorithm. It is shown that in the discrete-time case the WSM algorithm leads to semitractability of the corresponding optimal stopping problem in the sense that its complexity is bounded in order by (Formula presented.) with (Formula presented.) 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 cannot prove semitractability 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. © 2020 Wiley Periodicals LLC
- ItemOn the optimal combination of tensor optimization methods(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2020) Kamzolov, Dmitry; Gasnikov, Alexander; Dvurechensky, PavelWe 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.
- ItemSimple Monte Carlo and the metropolis algorithm(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2006) Mathé, Peter; Novak, ErichWe 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.
- ItemZ2-Thurston norm and complexity of 3-manifolds, II(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2017) Jaco, William; Rubinstein, J. Hyam; Spreer, Jonathan; Tillmann, StephanIn this sequel to earlier papers by three of the authors, we obtain a new bound on the complexity of a closed 3-manifold, as well as a characterisation of manifolds realising our complexity bounds. As an application, we obtain the first infinite families of minimal triangulations of Seifert fibred spaces modelled on Thurston's geometry SL2(R)˜.
- ItemSemi-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.