Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2020 | Submitted + Published
Journal Article Open

Online Optimization with Predictions and Non-convex Losses

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.

Additional Information

© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. Received October 2019; revised December 2019; accepted January 2020. 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.

Attached Files

Published - 3379484.pdf

Submitted - 1911.03827.pdf

Files

1911.03827.pdf
Files (2.2 MB)
Name Size Download all
md5:fc4262dd3dedf59b405a318bf4cb1fe0
1.1 MB Preview Download
md5:e668b3f474ae1c2a5d3d4e6043c55c44
1.1 MB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 19, 2023