Font Size: a A A

Nonconvex And Stochastic Algorithms In Machine Learning Research

Posted on:2019-10-05Degree:DoctorType:Dissertation
Country:ChinaCandidate:T SunFull Text:PDF
GTID:1368330611993052Subject:Mathematics
Abstract/Summary:PDF Full Text Request
Machine learning is a multi-disciplinary subject involving many disciplines such as probability theory,statistics,approximation theory,convex analysis,and algorithm complexity theory.It specializes in how computers simulate or implement human learning behaviors to acquire new knowledge or skills and reorganize existing knowledge structures to continuously improve their performance.Algorithm theory and application is one of the most important cores in machine learning.Among them,the optimization algorithm is widely studied and applied because of its simplicity and efficiency.Due to the increasing size of data,the size of the data set has hindered the use of second-order or higher-order algorithms.Therefore,the first-order algorithm has been the core of machine learning research in recent years.With the developments of problem models in machine learning,such as deep learning,non-convex problems and models have also attracted attentions.This makes the study of nonconvex algorithms be more meaningful.And due to the hugeness of the data set,in the algorithm,the random algorithm has become a very effective and easy methods.The main contents can be summarized as follows:1,we consider three general ADMM algorithms.The first one is to present a general ADMM convergence framework.Under this framework,convergence of many existing ADMMs can be directly obtained by this framework.And we can also prove the convergence of many other ADMMs.The second and third one are for structural nonconvex optimization problems.2,we consider two inexact algorithms.The first is an inexact accelerated algorithm.Compared with previous studies,the assumptions of this algorithm are more realistic.And we also considered a large class of random noises.The first-order catalyst algorithm in machine learning can be regareded as a special case of this algorithm.In the second part,we present the convergence framework for inexact nonconvex algorithms.which can be applied to various first-order nonconvex algorithms.3,we have proven a selection of convergence results for asynchronous parallel algorithm under bounded and unbounded delays,and stochastic and deterministic block choices.These results do not require the independence assumption that occurs in the vast majority of other work so far.These results were obtained with the use of Lyapunov function techniques,and treating delays directly,rather than modeling them as noise4,we analyzed the stochastic gradient descent method where the samples are taken on a trajectory of Markov chain.One of our main contributions is non-ergodic convergence analysis for convex MCGD,which uses a novel line of analysis.The result is then extended to the inexact version.This analysis lets us establish convergence for non-reversible finite-state Markov chains and for nonconvex minimization problems.
Keywords/Search Tags:Convergence, Nonconvex algorithm, Stochastic algorithm, Markov chain
PDF Full Text Request
Related items