Universal Convexification via Risk-Aversion
Krishnamurthy Dvijotham, Maryam Fazel, Emanuel Todorov
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 ad-
ditive approximation guarantees under some
assumptions. In simple settings, the convexi-
fication procedure can be applied directly and
standard optimization methods can be used.
In the general case we rely on stochastic gra-
dient algorithms, whose convergence rate can
be bounded using the convexity of the under-
lying optimization problem. We then extend
the framework to a general class of discrete-
time dynamical systems where our convex-
ification 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.
PDF Link: /papers/14/p162-dvijotham.pdf
AUTHOR = "Krishnamurthy Dvijotham
and Maryam Fazel and Emanuel Todorov",
TITLE = "Universal Convexification via Risk-Aversion",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "162--171"