Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
1answer
18 views

KKT condition for the proximal algorithm

This slide shows that the KKT condition for the proximal gradient descent is this inequality. I don't know where this comes from. Using KKT , we can only get equality for the stationary condition, ...
2
votes
1answer
34 views

Gradient of matrices formula with respect to one member?

For an machine learning assignement I have the following Loss-function: $$L(D, W) = \frac{1}{2}||DW-X||^2_F$$ Where $D, W$ and $X$ are matrices. In one part of the assignment I need to calculate ...
0
votes
1answer
40 views

Projected gradient descent

$\newcommand{\R}{\mathbb{R}}$There's the following problem that I found in a book: Let function $f:\R^2\to\R$ be defined as $$ f(x) = x_1 + x_1x_2 + (1 + x_2)^2 $$ Considering the feasible set $$ X ...
0
votes
0answers
9 views

How does stochastic variance reduced gradient (SVRG) reduce the variance?

The update rule for SVRG is the following: $w^{(t)} = w^{(t-1)} - \eta(_t\nabla f_i(w^{(t-1)}) - \nabla f_i(\hat w) + \frac{1}{n}\sum_{i=1}^n f_i(\hat w))$ While I understand that $ v_t := \nabla ...
0
votes
1answer
17 views

What will be the value of sub gradient at $0$ for function $|x|$

I am learning about Lasso Regression and came across taking gradient with respect to $0$. I came to know about subgradient but could not understand what will be its value at $0$. In lasso regression, ...
0
votes
1answer
20 views

Gradient descent orthogonal steps

For the steepest descent algorithm it's stated that Since $\alpha_k$ minimizes $\alpha\mapsto f(x_k + \alpha p_k)$ it follows $$ \nabla f(x_k + \alpha_k p_k)^Tp_k=0. $$ where $p_k = -\nabla f(x_k)$....
0
votes
2answers
33 views

Minimizing univariate quadratic via gradient descent — choosing the step size

I'm learning gradient descent method and I saw different (and opposite) things on my referrals. I have the following function $$f(x) = 2x^2 - 5x$$ and I have to calculate some iterations of ...
1
vote
0answers
19 views

Convergence Rates of Stochastic Gradient Descent with different sample size

Given a convex function $F(x)$ to be optimized with $F(x^*)$ being the optimal value at $x^*\in\mathbb{R}^n$. The difference $|F(x)-F(x^*)|$ is called the excess error. Using Stochastic Gradient ...
0
votes
0answers
27 views

How to calculate gradient of the Hessian in $\mathbb{R}^d$

