Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design

Maria-Florina Balcan, Wesley Pegden, Dravyansh Sharma
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7111-7116, 2026.

Abstract

Classical online optimization theory focuses on regret guarantees for convex Lipschitz functions. However, online optimization problems motivated by machine learning for algorithm design fall outside this regime, since typically an algorithm’s performance as a function of its hyperparameters is a highly volatile function. This has inspired recent work on online optimization of piecewise-Lipschitz functions with complex transition boundaries. We provide open questions in this direction. Resolving these questions would advance the learning-theoretic foundation for adaptive algorithm design by clarifying when desirable sublinear regret guarantees are possible for learning the algorithms from online problem instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-balcan26a, title = {Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design}, author = {Balcan, Maria-Florina and Pegden, Wesley and Sharma, Dravyansh}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {7111--7116}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/balcan26a/balcan26a.pdf}, url = {https://proceedings.mlr.press/v336/balcan26a.html}, abstract = {Classical online optimization theory focuses on regret guarantees for convex Lipschitz functions. However, online optimization problems motivated by machine learning for algorithm design fall outside this regime, since typically an algorithm’s performance as a function of its hyperparameters is a highly volatile function. This has inspired recent work on online optimization of piecewise-Lipschitz functions with complex transition boundaries. We provide open questions in this direction. Resolving these questions would advance the learning-theoretic foundation for adaptive algorithm design by clarifying when desirable sublinear regret guarantees are possible for learning the algorithms from online problem instances.} }
Endnote
%0 Conference Paper %T Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design %A Maria-Florina Balcan %A Wesley Pegden %A Dravyansh Sharma %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-balcan26a %I PMLR %P 7111--7116 %U https://proceedings.mlr.press/v336/balcan26a.html %V 336 %X Classical online optimization theory focuses on regret guarantees for convex Lipschitz functions. However, online optimization problems motivated by machine learning for algorithm design fall outside this regime, since typically an algorithm’s performance as a function of its hyperparameters is a highly volatile function. This has inspired recent work on online optimization of piecewise-Lipschitz functions with complex transition boundaries. We provide open questions in this direction. Resolving these questions would advance the learning-theoretic foundation for adaptive algorithm design by clarifying when desirable sublinear regret guarantees are possible for learning the algorithms from online problem instances.
APA
Balcan, M., Pegden, W. & Sharma, D.. (2026). Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:7111-7116 Available from https://proceedings.mlr.press/v336/balcan26a.html.

Related Material