 |
Center for Nonlinear Studies |
We develop a framework for convexifying a general class of optimization problems. We analyze the suboptimality of the solution to the convexified problem relative to the original nonconvex problem, and prove additive approximation guarantees under some assumptions. In simple supervised learning settings, the convexification procedure can be applied directly and standard optimization methods can be used. In the general case we rely on stochastic gradient algorithms, whose convergence rate can be bounded using the convexity of the underlying optimization problem. We then extend the framework to a general class of discrete-time dynamical systems -- where our convexification approach falls under the paradigm of risk-sensitive Markov Decision Processes. We derive the first model-based and model-free policy gradient optimization algorithms with guaranteed convergence to the optimal solution. We also present numerical results in different machine learning applications.
Host: Misha Chertkov