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
0answers
30 views

Why my gradient descent seems to diverge “pair-wise”?

Why my gradient descent seems to diverge "pair-wise"? I've checked the algorithms and they work for golden section line search and "small step parameter". However, when trying to get the algo to ...
1
vote
2answers
39 views

Proximal gradient method justification

If $f$ and $g$ are respectively a differentiable function and a convex, lower semi-continuous function, then the algorithm defined by: $$ x^{k+1} = \text{prox}_{\gamma{g}}[x^{k} - \gamma\nabla{f(x^{k}...
1
vote
1answer
49 views

Calculate gradient of the spectral norm analytically

Given a matrix $F \in \mathbb{C}^{m \times n}$ such that a $m>n$ and other matrix $A$ (non-symmetric matrix) of size $n \times n$ and spectral norm as: $$\|A-F^*\operatorname{diag}(b)F\|_2 = \...
0
votes
0answers
16 views

How to take derivative of log loss function in gradient descent?

I know the gradient descent about $z=wx+b$. But how to implement the derivative values of $w$ and $b$ in Python? I see some example like ...
1
vote
0answers
16 views

Projected Conjugate Gradient or BFGS for bound constrained optimization

We know how projected gradient descent works for bound constrained optimization (https://neos-guide.org/content/gradient-projection-methods). It is basically steepest descent with an additional ...
0
votes
0answers
36 views

Gradient Descent for Exponential Functions

I am trying to develop a non-linear regression for several functions (power, log and exponential). the idea was to use a log transformation to get an initial set of points, close enough to the real ...
1
vote
0answers
38 views

Complex scalar derivative of trace of complex matrices $\frac{d}{d z} Tr[A U(z) B U^H(z)] $

I'm trying to numerically find the maximum of $$ f(z) = Tr[ A\;U B\; U^H], \quad U=U(z,z^*),\\ A,B,U\in\mathbb{C}^{n\times n},\;\; A=A^H, \quad B=B^H $$ using gradient descent(ascent) w.r.t. $z \in {...
0
votes
0answers
16 views

Problem in calculating the gradient of a function?

I am trying to understand the gradient calculation of a formula, which is an optimization function and trying to maximize the GDL (Generalized Dice Loss) where, w_l...
0
votes
0answers
11 views

Will the gradient ascent method work?

I'm trying to use the gradient ascent method on a function $F{\theta}$, where $F$ is the multiplication of Normal multivariate densities, with a composition of a very complex function of the ...
2
votes
1answer
40 views

Looking for two separate functions with intersecting point and equal gradient

I want to explain a disadvantage of Gradient Descent where the gradient itself doesn't give information about how far we are away from the local/global minimum. Say we have two functions with an ...
0
votes
1answer
13 views

Explanation of gradient descent on convex quadratic

Can someone explain the following: $$f(x) = \frac{1}{2}w^TAw - b^Tw$$ Assume AA is symmetric and invertible, then the optimal solution $w^{\star}$ occurs at $$w^{\star} = A^{-1}b$$ and $$\nabla f(w)...
0
votes
0answers
27 views

Newton's Method for a step size to move in the direction of the gradient

I am reading this article that talks about Newton's method that can give us an ideal step size to move in the direction of the gradient. I do not understand what $\epsilon$ is in the following part ...
0
votes
0answers
41 views

How relevant are theoretical convex optimization convergence rates in practice, when parameters are unknown and function may be nonconvex?

There are many theoretical results known on convergence rates for various (possibly stochastic) convex optimization problems. For example, the popular review on optimization algorithms for machine ...
0
votes
1answer
37 views

Convergence rate of Gradient Descent

I was trying to solve a simple gradient descent problem. If we have $f(x) = x^2$, and a learning rate, $\eta$, that guarantees that the algorithm converges, then in how many steps will my algorithm be ...
0
votes
0answers
8 views

Gradient ascent curves

Let $f:R^2\rightarrow R$ be continuously differentiable $m$ times. Pick $(x,y) \in R^2$. Define the "gradient ascent curve from $(x,y)$ on $f$" to be the limit of the path followed by performing ...
0
votes
0answers
19 views

Total Least Square fitting

Say I want to fit a straight line using Total Least Square (as opposed to Least Square), which is to minimize the sum of (yi-k*xi-b)^2/(k^2+1) over all xi's and yi's, where xi's and yi's are training ...
0
votes
1answer
30 views

minimize a function using SGD

I have to solve the following exercice : $$ min ||Ax - y||_2 + ||x||_2^2$$with respect to x, where A ∈ $R^{q×p}$, x ∈ $R^p$ and y ∈ $R^q$. Use stochastic gradient descent. My first question is how ...
1
vote
0answers
32 views

Mirror descent on a 1-ball

I have been recently reading about mirror descent, which essentially generalizes gradient descent to non-Euclidean spaces. Nearly every reference I find on this subject gives the same example for ...
1
vote
1answer
34 views

Functional Gradient Descent and Functional Taylor Expansion

The questions are based on the below screenshots. Can somebody explain how the functional Taylor expansion is related to a "standard" function Taylor expansion? In particular, I am concerned with ...
1
vote
1answer
34 views

Is Lipschitz condition on derivatives essentially the same thing as epsilon-delta proof?

I am very confused about Lipchitz gradient/derivative. It's often used in machine learning proofs about gradient descent. Are Lipschitz and epsilon delta proof essentially the same thing? Lipchitz: ...
1
vote
0answers
35 views

Why is the Frank-Wolfe algorithm projection-free while gradient descent isn't?

While reading this article about the Frank-Wolfe algorithm, I did not understand why the Frank-Wolfe algorithm is projection-free, while the gradient descent is not. I think the problem is, that I do ...
2
votes
0answers
23 views

How to solve linear regression with an uncommon error function?

For common linear regression problems, the error terms are $l2$ norm. In other words, the error between measurement (independent values) $y$, and estimate $\hat{y}=X\beta$ is measured as $||y-\hat{y}||...
1
vote
1answer
44 views

L2-norm with estimated weights

Suppose I'm performing linear regression. My lecturer said the formula below can be used for estimating the weight vector that is passed to the L2-norm part of the loss function but he didn't ...
0
votes
1answer
48 views

Derivate of an Inverse of a Matrix

I have the following loss function. $$||\theta - (X^T X)^{-1} X^T y||_2^2$$ $$X\space \text{ is a matrix, } \theta \text{ and } y \text{ are known vectors.}$$ I have another constraint for $X$, ...
0
votes
2answers
34 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
1answer
54 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
26 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
16 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| ...
1
vote
1answer
46 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
19 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
46 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
13 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
43 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
28 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
170 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
28 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
76 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
119 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
64 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
82 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
69 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
12 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
29 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
249 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
26 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 ...
1
vote
1answer
45 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 ...
1
vote
1answer
74 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
33 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 ...
4
votes
2answers
144 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
17 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 ...