Abstract:
We consider the problem of estimating a function from n noisy samples whose discrete Total Variation (TV) is bounded by C_n. We reveal a deep connection to the seemingly disparate problem of <i>Strongly Adaptive</i> online learning [Daniely et al 2015] and provide an O(n \log n) time algorithm that attains the near minimax optimal rate of \tilde O (n^{1/3}C_n^{2/3}) under squared error loss. The resulting algorithm runs online and optimally <i>adapts</i> to the <i>unknown</i> smoothness parameter C_n. This leads to a new and more versatile alternative to wavelets-based methods for (1) adaptively estimating TV bounded functions; (2) online forecasting of TV bounded trends in time series.
