Consider using gradient descent to minimize a quadratic objective with Hessian $H$. $$\begin{equation} f(w)=\frac{1}{2}(w-w_*)^TH(w-w_*) \label{loss} \end{equation}$$ We can specialize by letting $H$ have $i$'th eigenvalue proportional to $\frac{1}{i}$ . This decay was observed in some convolutional network

Suppose we sample $(x_1,x_2)$ uniformly from unit circle, are interested in the distribution of the following quantity. $$ X=\left(\begin{array}{cc}x_1& x_2\end{array}\right)\cdot \left(\begin{array}{cc} 3&0\\ 0&1\\ \end{array}\right)\cdot \left( \begin{

Consider minimizing a simple quadratic using gradient descent, assuming it attains 0 at optimum $w_*$ $$\begin{equation} f(w)=\frac{1}{2}(w-w_*)^TH(w-w_*) \label{loss0} \end{equation}$$ This kind of problem is sometimes called linear estimation problem because we are trying to solve for the point where $\nabla

Consider minimizing the following objective using gradient descent with learning rate $\alpha$ and $x\in \mathbb{R}^n$ $$\begin{equation}y=x^T H x \label{loss} \end{equation} $$Where $H$ is Hessian matrix with $i$'th eigenvalue proportional to $\frac{1}{i}$ . This  decay was observed in some

Two ways of finding $w$ such that $f(w)=b$: 1. solve $f(w)=b$ by using approximate inverse $g\approx f^{-1}$ on current residual $f(w)-b$ to update $w$ 2. minimize $\|f(w)-b\|^2$ using gradient descent in transformed coordinates $u=T w$ The former approach

* Left preconditioning refactors examples to be uncorrelated and on the same scale. Examples: Affine Projection algorithm, normalized LMS, Kaczmarz, normalized SGD. * Right preconditioning refactors features to be uncorrelated and on the same scale. Examples: Recursive Least Squares, Newton Method, feature normalization. * Most popular ML optimizers can be viewed as a

Suppose our problem is to minimize a quadratic $y=\frac{1}{2} c x^2$ using gradient descent. $w_{k+1}=w_k-\alpha g(w)$ Gradient descent has a learning rate parameter $\alpha$, also known as step size , what value should we use? For the problem above, you can

Suppose you have a simple composition of d dense functions. Computing Jacobian needs d matrix multiplications. What about computing Hessian vector product? The answer is 5*d. You can calculate it manually by differentiating function composition twice, grouping shared work together in temporary messages, and then counting the number of

Take classical problem in 2D, the Rosenbrock function. This problem is ill-conditioned, and you have a high probability of landing in a narrow valley, which makes your gradient descent perform poorly. With a random initialization, it is easy to end up in the narrow valley of a 2D ill-conditioned problem,