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
1 answer
49 views

why gradient descent does not always land at the global minimum closest to the starting point?

I am given this function $\boxed{f(x,y)=((x^2+y^2)-1)^2}$. I need to do gradient descent analysis on it. I have studied that it's not trivial to show mathematically "ball reaches to the global ...
user avatar
0 votes
0 answers
11 views

Gradient calculation for an autoregressive probit model

I am using the following specification to estimate a binary choice Probit model: $$ P(y_t=1|x_t) = \Phi(\pi_t), $$ where $\Phi$ is the cumulative distribution function of the normal distribution. My ...
user avatar
2 votes
0 answers
15 views

Taking multiple optimization steps on the same trajectory not well justified.

I am reading the paper Proximal Policy Optimization Algorithms found at https://arxiv.org/pdf/1707.06347.pdf. In this paper they say "While it is appealing to perform multiple steps of ...
user avatar
  • 21
1 vote
0 answers
15 views

Uniquene solution to minimisation of a Non Linear Objective Function

I am trying to estimate the path of a random described by the following SSM \begin{align} x_{t+1} = x_{t} + q_{t+1} \newline y_{t+1} = h(x_{t+1}) + r_{t+1} \end{align} where $h(x_{t+1}) =...
user avatar
0 votes
0 answers
10 views

Uniqueness in minimisation of Lp-Norm using Gradient Descent

I am trying to estimate the path of a random described by the following SSM ...
user avatar
1 vote
0 answers
67 views

Find the Lipschitz constant

The question: Let $f(x) = ln(x + \sqrt{3 + x^2}) + \frac{1}{2}(x-2)^2$ with no restrictions on domain. Determine the Lipschitz constant $L$ for the basic statement: $$| \nabla f(x) - \nabla f(y)| \...
user avatar
  • 23
1 vote
0 answers
14 views

Example of local convergence to a global optimum for nonconvex gradient descent

These slides give an overview of some results in nonconvex optimization with gradient descent (GD). They suggest a few types of results that are proven about nonconvex GD: Convergence to a local ...
user avatar
0 votes
0 answers
14 views

What should I do when the Lipchitz constant getting close to zero?

I try to apply gradient descent on a very bad scale regression problem which the samallest Eigen values is $1.6e-8$ and the biggest Eigen value is $1.7e+8$. Then in this case that the Lipschitz ...
user avatar
  • 1
2 votes
0 answers
33 views

How "Optimal" are Solutions from Gradient Descent?

When optimizing the Loss Functions of Neural Networks using (some version of the) Gradient Descent algorithm, I have often heard this situation described as a Sequential Optimization Problem. This ...
user avatar
  • 1,688
1 vote
0 answers
24 views

Can Gradient Descent be "Combined" with Dynamic Programming?

