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."
999
questions
0
votes
0
answers
23
views
Nelder-Mead implementation in Python
I am working on a non-linear optimization problem, containing bounds and constraints for the variables. Very complex problem involving networks and logical functions. I have been switching a tool from ...
- 131
0
votes
0
answers
18
views
How to calculate convergence rate of gradient descent
I am researching on gradient descent. I am looking at the convex case with Lipschitz-continous gradients.
For that I'm using Nesterov's "Lectures on convex optimitzation".
His result for the ...
- 1
1
vote
0
answers
44
views
Gradient descent derivation
Background: Regular gradient descent can be written something like $x_{t + 1} = x_t - \eta g_t$, where $g_t$ is the gradient of the function we're trying to optimize.
Problem: If we have a (symmetric, ...
- 71
2
votes
1
answer
41
views
How do I minimize sum of modules?
I need to minimize sum of modulus of linear combinations of the variables. For example:
$$
f = |1+a-2b+3c| + |-a+b+c| + |a| + |b| + |c|
$$
My initial plan was to calculate gradient and then perform ...
- 137
0
votes
2
answers
137
views
Clarification on the Interpretation of Gradient Vectors
This is a quick question! I keep seeing gradient vectors explained as such:
"If you imagine standing at a point $(x_0,y_0...)$ in the input space
$f$, the vector $\triangledown f$$(x_0,y_0...)$ ...
- 83
0
votes
0
answers
29
views
Understanding Gradient descent with momentum equations
I'm working on implementing gradient descent with momentum for root finding but I am slightly confused about a part of the equation, it's said that you can replace your regular gradient step by doing: ...
- 11
0
votes
0
answers
55
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....
- 2,298
1
vote
1
answer
27
views
Unbiased estimate of log-likelihood of Markov bridge
Note: Cross-post from CrossValidated.
I have the following problem I am trying to solve. I have a parametric family of "transition" distributions $p_\theta(x_{i+1}\mid x_i)$ and I am given a ...
- 29.5k
0
votes
0
answers
26
views
Looking for a source to cite for the fact that conjugate gradient converges more slowly when matrix is positive semidefinite
This is surprisingly difficult for me to look up for some reason. I assume it's stated somewhere in a canonical textbook on the subject but I haven't been able to find anything. For a simple example, ...
- 221
0
votes
0
answers
29
views
Finding the closest positive definite matrix
Let $L$ be the symbolic $n \times n$ lower triangular matrix and $S$ a real symmetric $n \times n$ positive semidefinite matrix. Fix a real symmetric $n \times n$ positive definite matrix $A$ with the ...
- 187
0
votes
0
answers
25
views
Gradient steepest ascent interpretation breakdown
We tend to be taught to interpret the gradient to be the direction of steepest ascent of a vector valued function.
However, I'm confused as to why when we reach the minimum of a function, say f(x,y) = ...
- 1
0
votes
0
answers
12
views
Gradient Descent: Converting geometric bound on successive $x$-values to bound on successive function values
I have the following problem:
For a $L$-smooth and $\mu$-strongly convex function $f$, prove that gradient descent with step size $t\leq\frac{1}{L}$ satisfies $f(x_n)-f(x^*)\leq(1-\mu t)(f(x_{n-1})-f(...
1
vote
0
answers
30
views
How to compute the optimization process of PPO algorithm?
I'm building the Proximal Policy Optimization algorithm from scratch (well, using PyTorch). I've been studying it by my own, but I'm a little bit confused in the optimization phase, here is the thing.
...
- 111
0
votes
0
answers
61
views
Convergence condition for gradient descent on a non-linear convex function
The Wikipedia page about the Landweber iteration (https://en.wikipedia.org/wiki/Landweber_iteration#:~:text=The%20Landweber%20iteration%20or%20Landweber%20algorithm%20is%20an,special%20case%20of%...
- 60
0
votes
0
answers
9
views
Different step sizes for each feature in a multiple linear regression
I am trying to learn multiple linear regression using MATLAB. I am using Weight (x1) and Horsepower (x2) as features to predict the mileage (y) of the vehicle.
So, the model would be $y_{est}= w_1x_1+...
- 137
0
votes
0
answers
20
views
Show the convergence of a numerical algorithm (gradient type)
I would like to know if I have a good understanding of what explains the following result
Let $V$ be an Hilbert space, $J$ a strongly convex and differentiable functional. Assume $J’$ is locally ...
- 1,262
0
votes
1
answer
87
views
Gradient of a loss function
Considering the following Loss function:
$$A{L_t}\left( {{\mathbf{w}_t}} \right) = \sum\nolimits_{j = 1}^k {{L_t}\left( {{b^j}} \right)w_t^j}$$
I want to calculate the gradient of it ($\nabla A{L_t}\...
- 113
0
votes
0
answers
29
views
Deriving a gradient of a function involving matrix inversion
There are component of a cost function $f(\mathbf{s})$ where $\mathbf{s}\in\mathbb{C}^N$ is the parameter (input) of the function and $\mathbb{C}$ denotes the complex dimension. There are matrices $\...
- 27
0
votes
0
answers
26
views
Weight Vector calculation in CW-OGD strategy
I'm trying to understand an Online Portfolio Selection (OPS) strategy proposed by Zhang et al. (2021), named combination weights based on online gradient descent (CW-OGD). The algorithm is as follows:
...
- 113
0
votes
2
answers
74
views
convergence of gradient descent algorithm
How to show that for $r>0$ small enough, the sequences $(x_n)_n$ and $(y_n)_n$ defined by :
$$
x_{n+1} = x_n -4r(x_n^3+y_n)\\
y_{n+1} = y_n -4r(y_n^3+x_n)
$$
are converging for any inital condition ...
- 1,942
1
vote
0
answers
32
views
Gradient flow of Nesterov accelerated gradient methods
I am reading a nice paper [1] that gives a differential equation for NAG methods. The updating rules of NAG are:
$$x_k = y_{k-1} - \eta \nabla f(y_{k-1}) \tag{1}$$
$$y_k = x_k + \frac{k-1}{k+2}(x_k - ...
- 33
0
votes
0
answers
29
views
How to make the gradient for a negative in triplet loss move ortogonal to the anchor and positive?
So i've implemented a convolutional neural network in C++ and I'm playing around with loss functions and gradient calculations. The network outputs the f(a), f(p) and f(n) of the last layer, which is ...
- 1
0
votes
0
answers
45
views
Proof for basic properties of proximal operators
I am reading the paper "Proximal algorithms" by N. Parikh and S. Boyd, and I found interesting the basic properties of proximal operators. However, I can't prove the equivalence for the ...
2
votes
1
answer
119
views
Compute the complexity of the gradient descent.
Let $f$ be a $L$-smooth and convex function. We denote $\|\cdot\|$ to be the $\ell_{2}$-norm on $\mathbb{R}^{n}$. The definition of $f$ being $L$-smooth is the following $$f(x)\leq f(y)+\langle \nabla ...
- 5,575
1
vote
1
answer
64
views
How to use co-coercity property to prove $\|x_k - x^* \|\leq (\frac{L-m}{L+m})^k \|x_0 - x^*\|$ for steepest descent with $\alpha = \frac{2}{L+m}$?
I am trying to solve exercise 3.5 in Optimization for Data Analysis but can't seem to get it quite right.
The exercise is as follows:
Suppose that $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is a ...
- 11
1
vote
1
answer
52
views
Seeking Proof for Geometric Optimality Condition in Constrained Optimization
I've been studying constrained optimization problems and came across the geometric optimality condition, which states that if x^* is an optimal solution and there exists an arbitrary smooth curve $\...
- 13
0
votes
0
answers
11
views
Convergence of stochastic approximation with markov chain input and some nontrivial dependence on input?
Assume $u_t$ is some time-homogenous Markov-Chain with unique stationary distribution $\pi$.
Consider iterations of the form
$$x_{t} = f(y_t,u_t)$$
$$y_{t+1} = y_t + \varepsilon_t \nabla_y g(v,w,y)\...
- 1,484
1
vote
0
answers
42
views
Coefficient for the gradient term in stochastic gradient descent (SGD) with momentum
I'm studying SGD with momentum and have come across two versions of the update formula.
The first is from a wiki same as from the original paper:
$$
\Delta w^t = \alpha * \Delta w^{t-1} - lr * \nabla ...
- 23
0
votes
0
answers
23
views
Is it possible to change a weight matrix $W$ so it minimize a vector $J$?
Assume that we have a weight matrix $W \in \Re^{n x n}$ somewhere and if it's changing, then a vector $J \in \Re^{m}$ is going to be minimized.
The problem is that this is not an ordinary optimization ...
- 2,850
0
votes
0
answers
25
views
Help understanding convergence proof (Momentum algorithm)
I am trying to understand the convergence analysis/derivation of the momentum algorithm, or the stochastic heavy ball algorithm, using the regret bound analysis from different research papers.
https:/...
- 21
0
votes
0
answers
39
views
What is the form of the gradient with respect to a complex matrix?
We know that the definition of the gradient of a real-valued function with respect to a parameter is that the steepest incremental direction at the point of the current parameter position. The form of ...
- 27
2
votes
1
answer
121
views
Gradient descent minimum step size
Consider a differentiable function $f:\mathbb{R}^n \rightarrow \mathbb{R} $. We want to find stationary point of the gradient of $f$. Therefore choose stepsize $\sigma_k$ and direction $d_k$, such ...
- 389
1
vote
2
answers
97
views
The steepest descent direction constrained to non-negative variables
Recently, another user asked about the steepest descent direction constrained to non-negative variables, but using the $L_1$ norm to avoid null directions, see this link. His ideas led to the ...
- 716
1
vote
0
answers
61
views
gradient's norm is greater than epsilon, implies the function unbounded?
I am trying to prove a step from a larger problem, and I think that it's correct because the geometry intuition that the function is decreasing on the direction that is opposite to the gradient and ...
- 11
0
votes
0
answers
31
views
About minimizing dynamic of a convex function
Suppose that we have a strictly convex function $f: \mathbb R \rightarrow \mathbb R$ that admits a unique minimizer $x^*$ and $f(x^*)=0$. Let $x_0< x^*$, clearly $f$ is decreasing on $[x_0,x^*)$ ...
- 313
0
votes
1
answer
63
views
Projection onto unit $\ell_2$ ball in explicit form not projection form
When the gradient of a differentiable scalar-valued function is Lipschitz, i.e.,
$$ \|\nabla f(y) - \nabla f(x)\| \leq L\|y-x\| $$
for all $x, y \in \mathbb{R}^n$ and some $L>0$, then it is well-...
- 113
1
vote
0
answers
78
views
Comparing the rate of convergence of steepest descent method
I am wondering if we can compare the convergence rate of optimization methods, measured using different error definition.
For example, from the book Optimization for Data Analytics, the authors ...
- 11
0
votes
0
answers
100
views
Why is conjugate gradient descent a better option than gradient descent?
From what I understand, we use the conjugate gradient method to solve a linear equation or to optimize a quadratic equation. Why is it more efficient in solving those problems than the gradient ...
3
votes
0
answers
79
views
What happens if you apply "gradient descent" to the complex derivative?
In gradient descent you have a function $f:\mathbb{R} \rightarrow \mathbb{R}$. You choose an initial point $x_0$, and set $$x_{i+1} = x_i - \gamma f'(x_i)$$ Repeating this with small enough step size $...
- 273
1
vote
0
answers
32
views
Correlation between hinge loss function, Langrage function and $a_i$
The function $f(w,b) = \frac{1}{2} ||w||^2$ is our objective function while our constraints are all the correct classifications of the data points expressed as $g(w,b) = \sum_{i=1}^{l} (y_i (x_i \cdot ...
- 11
0
votes
0
answers
28
views
Clipped projected gradient descent gets stuck in local minima
I have a Linear Programming problem of the form min $cx$ s.t. $Ax=b$, $x\geq0$ which I want to solve using projected gradient descent.
I derived the projection operators
$P = I - A^T (A * A^T)^{-1} * ...
- 13
-1
votes
2
answers
83
views
Why doesn't optimization result in the same weights for all neurons in the same layer? [closed]
I would like to understand why in a single-layer network, given that all neurons use the same training examples (all of them), the gradient descent method does not reach the same solution for the ...
- 11
0
votes
0
answers
13
views
How does batch normalization enable larger learning rate?
I struggle to understand how batch normalization (BN) enables larger learning rates during gradient descent according to the original paper. I am aware that some of the explanations given in the ...
- 23
3
votes
2
answers
74
views
Show that in gradient descent the gradient goes against 0 (Under certain conditions)
So we have gradient descent: $$x^{(i+1)} = x^{(i)} - \tau \nabla f(x^{(i)})$$
And we gotta show that $$\left|\nabla f\left(x^{(j)}\right)\right| \to 0$$
The conditions are:
$f: \mathbb R^n \to \...
- 81
0
votes
1
answer
107
views
Is it possible to "derive" gradient descent using Lagrangian multipliers?
I'm thinking about this in 1-dimension but would have thought this will generalise fairly trivially to higher dimensions.
If we're currently at $x=x_{1}$, and we have relatively easy access to $f(x_{1}...
- 101
1
vote
0
answers
45
views
Vanishing/Exploding gradients clarification
I'm trying to gain deper understanding of the logic behind vanishing and exploding gradients. Most sources I've come across explain the problem by saying that when the weights become too small, the ...
- 23
0
votes
0
answers
34
views
Graident of Weighted Power Mean W.R.T Parametirization of ML Model
Let $H = \{h_{\theta}: \theta \in \Theta \subseteq \mathbb{R}^d\}$ be the hypothesis class that we will use to find the classifier for the classification task of interest, where each classifier $h \in ...
2
votes
1
answer
116
views
Minimize $f(x,y) = x^2 - cxy + y^2$ using co-ordinate descent $\big{(}$for $c \in [0,2) \big)$
In a course I am taking on programming and algorithms for data scientists, I came across the following example of using co-ordinate descent to find a local minimum of a function. However, it is ...
- 3,741
0
votes
1
answer
73
views
Gradient descent over a restricted convex domain — how do we guarantee that we stay in the domain if the global minimizer is outside of it?
Let $f:\mathbb R^d \rightarrow \mathbb R$ be a convex function and $A \subset \mathbb R^d$ a convex set. We are interested in finding the minimum of $f$ over $A$. We have the gradient of $f$ and we ...
- 2,156
1
vote
0
answers
42
views
On gradient descent on $\beta \mapsto \frac1n \sum_{i=1}^{m} r_i^2(\beta)$
In the gradient descent algorithm that is used in minimizing a cost function. We give the general gradient descent update rule:
$$ x_{n+1} = x_n - \lambda \nabla f(x_n) $$
We want to apply it to the ...
- 148