Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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."

0
votes
2answers
19 views

Obtaining the gradient of a vector-valued function

I have read that obtaining the gradient of a vector-valued function $f:\mathbb{R}^n \to \mathbb{R}^m$ is the same as obtaining the Jacobian of this function. Nevertheless, this function has only one ...
2
votes
0answers
35 views

Gradient Descent: Cost Function

I'm trying to implement the gradient descent method for the problem of minimising the following function: $$f(x) = \frac{1}{2}(x-m)^{T}A(x-m)-\sum\limits_{i=1}^n\log\left(x_i^{2}\right),$$ where $x \...
1
vote
1answer
18 views

Gradient descent (derivative) from an algorithm to minimize the error, but doesn't work with negative real value

Best I've a simple algorithm and I would like to minimize its error. Therefore I'm planning to calculate the derivatives with respect to the input. algorithm: -- constant values -- $$ real = 3 $$ -- ...
1
vote
0answers
12 views

BFGS: Wolfe conditions and Algorithm error on absolute values

I debated whether to put this in SO or Mathematics but the problem I suspect is more a mathematical question rather than a programming one. I have a simple objective function: $$f(x) = |x_0| + |x_1| ...
0
votes
0answers
16 views

question about subgradient method proof re: moving closer to optimal set

The exercise is: And the first line of the provided solution says: I am not sure I buy this. How can we simply replace the $f(x) - f(x^*)$ with $g^T(x - x^*)$? Isn't the inequality in the wrong ...
1
vote
1answer
43 views

Understanding gradient related sequence

Given $f : \mathbb{R}^n \rightarrow \mathbb{R}$ and a sequence $\{ x_k\} \in \mathbb{R}^n$, a sequence $\{ v_k\} \in \mathbb{R}^n$ is said to be gradient related ([1]) if for any subsequence $\{ x_k\}...
0
votes
0answers
17 views

How to find a global(local, if global is impossible) minimizer under some equation constraints in a reasonable time?

I'm looking for an algorithm that finds a global minimizer of a $C^1$ class function $f: \mathbb R^n \to \mathbb R$ under the constraint $x\in S$, where $S = \{x\in\mathbb R^n | g(x)=0, x_i\geq 0$ for ...
1
vote
0answers
23 views

Derivation of Weight Update for Softmax Policy Gradient (RL)

Following this resource on Policy Gradients, I've arrived at $$\nabla_\theta J(\theta) = (\sum\nolimits_{t=1}^{T}\nabla_\theta \ln \pi_\theta (a_t | s_t))(\sum\nolimits_{t=1}^{T}r\ (s_t, a_t))$$ as ...
0
votes
0answers
9 views

is negative directional derivative a sufficient condition for descent direction?

According to my lecture notes, this is the definition of a descent direction: $\bf{d}\in\mathbb{R}^n$ is called descent direction of the function $f:\mathbb{R}^n\to\mathbb{R}^n$ at the point $\bf{x}...
0
votes
0answers
20 views

Why gradient descent fails in this problem?

$f(x_1,x_2) = sup_{y_1,y_2}(x_1y_1+\gamma x_2y_2) : y_1^2+y_2^2 \leq 1, y_1 \geq 1/\sqrt{1+\gamma}, \gamma >1$ When applying gradient descent with starting point $x_0 = (\gamma, 1)$ and exact line ...
0
votes
0answers
23 views

Gradient method: convergence in finite number of steps for $f(x_1,x_2) = x_1^2 + 4x_2^2 - 4x_1 - 8x_2$

$f(x_1,x_2) = x_1^2 + 4x_2^2 - 4x_1 - 8x_2$ I already proved that the minimum point is $(2,1)$ finding the gradient and analysing the eigenvalues of Hessian matrix. I need to prove that gradient ...
2
votes
1answer
152 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)}$$ ...
0
votes
0answers
26 views

Closed form solution for Gradient Descent step - from B and V

