Diminishing Regret for Online Nonconvex Optimization

Sang Woo Park, Julie Mulvaney-Kemp, Ming Jin, Javad Lavaei

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

2 Scopus citations


A single nonconvex optimization is NP-hard in the worst case, and so is a sequence of nonconvex problems viewed separately. For online nonconvex optimization (ONO) problems, widely used local search algorithms are guaranteed to track a sequence of local optima, but offer no promises about global optimality. In this paper, we introduce the concept of nonconvexity regret to measure the performance of a local search method against a global optimization solver for ONO. We define the notion of depth of a global minimum, and show that memory and random explorations drive the nonconvexity regret to zero if the variability of the objective function is low compared to the depth of the global minima. We prove probabilistic guarantees on the regret bound that depend on the evolution of the landscapes of the time-varying objective functions. Then, based on the notions of missing mass and 1-occupancy set, we develop a practical algorithm that works even when there is no such information on the landscapes. The theoretical results imply that the existence of a low-complexity optimization at any arbitrary time instance of ONO can nullify the NP-hardness of the entire ONO problem. The results are verified through numerical simulations.

Original languageEnglish (US)
Title of host publication2021 American Control Conference, ACC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781665441971
StatePublished - May 25 2021
Externally publishedYes
Event2021 American Control Conference, ACC 2021 - Virtual, New Orleans, United States
Duration: May 25 2021May 28 2021

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Conference2021 American Control Conference, ACC 2021
Country/TerritoryUnited States
CityVirtual, New Orleans

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Diminishing Regret for Online Nonconvex Optimization'. Together they form a unique fingerprint.

Cite this