Compare different SG-Schemes based on large least square problems
Ramkrishna Acharya, Durga Pokharel · 2025
Read Compare different SG-Schemes based on large least square problems by Ramkrishna Acharya, Durga Pokharel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01507.txt.
Introduction
Ramkrishna Acharya compares popular gradient-based training schemes, the optimizers that tune machine learning models, on large least-squares problems. Optimizers decide how a model steps toward better settings. Small choices in their settings can change speed and final quality a lot.
The study runs the schemes under varied settings and judges them on the same yardstick problems. Least-squares tasks are a clean test bed, since their best answers can be computed directly. Code for the runs is posted in a public repository for anyone to repeat. The review is aimed at users who pick an optimizer by habit. A clear side-by-side can save compute and guesswork. The catalog record also names Durga Pokharel as a co-author.
Catalog record
| CREATOR | Ramkrishna Acharya, Durga Pokharel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01507
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compare different SG-Schemes based on large least square problems Ramkrishna Acharya, Durga Pokharel Abstract This study reviews popular stochastic gradient-based schemes based on large least-square problems. These schemes, often called optimizers in machine learning, play a crucial role in finding better model parameters. Hence, this study focuses on viewing such optimizers with different hyper-parameters and analyzing them based on least square problems. Codes that produced results in this work are available on GitHub . 1 Introduction 1.1 Least Squares Problems Least squares problems are common problems in which we try to find the best-fitting curve to a given set of points by minimizing the sum of the squares of the offsets (”the residuals”) of the points from the curve. 1 1 footnotetext: [ 8 ] Alternatively, they can be defined as a parameter estimation method in regression analysis based on minimizing the sum of squared residuals (RSS). Let: • \mathbf{y}\in\mathbb{R}^{n} be the vector of observed values • \mathbf{X}\in\mathbb{R}^{n\times p} be the matrix of input features • \boldsymbol{\theta}\in\mathbb{R}^{p} be the vector of regression coefficients (or parameters) Then such a least squares problem can be defined as the matrix form of: \mathbf{y}=\mathbf{X}\boldsymbol{\theta}+\boldsymbol{\epsilon} (1) where \boldsymbol{\epsilon}\in\mathbb{R}^{n} represents the error terms, typically assumed to be normally distributed. Then the sum of squared residuals (RSS) can be written as: \text{RSS}=(\mathbf{y}-\mathbf{X}\boldsymbol{\theta})^{T}(\mathbf{y}-\mathbf{X}\boldsymbol{\theta}) (2) Alternatively, in terms of the error vector \boldsymbol{\epsilon} , RSS can be expressed as: \text{RSS}=\boldsymbol{\epsilon}^{T}\boldsymbol{\epsilon} \text{RSS}=\boldsymbol{\epsilon}^{T}\boldsymbol{\epsilon}:=(\mathbf{y}-\mathbf{X}\boldsymbol{\theta})^{T}(\mathbf{y}-\mathbf{X}\boldsymbol{\theta}) (3) The parameters \theta can be found by minimizing the sum of squared residuals. Expanding on the above expression: \boldsymbol{\epsilon}^{T}\boldsymbol{\epsilon}=\mathbf{y}^{T}\mathbf{y}-2\boldsymbol{\theta}^{T}\mathbf{X}^{T}\mathbf{y}+\boldsymbol{\theta}^{T}\mathbf{X}^{T}\mathbf{X}\boldsymbol{\theta} To minimize RSS, we take the derivative with respect to \boldsymbol{\theta} and set it to zero: \frac{\partial\boldsymbol{\epsilon}^{T}\boldsymbol{\epsilon}}{\partial\boldsymbol{\theta}}=-2\mathbf{X}^{T}\mathbf{y}+2\mathbf{X}^{T}\mathbf{X}\boldsymbol{\theta}=0 Solving for \boldsymbol{\theta} : \boldsymbol{\theta}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y} (4) where \mathbf{X}^{T}\mathbf{X} is assumed to be invertible. 2 Methodology 2.1 Least Squares and Gradient Scheme Gradient descent is an optimization algorithm used to minimize some convex functions by iteratively moving in the direction of the steepest descent as defined by the negative of the gradient. The parameter update technique is given by 4 i.e. \boldsymbol{\hat{\theta}}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y} could have problems: • (\mathbf{X}^{T}\mathbf{X})^{-1} might not be invertible. • Our \mathbf{X} might be too big and cause storage problems while loading it. • The number of observations (rows in \mathbf{X} ) could be smaller than features (columns in \mathbf{X} ). But, we could find the best parameters \boldsymbol{\hat{\theta}} with an iterative update method. Let’s define \mathbf{f}(\mathbf{X};\boldsymbol{\theta})=\mathbf{X}\boldsymbol{\theta}+\boldsymbol{\epsilon} as a regression function, and J(\mathbf{f}(\mathbf{X};\boldsymbol{\theta}),\mathbf{y}) be a convex loss function we try to minimize. Then an example of such an iterative method can be shown in the algorithm 1 . Algorithm 1 Simple Gradient Descent Algorithm for Least Squares Regression 1: Initialize parameters \boldsymbol{\theta} , learning rate (step length) \eta 2: while stopping criterion not met do 3: for each data point (\mathbf{X}^{(i)},y^{(i)}) in (\mathbf{X},\mathbf{y}) do 4: Compute gradient estimate: g=\frac{\partial}{\partial\theta}J(f(X^{(i)};\theta),y^{(i)}) 5: Update parameters: \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta g 6: end for 7: end while 2.2 Different Choices to Make While Updating Parameters In machine learning, we use gradient descent to update the parameters of our model. In our case, we try to fit a linear regression model and try to find the best parameters \theta . The following section explains some of the different choices one can make: • Loss Functions : Example: Mean Squared Error (MSE), Mean Absolute Error (MAE), etc. • Batch Size : Example: Batch size of 1, batch size of data counts, and any real values in between. • Optimizers : Example: Variable learning rate, constant learning rate, momentum, etc. 2.2.1 Loss Functions Loss functions are the convex functions we try to minimize. By finding the gradients with respect to the parameters, we find the direction and magnitude needed for our parameter to be updated. Hence it plays a crucial role in gradient schemes. Mean Squared Error and Mean Absolute Error are the most common examples of convex functions. 1. Mean Squared Error (MSE) \text{J}(\boldsymbol{\theta})=\frac{1}{N}\sum_{i=1}^{N}(y^{(i)}-f(X^{(i)};\theta))^{2}:=\frac{1}{N}\sum_{i=1}^{N}j_{i}(\theta) where y^{(i)} are the observed values, and N is the number of data points. MSE is smooth and convex in nature and a good choice for regression tasks. 2. Mean Absolute Error (MAE) \text{J}(\boldsymbol{\theta})=\frac{1}{N}\sum_{i=1}^{N}|y^{(i)}-f(X^{(i)};\theta)|:=\frac{1}{N}\sum_{i=1}^{N}j_{i}(\theta) In MSE, we need to calculate the squared term but here in MAE, we calculate the absolute of difference between target and predicted values. It is easier to compute in the sense that we do not need to calculate squared now but it is not a smooth function. Furthermore, it is not differentiable at y^{(i)}=f(X^{(i)};\theta) . Figure 1: MSE vs MAE 2.2.2 Gradient Descent Variants based on Batch Size 1. Batch Gradient Descent Batch gradient descent, also known as vanilla gradient descent, computes the gradient of the loss function for the parameters \theta for the entire training dataset. The following algorithm 2 shows how it performs parameter updates. Algorithm 2 Batch Gradient Descent Algorithm 1: Initialize parameters \boldsymbol{\theta} , learning rate (step length) \eta 2: while stopping criterion not met do 3: Compute gradient estimate: g=\frac{1}{N}\sum_{i=1}^{N}\frac{\partial j_{i}(\theta)}{\partial\boldsymbol{\theta}} 4: Update parameters: \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta g 5: end while As we need to calculate the gradients for the whole dataset to perform just one update, batch gradient descent can be very slow and is intractable for datasets that don’t fit in memory. Batch gradient descent also doesn’t allow us to update our model online, i.e. with new examples on the fly. Batch gradient descent is guaranteed to converge to the global minimum for convex error surfaces and a local minimum for non-convex surfaces. [ 5 ] 2. Stochastic Gradient Descent Stochastic gradient descent (SGD) performs a parameter update for each training example (x^{(i)},y^{(i)}) . The following algorithm 3 shows how it performs parameter updates. Algorithm 3 Stochastic Gradient Descent Algorithm 1: Initialize parameters \boldsymbol{\theta} , learning rate (step length) \eta 2: while stopping criterion not met do 3: Randomly choose single data point (\mathbf{X}^{(i)},y^{(i)}) from (\mathbf{X},\mathbf{y}) 4: Compute gradient estimate: g=\frac{\partial}{\partial\theta}j_{i}(\theta) 5: Update parameters: \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta g 6: end while While batch gradient descent performs redundant computations for large datasets with similar examples, SGD does parameter updates one at a time. Hence it can be used to learn online. 3. Mini-Batch Gradient Descent Mini-batch gradient descent takes the best of both batch and stochastic gradient descent and performs a parameter update for every mini-batch of B training examples. The following algorithm 4 shows how it performs parameter updates. Algorithm 4 Mini-Batch Gradient Descent Algorithm 1: Initialize parameters \boldsymbol{\theta} , learning rate (step length) \eta , and B batch size. 2: while stopping criterion not met do 3: Randomly sample B examples. 4: Compute gradient estimate: g=\frac{1}{B}\sum_{b=1}^{B}\frac{\partial}{\partial\boldsymbol{\theta}}j_{b}(\theta) 5: Update parameters: \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta g 6: end while Remarks On Gradient Descent Varients Based on Batch Size • As we are updating parameters after calculating only one gradient in stochastic gradient descent, it will be faster and need little memory to hold gradients, but updating too frequently causes gradients to be noisy and computationally inefficient. But this can also help escape the local minimum and find the global one. • Using batch gradient descent, we update parameters based on gradients of all data points so loading large datasets is problematic. While it could generate smoother losses, calculating the gradients for all data points is time-consuming. • Using mini-batch gradient descent, we update parameters based on a small batch of the data points which will be smoother than stochastic gradient descent