Machine Learning, etc

Machine Learning, etc

Sign in Subscribe

Gradient descent under harmonic eigenvalue decay

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

Value of quadratic form on a unit circle

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{

Gradient descent on a quadratic

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

Gradient descent under harmonic eigenvalue decay: worst-case analysis

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

Critical batch-size and effective dimension in Ordinary Least Squares

Critical batch-size and effective dimension in Ordinary Least Squares

Why do we get diminishing returns with larger batch sizes? As you increase the mini-batch size, the estimate of the gradient gets more accurate. At some point it's so close to the "full gradient" estimate, that increasing it further doesn't help much. We can

Introduction to residual correction

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

Preconditioning in least-squares and ML

* 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

Optimal learning rate for high-dimensional quadratic

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

How many matmuls are needed to compute Hessian-vector product of a linear neural network?

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

Why condition number doesn't matter

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,