A Batch-to-Online Transformation under Random-Order Model
This work provides a general method for designing efficient online algorithms from offline counterparts, which is incremental but applicable across multiple domains in machine learning.
The paper tackles the problem of developing online algorithms with low approximate regret by introducing a transformation framework that converts offline approximation algorithms into online ones under the random-order model, achieving polylogarithmic regret for problems like clustering, matrix approximation, and regression.
We introduce a transformation framework that can be utilized to develop online algorithms with low $ε$-approximate regret in the random-order model from offline approximation algorithms. We first give a general reduction theorem that transforms an offline approximation algorithm with low average sensitivity to an online algorithm with low $ε$-approximate regret. We then demonstrate that offline approximation algorithms can be transformed into a low-sensitivity version using a coreset construction method. To showcase the versatility of our approach, we apply it to various problems, including online $(k,z)$-clustering, online matrix approximation, and online regression, and successfully achieve polylogarithmic $ε$-approximate regret for each problem. Moreover, we show that in all three cases, our algorithm also enjoys low inconsistency, which may be desired in some online applications.