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

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.