Conference proceeding
Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
Proceedings of Machine Learning Research, Vol.48, pp.449-457
International Conference on Machine Learning, 33rd (New York, New York, USA, 07/2016)
07/2016
Abstract
This work focuses on dynamic regret of online convex optimization that compares the performance of online learning to a clairvoyant who knows the sequence of loss functions in advance and hence selects the minimizer of the loss function at each step. By assuming that the clairvoyant moves slowly (i.e., the minimizers change slowly), we present several improved variation-based upper bounds of the dynamic regret under the true and noisy gradient feedback, which are \it optimal in light of the presented lower bounds. The key to our analysis is to explore a regularity metric that measures the temporal changes in the clairvoyant’s minimizers, to which we refer as path variation. Firstly, we present a general lower bound in terms of the path variation, and then show that under full information or gradient feedback we are able to achieve an optimal dynamic regret. Secondly, we present a lower bound with noisy gradient feedback and then show that we can achieve optimal dynamic regrets under a stochastic gradient feedback and two-point bandit feedback. Moreover, for a sequence of smooth loss functions that admit a small variation in the gradients, our dynamic regret under the two-point bandit feedback matches that is achieved with full information.
Details
- Title: Subtitle
- Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
- Creators
- Tianbao YangLijun ZhangRong JinJinfeng Yi
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of Machine Learning Research, Vol.48, pp.449-457
- Conference
- International Conference on Machine Learning, 33rd (New York, New York, USA, 07/2016)
- Language
- English
- Date published
- 07/2016
- Academic Unit
- Computer Science
- Record Identifier
- 9984259431302771
Metrics
9 Record Views