Convex relaxation regression: Black-box optimization of smooth functions by learning their convex envelopes

Mohammad Gheshlaghi Azar, Eva L. Dyer, Konrad P. Körding

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Finding efficient and provable methods to solve non-convex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle non-convex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxations typically must be found on a problemby-problem basis. Thus, providing a generalpurpose 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-δ, the solution of our algorithm converges to the global optimizer of f with error O (log(1/δ/T)α) for some α > 0. Our approach enables the use of convex optimization tools to solve non-convex optimization problems.

Original languageEnglish (US)
Title of host publication32nd Conference on Uncertainty in Artificial Intelligence 2016, UAI 2016
PublisherAssociation For Uncertainty in Artificial Intelligence (AUAI)
Pages22-31
Number of pages10
ISBN (Electronic)9781510827806
StatePublished - Jan 1 2016
Event32nd Conference on Uncertainty in Artificial Intelligence 2016, UAI 2016 - Jersey City, United States
Duration: Jun 25 2016Jun 29 2016

Other

Other32nd Conference on Uncertainty in Artificial Intelligence 2016, UAI 2016
CountryUnited States
CityJersey City
Period6/25/166/29/16

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Convex relaxation regression: Black-box optimization of smooth functions by learning their convex envelopes'. Together they form a unique fingerprint.

Cite this