Skip to main content

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
1 vote
0 answers
22 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 $\...
beanbanx's user avatar
0 votes
1 answer
52 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 - ...
msantama's user avatar
  • 1,213
0 votes
0 answers
24 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-...
Henri's user avatar
  • 1
0 votes
0 answers
22 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 ...
user avatar
1 vote
1 answer
54 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 ...
Saunders's user avatar
  • 670
0 votes
1 answer
155 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 ...
Carlo Wood's user avatar
0 votes
0 answers
19 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: ...
ufghd34's user avatar
  • 81
2 votes
2 answers
81 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}{\...
jam's user avatar
  • 81
0 votes
0 answers
26 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?
Aniket Sinha's user avatar
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://...
ufghd34's user avatar
  • 81
0 votes
1 answer
41 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 ...
S M's user avatar
  • 71
1 vote
0 answers
68 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{...
user3284182's user avatar
2 votes
1 answer
86 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. ...
user3284182's user avatar
2 votes
1 answer
39 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}$ ...
xenuti's user avatar
  • 153
0 votes
0 answers
15 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: $$ \...
Shreyas Bharadwaj's user avatar
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 $\...
Saunders's user avatar
  • 670
1 vote
0 answers
27 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^\...
samsamradas's user avatar
0 votes
0 answers
6 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 ...
samsamradas's user avatar
0 votes
0 answers
29 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 ...
Patricio's user avatar
  • 577
1 vote
0 answers
41 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 ...
LNTR's user avatar
  • 11
0 votes
0 answers
10 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 ...
Lyndon Alcock's user avatar
0 votes
1 answer
60 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. ...
Marco Gandolfi's user avatar
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}^...
mtcrawshaw's user avatar
0 votes
1 answer
102 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 ...
Artyom Vancyan's user avatar
3 votes
1 answer
71 views

Least square derivatives

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}, \...
user avatar
1 vote
0 answers
21 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 ...
Aleph's user avatar
  • 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 ...
Marlon Brando's user avatar
2 votes
0 answers
33 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}^...
Miku_39's user avatar
  • 93
0 votes
1 answer
23 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 ...
Alisa Petrova's user avatar
1 vote
0 answers
31 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 ($\...
chloe's user avatar
  • 1,052
0 votes
0 answers
11 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 ...
NSR's user avatar
  • 874
0 votes
0 answers
17 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 ...
Antonio Hernandez's user avatar
0 votes
0 answers
28 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 ...
WalaWizon's user avatar
0 votes
0 answers
52 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}}) $$ ...
gomahv's user avatar
  • 1
0 votes
0 answers
19 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 ...
joseph rance's user avatar
1 vote
1 answer
47 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{...
Mo Bere's user avatar
  • 53
0 votes
1 answer
112 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 \\ ...
LostInTheSauce's user avatar
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 ...
user1031129's user avatar
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 ...
Sparsity's user avatar
  • 119
1 vote
1 answer
61 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}$....
Shreyas Bharadwaj's user avatar
5 votes
1 answer
135 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 ...
Small Deviation's user avatar
1 vote
1 answer
73 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} ...
Kaira's user avatar
  • 1,565
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 ...
Nicolas's user avatar
  • 179
0 votes
1 answer
63 views

Expressing the gradient of the softmax cost function using matrix multiplication

Let $X_{M\times N}$ be the attribute matrix ($M$ number of attributes and $N$ of samples), Let $Y_{K\times N}$ be the labels matrix in one hot representation ($K$ number of classes), and $W_{M\times K}...
CforLinux 's user avatar
0 votes
1 answer
50 views

One-point estimate to the gradient

The question came to me when I'm reading a paper of an optimization algorithm. It is an iterative method and in each step we need to find the gradient of $f:\mathbb{R}^d\rightarrow \mathbb{R}$ and do ...
PPP's user avatar
  • 447
0 votes
0 answers
21 views

Gradient of Robust SVDD

In the process of opimizing the obj function in Robust SVDD. How to obtain the gradient of the objective function using the chain rule? $$J(R, c) = R + C \sum_{i=1}^N max(0,||x_i - c||-R)$$ R is the ...
Robin's user avatar
  • 3
0 votes
0 answers
24 views

Solving a matrix optimization problem (part 2)

Problem definition This post is a follow up of this previous one. Consider the following $m\times(n+1)$ matrix \begin{equation*} B(\sigma)\triangleq \left[\begin{array}{ccc} b_0^n(s_1) & \cdots &...
matteogost's user avatar
0 votes
1 answer
126 views

Numerical gradient calculation for optimal control of PDE

I have two related questions regarding the correct way to perform numerical gradient descent for an optimal control problem with a non-uniform mesh/grid. 1) Say I am solving a PDE-constrained ...
Frubiclé's user avatar
  • 603
4 votes
2 answers
346 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$ ...
Phoenix's user avatar
  • 103
0 votes
0 answers
42 views

Unsure if I computed partial derivative of Loss function correctly

Merry Christmas and happy holidays everyone! I want to make a quick preface to this question, to say that this is about computing the gradient (derivative) of the loss with respect to specific word-...
ZenPyro's user avatar
  • 85

1
2 3 4 5
21