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

Filter by
Sorted by
Tagged with
0
votes
0answers
7 views

Gradient matrix of loss function for single hidden layer neural network

so I have a function $$\hat y=f(x)=\mathbf{w}_2^\mathsf{T}\pi(\mathbf z)$$ with $$\mathbf z=\mathbf W_1^\mathsf T\mathbf x$$ and $$\pi(x)={1\over1+e^{-x}}$$. As squared loss we use $$l={1\over 2}(y-...
0
votes
0answers
26 views

Gradient descent with non-Lipschitz continuous gradients

In general, we know that for strongly convex functions for which we can compute the Hessian and find the Lipschitz constant $L$ of the gradient, gradient descent will converge provided that the step ...
0
votes
0answers
4 views

Understanding the proof of convergence of SGD

I'm trying to understand this paper, which proves the convergence of Stochastic Gradient Descent. Firstly, I noticed that Lemma 1.2 proof (at the end, section 4 - missing proofs) uses the fact that ...
0
votes
0answers
23 views

Calculating Gradient

If we want to take derivative of $$\sum_{(x,y)}||v^TReLU(Mx)-y||_F^2$$ with respect to M, where $v\in \mathbb{R}^{k\times1}, M\in \mathbb{R}^{k\times d}, x\in \mathbb{R}^{d\times 1}$ and $y\in \mathbb{...
0
votes
0answers
12 views

How do I get the projection function for the gradient method?

I need to calculate the projection function for $$ \text{minimize}\quad g(v)=(1/2)v^{T}DD^{T}v-y^{T}D^{T}v$$ $$\text{subject to} \quad -\lambda\leq v \leq\lambda$$ but I don't know how. Could you ...
0
votes
0answers
25 views

Can LASSO algorithm solve for sparse $w$ in an under-determined system?

Consider the model $\bf y=Xw+n$ where $\bf w$ is a sparse complex number vector of length p, X is a N x p known complex number matrix, and $\bf n$ is a complex Gaussian noise. I'm confused because ...
0
votes
0answers
23 views

Why and how is it possible for a globalized BFGS implementation to not produce a descent direction towards the minimum?

In my class we learned that the hessian matrix approximation used in the (inverse) BFGS method doesn't always produce a descent direction (same as newtons method) - but how and why? Can someone give ...
1
vote
1answer
25 views

How do I optimize a rotation of the roots of unity?

Any rotation of the $m$th roots of unity is a finite normalized tight frame (FNTF) of $\mathbb{R}^2$. According to Benedetto and Fickus, every minimizer $\{x_i\}_{i=1}^{m}$ of the "frame potential" $...
1
vote
0answers
17 views

Numerical solution for gradient(slope)

Abstract I have the next equation to find a force, for my problem: $$U=-\int \vec{m}\small{(x)}\times \vec{B}(x)dV$$ $$\vec{F}=-\nabla U$$ Considering 3-dimensional space with x,y,z coordinates, ...
1
vote
0answers
33 views

How to calculate the Riemannian gradient in practice (optimization)?

In a couple of papers, I saw steepest descent defined by $\mathbf{v} = -\mathbf{G}_p^{-1}\nabla f(\mathbf{p}) \in T_x\mathbb{R}^n$ where $\mathbf{G}$ is the Riemannian metric tensor of an manifold. ...
0
votes
0answers
34 views

Relationship between Lyapunov functions and gradient Systems

given a nonlinear system $f(z) = \dot{z}$ that induces gradient dynamics so that $\nabla V(z) = -f(z)$ where V(z) is the potential function of the system. Is the potential function of a gradient ...
0
votes
0answers
57 views

Derive a parameter update rule for a batch gradient descent algorithm

For a given cost function, how do you derive closed form parameter update rules for $θ_k$ (The weight parameters) $$J(Θ) = \frac{1}{4N}\sum_{n=1}^{N} (h_θ(x^{(n)}) - y^{(n)})^4 $$ The gradient ...
0
votes
1answer
34 views

Find the gradient of the following function

The function is: $\frac{1}{n}\Sigma^n_{i=1}E(y_i-w^Tx_i)+\frac{\theta}{2}||w||^2_2$ where $E(k)={\{^{\frac{1}{2}k^2,\space\space\space\space |k|<1}_{|k|-\frac{1}{2}\space\space|k|\geq1}}$ What ...
0
votes
0answers
17 views

Help deriving basic equations for matrix tri-factorization using gradient descent

So for some background, I only have some basic understanding of matrix calculation. Based on what I remembered from backpropagation, I successfully derived equations for Matrix factorization using ...
4
votes
1answer
62 views

Gradient Descent and its Variants

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, Optimization refers to the ...
1
vote
1answer
28 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 ...
27
votes
2answers
135 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 ...
0
votes
1answer
31 views

The projection of a point to a ball.

I woul'd like to solve this. $argmin_{x│||x||≤R} ||x-y||$ This problem is equivalent to $argmin_{x│||x||^2≤R^2} ∑_{(i=1)}^d(x_i-y_i )^2 $. The Lagrangian is $L(w,a)=||w-y||+a(||w||^2-R^2 )=∑_{(i=1)}...
1
vote
1answer
36 views

How to prove a MSE loss function is convex for linear regression

$$MSE(w)=1/N∥y−Xw∥^2.$$ from what I have understood, If I'm able to prove $MSE(w) +\nabla MSE(w) * (z-w) \leq MSE(z)$. I found the partial derivative of $MSE(w)$ but I'm stuck there. Can someone help ...
2
votes
1answer
85 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|_{...
5
votes
1answer
87 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}^...
0
votes
0answers
21 views

Reference request: Gradient descent and stochastic variants

I am currently working on my bachelor thesis for mathematics. The topic is gradient descent and stochastic variants. I have knowledge in higher dimensional analysis, basic numerical analysis and ...
1
vote
1answer
14 views

Some questions about gradient descent method.

I want to make sure that I understand a Gradient descent method correctly. Let's say, there is a optimization problem $f = x^2+y^2 \rightarrow min$. I randomly choose the estimate of the minimum - $(0;...
0
votes
0answers
26 views

Zig-zag Behavior of the Gradient Descent method.

It is said that the steepest descent method has a zig-zag behavior, so the search directions of two successive iterations are orthogonal to each other. Now, I don't understand why we have to zig-zag ...
0
votes
0answers
35 views

At what minimum step length gradient descent cannot find the minimum function

At what minimum step length gradient descent cannot find the minimum function $x_0 = 2, f(x) = (x-1)^4 +\cos(2)$. I understand basic idea of gradient descent, I understant step is constant. Should ...
0
votes
0answers
25 views

Gradient Descent for Tensor Decomposition - Find low rank dimensions

I encountered this paper on travel time estimation using Tensor Decomposition and at Page 4, Figure 5 there is an algorithm to decompose a tensor using Gradient Descent. The first line of this ...
0
votes
0answers
7 views

Trouble with the derivation of the cost function from this paper

I'm trying to derive the cost function in a similar manner as done in the image taken from a paper attached, however the expression that results after the gradient calculation does not seem right to ...
0
votes
0answers
20 views

Covariant Derivative vs Partial Derivative Contradiction

I am doing gradient descent with respect to se loss function L. I have found that the partial derivative wrt some of the parameters is zero whilst the covariant derivative wrt the same parameters is ...
0
votes
0answers
11 views

Geometric interpretation of how function lower bounds aid gradient descent

Suppose we are given a smooth (i.e., gradients are Lipschitz) function $f(x)$ and we try to find its minima via a simple gradient descent approach. Smoothness tells us that at each point $x$, the ...
0
votes
0answers
4 views

What is the gradient of Q-value W.R.T policy parameters?

I have been recently studying Actor-Critic algorithms, and I ran into this question: Let $Q_{\omega}$ be the critic network, and $\pi_{\theta}$ be the actor. It is known that in order to maximize the ...
1
vote
0answers
15 views

Contraction property of scaled gradient descent

Let $f(x):\mathbb{R}^n \to \mathbb{R}$ be $\sigma$-strongly convex and $L$-Lipschitz continuous. Assume to apply a scaled gradient descent to find the minimum $x_\star$ of $f$, i.e., $$ x_{k+1} = x_{...
0
votes
1answer
26 views

How to show steepest descent will not converge to local but to global minima of funtion.

for a function $f(x, y) = 0.5*x^2 +0.25*y^4 −0.5*y^2$. Show that there are infinitely many starting points for which gradient (steepest) descent will not converge to a local, let alone global, ...
0
votes
0answers
15 views

Differentiable approximation of supremum of a function

I am trying to solve an optimization problem of the form: min$_y$ f(y), s.t. g(y,t)$\leq0$ ∀ t∈D. As I can calculate the gradients for f and g, I was thinking of using a penalty method, in which ...
0
votes
0answers
15 views

Gradient of Column Vector

I saw the gradient of a function, $f(x,y) = \| x - y \|^2$ as $\nabla f_x = 2x^T(x-y)$ where $x$ and $y$ are column vectors. I really would love to know the Mathematics behind this. Also, I thought ...
2
votes
1answer
43 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 ...
0
votes
2answers
32 views

Tangent plane parallel to given plane

Let $S$ be the surface in $R^3$ given by $z = \sqrt{2x^2+y^4+1}$ and $P$ be the plane given by $x-y-z=0$. Find an equation of the plane tangent to $S$ and parallel to $P$. Progress I have made so far:...
1
vote
0answers
14 views

Find standard deviation $s$ such that $\mathbb{P}(X \in [-t, t]) = 1 - \alpha$ for $X \sim \mathcal{N}(0, s)$

Let $t >0$ and $\alpha \in (0, 1)$. I am looking for the standard deviation $s > 0$ such that $\mathbb{P}(X \in [-t, t]) = 1 - \alpha$ for any $X \sim \mathcal{N}(0, s)$. Let $s$ be a ...
0
votes
1answer
32 views

Newton's method derivation and gradient descent.

I am confused by answers here and there... I want to clarify on derivation process of Newton's method. So basically taking first 3 terms of a Taylor expansion: $$f(x+h)=f(x)+h f'(x)+\frac{1}{2} h^2 f'...
1
vote
1answer
41 views

Find steepest direction of a mountain

I need to find the steepest direction for a traveler that walks over a mountain in two questions: In the first one, the mountain described as a function: $ z = f(x,y) = 10 - 2x^2-3y^2$ And the ...
0
votes
0answers
12 views

Gradient of linear program with respect to constraints

Let $\mu = \sum_i a_i\delta(x_i), \nu = \sum_i b_i\delta(y_i)$ be two weighted discrete distributions. Define also the Euclidean cost matrix $\mathbf{C}_{ij} = \|x_i-y_j\|_2$. The 2-Wasserstein ...
0
votes
1answer
44 views

Intuition for gradient of steepest descent direction of a plane?

Assume I have a vector $v$ in $\mathbb{R}^3$ with elements $v=\left[x,y,z\right]^T$. Assume further that there is a plane in $\mathbb{R}^3$ for which $v$ is the steepest descent direction in $z$ if $z ...
0
votes
0answers
10 views

Regularization parameter as Lagrange multiplier

Can I think of the regularization parameter in regularized gradient descent: as a Lagrange multiplier? If yes, when solving this optimization problem, should lambda be fixed? I heard that Lagrange ...
0
votes
1answer
22 views

What does $g\left(w^{t}, x^{t}\right) \in \partial_{w} f\left(w^{t}, x^{t}\right)$ mean?

I'm reading a paper about Gradient Descend Method in which there is a paragraph: IMHO, $\partial_{w} f\left(w^{t}, x^{t}\right)$ is the partial derivative of $f$ w.r.t $w$, so it's a number. I don't ...
0
votes
0answers
36 views

Proximal Mapping of $L^1$ and $L^2$ norm

We are given $w \in \mathbb{R}^n$. We wish to compute the proximal map $$\arg\min_u \Big[\frac{1}{2\eta}||u-w||_2^2 + \frac{\lambda}{2}u^Tu + \mu \sum|u_i|\Big]$$ I tried getting the derivative, ...
0
votes
2answers
28 views

How to minimize a quadratic expression over two parameter spaces?

I have asked this question before, however no one could answer it. I wish to know how can I minimize a quadratic expression over two parameter spaces. I have developed a rudimentary method and I want ...
0
votes
0answers
21 views

Gradient calculation for proportional odds (ordinal logistic) model

I am trying to calculate a gradient for a proportional odds model. http://fa.bianp.net/blog/2013/logistic-ordinal-regression/ What steps are required to take the derivative with respect to w? $$\...
0
votes
0answers
13 views

How can I find the gradient of a non linear SVM wrt input?

Given that an SVM will have the following function: And if I was to use a kernel, this would become: Where the kernel can be the Gaussian kernel: How Would I go about finding its gradient wrt the ...
0
votes
0answers
14 views

Gradient descent to estimate the ground truth pdf

I have a function $I_d(x)$ which defined over a plane. I could simulate the values of this function at different points. I have a ground truth probability density vector $p({\bf x})=(p_1(x),...,p_d(x))...
1
vote
0answers
17 views

Using Dual Simplex with Projected Gradient Descent - Does that work?

Assume that we are going to minimize this objective function: $$J_{min} = \frac{1}{2}x^TQx + c^Tx$$ With subject too: $$Ax \leq b_{lb} \\ x \geq 0 $$ The objective function have its origins from ...
0
votes
0answers
88 views

Find the lines for which the matrix of partial derivatives is singular

Let $f(x,y) \in \mathbb{R}^2$ that belongs to $C^{\infty}$-class, denote $H = \begin{bmatrix} \frac{\partial^2f(x,y)}{\partial x^2} & \frac{\partial^2f(x,y)}{\partial x\partial y} \\ \frac{\...

1
2 3 4 5
13