Markov Decision Processes are the major model of controlled stochastic processes in discrete time. Value iteration (VI) is one of the major methods for finding optimal policies. For each discount factor, starting from a finite number of iterations, which is called the turnpike integer, value iteration algorithms always generate decision rules which are deterministic optimal policies for the infinite-horizon problems. This fact justifies the rolling horizon approach for computing infinite-horizon optimal policies by conducting a finite number of value iterations. In this talk, we will first discuss the complexity of using VI to approximately solve MDPs, and then introduce properties of turnpike integers and provide their upper bounds.

We will present recent results obtained with J. Hounie on the removability sets of singularities for bounded solutions and the propagation of zeros across rough (nondifferentiable) boundaries for solutions of systems of complex vector fields including CR vector fields.

This talk focuses on the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that have proposed effective algorithms, based on Polyak’s heavy ball method and the Nesterov accelerated gradient method, to achieve convergence to a local minimum of nonconvex functions, we describe a broad class of Nesterov-type accelerated methods and put forth a rigorous study of these methods encompassing the escape from saddle points and convergence to local minima through an asymptotic analysis. In the asymptotic regime, we first answer an open question of whether Nesterov’s accelerated gradient method (NAG) with variable momentum parameters avoids strict saddle points almost surely with respect to a random initialization and a random step-size. We then develop two metrics of asymptotic rates of convergence and divergence, and evaluate these two metrics for several popular standard accelerated methods such as the NAG and Nesterov’s accelerated gradient with constant momentum (NCM) near strict saddle points. Theoretical results on the asymptotic behavior are demonstrated on the phase retrieval problem.