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
0
votes
0
answers
26
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 ...
- 129
1
vote
0
answers
48
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+...
- 962
3
votes
0
answers
70
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
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
0
votes
0
answers
45
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
46
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
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
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
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
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 ...
user1258572
1
vote
1
answer
66
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 ...
- 670
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
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
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}{\...
- 81
0
votes
0
answers
30
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 ...
- 81
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
95
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. ...
- 113
2
votes
1
answer
40
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}$
...
- 153
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:
$$ \...
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 $\...
- 670
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^\...
- 561
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 ...
- 561
0
votes
0
answers
31
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 ...
- 577
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 ...
1
vote
1
answer
82
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.
...
- 107
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
0
votes
1
answer
127
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 ...
- 105
3
votes
1
answer
76
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}, \...
user1304586
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
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
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
1
answer
25
views
Find smallest step size so that gradient descent will diverge
Suppose I want to use fixed-sized gradient descent for a function like $y=x^2$ using the formula starting at some point (for example $x_0=4$):
$x_{i+1}=x_{i}-\alpha*f'_{x}(x_i)$
I am trying to figure ...
1
vote
0
answers
33
views
How to verify whether a direction is the steepest descent, in multi-variables case?
Consider the following energy function $$-\sum_{i<j\in[n]}\cos(\theta_i-\theta_j)$$ where $\theta_i\in\mathbb{R}$, for $\forall i\in[n]$.
At any vector $\vec\theta$ that is not all-equal vector ($\...
- 1,052
0
votes
0
answers
13
views
Help understand a gradient derivation for RankNET
I am reading the RankNet to LambdaMART paper : https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf , where the author makes a particular claim in equation (1). They ...
- 894
0
votes
0
answers
19
views
How to get the gradient of this function?
I'm trying to approximate a image with a sum of radial basis functions $\phi(x_i, \theta_i)$ where each $x_i\in R²$ and it is the coordinate of every pixel of the original image. $\theta_i$ is the ...
0
votes
0
answers
29
views
Computing gradient over all examples in Gradient Descent
I am studying about Gradient Descent and Stochastic Gradient Descent, and the text says that one of the advantages of sgd over gd is, that gd can be computationally expensive for large datasets. In ...
- 15
0
votes
0
answers
54
views
Gradient of a complex scalar with respect to a real vector
I have a question regarding a regression problem. Suppose vector $\mathbf{p}$ is real and has length N. Now suppose $\mathbf{p}$ is the input to the following equation:
$$
y = f(e^{i\mathbf{p}})
$$
...
- 1
0
votes
0
answers
22
views
Relationship between model variance and dataset size for SGD
I'm looking for some function that describes the variance of model weights when trained with Stochastic Gradient Descent for $m$ independent minibatches.
I can apply central limit theorem to a single ...
1
vote
1
answer
49
views
Prove an inequality from a scalar product
This exercice is a proof of the convergence of the gradient descent towards a stationary point. Let $\mathbf{v}_1, \dots, \mathbf{v}_T$ be a sequence of gradients. We have $\mathbf{w}^{(1)} = \mathbf{...
- 53
0
votes
1
answer
116
views
Choose start vector for gradient descent so that it converges with one step
I'm currently looking at an old exam and I have encountered the following task:
$ A=\left( \begin{array}{rrr}
2 & -1 \\
-1 & 2 \\
\end{array}\right)$ $b=\left( \begin{array}{rrr}
1 \\
1 \\
...
0
votes
0
answers
16
views
What is the steady state distribution of this Poisson process with non-constant rate?
I am looking for the steady state distribution of the following Poisson process:
$$d x(t) = -k_1(x(t)-k_2)dt + k_3dN(t)$$
where $k_1$, $k_2$ and $k_3$ are constants and the rate $\lambda(x)$ of the ...
0
votes
0
answers
12
views
Results on convergence and runtime rates of proximal algorithms
Are there any known results on the convergence rates and computational runtime of proximal algorithms? I'm interested in finding out how well they scale with increasing number of input dimensions, but ...
- 119
2
votes
1
answer
69
views
Gradient of Function of Complex Matrices
Consider the following function:
$$ f(T) = \| T^{T}TB - C\|^2_2 $$
where $T, B, $ and $C$ are all complex matrices. Let $T = X + iY.$ I wish to compute $\nabla f$ i.e. $\dfrac{\partial f}{\partial T}$....
5
votes
1
answer
141
views
Discretization Error of Mirror Descent
It is well known that for sufficiently differentiable functions $f$ and small $\eta>0$ the iterate given by gradient descent $$ x_{k+1}=x_k-\eta \nabla f(x_k)$$ is within $\mathcal O(\eta^2)$ of ...
- 2,337
1
vote
1
answer
81
views
Connection between gradient descent and Newton's method
Given a function $f:\mathbb{R}^d\to \mathbb{R}$, suppose we want to find the minimum of $f$. The gradient descent method finds $x$ that attains the minimum by iterating the following formula:
$x_{n+1} ...
- 1,619
1
vote
0
answers
18
views
Linear least squares involving linear functionals
Let $\Omega\subset\mathbb{R}^d$ be a domain. Suppose $H$ is the second order Frechét derivatives of a function $f\in L^2(\Omega)$, then $H\in (L^2\times L^2)^{*}$. Let $g\in (L^2(\Omega))^{*}$ and we ...
- 179