A Caltech Library Service

Online Optimization with Predictions and Non-convex Losses

Lin, Yiheng (2021) Online Optimization with Predictions and Non-convex Losses. In: 2021 55th Annual Conference on Information Sciences and Systems (CISS). IEEE , Piscataway, NJ, p. 1. ISBN 9781665412681.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Smoothed online optimization considers an online learning setting where the learner, besides a per-round hitting cost, also incurs a switching cost when changing its decision between rounds. It has received significant attention recently due to its close connections with applications in control and resource allocation. A line of work in this area seeks to design online algorithms that achieve near-optimal costs by leveraging predictions of future cost functions. However, optimistic results are only known under some specific combination of assumptions about the hitting and switching costs, and no general results are known. In this work, we provide 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 near-optimal competitive ratio with the help of predictions. The two conditions we give are general because they do not require the cost function to be convex, and natural counterexamples might arise when they are not satisfied.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Lin, Yiheng0000-0001-6524-2877
Additional Information:© 2021 IEEE.
Subject Keywords:online learning, online non-convex optimization, competitive analysis
Record Number:CaltechAUTHORS:20210503-115704933
Persistent URL:
Official Citation:Y. Lin, "Online Optimization with Predictions and Non-convex Losses," 2021 55th Annual Conference on Information Sciences and Systems (CISS), 2021, pp. 1-1, doi: 10.1109/CISS50987.2021.9400213
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108938
Deposited By: George Porter
Deposited On:04 May 2021 14:23
Last Modified:23 Dec 2022 18:35

Repository Staff Only: item control page