I have a learning sample $D_n = f(X_i, Y_i)_{i=1}^n$ where the $X_i$’s are $\mathbb{R}^d$-valued and the $Y_i$’s are $\{-1, 1\}$-valued. $$ f(\theta) = \frac{1}{n} \sum_{i=1}^{n} \exp(-Y_i (\theta^T ...
0
votes
0answers
19 views

How to compute the gradient using chain rule for $\min_x l(f(g(x)))$?

Assume I have a complex optimization function as follow: $$\min_x l(f(g(x)))$$ Here $x$ is a matrix. and $l(\cdot)$,$f(\cdot)$ and $g(\cdot)$ is some function. $l(f(g(x)))$ means composite function....
-1
votes
1answer
17 views

Analysis of optimization procedure for two equivalent optimization problems

I come up with this question. Assume the optimization problem is: $$argmin_w\|\hat{y}(w)-y\|^2$$ Now suppose there is a overcomplete set for the representation of $\hat{y}$ and $y$, this set has lots ...
0
votes
0answers
16 views

Mix discrete and continuous derivatives

I have a problem where I try to compute the derivative of a function with respect to continuous inputs. Somewhere in the process, I make my inputs discrete with a floor function and then I go on with ...
0
votes
1answer
47 views

Projected Gradient on convex constraint set with explicit geometry

Assume the function $f(x,y) = 3x + 3y$ and the constraint set: $$ S = \{ x \in \mathbb{R}^n : x^2 + \frac{y^2}{9} \leq 1 \} $$ Complete one step of the Projected Gradient algorithm with $x_o = \...
0
votes
0answers
22 views

Estimating rate of decay of residual norms in gradient descent

I am using gradient descent to solve the linear system $Ax=b$, where matrix $A$ is symmetric and positive definite. More precisely, I am attempting to solve the following quadratic program $$\text{...
1
vote
0answers
24 views

Handling singular matrices in gradient-descent optimization.

Right now I am coding up optimization for a 70 dimension nonlinear optimization, where the analytical gradient is unavailable. I have some non-linear constraints that maps the structural parameters ...
1
vote
1answer
34 views

how is local minima possible in gradient descent?

gradient descent works on the equation of mean squared error, which is an equation of a parabola y=x^2 we often say weight adjustment in a neural network by ...
1
vote
0answers
22 views

Regression — gradient descent versus statistical methods

In a machine learning course, the professor described the gradient descent method for calculating the regression line. Shortly, we're looking for the $a$ and $b$ in $y=ax+b$ which describes the line. ...
0
votes
0answers
35 views

Characterizing class of functions from their gradient descent trajectory

Let $f : \mathbb R^d \to \mathbb R$ be a function with at least one minimum. Suppose that $f$ has the property that the gradient descent trajectory from any point of the function is a straight line to ...
0
votes
0answers
21 views

Gradient Descent with single constraint in MATLAB

I am trying to understand working of a matlab code (R2015b) that implements gradient descent method. For this I considered a following example My objective function is \begin{align} \text{minimize}...
1
vote
1answer
41 views

Doubt about how exactly was calculated this gradient descent cost function using Octave\MatLab. How is it exactly working?

I am following a machine learning course on Coursera and I am doing the following exercise using Octave (MatLab should be the same). The excercise is related to the calculation of the cost function ...
2
votes
0answers
66 views

Gradient Descent vs Lagrange Multipliers

I'm bit confused between Gradient descent and convex optimization using Lagrange Multipliers. I know that we use Lagrange multipliers when we have an optimization problem with one or more constraints. ...
0
votes
1answer
6 views

SGD Update rule simplification yielding extra transpose

In short, I’m trying to go from the first line to the second line in this equation: I feel foolish but on the second line my factor of $x_t$ is coming out transposed. Can someone please illuminate ...
2
votes
0answers
43 views

positive definite function

Let $\phi = [x1^2, x1x2, x2^2]^\top$. $W_1 ^\top \phi(x)$ and $W^{* \top} \phi(x)$ are positive definite functions and $A$ is a rank-1 positive semi definite matrix ($0<$one eigenvalue$<1$, the ...
0
votes
0answers
16 views

Gradient optimization with attractors/preferences, that respects already emerged structures in parameter subspace?

One can assume that certain structures have emerged in the space of parameters which are being optimized to achieve some minimum of some function over those parameters, e.g. f(p1, p2, ...). By ...
2
votes
0answers
39 views

Step size in gradient descent

I am trying to minimize the function $f(X) = \|A - XYY^TX^T\|_F^2$ where the gradient of $f$ follows the bound given belew where $A,X,Y \in R^{n \times n}$ $$\|\nabla f(X_1) - \nabla f(X_2)\|\leq L\|...
0
votes
0answers
79 views

Double nested nabla operator?

Suppose: $f(\vec{x}, \vec{\theta}):R^m \times R^n \rightarrow R$ Functional $L_(T_i ) (f_θ)=\sum_{x_k^{T_i} \in T_i} loss_{T_i}(f(x_k^{T_i} , \theta)$, where $T_i \sim T$ $\theta_i^{T_i}=\theta-\...
0
votes
1answer
18 views

Intuitive understanding of Gradient-based Optimization

I'm working my way through Deep Learning by Goodfellow, Bengio, & Courville (from MIT Press) and have become stuck on the following problem from page 86. I have experience with Mathematica 11.3 ...
0
votes
1answer
62 views

Numerical Implementation: Solution for the Euler Lagrange Equation Of the Rudin Osher Fatemi (ROF) Total Variation Denoising Model

I am watching some wonderful videos on Variational Methods in Image Processing, and the presenter talks about how variational methods are used to de-blur or denoise images, as well as other ...
0
votes
1answer
39 views

Derivation of the optimal step size of steepest descent

Let be $$f(x) = \frac{1}{2}x^TAx +b^Tx$$ where $A$ is a symmetric positive definite matrix and $b \in \mathbb{R}^d$. We know that such a function is systematically twice (and even infinitely) ...
0
votes
2answers
17 views

How is $(x_1,x_2)$ normal to $x_1w_1 + x_2w_2 = y$?

Note: this question is related to the maths of Neural Nets, if you need clarification about the question do comment. Raul Rojas' Neural Networks A Systematic Introduction, section 8.1.2 relates off-...
0
votes
0answers
12 views

Derivative (Jacobian) of transposed function

Let $x \in R^n$, $F \in R^{m \times n}$ and $f(x) = Fx$. It's easy to conclude that the Jacobian of $f(x)$ is $Df(x) = F$. Where $Df(x)_{ij} = \frac{\partial f_i}{\partial x_j}$. Therefore $\nabla ...
3
votes
1answer
58 views

Textbook Recommendations: Solving Systems of Matrix ODEs

This is in reference to the works of Trendafilov whose approaches to multivariate statistical problems boil down to solving a dynamical system involving matrices. Question: Can anyone suggest a book/...
0
votes
1answer
25 views

Proof of Batch Gradient Descent's cost function gradient vector

In the book Hands-On Machine Learning with Scikit-Learn & TensorFlow, the author only showed the formula for the Batch Gradient Descent method, such as: $ \dfrac{\partial}{\partial \theta_{j}} ...
0
votes
0answers
25 views

Confused about Nesterov momentum gradient descent algorithm

I've found a variety of variations of writing Nesterov but I cannot understand why they cannot simply be expanded into a one liner. Here is one I found that can just be re-arranged, can someone ...
1
vote
1answer
39 views

Quadratic Gradient Descent Optimum Step Size

First i have searched this forum but could not find a question that matched mine, though some are somewhat similar. my issue is whether or not the signage matters when i try to calculate the optimum ...
2
votes
0answers
86 views

Using Coordinate Descent on Projected Space

My goal is to maximize an objective function using coordinate descent over a 3-dimensional vector. In the simple case the domain over which I am maximizing is defined as follows: $X \in \mathcal{X}$ ...
0
votes
0answers
8 views

`Antisymmetric Preconditioning' for Gradient Descent

When minimising a convex function $f : \mathbf{R}^d \to \mathbf{R}$, a standard approach is to work with the gradient flow ODE \begin{align} \dot{x} = - \nabla f (x) \end{align} and then take some ...
1
vote
1answer
48 views

Gradient of Quadratic Form with Inverse of Complex Matrices

I want to calculate the gradient of $$ w^H H F (F^H F)^{-1} F^H H^H w $$ with respect to $ F $, which is complex. I am basing on this previous answer Derivative of Nested Matrix Quadratic Form ...
0
votes
0answers
27 views

Zoutendijk's Lemma Using Goldstein Conditions

I am reading Numerical Optimization by Wright and Nocedal and in page 39, it says that a similar result to Zoutendijk's lemma (Theorem 3.2) can be proven using the Goldstein conditions instead of the ...
0
votes
1answer
40 views

Getting to the gradient descent algorithm

I understand that gradient descent comes from the (quite natural) idea that we might want to choose our next weight vector ($w^{t+1}$) as $$w^{t+1} = \arg \min_w \frac{1}{2} \|w-w^t\|^{2} + \eta f(w^...
0
votes
0answers
34 views

I am trying to find the maximum learning rate or stepping rate of steepest descent algorithm in 2 dimensions

Let $f(x,y) = (x-y)^4+2x^2+y^2-x+2y$. I am trying to numerically find the miniumum of $f$. We define a fixed-point iteration scheme \begin{align*} g(x, y) = \vec{x}_{n+1} = \vec{x}_{n} - a\nabla f \...
1
vote
0answers
30 views

Are the initial values of the slope, intercept and the learning rate in gradient descent experimental?

I am having some problems trying to implement a gradient descent algorithm. Like I said in the title, initial values of these properties drastically change the outcome of the slope and the intercept ...
0
votes
0answers
22 views

Richardson's Iteration, Gradient Method and Spectral Radius

Richardson's iteration introduce a scalar $\alpha$ to the update formula: $$ \textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)} $$ And compute $\alpha$ by minimizing the spectral radius:...
1
vote
1answer
44 views

How do you calculate gradient descent when you have a point which gives two different values?

I am trying to implement gradient decent algorithm. The dataset on which I am working has points which are of a partial function I guess. For example these are a subset of the dataset. $(1, 10)$ $(...
0
votes
0answers
20 views

Classical gradient descent optimization of smooth nonnegative function $f$ restricted to hypercube $C = [-R,R]^s$.

Let $f : \mathbb{R}^s \rightarrow \mathbb{R}_{\geq 0}$ be a smooth, nonnegative function and $R > 0$. Now chose a point $x_0 \in (-R,R)^s$ in the interior of the compact hypercube $C := [-R,R]^s$. ...
0
votes
0answers
13 views

Expand a discrete 2D function

I have discrete 2D function $Z$ defined over grid $X \times Y$, where X and Y numbers grid's collumns and rows. Generating values of $Z$, however, is very costly, preventing me from reaching ...
0
votes
0answers
11 views

Reason for differences in EWA equations and Momentum equations

I am trying to learn more about optimization algorithms regularly used in deep learning, starting with alternating least squares and gradient descent. One snag I have run into is a difference in ...
1
vote
0answers
129 views

Projected gradient descent with matrices

I have a scalar function $f(\rho) = Tr(\rho H) + c\ Tr(\rho\log\rho)$, where $Tr$ is trace, $\rho$ is a positive semidefinite matrix with trace 1 and $H$ is a Hermitian matrix and $c$ is a postive ...
1
vote
0answers
64 views

Derivation of partial derivative of cost function with respect to weights in backpropagation algorithm

I am studying Machine Learning from Andrew Ng's Machine Learning course on coursera. I am stuck at understanding math behind back propagation. Here is an image of backpropagation algorithm from his ...
2
votes
1answer
66 views

Mazur's lemma without Hahn-Banach theorem/axiom of choice?

In the development of gradient-flow theory (in Hilbert-space $H$), we soon stumble on the question whether the function $u \mapsto \varphi[u]:=\frac{1}{2}\|u\|^2+I[u]$ -where $I:H \to \mathbb{C}$ is ...