MODIFIED STOCHASTIC VARIANCE REDUCTION GRADIENT DESCENT ALGORITHM AND ITS APPLICATION

open_access
Open Access
Author:
Fei, Cai
Area of Honors:
Industrial Engineering
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Tao Yao, Thesis Supervisor
Dr. Catherine Mary Harmonosky, Thesis Honors Advisor
Keywords:
Machine Learning
Gradient Descent
Mathematical Optimization
Stochastic Gradient Descent
Abstract:
While machine learning is becoming an indispensable element in our modern society, various algorithms are developed to help decision makers solve complicated problems. A major theme of this study is to review and analyze popular algorithms with a focus on Stochastic Gradient (SG) based methods in large-scale machine learning problems. While SG has been the fundamental method playing an essential role in optimization problems, the algorithm has been further modified by various researchers for improved performances. Stochastic Gradient Descent with Variance Reduction (SVRG) is a method known for its low computation cost and fast convergence rate in solving convex optimization problems. However, in nonconvex settings, the existence of saddle points negatively influences the performance of the algorithm. While the practical problems in the real-world majorly lie in nonconvex settings, to further improve the performance of SVRG, a new algorithm is designed and discussed in this study. The new algorithm combines traditional SVRG with two additional features introduced by Perturbed Accelerated Gradient Descent (Perturbed AGD) to expedite algorithm from escaping from saddle points, which ultimately leads to convergence in nonconvex optimization. This study focuses on the elaboration of the modified SVRG algorithm and its implementation with a synthetic and an empirical dataset.