2021, Agafonov, Artem, Kamzolov, Dmitry, Dvurechensky, Pavel, Gasnikov, Alexander

We propose a general non-accelerated tensor method under inexact information on higher- order derivatives, analyze its convergence rate, and provide sufficient conditions for this method to have similar complexity as the exact tensor method. As a corollary, we propose the first stochastic tensor method for convex optimization and obtain sufficient mini-batch sizes for each derivative.

2014, Belomestny, Denis, Hildebrand, Roland, Schoenmakers, John G.M.

The optimal stopping problem arising in the pricing of American options can be tackled by the so called dual martingale approach. In this approach, a dual problem is formulated over the space of martingales. A feasible solution of the dual problem yields an upper bound for the solution of the original primal problem. In practice, the optimization is performed over a finite-dimensional subspace of martingales. A sample of paths of the underlying stochastic process is produced by a Monte-Carlo simulation, and the expectation is replaced by the empirical mean. As a rule the resulting optimization problem, which can be written as a linear program, yields a martingale such that the variance of the obtained estimator can be large. In order to decrease this variance, a penalizing term can be added to the objective function of the path-wise optimization problem. In this paper, we provide a rigorous analysis of the optimization problems obtained by adding different penalty functions. In particular, a convergence analysis implies that it is better to minimize the empirical maximum instead of the empirical mean. Numerical simulations confirm the variance reduction effect of the new approach.