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 additive approximation guarantees under some assumptions. In simple 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 discretetime 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.

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 additive approximation guarantees under some assumptions. In simple 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 discretetime 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.}, 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 additive approximation guarantees under some assumptions. In simple 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 discretetime 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. %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