Online Optimization of Smoothed Piecewise Constant Functions

In this paper, we study the problem of online optimization of piecewise constant functions. This is motivated by the question of selecting optimal parameters for learning algorithms. Recently, Gupta and Roughgarden (2016) introduced a probably approximately correct (PAC) framework for choosing parameters of algorithms. Imagine a situation, when a website wishes to provide personalized results to a user. To respond to a user's query, the service provider may need to implement a learning (or some other type of) algorithm which involves choosing parameters. The choice of parameters affects the quality of solution and ideally we would like to design a mechanism where the service provider learns from past instances, or at least employs a strategy that has low regret with respect to the single optimal solution in hindsight. In many learning problems, the goal is to find parameters by optimizing a continuous function (of the parameters); however, ever so often one encounters problems with discrete solutions, such as k-means or independent set, which result in objective functions that have discontinuities. Concretely, we consider the problem of online optimization of piecewise constant functions over the domain [0, 1).