Диссертации, представленные на защиту и подготовленные в НИУ ВШЭ

Interior point methods have a history of more than 35 years and their appearance made a major breakthrough in convex optimization. These methods are still actively used for solving large-scale optimization problems and remain out of competition.One of the important practical aspects of implementing any continuous optimization algorithm is the appropriate choice of the step length. This problem for interior point methods is the focus of this thesis. In this work, we propose to use an approach in which the problem of finding the optimal step of the method is formed as an optimal control problem and then optimal control theory is applied to solve it. We apply this approach to Newton’s method for minimizing self-concordant functions, because this method is used to solve the auxiliary problem in interior point methods where self-concordant barriers are employed to solve conic programming problems. We likewise apply the approach to the task of finding the optimal step for approaching the central path in problems with self-concordant barriers. The first problem has been solved analytically and the resulting step length is optimal for Newton’s method. The second problem has no closed-form solution and was solved numerically for the two-dimensional case.

In this PhD dissertation, we address the problems of optimal stopping and learning in Markov decision processes used in reinforcement learning (RL). In the first direction, we derive complexity estimates for the algorithm called Weighted Stochastic Mesh (WSM) and give a new method for comparing the complexity of optimal stopping algorithms with the semi tractability index. We show that WSM is optimal with respect to this criterion when the commonly used regression methods are much less effective. For reinforcement learning, we give a non-asymptotic convergence analysis of a stochastic approximation scheme with two time scales - gradient TD - under assumptions of "martingale increment" noise - buffer replay - and of "Markov noise" (when learning is done along a single run). We obtain upper bounds that are rate-optimal by constructing an error expansion method that provides accurate control of the remainders terms. We also present a new algorithm for variance reduction in policy gradient schemes. The proposed approach is based on minimising an estimator for the empirical variance of the weighted rewards. We establish theoretical and practical gains over the classical actor-critic (A2C) method.