In most applications of Gradient Descent (e.g. optimizing the Loss Functions of Neural Networks) - regardless of the "type" of Gradient Descent algorithm being used (e.g. Stochastic Gradient ...
user avatar
  • 1,688
0 votes
1 answer
33 views

Finding Matrix Corresponding to Ellipses of Cost Function

For a given cost function $$J(w)=(w-w_0)^TA(w-w_o)$$ it is known that contours of J(w) are ellipses with principal directions have angle of 45° and -45° with the horizontal axis. If eigenvalues of A ...
user avatar
  • 3
1 vote
0 answers
34 views

Differentiating through Optimization Paths

I'm reading the paper "Optimizing Millions of Hyperparameters by Implicit Differentiation". The key contribution of the paper is to show that you can replace optimizing through the ...
user avatar
  • 11
-1 votes
0 answers
21 views

Problem With Deep Learning Book By Aaron Courville, Ian Goodfellow, and Yoshua Bengio

Hello Everyone, I am reading Deep Learning Book By Aaron Courville, Ian Goodfellow, and Yoshua Bengio. In the Numerical consumption chapter, section 4.3.1 got a problem, There were a linked, We can ...
user avatar
4 votes
2 answers
118 views

EM Algorithm vs Gradient Descent

I was reading about the EM algorithm (https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm) - this algorithm is used for optimizing functions (e.g. the Likelihood Functions ...
user avatar
  • 1,688
0 votes
0 answers
25 views

Projecting a point onto a convex set given by Log-Sum-Exp

Motivated by a wish to encode signal temporal logic specs (with linear predicates) as optimization problems w/o mixed integer approaches, I've been attempting to find a way to define the projection ...
user avatar
  • 48
1 vote
1 answer
55 views

Newton's method is Quasi-Newton when the function is a non-degenerate quadratic

With the update step $\textbf x_{t+1} = \textbf x_t - H_t^{-1}\nabla f(\textbf x_t)$, where $H_t \in \mathbb R^{d\times d}$ is symmetric and satisfies $\nabla f(\textbf x_t) - \nabla f(\textbf x_{t-...
user avatar
0 votes
0 answers
43 views

Bad Convergence, Gradient Descent

I'm trying a Gradient Descent, (maybe Newtons Method?) for Linear Regression and getting wildly different solutions from the faster, more straight-forward linear equations, but can't find my mistake ...
user avatar
  • 2,907
0 votes
1 answer
18 views

Upper bound for Telescoping sum in gradient descent

I am studying a chapter in gradient descent . At some point we reach the sum in the left of the enequality and the writer says it's telescopic so this enequality holds: $\sum_{t=1}^T \Big( ||x_t - x^*|...
user avatar
0 votes
1 answer
28 views

Projected gradient reach minimizer when $\textbf x_{t+1} = \textbf x_{t}$

Suppose that a closed subset $X \subseteq \mathbb R^d$ is convex, and we have the following projected gradient descent algorithm: $ \DeclareMathOperator*{\argmin}{\arg\!\min} \DeclareMathOperator*{\...
user avatar
0 votes
1 answer
33 views

Convergence of gradient descent for linear least squares

I'm trying to prove that when I use gradient descent for the least squares optimization problem $x^* = arg min_{x \in \mathbb{R}^n} \frac 1 2 \| Ax - b \|_2^2$ with the gradient descent rule $x^{t+1} ...
user avatar
  • 5,325
0 votes
0 answers
38 views

Question about a convex optimization using gradient descent

Recently I have read a paper, but I was confused about the optimized method of this article. In the following I will try to abstract the problem in the text. Supposed that we have six variables $\bf{\...
user avatar
1 vote
0 answers
27 views

Constant step lengths in subgradient method

I was reading these notes (if the previous link doesn't work, use this) on the subgradient method, it says that the choice for step sizes (or step lengths) are determined before the algorithm is run, ...
user avatar
1 vote
1 answer
48 views

Can optimization algorithms "bounce around" forever?

I have the following question on the convergence of numerical optimization algorithms. When it comes to convex functions, it can be shown that algorithms like gradient descent converge after an ...
user avatar
  • 1,688
0 votes
0 answers
27 views

Gradient descent calculation split in 2 steps

In a machine learning course I am taking we have an assignment with a notebook (In linear models). So far I have calculated the cost and the sigmoid in a logistic regression and the next exercise ...
user avatar
0 votes
1 answer
18 views

Encoding line search condition into the proximal gradient subproblem

Given a convex function $f$, we often want to solve the problem like $$\inf_{x \in A} f(x),$$ for some convex feasibility set $A$. With the starting point $x \in A$, we can approximate the gradient $\...
user avatar
  • 710
1 vote
2 answers
74 views

When are solutions to $Ax=b$ in the row span of $A$

Given an $m \times n$ matrix $A$ where $m < n$ and rows of $A$ are linearly independent, can we say that all possible solutions to $Ax=b$ are in the row span of $A$? EDIT for context: We are using ...
user avatar
  • 35
1 vote
0 answers
32 views

Calculus of variations: Lagrange multiplyers

I have a system of coupled PDEs which I solve numerically. I wish to optimise a particular objective function using gradient ascent, where the system of PDEs feature as constraints. I can't get the ...
user avatar
  • 11
0 votes
1 answer
41 views

Feasible descent

Consider a NLP $\min\{f(x): g(x) \le 0\}$. There are no equality constraints. The problem is feasible for small steps $t > 0$. I have to prove that $g(x + td) \le 0$ if $g(x) < 0$, where $t$ is ...
user avatar
  • 3
1 vote
1 answer
35 views

Is there an 'inner product wrt a matrix' version of gradient descent?

Gradient descent generally starts with a first order Taylor approximation motivation. If we have a function $f:\mathbb{R}^p\rightarrow\mathbb{R}^p$, and we start at a point $x\in \mathbb{R}^p$, then ...
user avatar
  • 551
0 votes
1 answer
42 views

Gradient descent inside the expectation-maximization (EM) algorithm

I am feeling super uncertain about how much I can play around with the EM algorithm. Here is my question: In the EM algorithm, during the M-step, one attempts to find a parameter value, $\theta$, that ...
user avatar
1 vote
1 answer
63 views

Interchange of Limits: Gradient and Expectation

In the excellent book "Understanding Machine Learning: From Theory to Algorithms", the authors prove the convergence properties for the stochastic gradient descent (SGD) algorithm in Chapter ...
user avatar
  • 55
2 votes
1 answer
63 views

Understanding two steps in the proof of Armijo's Convergence Theorem

I was reading this paper in which Armijo proves his convergence theorem, and I struggle understanding some of the steps in the proof. The following questions regard the first theorem in the paper, ...
user avatar
  • 3,725
1 vote
1 answer
67 views

Proximal Gradient Descent

I am trying to solve the below optimization problem using proximal gradient descent on a dataset in python: $f(\theta) = \arg\min_{\theta \in R^d}\frac{1}{m}\sum_{i=1}^m\Big [log(1+exp(x_i\theta))-...
user avatar
0 votes
1 answer
38 views

Gradient descent algorithm explanation

How do I get from the derivative in the second last line to get xj in the last line?
user avatar
0 votes
1 answer
34 views

Gradient descend: What is the correlation of the different terms in the equation

I understand how the sequential gradient descend works, but I fail to understand the equation itself on how the next better weight wj is calculated. I can't visualize it graphically. What exactly does ...
user avatar
  • 101
0 votes
0 answers
43 views

How to understand this gradient used here to compute the square root of $x$?

I found a snippet of C++ code to compute the square root of non-negative integer x via MSE Loss function and gradient descent. ...
user avatar
0 votes
0 answers
28 views

Do Metric Learning losses translate semantic similarity in neighborhood relations in the shared embedding space?

The figure below illustrates the typical architecture applied to jointly represent an image (img) and its description (desc). Representation Learning-based Model Given a set of ...
user avatar
0 votes
0 answers
24 views

Poisson regression gradient descent constant step size

For $x_1,...,x_n \in \mathbb{R}$, $y_i \sim \text{Poi}(\exp(\beta x_i))$, the log-likelihood of $\beta$ is given by: $\mathcal{l}(\beta) = \sum^n_{i = 1}\exp(\beta x_i - y_i x_i \beta)$ We would like ...
user avatar
0 votes
0 answers
19 views

Will metrics matter in manifold optimization?

Given a function $f$ and a manifold $\mathcal{M}$, the optimal solution has no relationship to the metric of the manifold. But if we choose different metrics, we will get different Riemann gradients. ...
user avatar
0 votes
1 answer
39 views

Finding the gradient with respect to a matrix in the context of a dynamical system

I have a simple dynamical system where the vectors $\mathbf{x}$, $\mathbf{z}$ and $\mathbf{b}$ evolve over time $t$ as follows: $\large \mathbf{\hat{x}}_{t} \leftarrow \mathbf{x}_{t-1} + V\cdot\mathbf{...
user avatar
  • 877
1 vote
1 answer
41 views

A proof involving Batch-Normalization and SGD in Neural Networks

I am trying to understand a proof from this paper. Consider the following setting: We train a neural network layer with SGD, that is by updating the weights according to $$w_{t+1} = w_{t} - \eta \...
user avatar
  • 519
0 votes
0 answers
28 views

Q-Convergence Explanation

I've been reading about convergence rates, in particular Q-convergence. But I'm struggling to understand it. I know that a sequence will converge Q-linearly to a number $L$ if there exist some $\mu \...
user avatar
0 votes
0 answers
43 views

Compute the gradient of Function Defined by Integral

I would like to know how to compute the gradient of Function Defined by Integral For example, Let $\displaystyle f(x(t),y(t))=\int_{0}^{k}g(x(t),y(t))\rm{d}t$ be function and $t\in\mathbb{R}^{+}$ $$\...
user avatar
  • 4,718
0 votes
0 answers
9 views

What is the relation between strong convexity and the step-sizes in gradient descent?

I would like to use gradient descent methods for minimising a strong convexity function where $$f(x)-f(\bar{x})-\nabla f(\bar{x})^T(x-\bar{x}) \geq \frac{m}{2}\|x-\bar{x}\|^2$$ I would like to know ...
user avatar
  • 1
0 votes
0 answers
28 views

Proving the bound on the expectation of stochastic gradient descent conditional on previous step

I'm trying to do a question that asks show that E[f(Xk+1)|Xk] ≤ f(Xk), k ≥ 0. where f is an L-smooth, convex function that is the average of fi(x). Stochastic gradient descent is applied to start ...
user avatar
  • 11
0 votes
0 answers
34 views

multiple losses with L-BFGS in torch

I am using the torch iimplementation of L-BFGS to minimize a loss function, which is given as the sum of $n$ loss function loss = loss_1 + loss_2 + ... + loss_n Computing each of the losses loss_i is ...
user avatar
1 vote
4 answers
71 views

Question About Gradient Descent

Gradient descent is numerical optimization method for finding local/global minimum of function. It is given by following formula: $$ x_{n+1} = x_n - \alpha \nabla f(x_n) $$ For sake of simplicity let ...
user avatar
0 votes
1 answer
93 views

What Exactly is Step Size in Gradient Descent Method?

Gradient descent is numerical optimization method for finding local/global minimum of function. It is given by following formula: $$ x_{n+1} = x_n - \alpha \nabla f(x_n) $$ There is countless content ...
user avatar
0 votes
0 answers
19 views

Understanding the rewritten form of Nesterov Accelerated Gradient used to derive Nadam

This, other papers and this blog suggest that we can rewrite the NAG algorithm which basically does $$\theta _{t+1\:}=\theta _t\:-m_t$$ with $$m_t=\gamma \:m_{t-1}+\eta \frac{\partial L(\theta _t-\...
user avatar
  • 448
0 votes
1 answer
32 views

least squares with L1 regularization in selected entries

Say for $x \in \mathbb{R}^n$, I'm minimizing $\|Ax - b \|_2^2$ with L1 regularization on selected entries of $x$. i.e. instead of directly add a $\|x\|_1$ regularization term, it would be on $|x_i| + |...
user avatar
  • 155

1
2 3 4 5
18