I am trying to derive the Gradient descent step xk also given as excercise 9.6 in the book - Convex Optimisation - B and V . The G.D step is found for the following function . $$f(x) =\frac{(x_{1}^{2}...
3
votes
0answers
70 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 ...
2
votes
1answer
100 views

Second-Order Taylor Series Terms In Gradient Descent

My machine learning textbook states the following when discussing second-order Taylor series approximations in the context of Gradient descent: The (directional) second derivative tells us how well ...
0
votes
1answer
61 views

Two different ways to train a neural network

Gradient descent (GD) is a common algorithm designed to find a local minimum of an assigned cost function. Simple feedforward neural networks, as long as my understanding goes, try to estimate a ...
1
vote
1answer
73 views

Gradient Descent and an ascent direction

Consider $f:\mathbb R^n \to \mathbb R$ such that $f$ is quadratic and convex. Meaning, $f(x)=x^TAx+b^Tx$ for $A\succ0$. Conjecture: Consider the Gradient Descent method with exact line search for ...
0
votes
0answers
49 views

Derivative of Fourier Transform to phase for Gradient descent

My Problem is the following: I have the complex signal over time $$f(t) = r(t)\cdot exp(i\phi(t)) \in \mathbb{C}$$ with the corresponding discrete Fourier Transform in frequency space $$s(\omega) = ...
0
votes
0answers
11 views

pocs vs conjugate gradient.

I am just wondering in general, how does conjugate gradient vs pocs (projection onto convex sets) in terms of approaching the true solution? I am doing simulation, but I would really like to have ...
0
votes
0answers
28 views

Reason why gradient descent cannot jump between connected components of level sets (when choosing appropriate step size)

Let us assume we have a function that is $l$-strongly convex and $L$-smooth on a connected component of a level set; why can gradient descent not jump from one connected component to another one when ...
0
votes
1answer
93 views

Is logistic loss function L-smooth?

Assume $f(x)$ has an L-Lipschitz continuous gradient say $L$ i.e there is a constant L>0 such that $$\|\nabla f(x) - \nabla f(y)\|_2 \le L\|x-y\|_2$$ for any $x,y$. Does $f(\beta) = \sum_{i=1}^n Y_i ...
0
votes
0answers
23 views

Problem related to Lipschitz Steepest Descent

(a) suppose that $f$ is quadratic and of the form $f(x)=1/2x^TQx-b^Tx$, where Q is positive definite and symmetric. Show that the Lipschitz condition $||\nabla f(x) - \nabla f(y)|| <= L||x-y||$ is ...
2
votes
1answer
42 views

Does this gradient descent with asymptotically vanishing stepsize converge?

Suppose $f: \mathbb R^n \to \mathbb R$ is a $C^1$ convex function with gradient being Lipschitz continuous, i.e., $\|\nabla f(x) - \nabla f(y)\|_2 \le L\|x-y\|_2$. Consider the gradient update scheme ...
2
votes
1answer
55 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 ...
0
votes
0answers
31 views

Smooth but not convex

In Theorem 4.2. of the following lecture http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_4_Scribe_Notes.final.pdf it is shown that when the objective function is smooth and not necessarily ...
5
votes
2answers
120 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 = \...
0
votes
0answers
13 views

Discrete vector field - find local min / max

I have discrete vector field defined on grid 640x480. The input data are from some wind simulation. At each point, I have direction and magnitude. I want to locate locale extrema. I have tried to use ...
1
vote
0answers
24 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 ...
0
votes
0answers
23 views

Gradient descent vs. system of equations

Given the matrices $\mathbf{t}_{M\times 1}$ and $\mathbf{Q}_{M\times N}$, we want to find $\mathbf{p}_{N\times 1}$ that minimizes $\epsilon = ||\mathbf{t} - \mathbf{Q}\mathbf{p}||_2$. In order to do ...
1
vote
0answers
33 views

Condition number of Hessian matrix when Hessian is singular

In gradient descent on a quadratic problem, $$\min _{x \in \mathbb{R}^n}\frac12 \langle Hx, x \rangle + \langle b, x \rangle + c \qquad H \text{ symmetric, positive semi-definite}\quad b \in \...
0
votes
1answer
61 views

Gradient descent on non-linear function with linear constraints

Here is an optimization problem I'm trying to solve: Objective function to be minimized: $$ f(x) = -\sum_{i=1}^{n}(x_{i}+a_{i})\bigg[1-\exp\bigg(-\frac{x_ib_i}{x_i+a_i}\bigg)\bigg] $$ where the ...
0
votes
1answer
22 views

softmax binary classification and monotonically decreasing substitution function

In this paper and later in this paper authors explain a modification to the original softmax function. If the original softmax function is: $$\mbox{soft}(i) = \frac{e^{w_{y_i}^T\cdot \ x_i}}{\sum_je^{...
0
votes
0answers
43 views

Support Vector Machines: question about the underlying math

I'm new to Support Vector Machines and I've been trying to get into the underlying math (instead of just using Scikit Learn or something like that). I understand the math behind it up to the point ...
0
votes
0answers
40 views

Non-convex Constraint Satisfaction problem

I am not an expert on constrained optimization problems so I was wondering whether some of you could help me out. Let $h_{\mu}$ stand for : \begin{equation} h_{\mu} (\vec{X}) = \frac{1}{\sqrt{N}} \...
0
votes
1answer
37 views

Addition of two L-smooth function is also L-smooth?

Assume $f(x)$ has an L-Lipschitz continuous gradient say $L_1$ i.e there is a constant L>0 such that $$\|\nabla f(x) - \nabla f(y)\|_2 \le L\|x-y\|_2$$ for any $x,y$. Also $g(x)$ has an L-Lipschitz ...
0
votes
2answers
67 views

Example of convex function which is differentiable, but not twice differentiable?

Are there convex functions for which hessian is not defined, but the gradient is defined everywhere? I was looking at projected gradient descent, as well as Newton's method for solving optimization ...
0
votes
3answers
87 views

Why do we need sub-gradient methods for non-differentiable functions?

Why do we need sub-gradient methods for non-differentiable functions? Consider optimizing $f(x) = max_{i} (a_{i}^Tx+b_{i})$. Clearly this is non-differentiable at multiple points, and the ...
0
votes
1answer
35 views

Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient

Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient i.e there is a constant L>0 such that $$||\nabla f(x) - \nabla f(y)||_2 \le L||x-y||_2$$ for any $x,y$? I tried to derive it ...
0
votes
0answers
154 views

Partial derivative in gradient descent for social recommendations

In paper entitled with "recommendations in signed social networks" by Jiliang Tang, he suggest model for capturing local and global information from signed social networks as follows: $$min \sum_{i=1}...
0
votes
0answers
17 views

What formal argument allow to pass from EL equations to gradient descent?

Given a functional of the form $$ J[y] = \int_{a}^b F(x,y,y')dx $$ the EL equation is given by $$ \frac{dJ}{dy} = \left( \frac{\partial}{\partial y} - \frac{d}{dx}\frac{\partial}{\partial y'} \...
0
votes
0answers
15 views

Optimization and splitting the problem by dependent/independent variables

I have the following nonlinear function: $$f_{(a,b,c,d)}$$ and measurements : $$f_{measured}^{i}$$ for $i = 1, 2, 3, 4 ...$ The problem is defined as minimization of : $$\min_{a,b,c,d}\bigg(\sum_{...
1
vote
0answers
33 views

Gradient descent versus finding where the gradient vanishes via solving systems of equations

I started learning machine learning and got stuck at the following questions: Why do we need to iterate the gradient descent algorithm? Why don't we equate the gradient to zero and find all local ...
0
votes
0answers
50 views

Can someone help me derive this equation?

I have read this paper Translation-based Recommendations and I have some question about the derivation. I'm not familiar with the derivative of vector. I want to derive $$\frac{\partial (\hat{p}_u,...
0
votes
0answers
30 views

About the feasibility of a subgradient step

A vector $v \in \mathbb{R}^d$ is a subgradient of a function $f\colon \mathbb{R}^d \to \mathbb{R}$ in a point $x \in \mathbb{R}^d$ if, for every $y \in \mathbb{R}^d$, $$f(y) \ge f(x) + \langle x - y,...
0
votes
2answers
162 views

Why does the projected gradient 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 ...
2
votes
1answer
53 views

Gradient derived from Jacobian?

I was reading this wikipedia page on gradient descent (section: Solution of non-linear system) when I came across this formula: $\nabla F(\mathbf {x} ^{(0)})=J_{G}(\mathbf {x} ^{(0)})^{\mathrm {T} }G(...
1
vote
0answers
35 views

Backpropagation: Derivaiton of Loss Gradient

In the book "Artifical Intelligence: A Modern Approach" from S. Russel there is a derivation of the gradient of the loss with respect to the weights w used for backpropagation on page 735. I stumbled ...
0
votes
0answers
41 views

Finding the gradient of a variant of a total variation regularized least squares cost function

As the question states, given a sum-function : $$f(x) = \sum_{ij}\left({\sqrt{(x_{ij} - y_{ij})^2+1}}+\frac{1}{2}\sqrt{(x_{ij}-x_{i+1j})^2+(x_{ij}-x_{ij+1})^2 +1}\right)$$ where $x_{ij} $ describes ...
0
votes
0answers
43 views

Is there a hat matrix for gradient descent?

Assume gradient descent on a linear cost function converges for some sequence of examples, is it possible to define a hat matrix for gradient descent that accounts for the gradient update of these ...
1
vote
1answer
63 views

Gradient/Steepest Descent: Solving for a Step Size That Makes the Directional Derivative Vanish?

The following excerpt is from chapter 4.3 of Deep Learning, by Goodfellow, Bengio, and Courville: The authors state that sometimes we can solve for the step size that makes the directional derivative ...