Questions tagged [gradient-descent]

Gradient descent is a first-order iterative optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient (or of the approximate gradient) of the function at the current point. For stochastic gradient descent there is also the [sgd] tag.

Filter by
Sorted by
Tagged with
3
votes
2answers
2k views

Finding the Peak of a Kernel Density Estimator

I implemented a Kernel Density Estimator. I have a multivariate dataset that I use with it and I would like to find the point of highest likelihood. A way I thought about is sampling n points using ...
79
votes
7answers
42k views

Why use gradient descent for linear regression, when a closed-form math solution is available?

I am taking the Machine Learning courses online and learnt about Gradient Descent for calculating the optimal values in the hypothesis. h(x) = B0 + B1X why we ...
0
votes
0answers
15 views

For linear regression, do different hypothesis equations change the gradient descent equation I need to use?

For example, take the hypothesis function $h(x) = \theta_0 + \theta_1x_1 + \theta_2x_2$ When plugged into the MSE equation I get $J(\theta_0, \theta_1, \theta_2) = \frac{1}{2m} \sum_{i=1}^{m}(\...
0
votes
0answers
25 views

How to compute gradient of neural net

I can't come up with with gradient. I've been trying for a couple hours now but I can't get it right. I'm building a neural net with the following properties: two class classification, 1 hidden layer ...
1
vote
1answer
31 views

How does the batch size affect the Stochastic Gradient Descent optimizer? (Example using Keras)

First of all, I know that there are lots of questions and answers about the topic throughout the site $-$ such as here, here or here (and I've probably read them all). However, I am still confused. ...
0
votes
0answers
16 views

Vanishing gradient appears from the first iteration

I made a neural network for regression problem. It has 9 convolution layers and two fully connected layers at the end. All layers have ReLU activation function except the last FC layer. This is the ...
0
votes
1answer
22 views

Do we have guarantees about Adam's convergence when we reach an region with gradient $0$?

Recall the Adam update rule: $$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$$ $$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$$ $$\hat{m}_t = \dfrac{m_t}{1 - \beta^t_1}$$ $$\hat{v}_t = \dfrac{v_t}{1 - \...
1
vote
0answers
17 views

How to minimize the sum of Frobenius norm and Nuclear norm

I have to minimize an objective function of the the form : $||X_{s} - Y_{s}D_{s}||_{F}^{2} + ||D_{s}||_{F}^{2} + ||D_{s}||_{*}^{2}$ where $||.||_{F}$ denotes the Frobenius norm and $||.||_{*}$ ...
25
votes
2answers
10k views

Gradient backpropagation through ResNet skip connections

I'm curious about how gradients are back-propagated through a neural network using ResNet modules/skip connections. I've seen a couple of questions about ResNet (e.g. Neural network with skip-layer ...
1
vote
1answer
1k views

stochastic gradient descent of ridge regression when regularization parameter is very big

As we know, the gradient of ridge regression is: $$ g = \frac{\partial L}{\partial \theta} = -X_i^T(y_i-X_i\theta)+2\lambda\theta $$ where $X_i$ is the $i$th training sample. The update of $\theta$ is ...
0
votes
0answers
4 views

General method to add feature selection to an objective function?

In general, if you have an objective function that is differentiable with regards to its parameters you can apply gradient descent to minimize it (and even if it's not using a variety of possible ...
1
vote
0answers
18 views

Hessian Matrix for MultiClass Softmax in Gradient Boosting (XGBoost): $2p_i(1-p_i)$

In the context of MultiClass Softmax, for a particular training instance, label and prediction $y, p \in \mathbb{R}^K$ (K categories). The hessian matrix for Multiclass SoftMax with K categories is a $...
3
votes
1answer
1k views

How to penalize a regression loss function to account for correctness on the sign of the prediction?

I am dealing with a regression problem (my targets could potentially take values between -inf to +inf). To optimise my model, I have two objectives: 1) Predictions should be close to the targets. 2)...
1
vote
0answers
79 views

What derivative to use in Gradient boosting decision tree for a semi-supervised model

I am trying to build a semi-supervised prediction model with a Gradient Boosting decision trees. The learning phase is done using the following input: $X \in \mathbb{R}^{n\times p} $ $O(X) \in \...
74
votes
2answers
46k views

Solving for regression parameters in closed-form vs gradient descent

In Andrew Ng's machine learning course, he introduces linear regression and logistic regression, and shows how to fit the model parameters using gradient descent and Newton's method. I know gradient ...
0
votes
1answer
26 views

cross-validation with batch gradient descent

I have a question about using batch gradient descent along with cross-validation. When using batch gradient Descent, data is split into batches which are used to train the model and update the ...
8
votes
3answers
154 views

How to test for the best parameters for transformed independent variable in linear model

Let's assume that I have a linear model with $k$ variables: $y = \beta_0 + \beta_1\cdot x_1 + \dots + \beta_k \cdot x_k$. Now, I want to add variable $x_{k+1}$, but, according to domain knowledge, ...
1
vote
1answer
452 views

Batch gradient descent in Perceptron linear classifier

I'm learning about batch gradient descent for the Perceptron linear classifier and I'm confused about the update rule. On Wikipedia, it says that the update rule for batch gradient descent is $w := w -...
2
votes
1answer
43 views

Decomposing Gradient Decent Error in Eigenvector Space

I'm going through Why Momentum Really Works and am unable to understand the following line in the article. "By writing the contributions of each eigenspace’s error to the loss $$f(w^{k})-f(w^{\star})=...
1
vote
0answers
13 views

Mathematical proof of tradeoff between estimation error and computation cost in mini-batch gradient descent

" with more examples, the estimate would have a lower standard error, but the return is less than linear compared to the computational burden we incur." Came across this line while studying one ...
6
votes
2answers
196 views

What types of functions can be implemented in a layer of a Neural Networks?

One of the most common algorithms for training Neural Networks is back propagation, which essentially does (stochastic) gradient descent on the training objective function. Gradient descent can be ...
22
votes
4answers
8k views

When are genetic algorithms a good choice for optimization?

Genetic algorithms are one form of optimization method. Often stochastic gradient descent and its derivatives are the best choice for function optimization, but genetic algorithms are still sometimes ...
0
votes
0answers
23 views

Reinforcement Learning - Value Function Approximation

I am new to Reinforcement (Machine) Learning; I started my project with Q Learning (Tabular Q), which was easy to understand. I am now trying to write the code for Value Function Approximation. I ...
0
votes
1answer
162 views

Finding maximum likelihood solution of a continuous state HMM

The likelihood of a hidden Markov model (HMM) for states $x_0, \dots, x_N$ and observations $y_1, \dots, y_N$ can be written as $$ L = f(x_0) \prod_{i=1}^N f(y_i | x_i) f(x_i | x_{i-1} )$$ where we ...
3
votes
1answer
304 views

When training on a very large data set using SGD what part of the training set does one use to asses the current accuracy?

It is common in Deep Learning to use SGD (with mini batches). However it is also common that the data sets are too large to compute the full current accuracy of the model using the whole data set as ...
3
votes
1answer
35 views

Distribution of gradients across dimensions for neural networks

Does the distribution of gradients for neural networks known to follow a particular distribution? That is, suppose I've a model with $N$ parameters. Then, the (stochastic) gradient at some point is a ...
1
vote
2answers
39 views

is there a “generic” gradient descent

on this week we learned that the general form of the update step for gradient descent is: $x := x - \alpha \frac{\partial f}{\partial x}$ So, in order to find x where f is minimum, we have to ...
2
votes
2answers
2k views

What is the computational cost of gradient descent vs linear regression?

I know the computational costs for the closed form of linear regression is $O(n^3)$, but I can't find a similar cost comparison to gradient descent. There are some similar questions here with people "...
2
votes
0answers
20 views

Hill Climbing with hysteresis

I'm trying to solve a specific problem related to my work in experimental physics. However, I'll try to keep my question as general as possible so that it is useful to a wider audience. If some ...
4
votes
3answers
6k views

Batch Normalization shift/scale parameters defeat the point

According to the paper introducting Batch Normalization, the actual BN function is given as: Input: Values of $x$ over a mini-batch $\mathcal B = \{x_{1,\ldots,m}\}$; parameters to be learned $\gamma,...
11
votes
2answers
1k views

Are Residual Networks related to Gradient Boosting?

Recently, we saw the emergence of the Residual Neural Net, wherein, each layer consists of a computational module $c_i$ and a shortcut connection that preserves the input to the layer such as the ...
0
votes
1answer
46 views

using finite difference to estimate high dimensional gradient in gradient descent methods

I'm not very familiar with optimization problem, but I know that if the gradient of function is hard to find, it can use finite difference method to estimate it. Like scipy.minimize, it would use this ...
0
votes
1answer
39 views

Why using gradient decent if we can just minimize function in closed form?

I don't really understand why gradient descent is so important in neural networks? Wouldn't it be much easier to define an objective function in a way to do ...
3
votes
1answer
524 views

Mini-batching dependent data

I have a neural network I am training on some time series data. Naturally I want to sequentially mini-batch this data if at all possible. However, it seems that if the data size isn't a multiple of ...
1
vote
1answer
2k views

How to make stochastic gradient descent algorithm converge to the optimum?

(Background info taken from my blog) In logistic regression, the hypothesis function, which models the relationshiop between the dependent variable $P(y = 1)$ and the independent variable $X$, is : ...
0
votes
1answer
652 views

Motivation behind parameter sharding for Downpour SGD

Why does the Downpour model shard the parameters into separate groups? Is there any advantage of making one cluster responsible for changing only certain parameters?
1
vote
1answer
624 views

what is the correct formula of momentum for gradient descent?

I have been trying to get a better understanding of momentum, but in my search for clarification I got pretty confused. The main reason is that there seem to be multiple different, non-equivalent ...
0
votes
0answers
8 views

Gradient of a convex loss for linear classifiers

Let L(w; x; y) be a convex loss function for a linear classifier w. Can you always express the gradient of ...
5
votes
1answer
473 views

Does RMSProp/Adam solve vanishing gradient problem?

RMSProp and Adam both scale the effectively learning rate by dividing the moving average of past gradients (root mean squared). So if the first layer has gradient much smaller than the last layer, ...
0
votes
1answer
29 views

Interpreting cost change plot in a neural network for learning XOR

I tried to build a neural net for learning XOR. The design is as follows: 1st layer: compute linear function of input 4:2 with 2:2 weights and adding 1:2 bias. 2nd layer: apply sigmoid to all ...
1
vote
1answer
98 views

Can we apply analyticity of a neural network to improve upon gradient descent? [duplicate]

Gradient descent uses the first order derivative information of the objective function as a function of the parameters. Gradient descent therefore uses only “local” information about the objective ...
0
votes
0answers
31 views

Why is the step length by default equal to 1 in gradient boosting?

On ESL p.359, it explains steepest descent: But in 10.37, it is trying to minimize the distance to g_im. It looks like the default step length is 1. Why is it so?
1
vote
0answers
22 views

Logistic regression fitting methods clarification

Each book I read propose a different fitting method for Logistic Regression. The general idea is to maximize this expression. $$ Pr\left(\beta|y,X,M\right) = \frac{Pr\left(y|\beta,X,M\right) Pr(\...
0
votes
1answer
29 views

Decision tree that fits a regression at leaf nodes

Is there any academic work on any Decision Tree that fits a regression at its final leaf node? For instance, suppose I have 100 features (X), and use them build a tree with 3 depths such that I have ...
1
vote
1answer
186 views

Consistency of ReLU gradient

In Goodfellow et al.'s Deep Learning, the authors write, "rectified linear units use the activation function $g(z) = \max\{0,z\}$... The gradients are not only large but consistent" (187). What does ...
0
votes
2answers
31 views

Neural network training: skipping layers when performing weight updates

Suppose you had many models that are trained to classify a sequence of logical characters into 'satisfiable' or 'unsatisfiable' (e.g., the sequence "A and notA" is unsatisfiable). Suppose all of these ...
1
vote
1answer
72 views

Why is local-m Attention differentiable?

In this paper (https://arxiv.org/pdf/1508.04025.pdf) local attention is introduced. With local-m attention, we compute the attention vector over the source hidden states within a window around the ...
4
votes
0answers
309 views

Proximal Gradient Descent and Proximal Coordinate descent for Lasso Problem

Why is proximal coordinate descent much less affected by bad conditioning than proximal gradient descent? For example, we can consider this problem : $\min_x \frac{1}{2}\|Ax-b\|^2_2 + \lambda\|x\|_1$ ...
1
vote
1answer
546 views

Meaning of partial derivative in gradient descent

I haven't quite understood the correct meaning of what it means to take the partial derivative of a cost function with respect to the parameters, say theta. Suppose these parameters include 2 arrays ...
4
votes
1answer
288 views

Gradient descent: Shouldn't step size be proportional to inverse of gradient of residual?

It has been decades since I coded up any type of gradient descent algorithm to drive a function to zero (or to a minimum). I am following this tutorial, which minimizes $J(\overrightarrow{\theta})$. ...

1 2 3 4 5 15