CaltechAUTHORS
  A Caltech Library Service

Online Optimization with Predictions and Non-convex Losses

Lin, Yiheng and Goel, Gautam and Wierman, Adam (2020) Online Optimization with Predictions and Non-convex Losses. ACM SIGMETRICS Performance Evaluation Review, 48 (1). pp. 9-10. ISSN 0163-5999. https://resolver.caltech.edu/CaltechAUTHORS:20200709-141107614

[img] PDF - Published Version
See Usage Policy.

1113Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200709-141107614

Abstract

We study online optimization in a setting where an online learner seeks to optimize a per-round hitting cost, which may be non-convex, while incurring a movement cost when changing actions between rounds. We ask: under what general conditions is it possible for an online learner to leverage predictions of future cost functions in order to achieve near-optimal costs? Prior work has provided near-optimal online algorithms for specific combinations of assumptions about hitting and switching costs, but no general results are known. In this work, we give two general sufficient conditions that specify a relationship between the hitting and movement costs which guarantees that a new algorithm, Synchronized Fixed Horizon Control (SFHC), achieves a 1+O(1/w) competitive ratio, where w is the number of predictions available to the learner. Our conditions do not require the cost functions to be convex, and we also derive competitive ratio results for non-convex hitting and movement costs. Our results provide the first constant, dimension-free competitive ratio for online non-convex optimization with movement costs. We also give an example of a natural problem, Convex Body Chasing (CBC), where the sufficient conditions are not satisfied and prove that no online algorithm can have a competitive ratio that converges to 1.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3393691.3394208DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20200214-105548481Related ItemConference Paper
Additional Information:© 2020 Copyright held by the owner/author(s). This work was done when Yiheng Lin was visiting California Institute of Technology. This work was supported by NSF grants AitF-1637598 and CNS-1518941, with additional support for Gautam Goel provided by an Amazon AWS AI Fellowship.
Funders:
Funding AgencyGrant Number
NSFAitF-1637598
NSFCNS-1518941
Amazon Web ServicesUNSPECIFIED
Subject Keywords:Online non-convex optimization, online convex optimization (OCO), non-convex optimization, competitive analysis
Issue or Number:1
Record Number:CaltechAUTHORS:20200709-141107614
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200709-141107614
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104313
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Jul 2020 21:53
Last Modified:04 Nov 2020 19:43

Repository Staff Only: item control page