Stochastic gradient descent

Stochastic gradient descent (abbreviated as SGD) is an iterative method often used for machine learning, optimizing the gradient descent during each search once a random weight vector is picked. The gradient descent is a strategy that searches through a large or infinite hypothesis space whenever 1) there are hypotheses continuously being parameterized and 2) the errors are differentiable based on the parameters. The problem with gradient descent is that converging to a local minimum takes extensive time and determining a global minimum is not guaranteed (McGrawHill, 92). The gradient descent picks any random weight vector and continuously updates it incrementally when an error calculation is completed to improve convergence (Needell, Ward, Nati Srebro, 14). The method seeks to determine the steepest descent and it reduces the number of iterations and the time taken to search large quantities of data points. Over the recent years, the data sizes have increased immensely such that current processing capabilities are not enough (Bottou, 177). Stochastic gradient descent is being used in neural networks and decreases machine computation time while increasing complexity and performance for large-scale problems.

Authors: Jonathon Price, Alfred Wong, Tiancheng Yuan, Joshua Matthews, Taiwo Olorunniwo (SYSEN 5800 Fall 2020)
Steward: Fengqi You

Problem Formulation

Theory

SGD is a variation on gradient descent, also called batch gradient descent. Below is a brief review of the gradient descent algorithm.

Gradient Descent

Given a function J(λ) and a vector of parameters theta, gradient descent seeks to find the optimum parameters such that we minimize J(λ).
min J(λ)
In order to optimize the parameters theta, gradient descent incrementally changes the parameters theta by computing the gradient at theta times a defined learning rate.

Methodology

[Insert text]

Algorithmic Discussion

[Insert text]

Numerical Example

[Insert text]

Application

SGD, often referred to as the cornerstone for deep learning, is an algorithm for training a wide range of models in machine learning. Due to SGD’s efficiency in dealing with large scale datasets, it is the most common method for training deep neural networks. Furthermore, SGD has received considerable attention and is applied to text classification and natural language processing. It is best suited for unconstrained optimization problems and is the main way to train large linear models on very large data sets. Implementation of stochastic gradient descent include areas in ridge regression and regularized logistic regression. Other problems, such as Lasso (Shalev-Shwartz and Tewari, 2011) and support vector machines (Menon, 2009) can be solved by stochastic gradient descent.

Support Vector Machine

SGD is a simple yet very efficient approach to fitting linear classifiers and regressors under convex functions such as (linear) Support Vector Machines (SVM). A support vector machine is a supervised machine learning model that uses classification algorithms for two-group classification problems. An SVM finds what is known as a separating hyperplane: a hyperplane (a line, in the two-dimensional case) which separates the two classes of points from one another (Sentence under review). It is a fast and dependable classification algorithm that performs very well with a limited amount of data to analyze. However, because SVM is computationally costly, software applications often do not provide sufficient performance in order to meet time requirements for large amounts of data. To improve SVM scalability regarding the size of the data set, SGD algorithms are used as a simplified procedure for evaluating the gradient of a function.

Logistic regression (Section in work)

Logistic regression models the probabilities for classification problems with two possible outcomes. It's an extension of the linear regression model for classification problems.It is a statistical technique with the input variables as continuous variables and the output variable as a binary variable. It is a class of regression where the independent variable is used to predict the dependent variable.

Full Waveform Inversion (FWI)

The Full Waveform Inversion (FWI) is a seismic imaging process by drawing information from the physical parameters of samples. Companies use the process to produce high-resolution high velocity depictions of subsurface activities. SDG supports the process because it can identify the minima and the overall global minimum in less time as there are many local minimums (Witte).

Conclusion

Stochastic Gradient Descent is an algorithm that seeks to find the steepest descent during each iteration. The process decreases the time it takes to search large data sets and determine local minima immensely. The process helps determine the global minimum. The SDG provides many applications in machine learning, geophysics, least mean squares (LMS), and other areas.

References

1. BORDES. A., BOTTOU, L., and GALLINARI, P. (2009): SGD-QN: Careful Quasi-Newton
2. Stochastic Gradient Descent. Journal of Machine Learning Research, 10:1737-1754
3. Bottou, L. (1991) Stochastic gradient learning in neural networks. Proceedings of Neuro-Nımes, 91.
4. Bottou, L. (2012) Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade, 421– 436. Springer.
5. Philipp Witte, Mathias Louboutin, Keegan Lensink, Michael Lange, Navjot Kukreja, Fabio Luporini, Gerard Gorman, Felix J. Herrmann; Full-waveform inversion, Part 3: Optimization. The Leading Edge ; 37 (2): 142–145. doi: https://doi.org/10.1190/tle37020142.1
6. Shalev-Shwartz, S. and Tewari, A. (2011) Stochastic methods for `1-regularized loss minimization. The Journal of Machine Learning Research, 12, 1865–1892.
7. Lopes, F.F.; Ferreira, J.C.; Fernandes, M.A.C. Parallel Implementation on FPGA of Support Vector Machines Using Stochastic Gradient Descent. Electronics 2019, 8, 631.
8. IOSR Journal of Computer Engineering (IOSR-JCE) e-ISSN: 2278-0661,p-ISSN: 2278-8727, Volume 17, Issue 4, Ver. III (July – Aug. 2015), PP 39-47 http://www.iosrjournals.org