Convex Relaxation Regression: Black-Box Optimization of Smooth Functions by Learning Their Convex Envelopes

Mohamm Gheshlaghi Azar Northwestern University, Eva Dyer Northwestern University, Konrad Kording Northwestern University
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:266-275, 2016.

Abstract

Finding efficient and provable methods to solve nonconvex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle nonconvex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxations typically must be found on a problem-by-problem basis. Thus, providing a general-purpose strategy to estimate a convex relaxation would have a wide reaching impact. Here, we introduce Convex Relaxation Regression (CoRR), an approach for learning convex relaxations for a class of smooth functions. The idea behind our approach is to estimate the convex envelope of a function $f$ by evaluating $f$ at a set of $T$ random points and then fitting a convex function to these function evaluations. We prove that with probability greater than $1-\delta$, the solution of our algorithm converges to the global optimizer of $f$ with error $O \(\frac{\log(1/\delta) }{T} )^\alpha )$ for some $\alpha > 0$. Our approach enables the use of convex optimization tools to solve

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-university16g, title = {Convex Relaxation Regression: Black-Box Optimization of Smooth Functions by Learning Their Convex Envelopes}, author = {University, Mohamm Gheshlaghi Azar Northwestern and University, Eva Dyer Northwestern and University, Konrad Kording Northwestern}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {266--275}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/university16g/university16g.pdf}, url = {https://proceedings.mlr.press/r14/university16g.html}, abstract = {Finding efficient and provable methods to solve nonconvex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle nonconvex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxations typically must be found on a problem-by-problem basis. Thus, providing a general-purpose strategy to estimate a convex relaxation would have a wide reaching impact. Here, we introduce Convex Relaxation Regression (CoRR), an approach for learning convex relaxations for a class of smooth functions. The idea behind our approach is to estimate the convex envelope of a function $f$ by evaluating $f$ at a set of $T$ random points and then fitting a convex function to these function evaluations. We prove that with probability greater than $1-\delta$, the solution of our algorithm converges to the global optimizer of $f$ with error $O \(\frac{\log(1/\delta) }{T} )^\alpha )$ for some $\alpha > 0$. Our approach enables the use of convex optimization tools to solve}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Convex Relaxation Regression: Black-Box Optimization of Smooth Functions by Learning Their Convex Envelopes %A Mohamm Gheshlaghi Azar Northwestern University %A Eva Dyer Northwestern University %A Konrad Kording Northwestern University %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-university16g %I PMLR %P 266--275 %U https://proceedings.mlr.press/r14/university16g.html %V R14 %X Finding efficient and provable methods to solve nonconvex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle nonconvex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxations typically must be found on a problem-by-problem basis. Thus, providing a general-purpose strategy to estimate a convex relaxation would have a wide reaching impact. Here, we introduce Convex Relaxation Regression (CoRR), an approach for learning convex relaxations for a class of smooth functions. The idea behind our approach is to estimate the convex envelope of a function $f$ by evaluating $f$ at a set of $T$ random points and then fitting a convex function to these function evaluations. We prove that with probability greater than $1-\delta$, the solution of our algorithm converges to the global optimizer of $f$ with error $O \(\frac{\log(1/\delta) }{T} )^\alpha )$ for some $\alpha > 0$. Our approach enables the use of convex optimization tools to solve %Z Reissued by PMLR on 04 October 2026.
APA
University, M.G.A.N., University, E.D.N. & University, K.K.N.. (2016). Convex Relaxation Regression: Black-Box Optimization of Smooth Functions by Learning Their Convex Envelopes. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:266-275 Available from https://proceedings.mlr.press/r14/university16g.html. Reissued by PMLR on 04 October 2026.

Related Material