Universal Convexification via Risk-Aversion

Krishnamurthy Dvijotham, Maryam Fazel, Emanuel Todorov
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:56-65, 2014.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-dvijotham14a, title = {Universal Convexification via Risk-Aversion}, author = {Dvijotham, Krishnamurthy and Fazel, Maryam and Todorov, Emanuel}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {56--65}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/dvijotham14a/dvijotham14a.pdf}, url = {https://proceedings.mlr.press/r12/dvijotham14a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Universal Convexification via Risk-Aversion %A Krishnamurthy Dvijotham %A Maryam Fazel %A Emanuel Todorov %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-dvijotham14a %I PMLR %P 56--65 %U https://proceedings.mlr.press/r12/dvijotham14a.html %V R12 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Dvijotham, K., Fazel, M. & Todorov, E.. (2014). Universal Convexification via Risk-Aversion. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:56-65 Available from https://proceedings.mlr.press/r12/dvijotham14a.html. Reissued by PMLR on 04 October 2026.

Related Material