Questions tagged [gradient-descent]
"Gradient descent is a first-order 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."
71
questions
4
votes
5
answers
5k
views
Gradient of a function as the direction of steepest ascent/descent
I am trying to really understand why the gradient of a function gives the direction of steepest ascent intuitively.
Assuming that the function is differentiable at the point in question,
a) I had a ...
- 492
48
votes
4
answers
42k
views
Gradient descent with constraints
In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method:
$$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$
where $\alpha_k$ is the step size ...
- 5,268
12
votes
2
answers
10k
views
Does gradient descent converge to a minimum-norm solution in least-squares problems?
Consider running gradient descent (GD) on the following optimization problem:
$$\arg\min_{\mathbf x \in \mathbb R^n} \| A\mathbf x-\mathbf b \|_2^2$$
where $\mathbf b$ lies in the column space of $A$...
- 3,145
3
votes
1
answer
885
views
A matrix calculus problem in backpropagation encountered when studying Deep Learning
I am studying the Algorithm 6.4 in the textbook Deep Learning, which is about backpropagation.
I am confused by this line:
$$\nabla_{W^{(k)}}J = gh^{(k-1)T}+\lambda\nabla_{W^{(k)}}{\Omega(\theta)}$$
...
- 885
72
votes
2
answers
47k
views
What is the difference between projected gradient descent and ordinary gradient descent?
I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
- 1,127
8
votes
3
answers
8k
views
Why is Newton's method faster than gradient descent?
Can you provide some intuition as to why Newton's method is faster than gradient descent?
Often we are in a scenario where we want to minimize a function f(x) where x is a vector of parameters. To do ...
- 1,074
22
votes
3
answers
45k
views
Optimal step size in gradient descent
Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\nabla F(a)$ implies that $F(b) \leq F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal $\gamma$ at ...
- 1,567
11
votes
1
answer
10k
views
Expectation of gradient in stochastic gradient descent algorithm
I'm studying stochastic gradient descent algorithm for optimization. It looks like this:
$$ \begin{aligned} L(w) &= \frac{1}{N} \sum_{n=1}^{N} L_n(w) \\ w^{(t+1)} &= w^{(t)} - \gamma \nabla ...
- 6,045
9
votes
2
answers
960
views
Gradient descent for differentiable convex functions
Suppose $f\colon\mathbb{R}^n\to\mathbb{R}$ is convex and differentiable, and assume that $f$ has a minimizer.
If $(x_k)$ is the sequence generated by exact gradient descent, must it converge to a ...
- 4,935
6
votes
2
answers
5k
views
Why does gradient ascent/descent exhibit zig-zag motion?
A good way to visualize gradient ascent/descent is to assume you are in a quadratic bowl or on a mountain. If I visualize this, then the direction of steepest ascent/descent is the one that points ...
- 426
3
votes
3
answers
4k
views
How to Project onto the Unit Simplex as Intersection of Two Sets (Optimizing a Convex Function)?
I would like to estimate a matrix $S$ by solving the following optimization problem
\begin{align}
&\min\limits_{s} f(S) \\
&\text{subject to }\sum_{i,j}s_{i,j}=1,\quad s_{i,j}\geq0~\forall(i,...
- 761
1
vote
2
answers
338
views
Is the sequence $(x_n)$ in Gradient Descent algorithm always convergent?
Let $f \in \mathcal C^1(\mathbb R^n,\mathbb R)$ be convex and $\nabla f$ be $L$-Lipschitz continuous. The sequence $(x_n)$ in Gradient Descent algorithm is defined as $$x_{n+1} = x_n -\gamma_n \nabla ...
- 17.7k
15
votes
3
answers
9k
views
Gradient is NOT the direction that points to the minimum or maximum
I understand that the gradient is the direction of steepest descent (ref: Why is gradient the direction of steepest ascent? and Gradient of a function as the direction of steepest ascent/descent).
...
- 426
3
votes
1
answer
705
views
Convergence of gradient descent without global Lipschitz gradient assumption
My question is very similar to this one and this one, but they haven't been answered.
Let $f \in C^2(\mathbb{R}^d, \mathbb{R})$ have compact sublevel sets and isolated critical points, and consider ...
- 1,722
2
votes
2
answers
486
views
Gradient descent: step size for a $C^{\infty}$ coercive function
Let $f: U \to \mathbb R$ be a $C^{\infty}$ function where $U$ is an open connected subset of $\mathbb R^n$. $f$ is coercive, i.e., $f(x) \to +\infty$ as $\|x\| \to \partial U$. This is equivalent to ...
- 3,548
0
votes
2
answers
193
views
is it wrong? -> using Gradient to get the steepest slope to go upwards, so in order get minimized loss we go the opposite [closed]
I am not good at mathematics and have been learning ML from Udacity.
In its tutorial video, the tutor says(I concluded it in a short way):
using Gradient to get the steepest slope to go upwards, so in ...
- 119
0
votes
1
answer
216
views
Is the directional derivative $f'(x;d)$ ALWAYS equal to $\nabla f^T d$? or only under certain conditions?
My professor always writes the directional derivative with the condition that the functionis $C^1$ smooth.
i see him write many times the directional derivative written as $f'(x;d)=\nabla f^T d$, but ...
- 1,603
0
votes
0
answers
91
views
Why is Gradient Descent always chosen for Neural Networks?
I am trying to understand why Gradient Descent are the chosen types of algorithm for optimizing the Loss Function in Neural Networks - and why other algorithms (e.g. EM Algorithm https://en.wikipedia....
- 3,224
72
votes
2
answers
50k
views
What is the difference between the Jacobian, Hessian and the Gradient?
I know there is a lot of topic regarding this on the internet, and trust me, I've googled it. But things are getting more and more confused for me.
From my understanding, The gradient is the slope of ...
- 951
26
votes
1
answer
23k
views
Log of Softmax function Derivative.
Could someone explain how that derivative was arrived at.
According to me, the derivative of $\log(\text{softmax})$ is
$$
\nabla\log(\text{softmax}) =
\begin{cases}
1-\text{softmax}, & \text{if $...
16
votes
7
answers
495
views
How can I "see" that calculus works for multidimensional problems?
Let's say I have some function f(x) = x^2 + b. I can see what's going on, I can count the slope geometrically even without knowing the rules of derivatives.
When I ...
- 209
11
votes
3
answers
10k
views
Why does gradient descent work?
On Wikipedia, this is the following description of gradient descent:
Gradient descent is based on the observation that if the multivariable function $F(\mathbf{x})$ is defined and differentiable ...
- 3,257
10
votes
1
answer
370
views
Are gradient flows the quickest way to minimize a function for a short time?
Let $F:\mathbb{R}^n \to \mathbb{R}$ be a smooth function, and let $p \in \mathbb{R}^n$. Let $\alpha(t)$ be the solution to the negative gradient flow of $F$, i.e.
$$ \alpha(0)=p, \, \, \dot \alpha(t)...
- 25.5k
9
votes
2
answers
3k
views
Intuition for gradient descent with Nesterov momentum
A clear article on
Nesterov’s Accelerated Gradient Descent
(S. Bubeck, April 2013)
says
The intuition behind the algorithm is quite difficult to grasp,
and unfortunately the analysis will not be ...
- 921
8
votes
1
answer
712
views
A possible bug in a highly cited paper (Adam gradient descent)?
My question comes from the paper Adam: A Method for Stochastic Optimization published on ICLR, which has been cited over $80,000$ times up to now. Specifically, in page 13, I think there is a 'bug' in ...
- 2,860
8
votes
1
answer
625
views
Physical interpretation of gradient descent
Introduction
Here are some high-level intuitions that seem to be folklore in the optimization community:
The gradient descent method is often motivated from a physical point of view, as a 'ball ...
- 3,560
6
votes
2
answers
5k
views
Why Does the Projected Gradient Descent Method Work?
Consider the problem
\begin{align*}
\min_{x \in \mathbb{R}^n} &\quad f(x) \\
s.t.: &\quad x \in C,
\end{align*}
where $C$ is a convex set. As $C$ is convex, the projection onto $C$, $P_C$, is ...
- 95
5
votes
1
answer
2k
views
Trying to understand the math behind backpropagation in neural nets
I am currently trying to understand the math used training neural network, in which gradient descent is used to minimize the error between the target and extracted. I currently following/reading this ...
- 325
5
votes
2
answers
346
views
Why must a function be closed for descent methods to work?
At the beginning of chapter 9 of Boyd & Vandenberghe's Convex Optimization, about unconstrained minimization, it is said:
The starting point $x^{(0)}$ for a method must lie in $\mathbf{dom} f$, ...
- 51
5
votes
1
answer
701
views
Proving: $\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}\leq f(x)-f(x^{*})\leq\frac{1}{2M}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$
let there be a strongly convex function $f(x)$.
I want to prove that if $\forall x\in Dom(f):mI\succcurlyeq\nabla^{2}f(x)\succcurlyeq MI$
then:
$\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^...
- 2,136
4
votes
1
answer
6k
views
Gradient descent versus Lagrange multipliers
I am new to optimization methods and trying to understand them. I am familiar with two main methods.
gradient descent, which, as I understood, means we try to calculate the next point on the ...
- 61
4
votes
0
answers
156
views
Gradient descent for functionals?
If $f:\mathbb{R}^2\longrightarrow\mathbb{R}$ is smooth, then given an initial point $x_0\in\mathbb{R}^2$, we can use gradient descent to find a sequence of points $\{x_i\}_{i=1}^{\infty}$ that ...
- 754
4
votes
2
answers
480
views
Gradient Descent for analytic function on a compact set
Suppose $f: K \to \mathbb R$ is an analytic function where $K \subset \mathbb R^n$ is a compact subset. Let us assume $f$ is not constant and $f$ achieves minimum at $\text{int}(K)$.
Let $\beta = \...
- 3,548
4
votes
0
answers
285
views
The stability of a gradient flow (discrete JKO scheme, proximal point)
Define a free energy functional on the space of probability densities (on $\mathbb{R}^d$, denoted $\mathcal{P}(\mathbb{R}^n)$)
$$E(\rho):=\int_{\mathbb{R}^d} f(x) \rho(x) dx+\int_{\mathbb{R}^d} \rho(x)...
3
votes
1
answer
612
views
Why is gradient describe the steepest ascent direction and not the steepest descent
I have checked all over the internet and I cannot find why is gradient shows you the steepest ascent and not the steepest descent
How can we proof that?
- 141
3
votes
3
answers
1k
views
Decrease in the size of gradient in gradient descent
Gradient descent reduces the value of the objective function in each iteration. This is repeated until convergence happens.
The question is if the norm of gradient has to decrease as well in every ...
- 3,626
3
votes
1
answer
3k
views
Gradient descent to solve nonlinear systems
I was reading the Wikipedia page for gradient descent, but I don't understand how the objective function:
Can be used to solve for $x_1, x_2,x_3$ as the objective function seems a bit arbitrary and I ...
- 493
3
votes
1
answer
120
views
Problem with Proof Gradient Steepest Ascent
I am going through the properties of the gradient, and in particular I try to proof why the gradient is pointing to the direction of the steepest ascent. Here is what I’ve done so far:
$$
\partial_vf(...
- 411
3
votes
1
answer
210
views
Gradient of Coefficient of Variation of weighted geometric mean
This question is another version of the one here which I've previously asked. the difference is instead of WM here we have exp(WM). exp(W×log(M)) is equivalent to weighted geometric mean of M when W ...
- 165
3
votes
0
answers
594
views
How to find Minimum of Function with Many Local Minima
I'm trying to find the smallest local minima within a given boundary condition, e.g., a circle. Currently, I'm using a monte carlo algorithm to approximate the minimum, followed by a gradient descent ...
- 355
3
votes
1
answer
322
views
first term in the asymptotic expansion using method of steepest descent
I am working with the following intgral:
$\int_{0}^{\infty}t^{n}e^{-x(t+\frac{1}{t})}dt$
as $x\rightarrow \infty$
Now, I have been trying to solve this using the method of steepest descent. After ...
- 423
2
votes
1
answer
759
views
proving:$f(x)-f(x^{*})\geq\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$
let there be a strongly convex function $f(x)$.
I want to prove that if: $\forall x\in Dom(f):mI\succcurlyeq\nabla^{2}f(x)$
then:
$f(x)-f(x^{*})\geq\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{...
- 2,136
2
votes
1
answer
561
views
Generalization of Gradient Using Jacobian, Hessian, Wronskian, and Laplacian?
I know there is a lot of topic regarding this on the internet, and trust me, I've googled it. But things are getting more and more confused for me.
From my understanding, The gradient is the slope of ...
- 951
2
votes
2
answers
3k
views
Gradient of a softmax applied on a linear function
I am trying to calculate the softmax gradient:
$$p_j=[f(\vec{x})]_j = \frac{e^{W_jx+b_j}}{\sum_k e^{W_kx+b_k}}$$
With the cross-entropy error:
$$L = -\sum_j y_j \log p_j$$
Using this question I get ...
- 2,940
2
votes
1
answer
411
views
Mazur's lemma without Hahn-Banach theorem/axiom of choice?
In the development of gradient-flow theory (in Hilbert-space $H$), we soon stumble on the question whether the function $u \mapsto \varphi[u]:=\frac{1}{2}\|u\|^2+I[u]$ -where $I:H \to \mathbb{C}$ is ...
- 2,475
2
votes
2
answers
857
views
Minimization of positive quadratic function using gradient descent in at most $ n $ steps
For minimization positive quadratic form $$f = \frac{1}{2}\left\langle Ax,x \right\rangle - \left\langle b,x\right\rangle \rightarrow \min_{x\in\mathbb{R}^n},$$ we use gradient descent $$x^{k+1} = x^{...
- 23
2
votes
1
answer
366
views
Gradient descent inside the expectation-maximization (EM) algorithm
I am feeling super uncertain about how much I can play around with the EM algorithm. Here is my question:
In the EM algorithm, during the M-step, one attempts to find a parameter value, $\theta$, that ...
2
votes
1
answer
95
views
Gradient of a complex-valued function with complex-valued variables
I have to minimize a cost function:
$J = \frac{1}{2} e^* e$, where $e \in C$ is the error between the output of my ML model $y \in C$ and the desired value $m \in C$. Therefore, e is a complex number. ...
- 113
2
votes
1
answer
69
views
Gradient of Function of Complex Matrices
Consider the following function:
$$ f(T) = \| T^{T}TB - C\|^2_2 $$
where $T, B, $ and $C$ are all complex matrices. Let $T = X + iY.$ I wish to compute $\nabla f$ i.e. $\dfrac{\partial f}{\partial T}$....
2
votes
1
answer
299
views
Gradient of Coefficient of Variance
I have a d×n matrix called M. What is the best 1×d W that minimizes CoV(WM) which is Coefficient of Variance of W×M, considering that W sums to 1
$$\underset{W}{\operatorname{argmin}}\frac{SD(WM)}{...
- 165