02/02/2021

Projection-free Online Learning in Dynamic Environments

Yuanyu Wan, Bo Xue, Lijun Zhang

Keywords:

Abstract Paper Similar Papers

Abstract: To efficiently solve high-dimensional problems with complicated constraints, projection-free online learning has received ever-increasing research interest. However, previous studies either focused on static regret that is not suitable for dynamic environments, or only established the dynamic regret bound under the smoothness of losses. In this paper, without the condition of the smoothness, we propose a novel projection-free online algorithm, and achieve an O(max{T^{2/3}V_T^{1/3},T^{1/2}}) dynamic regret bound for convex functions and an O(max{(TV_Tlog T)^{1/2},log T}) dynamic regret bound for strongly convex functions, where T is the time horizon and V_T denotes the variation of loss functions. Specifically, we first improve an existing projection-free algorithm called online conditional gradient (OCG) to enjoy small dynamic regret bounds with the prior knowledge of V_T. To work with unknowable V_T, we maintain multiple instances of the improved OCG that can handle different functional variations, and combine them with a meta-algorithm that can track the best one. Experimental results validate the efficiency and effectiveness of our algorithm.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948577
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 1
 1
 1
 1
 3:09 
 0
 0
 0
 0
 20:29 
 0
 0
 0
 0
 6:03 
 1
 1
 0
 0
 3:29 
 0
 0
 0
 0
 7:44 
 0
 0
 0
 0
 15:23 
 0
 0
 0
 0
 18:32 
 0
 0
 0
 0
 15:17 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 15:32 
 0
 0
 0
 0
 17:09 
 0
 0
 0
 0
 11:38 
 0
 0
 0
 0
 13:07 
 0
 0
 0
 0
 14:48 
 0
 0
 0
 0
 17:27 
 0
 0
 0
 0
 3:19 
 1
 1
 0
 1
 3:11 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 2:52 
 0
 0
 0
 0
 20:10 
 0
 0
 0
 0
 16:53 
 0
 0
 0
 0
 16:14 
 1
 1
 0
 1
 16:30 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 14:58 
 0
 0
 0
 0
 11:30 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 13:32 
 0
 0
 0
 0
 2:51 
 0
 0
 0
 0
 4:29 
 0
 0
 0
 0
 17:16 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 15:12 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 5:45 
 0
 0
 0
 0
 15:16