Font Size: a A A

Dynamic Regret Of Online Gradient Descent:Analyses And Applications

Posted on:2021-06-24Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y W ZhaoFull Text:PDF
GTID:1488306548491524Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
As one of widely-used online convex optimization methods,online gradient descent algorithm is usually used to solve online learning problems.It models online learning as a game.The game consists of two players:one is called the learner,and the other one is called the environment.For every round of the game,the learner plays a model based on the historical information,and the environment then plays a loss function.A lot of previous literatures investigate the online gradient descent method and its variants.The performance of those methods are usually measured by the "regret",which presents the gap of performance between those methods and the potential optimal method.However,previous researches assume that the optimal model is constant,that is,it does not change over time.This assumption is too strong,and only holds in the static environment,not in the dynamic environment.Note that the sequence of optimal models could change over time in the dynamic environment.The regret in the dynamic environment is called the"dynamic regret",and similarly the regret in the static environment is called the "static regret".Previous work has studied the online gradient descent method and its variants in the static environment,and provided rich analyses of static regret for those methods.Unfortunately,there is little knowledge about the online gradient descent method in the dynamic environment and its dynamic regret.The dissertation therefore provides system-atical investigation of the online gradient descent method in the dynamic environment.First,it analyzes the dynamic regret without switching cost for the online gradient descent method,and provides the upper bound(?)where D? mea-sures the dynamics in the environment,and T means the number of rounds of the game.It also finds the dynamic regret without switching cost of a online convex optimization problem is(?),which implies that the online gradient descent method is optimal to solve a general online convex optimization problem.Second,it studies the dynamic regret with switching cost for the online gradient descent in both adversary and non-adversary environments.In the non-adversary envi-ronment,the dynamic regret with switching cost of the online gradient descent is bounded by O(T1/1+? D?/1+?),where D measures the dynamics in the environment,and 1 ???2 is a constant defined in the switching cost.In the adversary environment,the dynamic re-gret with switching cost of the online gradient descent is(?).It shows that the switching cost has a significant impact on the dynamic regret of the online gradient descent in the non-adversary environment,but does not have an impact on the dynamic regret of the online gradient descent in the adversary environment.Third,it presents a projection-free online gradient descent method,and provides that its dynamic regret is bounded by(?).Since the online convex optimization prob-lem has(?)dynamic regret,the proposed projection-free online gradient descent is an optimal method to solve the online convex optimization problem.Fourth,it investigates the online gradient descent method in the decentralized setting,and provides(?)dynamic regret.Here,G represents the norm of the gradient of the loss function,?2 represents the variance of the randomness of the loss function,and n represents the number of nodes in the decentralized network.The analysis finds that communication between nodes in the decentralized network helps to reduce the stochastic component of the dynamic regret,but does not help to reduce the adversary component of the dynamic regret.Finally,we find three practical scenarios for the online gradient descent method,and propose effective methods for those tasks,including variance reduced stochastic gradient descent clustering method,communication-efficient and distributed stochastic gradient descent method,and efficient and robust methods to solve the "sum of norms" regularized problem.Extensive empirical studies show both the effectiveness and the efficiency of the proposed methods.
Keywords/Search Tags:online gradient descent, online learning, online convex optimization, dynamic regret, switching cost, stochastic gradient descent, gradient descent, decentralized optimization, distributed optimization
PDF Full Text Request
Related items