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."
1,041
questions
5
votes
2
answers
15k
views
Gradient descent: L2 norm regularization
So I've worked out Stochastic Gradient Descent to be the following formula approximately for Logistic Regression to be:
$
w_{t+1} = w_t - \eta((\sigma({w_t}^Tx_i) - y_t)x_t)
$
$p(\mathbf{y} = 1 | \...
CommunityBot
- 1
0
votes
0
answers
30
views
Derivation of the upper bound of the average regret of online-to-batch conversion in H-smoothness
I've been studying a paper (Smoothness, Low-Noise and Fast Rates) on the impact of smoothness on the convergence rate of online-to-batch conversion, specifically Theorem 2, which provides a bound on ...
- 139
1
vote
0
answers
50
views
Using differentiation under the integral sign for computing the gradient of the expectation.
I am following the work from Kingma and Welling, where they introduce Variational Autoencoders. To train such models they use the so called Evidence Lower Bound and maximize it. One way to solve this ...
- 21
0
votes
1
answer
53
views
Steepest descent method for $\min f=\sqrt{x_1^2+cx_2^2}$ for fix $c>1$
Want to prove $$\mathbf{x}_k=\left(\frac{c-1}{c+1}\right)^k\left(c,(-1)^k\right)^T$$
My attempt:
$$\mathbf{x}_0=(c,1)^T, \ \ \ \nabla f(\mathbf{x}_0)=\left(\frac{c}{\sqrt{c^2+c}},\frac{c^2}{\sqrt{c^2+...
- 2,562
3
votes
0
answers
72
views
How to approximate the gradient of $f(x)g(x)$ when $f(x)$ is non-differentiable but has a smooth approximate $h(x)$?
Consider optimizing $\sum_{t=1}^n f_t(x)g_t(x)$ using online gradient descent. However $f_t(x)$ is non-differentiable and has a smooth approximate $h_t(x)$ . The online gradient descent is as follows:...
- 123
1
vote
2
answers
4k
views
Partial derivative in gradient descent for logistic regression
I post this question here because I think this is a calculus problem
I'm a software engineer, and I have just started a Udacity's nanodegree of deep learning.
I have also worked my way through ...
CommunityBot
- 1
0
votes
0
answers
31
views
Adaptive Runge Kutta for gradient descent optimization
A version of this question was asked a couple of years ago here, but I am still not clear on why this is not used more widely (or seemingly at all).
Problem statement: Suppose you have some ...
- 1
2
votes
0
answers
34
views
How to conduct error analysis for gradient descent with a function not differentiable everywhere
I am trying to bound the error of a method which uses gradient descent on a function which has the term $\lVert Ax - b \rVert$. The analytical solution of the derivative of $\lVert Ax - b \rVert$ is $\...
- 27
3
votes
1
answer
1k
views
Using Runge-Kutta integration to increase the speed and stability of gradient descent?
For a gradient descent problem with $\mathbf{x}\in \mathbb{R}^N$ I can evaluate the gradient $\mathbf{\nabla}_\mathbf{x} \in \mathbb{R}^N$ that reduces the least squares error, $y$. However, simply ...
- 1
0
votes
0
answers
46
views
Number of iterations needed for the method of steepest descent
The function $f(x,y) = 4x^2 + 2y^2 + 2xy -4x + 6y$ has a unique global minimizer at $(x,y) = (1, -2)$
Starting at $(5,2)$ how many iterations of the steepest descent method would it take, at least, to ...
1
vote
0
answers
47
views
Newton-Kantorovich theorem: geometric intuition
I am trying to find some geometric intuition for the Newton-Kantorovich theorem, and I have investigated the special case of real numbers. The theorem states:
$$\textbf{The Newton-Kantorovich theorem}...
- 59
0
votes
1
answer
53
views
Proving inequality that arises in projected gradient descent
I am reading a paper in which the author uses projected gradient descent to produce iterates of the form:
$$\pi_{t + 1} = \underset{\pi \in \Pi}{\arg \max}\left\{ \left \langle \pi, Q \right \rangle - ...
- 1,223
0
votes
1
answer
2k
views
Difference between gradient and Jacobian in gradient descent
What is the difference between the computation of gradient (the partial derivative of error w.r.t. weight) in gradient descent and the computation of the Jacobian in Levenberg-Marquardt algorithm?
CommunityBot
- 1
0
votes
1
answer
117
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 ...
- 9,087
2
votes
1
answer
166
views
How to implement a 2D matrix version of wolfe line search?
In Wolfe line search, the product of a gradient $g$ and the descend direction $g$ must be calculated. In 1D, both gradient and direction are vectors. Consequently, the product $ g^Td $ is a scalar. ...
- 9,087
1
vote
2
answers
1k
views
Critic Loss in PPO
TL,DR: How precisely is the critic loss in PPO defined?
I am trying to understand the PPO algorithm so that I can implement it. Now I'm somewhat confused when it comes to the critic loss. According to ...
- 2,387
0
votes
0
answers
26
views
How to define complex valued spherical coordinates?
I am currently tackling an optimization problem involving complex valued vectors. However the optimization is solely about finding the optimal "direction" of the vector. So any (complex-...
- 1
0
votes
1
answer
1k
views
Partial derivatives of the multidimensional Rosenbrock function
I want to solve an optimization problem using multidimensional Rosenbrock function and gradient descent algorithm. The Rosenbrock function is given as follows:
$$ f(x) = \sum_{i=1}^{n-1} \left( 100 \...
CommunityBot
- 1
0
votes
0
answers
32
views
Understanding convergence rate of gradient descent
I am currently learning about gradient descent.
For the convex case, I found this estimation in Nesterovs book:
$f(x_k)-f^* \leq \frac{2L\|x_0-x^*\|^2}{k+4}$
Nesterov doesn't use the big o notation ...
CommunityBot
- 1
1
vote
1
answer
67
views
Convergence of SGD for least squares
Given $X\in\mathbb{R}^{m\times n}$ and $y\in\mathbb R^m$, we want to solve the least squares (LS) problem $$f(\theta)=\min_{\theta\in\mathbb R^n}\frac12||X\theta-y||^2.$$
This problem can be expressed ...
- 105
0
votes
1
answer
168
views
Using a cubic to predict a minimum between two points and their derivatives.
Background
After fitting a parabola through a few samples (value + derivative), our algorithm - in search of a minimum - normally would jump to the vertex of that parabola. However, it is possible ...
- 211
0
votes
2
answers
118
views
Direction of Steepest Decent of an Implicit Function.
If given an implicit surface like
$$
x^{6}z + x^{3}y^{2} + y^{2}z^{3} = 65
$$
How would I go about finding a $3$-D vector that points in the steepest downhill ...
- 91.4k
0
votes
0
answers
22
views
Can changing Gradient Descent step size/learing rate from constant 1/L to Armijo or exact line search change the convergence rate?
If instead of the classical $1/L$ constant step size we have adaptive step sizes chosen with exact line search or Armijo (let's say) can this alter the Big-O complexity of the convergence rate?
Here:
...
- 81
1
vote
1
answer
1k
views
Backtracking Line Search - Graphical Interpretation
I am new to convex optimization and got a little bit confused while reading up on the backtracking line search.
What is $f(x) + \alpha t \nabla f(x)^T\Delta x$ ? I know of the Taylor first order ...
CommunityBot
- 1
2
votes
2
answers
83
views
Is gradient the direction of steepest change always?
Let's say I have a function $f(x_1, x_2, x_3,...,x_n)$ then gradient is defined as
$$ \left( \nabla f \right) \left( \overrightarrow x \right) = \frac{\partial f}{\partial x_1} + \frac{\partial f}{\...
- 541
0
votes
0
answers
31
views
What if the dot product of gradient vector of two curves is zero at a point (x,y)?
If say the grad(f)•grad(g) at point (x,y) on both the curves is zero. Is it sufficient to show that the curves intersect orthogonally?
1
vote
0
answers
22
views
What are the bounds on the convergence rate of Gradient Descent for non-convex quadratic polynomials defined over a hypercube?
I know of several function-independent complexity bounds on convergence rates of (projected) Gradient Descent (to a KKT point of course) e.g:
https://doi.org/10.1007/s10107-019-01406-y
http://...
- 81
1
vote
1
answer
46
views
Application of the Method of Steepest Descents to Exponential Integral
I am trying to develop an asymptotic expansion of the following integral using the method of steepest descents:
$$ \int_{0}^{\infty} \frac{1}{t+1}e^{ix(t^3-3)}dt$$
I rearranged it into the form $\int ...
- 33.7k
1
vote
0
answers
70
views
How to initialize complex matrices in gradient descent?
I have four equations. Edit:
$(e + i \bar{e}) = ( m + i \bar{m} ) - (y + i \bar{y}) $,
$(y + i \bar{y}) = (W_3 + i \bar{W_3} ) (h + i \bar{h}) $
$(h + i \bar{h}) = (z + i \bar{z}) + (W_2 + i\bar{...
- 113
2
votes
1
answer
96
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. ...
- 37.7k
2
votes
1
answer
41
views
Prove that the sequence of points given by the gradient descent algorithm converges to zero.
This is an exercise and it seemed pretty simpl at a first glance but I don't how to continue. I have this function:
If $x < 0 $ then $f(x) = \frac{3}{2}x^{2}$
If $x \geq 0 $ then $f(x) = x^{4}$
...
- 151k
0
votes
0
answers
19
views
Gradient Descent Over the Set of Complex Symmetric Matrices
In the course of my research (somewhat related to compressive sensing), I am trying to determine a complex, symmetric matrix $L$ (i.e. $L = L^T$) through the following optimization formulation:
$$ \...
4
votes
2
answers
347
views
Exploring the convergence properties of a cost function involving orthogonal projection of one-hot vectors
$\newcommand{bm}[1]{\mathbf{#1}}$Given the semi-orthogonal fat matrix ${\bm B} \in\mathbb R^{c \times d}$ (i.e., $c\leq d$, $\bm {BB}^\top=\bm I$), the matrix $\bm X \in {\Bbb R}^{m \times n}$, $c$ ...
- 3,870
0
votes
1
answer
48
views
Prove an inequality for strongly convex function
Let $g:\mathbb R^m\to\mathbb R$ be $\mu$-strongly convex. Let $A\in\mathbb R^{m\times n}$ have full row rank (so $m\le n$). We are interested in the function $f(x)=g(Ax)$, $x\in\mathbb R^n$.
Let $\...
- 4,005
1
vote
0
answers
35
views
Logistic regression with gradient descent derivation
Our maximum likelihood is:
$$l(\beta)=\sum_{i=1}^{n}y\log(p(x))+(1-y)\log(1-p(x))$$
$$l(\beta) = \sum_{i=1}^{n} y^{(i)} \log(\sigma(\beta^\intercal x^{(i)})) + (1 - y^{(i)}) \log(1 - \sigma(\beta^\...
- 563
1
vote
0
answers
77
views
computation of the gram matrix for natural energy descent
I have found a paper on https://arxiv.org/abs/2302.13163 where a modification of the natural gradient descent is proposed.
The natural gradient can be computet with (eq. 8)
$$
\nabla^EL(\theta) := G^{-...
0
votes
0
answers
8
views
How many dimensions is the MSE error function
let's say we have n data points($y_i$) and our model:
$$h(x) = \theta_1 x + \theta_2$$
then:
$$MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - h(x_i))^2$$
$$MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - (\theta_1 ...
- 563
0
votes
0
answers
33
views
Stochastic gradient descent with momentum: eigenvalues
I am reading the article "How Momentum really works" (https://distill.pub/2017/momentum/), and i am confused in particularly one point:
I am trying to derive the convergence rate for ...
- 587
0
votes
1
answer
172
views
Confusion after attempting to apply chain rule with respect to matrix, using a Frobenius product.
Consider a loss function
$$ j = \frac{1}{2}||e||^2,$$
where $e=y-t,\quad$ $y=f(x,u) \in \mathbb{R}^{n},\quad$ $u=Wx \in \mathbb{R}^{m}, \quad x\in \mathbb{R}^n$.
Now I want to find the gradient of $...
- 37.7k
1
vote
1
answer
84
views
parametric optimization in differential equation through gradient descent
I need to solve a differential equation containing a parameter $n$, and based on a constraint I assign, I would like to find what is the value of $n$.
I would like to use a gradient descent method.
...
- 7,206
1
vote
0
answers
44
views
Using Gradient Descent for coefficient estimation in ARMA model
I'm trying to implement an ARMA model from scratch using gradient descent with adam optimizer to estimate its coefficients . I know it might not be the ideal solution. But the thing that I'm mostly ...
- 11
0
votes
0
answers
13
views
Calculation of discrete path function from discrete vector field?
Context
The paper "Stiffness-based optimization framework for the topology and fiber paths of continuous fiber composites" discusses a "streamline" method of path planning for 3D ...
0
votes
0
answers
32
views
Gradient descent on a convex function without a minimizer
From what I've seen, most of the proofs of convergence for gradient descent on convex functions assume that there exists at least one minimizer, i.e. for a convex $f: \mathbb{R} \rightarrow \mathbb{R}^...
- 43
4
votes
2
answers
264
views
Is L-Smoothness Equivalent to Globally Lipschitz Gradient without Convexity
The problem I am Having
Suppose $f:\mathbb E\mapsto \mathbb{\bar R}$, mapping from some euclidean space to augmented real with a well-defined gradient defined everywhere, and it has the smooth ...
- 75
0
votes
1
answer
137
views
How to find the global minimum of a convex function?
The Problem
The gradient descent algorithm finds a minimum of a convex function, but it does not guarantee that the found minimum is the global one. I don't know if it's possible to find a minimum of ...
- 2,021
3
votes
1
answer
77
views
Least square derivatives [closed]
Let $X_1, \ldots, X_N \in \mathbb{R}^p$ and $Y_1, \ldots, Y_N \in \mathbb{R}$. Define
$$
X=\left[\begin{array}{c}
X_1^{\top} \\
\vdots \\
X_N^{\top}
\end{array}\right] \in \mathbb{R}^{N \times p}, \...
- 37.7k
1
vote
0
answers
22
views
How to comment on goodness of loss functions?
I have two loss functions $\mathcal{L}_1$ and $\mathcal{L}_2$ to train my model. The model is predominantly a classification model. Both $\mathcal{L}_1$ and $\mathcal{L}_2$ takes two variants of the ...
- 164
2
votes
0
answers
36
views
Gradient descent for solving complex-valued $Ax = b$?
Suppose that $A \in \mathbb{R}^{n \times n}$ is symmetric positive definite. In this case, solving $Ax = b$ with $x,b \in \mathbb{R}^{n}$ is equivalent to find
\begin{align}
\underset{x \in \mathbb{R}^...
- 93
0
votes
0
answers
24
views
Gradient Steepest Descent
In the book I am currently reading, the steepest descent is described as follows:
$$\min_{\mathbf{x}} \frac{1}{2}x'Qx - x'b$$
Let this quadratic problem be the initial position and Q must be positive ...
- 213
2
votes
1
answer
68
views
Is there any method for gradient descent that achieves acceleration while moving always in the opposite direction of the gradient?
I'm studying gradient descent methods, in particular Nesterov's methods and others that achieve a better complexity (in terms of access to the gradient oracle) than regular gradient descent. In ...
- 377