Projection-free Online Learning

In recent years,with the increase of data volume and the popularization of highspeed data flow generation techniques,online learning algorithms based on online convex optimization have been developed in both theory and application.Many algorithms based on this framework have been designed and successfully applied in practice.However,in many application scenarios,these algorithms still have a computational bottleneck that limits their further applicability: the projection operation.When the algorithm's update generates an infeasible iterate that is out of the convex domain of interest,we have to project it back to regain feasibility.In many problems,the projection amounts to expensive algebraic operation.For example,in matrix learning and multi-class classification,where the convex domain is the set of all matrices with bounded nuclear norm,the projection operation amounts to computing a full singular value decomposition of a matrix.In order to avoid these expensive operations,the projection-free online learning algorithm based on conditional gradient has been proposed.It can eschew the projection operation by using a more efficient linear optimization step.Therefore,this kind of projection-free online learning algorithm has attracted a lot of attention recently.Although enjoying great advantages in computation,it still has some major problems in practice:(1)the regularization parameter has to be calculated using the maximum iteration number of rounds T,which is usually unknown in advance;(2)the algorithm currently does not have a distributed variant,which can not adapt to the increasingly common distributed computing environment;(3)the algorithm requires a direct access to the gradient of the loss functions,and thus can not handle particular settings where the gradients of functions can not be directly obtained.Based on the above problems,we carry out the following main research work:· we propose the adaptive online condition gradient algorithm and give corresponding regret bound,which eliminate the dependence of the maximum iteration number of ruonds T in projection-free online learning;· we propose the distributed online conditional gradient algorithm,which makes projection-free online learning adaptive to the data stream processing in the distributed setting;· we propose the bandit online conditional gradient algorithm,which makes it possible to use projection-free online learning without directly knowing the gradients of functions.We have proposed three new algorithms,which largely expands the applicable scenarios of projection-free online learning.For each algorithm,we give a new analysis of its regret bound.The algorithm design and the theoretical analysis of their regret bounds are the main innovations of our work.