<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Yaroslav Bulatov on Medium]]></title>
        <description><![CDATA[Stories by Yaroslav Bulatov on Medium]]></description>
        <link>https://medium.com/@yaroslavvb?source=rss-5511064b4364------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*_x9cIJJ5moy_I4ESv3ZSSQ.jpeg</url>
            <title>Stories by Yaroslav Bulatov on Medium</title>
            <link>https://medium.com/@yaroslavvb?source=rss-5511064b4364------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 18:26:33 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@yaroslavvb/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[NEW NAVY DEVICE LEARNS BY DOING]]></title>
            <link>https://yaroslavvb.medium.com/new-navy-device-learns-by-doing-62f31d2dc7ba?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/62f31d2dc7ba</guid>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Tue, 08 Oct 2024 14:46:39 GMT</pubDate>
            <atom:updated>2024-10-08T14:46:39.255Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>NEW NAVY DEVICE LEARNS BY DOING</strong></p><p><strong>1958, The New York Times</strong></p><p><strong>WASHINGTON, July 7 (UPI) — The Navy revealed the embryo of an electronic computer today that it expects will be able to walk, talk, see, write, reproduce itself and be conscious of its existence.</strong></p><p>WASHINGTON, July 7 (UPI) — The Navy revealed the embryo of an electronic computer today that it expects will be able to walk, talk, see, write, reproduce itself and be conscious of its existence.</p><p>The embryo — the Weather Bureau’s $2,000,000 “704” computer — learned to differentiate between right and left after fifty attempts in the Navy’s demonstration for newsmen.</p><p>The service said it would use this principle to build the first of its Perceptron thinking machines that will be able to read and write. It is expected to be finished in about a year at a cost of $100,000.</p><p>Dr. Frank Rosenblatt, designer of the Perceptron, conducted the demonstration. He said the machine would be the first device to think as the human brain. As do human beings, Perceptron will make mistakes at first, but will grow wiser as it gains experience, he said.</p><p>Dr. Rosenblatt, a research psychologist at the Cornell Aeronautical Laboratory, Buffalo, said Perceptrons might be fired to the planets as mechanical space explorers.</p><h3>Original</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/514/0*17ffuo_ckSOPJxsT" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/506/0*JuPqN9KTRDsLqSNQ" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=62f31d2dc7ba" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introduction to residual correction]]></title>
            <link>https://yaroslavvb.medium.com/introduction-to-residual-correction-ba183540a1b6?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/ba183540a1b6</guid>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Sat, 14 Oct 2023 02:04:07 GMT</pubDate>
            <atom:updated>2023-10-14T02:04:07.765Z</atom:updated>
            <content:encoded><![CDATA[<p>Better formated <a href="https://machine-learning-etc.ghost.io/linear-solvers-and-gradient-descent/">version</a> (LaTex) of this post on Ghost</p><p>Two ways of finding $w$ such that $f(w)=b$:</p><ol><li>solve $f(w)=b$ by using approximate inverse $g\approx f^{-1}$ on current residual $f(w)-b$ to update $w$</li><li>minimize $\|f(w)-b\|²$ using gradient descent in transformed coordinates $u=T w$</li></ol><p>The former approach is called the method of “residual correction” in scientific literature. The latter view is common in Machine Learning. These two views suggest following two ways to design a new iterative method :</p><ol><li>Craft an approximate inverse $g\approx f^{-1}$</li><li>Come up with a coordinate transformation $T$</li></ol><p>Often these views are interchangeable although “residual correction” view is <strong>more general</strong>.</p><p>Taking $f(w)=Aw$ we get Newton’s method if we:</p><ol><li>apply residual correction with $g(u)=A^\dagger u$</li><li>perform gradient descent with $T=(A^TA)^{-1/2}$.</li></ol><h3>Residual correction algorithm</h3><p>Suppose we seek $w$ such that $f(w)=b$. Start with a random $w$ and apply the following update:</p><p>$$\begin{equation} \label{iterate} w=w-g(f(w)-b) \end{equation}$$</p><p>Here, $g$ is the inverse of $f$ and this iteration converges in a single step. Make it cheaper by using an approximate inverse $g$ with $g(f(w))\approx w$. Approximation errors means we might not get the answer in a single step, but under some conditions iterating Eq $\ref{iterate}$ will shrink the error to 0.</p><p><a href="https://epubs.siam.org/doi/book/10.1137/1.9781611972467">Chatelin</a>, in Section 2.12 calls $g$ “an approximate local inverse”. A necessary condition for $\ref{iterate}$ to converge is that $I-g\circ f$ is a stable map. A sufficient condition is that it is contractive. Generally speaking, $g(f(w))$ must stay close to $w$. It converges if there’s some norm $\|\cdot\|$ such that the following holds for all relevant $w$:</p><p>$$\|g(f(w))-w\|&lt;\|w\|$$</p><p>Will can get $g$ by locally approximating $f$ with a linear function $f(w)\approx Aw$ and inverting that. Consider linear $f(w)=b$ corresponding to the following linear system:</p><p>$$ \begin{equation} \label{original} Aw=b \end{equation} $$</p><p>We can solve this in a single step of residual correction by using $g(y)=A^\dagger y$</p><p>$$ \begin{equation} \label{newton} w=w-A^\dagger(Aw-b) \end{equation} $$</p><p>For a greater family of algorithms, the following transformation is useful. Using properties of pseudo-inverse, rewrite Eq $\ref{newton}$</p><p>\begin{equation} \label{right} w=w-(A^T A)^\dagger A^T (Aw-b) \end{equation} \begin{equation} \label{left} w=w-A^T (A A^T)^\dagger (Aw-b) \end{equation}</p><p>When $A^T A$ is invertible, $(A^T A)^\dagger = (A^T A)^{-1}$ and iteration \ref{right} corresponds to Newton’s method.</p><p>When $A A^T$ is invertible, $(A AT)\dagger = (A AT){-1}$ and iteration \ref{left} corresponds to Affine Projection.</p><p>Affine Projection term is used in signal processing <a href="https://arxiv.org/abs/1504.06054">literature</a> whereas linear algebra papers <a href="https://arxiv.org/abs/1506.03296">call</a> it block Kaczmarz.</p><p>We can approximate $A^TA$ or $A A^T$ with a diagonal matrix for a cheap approximation of $A^\dagger$. In this case we get the following updates:</p><p>\begin{equation}<br> \label{left:diag}<br> w=w-(\text{diag}(A^T A))^{-1} A^T (Aw-b)<br> \end{equation}<br> \begin{equation}<br> \label{right:diag}<br> w=w-A^T (\text{diag}(A AT)){-1} (Aw-b)<br> \end{equation}</p><p>These two choices of approximate inverse correspond to gradient descent with feature normalization or example normalization respectively. The former can be viewed as Jacobi iteration. The latter can be seen as Kaczmarz update applied to every example in parallel. Kaczmarz is also known as normalized LMS.</p><p>Even cheaper is to approximate $A^\dagger\approx \mu A^T$ which gives standard gradient descent iteration on least squares objective over $\ref{original}$</p><p>\begin{equation}\label{gd}w=w-\mu A^T (Aw-b)\end{equation}</p><p>Using “approximate inverse” analogy, this choice means that we approximate true inverse $A^\dagger$ with $\mu A^T$. When $A$ is a unitary matrix, $A^\dagger=A^T$ so we can set $\mu=1$.</p><p>In high dimensions, up to $k$ random vectors $x$ will be mutually orthogonal with high probability, so with row normalization, $A^T\approx A^\dagger$. This means that on a random row-normalized problem, gradient descent converges like Newton’s method if the number of rows is less than $k$.</p><p>It can be shown that $k$ is proportional to $R$, the “intrinsic dimension” of $\Sigma$, the covariance of $x$.</p><p>$$R=\frac{\text{Tr}(\Sigma)}{\|\Sigma\|}$$</p><p>This quantity provides</p><ul><li>largest batch size for which gradient descent (GD) is effective</li><li>smallest batch size for which Newton’s update improves upon GD</li></ul><h3>Iterative linear solvers</h3><p>Linear iterative solvers typically deal with square $A$, we transform our problem as follows to guarantee “squareness” of $A$.</p><p>$$A^{T}Aw=A^Tb$$</p><p>Applying iteration $\ref{iterate}$ with $g(w)=\mu w$ to squared system gives the following update, known as the modified Richardson iteration.</p><p>$$w=w-\mu A^{T}(Aw-b)$$</p><p>For a general family of methods, consider iterating the following equation with $g(y)=Py$ used for approximate inverse of $f(w)=Aw$</p><p>$$\begin{equation}\label{pre}w=w — P (Aw-b)\end{equation}$$</p><p>Here $P$ is our “approximate inverse” or “preconditioner”. Plugging various choices of $P$ generates some named algorithms. Let $P=$</p><p>$$\begin{align} \text{gradient descent} &amp; : A^T\\ \text{sign-GD} &amp; : \text{sign}(A^T)\\ \text{sketched GD} &amp; : A^T S \\ \text{Newton} &amp; : A^\dagger=(A^TA)^\dagger A^T = A^T (AA^T)^\dagger\\ \text{KFAC-Newton} &amp; : A_1^\dagger \otimes A_2^\dagger, A\approx A_1\otimes A_2\\ \text{Affine Projection (AP)} &amp; : A^T(AA^T)^{-1} \\ \text{Mahalanobis AP} &amp; : B^{-1} A^T(AB^{-1}A^T)^{-1} \\ \text{Gower/Richtarik} &amp; : B^{-1} A^T S (S^T AB^{-1}A^TS)^\dagger S^T\\ \text{Jacobi} &amp; : D^{-1}A^T\\ \text{Gauss-Seidel} &amp; : (D+L)^{-1} A^T \\ \text{Newton} &amp; : (D+L+U)^{-1}A^T\\ \text{SOR} &amp; : (D/\omega+L)^{-1} A^T, 0&lt;\omega&lt;2, \omega \rightarrow 2\\ \text{Richardson, left-pre} &amp; : A^TL^T L\\ \text{Richardson, right-pre} &amp; : RR^T A^T\\ \text{Newton + left pre} &amp; : (A^TL^T L A)^{-1}A^T L^T L\\ \text{OLSE} &amp; : (A^T A)^{-1} A^T \\ \text{GLSE} &amp; : (A^T W^{-1}A)^{-1} A^T W^{-1} \\ \end{align}$$</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0EEraSEomkbVE8MN.png" /></figure><p>Terms:</p><ul><li>$B$ is a user-chosen positive definite matrix representing norm $\|w\|²=w^T B w$. Used to prioritize good fit in certain directions.</li><li>$S$ is a random sketching matrix representing sampling of rows (examples) from $A$</li><li>Matrices $D,L,U$ come from decomposition of $A^TA$ into diagonal/lower triangular/upper triangular parts: $A’A=(D+U+L)$</li></ul><p>Jacobi/Gauss-Seidel/SOR updates are the “least-squares” formulations, applied to system $A^TA w = A^T b$, classical updates don’t work because $A$ is not square.</p><h3>Convegence analysis</h3><p>Translating algorithm into this form simplifies analysis. Suppose system can be solved exactly. Define error and residual at step $k$</p><p>\begin{align} e_k &amp; = w_k — w^{*}\\ r_k &amp; = A w_k — b \end{align}</p><p>You can <a href="https://i.stack.imgur.com/ZDWlO.png">show</a> that error and residual evolve as follows</p><p>\begin{align} e_{k+1} &amp;= (I-PA)e_k \\ r_{k+1} &amp;= (I-AP)r_k \end{align}</p><p>Because $AP$ and $PA$ have the same spectrum, label errors and parameters converge at the same rate. This post <a href="https://scicomp.stackexchange.com/a/41598/18786">summarizes</a> conditions for this to converge, but a high-level intuition is that it converges if:</p><ol><li>$PA$ is not very large</li><li>$P^T$ is aligned with $A$</li></ol><p>You can see that in 1 dimension, $m$ examples, $P$ is a vector that must live in same halfspace as $A$ for it to converge. For many dimensions, this is replaced with condition that eigenvalues$(PA)&gt;0$</p><h3>Jacobi vs Adam</h3><p>Since $A$ contains examples as rows, $D$ has squares of feature norms on diagonal, so you can see that Jacobi method reduces to gradient descent with per-coordinate normalization. Adam/AdaGrad also perform per-coordinate normalization. Key differences:</p><ul><li>Jacobi computes $c$ from predictor gradients $f’(w)=A^T$</li><li>Adam computes $c$ from loss gradients $J(f(w))=A^T(Ax-b)$</li><li>Jacobi normalizes by $E[\|c\|²]$</li><li>Adam normalizes by $\sqrt{E[\|c\|²]}$</li><li>Without square root, Adam iteration would grow unstable as loss gradients converge to zero.</li><li>Predictor gradients $f’(w)$ do not converge to zero, hence division is stable.</li></ul><h3>Richardson with left/right preconditioning</h3><p>Matrices $L^T L$ and $R R^T$ are user-chosen, see this <a href="https://machine-learning-etc.ghost.io/preconditioners-in-optimization/">note</a>. Optimal choice of $L$ and $R$ are whitening matrices that decorrelate examples/features respectively. One can think of them as follows:</p><ul><li>Applying $L$ creates a new dataset without redundant examples</li><li>Optimal $L$ is a square root of Gram matrix $A A^T$</li><li>Applying $R$ creates a new parameter space without redundant features</li><li>Optimal $R$ is a square root of Hessian matrix $A^T A$</li></ul><p>Either kind of redundancy slows down convergence of Richardson iteration or gradient descent. This follows from Hessians of original problem and its dual having same eigenvalues: $\lambda(AA^T)=\lambda(A^T A)$</p><h3>Affine Projection</h3><p>The following update finds the closest point to solution in the subspace spanned by rows of $A$</p><p>$$w = w — A^T(AA^T)^{-1}(Aw-b)$$</p><p>When system is consistent, this solves the problem in one step. We can reduce cost by using $A_2$, a subset of rows from $A$.</p><p>$$w = w — A^T(A_2 A_2^T)^{-1}(Aw-b)$$</p><p>We can represent the act of sampling $k$ rows from $m\times n$ matrix $A$ using a random $m\times k$ matrix $S$</p><p>$$A_2=S^T A$$</p><p>A special case is sampling single row from $A$. This gives Kaczmarz algorithm, known as normalized LMS in signal processing.</p><p>$$w = w — a(a’ a)^{-1}(a’w-b)$$</p><p>We can modify the concept of “closest” by Mahalonobis distance $\|w-w^*\|_B$ instead of Euclidian</p><p>$$w = w — B^{-1}A^T(AB^{-1}A^T)^{-1}(Aw-b)$$</p><p>Combining these, we get the following update formula</p><p>$$\begin{equation}\label{richtarik}w = w — B^{-1} A^T S (S^T AB^{-1}A^TS)^\dagger S^T(Aw-b)\end{equation}$$</p><p>In <a href="https://arxiv.org/abs/1506.03296">Randomized Iterative Methods for Linear Systems</a>, Gower, Richtarik show that plugging various $S$, $B$ into $\ref{richtarik}$ recovers the following:</p><ul><li>random vector sketch</li><li>randomized Newton</li><li>randomized coordinate descent</li><li>randomized least squares coordinate descent</li><li>Gassian Kaczmarz</li></ul><h3>OLSE/GLSE</h3><p>Ordinary least squares estimator has the same form as Newton’s update. Generalized least squares estimator modifies it to take into account $m \times m$ error covariance matrix $W$, where $m$ is the number of examples.</p><p>$$w = w — (A^T W^{-1} A) A^T W^{-1} (Aw-b)$$</p><p>This update has the same form as Newton’s update on left-preconditioned system $LAw=Lb$ where $L^T L=W^{-1}$. To get intuition for this update, consider diagonal $W$ with $i$th diagonal entry giving noise variance on $i$th label.</p><p>$$ W=\left( \begin{matrix} \sigma_1² &amp; 0 &amp; \ldots &amp; \ldots\\ 0 &amp; \sigma_2² &amp; \ldots &amp; \ldots\\ \ldots &amp; \ldots &amp; \ldots &amp; \ldots\\ \ldots &amp; \ldots &amp; \ldots &amp; \sigma_m² \\ \end{matrix} \right) $$</p><p>GLSE is equivalent to dividing each equation by standard deviation of noise on corresponding label and applying Newton’s step to the resulting system.</p><p>Entries of $W$ don’t matter when exact solution is possible, otherwise this prioritizes good fit for low noise equations.</p><h3>Literature</h3><ul><li>Chatelin, Eigenvalues of Matrices, section 2.12 gives “local approximate inverse”</li><li>Puntanen, Matrix Tricks for Linear Statistical Models: Our Personal Top Twenty, Ch.2 has pseudo-inverse properties</li><li>Corless and Fillion, A Graduate Introduction to Numerical Methods from the Viewpoint of Backward Error Analysis, Section 7.3 gives standard forms of methods</li><li>Rao, Linear Models, Least Squares and Alternatives. Ch 4.2 talks about “Aitken Estimator”, aka GLSE, aka “weighted least squares” estimator</li><li>Ke Chen, “Matrix Preconditioning Techniques and Applications”, 3.3 gives “Richardson” and “operator” forms of standard methods</li><li>Hodberg, “Handbook of Linear Algebra”, Section 54.1, standard iterative methods and starting point for more advanced.</li><li>Vershynin, Roman. 2018. <em>High-Dimensional Probability: An Introduction with Applications in Data Science (Cambridge Series in Statistical and Probabilistic Mathematics)</em>. 1st ed. Cambridge University Press. Explains why random vectors are orthogonal in high dimensions.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ba183540a1b6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[‌Gradient descent under harmonic eigenvalue decay]]></title>
            <link>https://yaroslavvb.medium.com/gradient-descent-under-harmonic-eigenvalue-decay-d00ff6122307?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/d00ff6122307</guid>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Thu, 16 Feb 2023 21:32:20 GMT</pubDate>
            <atom:updated>2023-02-16T21:32:20.200Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*3Te7iFra5OazWXxY" /></figure><p>‌Better formatted <a href="https://machine-learning-etc.ghost.io/gradient-descent-under-harmonic-eigenvalue-decay-average-case-analysis/">version</a> on ghost (due to Latex support)‌</p><p>Consider using gradient descent to minimize a quadratic objective with Hessian $H$.</p><p>‌</p><p>$$\begin{equation} f(w)=\frac{1}{2}(w-w_*)^TH(w-w_*) \label{loss} \end{equation}$$</p><p>‌</p><p>We can specialize by letting $H$ have $i$’th eigenvalue proportional to $\frac{1}{i}$ . This decay was observed in some convolutional network problems and conjectured to hold more generally, see Section 3.5 of<em> Noisy Quadratic Model</em><a href="https://arxiv.org/abs/1907.04164"><em> paper</em></a><em>.</em></p><p>Because gradient descent on a quadratic is rotation and scale invariant, we can assume $H$ is diagonal with norm 1 without loss of generality, which gives a simple closed form for loss after $t$ steps. (for derivation, see Gradient Descent on a Quadratic <a href="https://machine-learning-etc.ghost.io/gradient-descent-linear-update/">post</a>)</p><p>‌</p><p>$$\begin{equation} L(t)=\sum_{i=1}^n (1-\alpha h_i)^{2t} h_i w_0² \label{loss2} \end{equation} $$</p><p>‌</p><p>Each starting point $w_0$ gives a different loss trajectory, but you <a href="https://machine-learning-etc.ghost.io/why-condition-number-doesnt-matter/">can show</a> that in high dimensions and diagonal Hessian, almost all trajectories cluster around the trajectory for starting point $1,1,1,\ldots,1$.</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*e-QpG9-y4MnaIJP8" /></figure><p>‌</p><p>‌<br>‌‌<br>‌</p><p>This means that it’s sufficient to analyze behavior of the following equation:</p><p>$$f(s,n)=\frac{1}{H_n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s\frac{1}{i}$$</p><p>This $H_n$ term refers to $n$th Harmonic number, and is there to make sure initial loss is constant regardless of dimensionality, which is the case for real-life models.</p><p>This equation can be better understood using asymptotic expansions which were provided to me by George Nemes on <a href="https://math.stackexchange.com/a/4192757/998">math.SE</a>. We can summarize it as follows:‌<br>‌</p><p>1) Loss initially drops sharply as negative log</p><p>2) Followed by slightly-super-exponential rate $1/(x e^x)$.</p><p>3) Eventually switching into traditional “exponential” decay.</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*dZgbIeiGAWjtn5WE" /></figure><p>‌</p><p>x-axis in this graph gives steps normalized by the number of dimensions. This means that as dimensionality grows, more training steps exhibit the ultra-rapid logarithmic loss decay.</p><p>The trick to obtain this is to replace our summation with an integral:</p><p>$$\begin{equation}L(s)\approx \int_{i=1}^n \left(1-\frac{1}{i}\right)^{2s} \mathrm{d}i\label{defInt}\end{equation}$$</p><p>Integral approximation corresponds to taking the area under smooth curve whereas the sum adds up area under step function below. Curve flattens out for large $n$, so integral approximation becomes more accurate as $n$ increases.</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*uUBc96ht6ByFWyW8" /></figure><p>‌</p><p>For most values, $1/i$ is small, hence we can approximate $1–1/i$ as $\text{exp}(-1/i)$, obtained from series expansion of $\text{exp}(-x)$</p><p>$$\text{exp}(-x)=1-x + O(x²) $$</p><p>Use this approximation to simplify the integral in Eq $\ref{defInt}$</p><p>$$L(s)\approx \int_{1}^n \frac{\text{exp}(-2s/i)}{i} \mathrm{d}i\approx E_1\left(\frac{2s}{n}\right)$$</p><p>Here $E_1$ is the<a href="https://dlmf.nist.gov/6.2#E1"> exponential integral</a>. This approximation is valid when the number of steps $s$ grows slower than dimensionality squared $n²$, confirmed by George Nemes<a href="https://math.stackexchange.com/a/4192757/998"> here</a>.</p><p>We can plot integral approximation of loss against exact loss after s steps and see that this approximation tracks true loss closely.</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*UT02CkFhgUjrMGsr" /></figure><p>‌</p><p>Now we can compute series expansion of $E_1$ at 0 and at $\infty$ to get small $s$ and large $s$ approximations. Define $x$ as the argument of $E_1$ in the last equation to get the expression of loss in terms of exponential integral.</p><p>You can think of $s$ as the “dual epoch” — normalize steps by the number of parameters rather than by number of examples.</p><p>As you see in worst case analysis (<a href="https://machine-learning-etc.ghost.io/worst-case-analysis-of-gradient-descent-for-harmonic-eigenvalue-decay/">post</a>), reaching dual epoch=1 is the first point in time when worst case analysis becomes sensitive to the smallest eigenvalue. And these expansions show that it will take more than $n²$ steps for typical case to resemble worst case.</p><p>Expanding $E_1(x)$ at $0$ and at $\infty$, we get the following small-x and large-x approximations.</p><p>$$L_\text{small}(x)\approx -\log(x)$$</p><p>$$L_\text{large}(x)\approx \frac{1}{x e^{x}}$$</p><p>Initial decay is logarithmic and this approximation is valid perhaps for the first $n/20$ steps.</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*V2Otzv1Tu5XZ1Wcb" /></figure><p>‌</p><p>Meanwhile, large-s approximation becomes good as the number of steps approaches the number of dimensions.</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*fg7QghSEooUcpFT7" /></figure><p>‌</p><p>The function that solves for the number of steps needed to reach a given loss is known as Lambert W function, or the “product log” function. We can use log as an upper bound.</p><p>For instance consider solving for the steps needed to achieve $10^{-k}$ loss:</p><p>‌</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*LiGkirl28KfvCz5k" /></figure><p>‌</p><p>‌<br>‌</p><p>725 words</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d00ff6122307" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Critical batch-size and effective dimension in Ordinary Least Squares]]></title>
            <link>https://yaroslavvb.medium.com/critical-batch-size-and-effective-dimension-in-ordinary-least-squares-bd1768fadf14?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/bd1768fadf14</guid>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Mon, 30 Jan 2023 17:06:40 GMT</pubDate>
            <atom:updated>2023-01-30T17:06:40.681Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Note: a better formatted version (due to lack of LaTeX support on medium) is </em><a href="https://machine-learning-etc.ghost.io/batch-size-step-size-and-dimensionality-for-linear-least-squares/"><em>here</em></a></p><p>Why do we get diminishing returns with larger batch sizes?</p><p>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.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*JNGX5llzxjOhz5bJ.png" /></figure><p>We can quantify <em>does not help much</em> by considering the setting of ordinary least squares.</p><h3>Background: Ordinary Least Squares (OLS)</h3><p>Suppose we need to find $w$ which satisfies the following $m\times n$ system of linear equations. Assume solution $w^*$ exists and is unique.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*w--QPcKy5ws-LvSt.png" /></figure><p>We can turn this into optimization problem by minimizing $J$, the sum of squared differences between left-hand side and right-hand side of each equation. These differences are known as <strong>residuals</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kMM7li3nWJSgIIJa.png" /></figure><p>Solution to this minimization problem is also the solution $w^*$ of the original problem.</p><p>This is a convex problem, so we can minimize it using gradient descent. Each step of gradient descent requires computing as many terms as there are equations $m$. This is expensive if $m$ is large.</p><p>Reduce the cost by randomly sampling $b$ equations at each step of gradient descent, and using corresponding random objective $\hat{J}$ to compute descent direction.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*K6AzTjDtCpgEYCHE.png" /></figure><p>This is known as “mini-batch SGD with batch size b”, or just “SGD”, and can be shown to converge to $w^*$ exponentially fast using <a href="https://arxiv.org/abs/1811.02564">techniques</a> of Belkin. In scientific computing, such approach would be called a “row-action method”.</p><p>The intuition is that gradient computed on just one of the terms will probably point in the same general direction as the gradient of the full sum, so we can step in that direction safely.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*FaQ_3Is9R9ZCjpoA.png" /></figure><p>Difference between current estimate $w$ and target $w^*$ is known as <strong>error</strong> $e$, and we are interested in driving it to $0$ as fast as possible.</p><p>Notes:• starting point $w$ is random, hence $e$ is random• hence we consider the <em>expected</em> behavior of error norm squared: $E\|e\|²$• good SGD step will decrease $E\|e\|²$ significantly</p><h3>Optimal Step Size for OLS</h3><p>For step size analysis, we only care about relative decrease in error, so can assume our starting error magnitude is $1$ ie, $E\|e\|² =1$. After one step of mini-batch SGD, we can show that the error magnitude will be the following:</p><p>Notes:</p><ul><li>$x$ is a coefficient vector of a randomly sampled equation</li><li>$\alpha$ is the step-size</li><li>$b$ is the batch-size</li><li>$E\langle x_1,x_2\rangle²$ is the strength of correlation for two IID drawn $x$</li><li>this assumes $e$ is isotropic — starting at $w$, any direction is equally likely to point to the solution $w^*$</li><li>obtained by <a href="https://i.stack.imgur.com/VWpjd.png">writing</a> action of SGD as a linear operator and taking trace</li></ul><p>Now we can solve for the step size which generates the largest decrease in expected error after 1 step:</p><p>$$\alpha_{opt}=\dfrac{b\ E\| x\| ^{2}}{E\| x\| ^{4}+\left( b-1\right) E\langle x_{1},x_{2} \rangle^{2}}$$</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*AU0vs6B26TeRJEvX.png" /></figure><p>Notes:</p><ul><li>in fully stochastic case $b=1$ and deterministic $x$ we get step size $1/\|x\|²$, same as in the Kaczmarz algorithm</li><li>for full batch case $b=\infty$ we get step size of $\operatorname{tr}H/\operatorname{tr}H²$ where $H$ is the Hessian of our full-batch objective $J$</li><li>fully stochastic step size is $E\|x\|²/E\|x\|⁴$</li><li>in the worst case scenario, fully stochastic step size is a factor of $d$ smaller than full-batch step size</li></ul><h3>Critical Batch Size for OLS</h3><p>Substituting $\alpha_\text{opt}$ into equation for expected error, we get the corresponding decrease in error magnitude</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/746/0*-RIX53E2zBoUsTpO.png" /></figure><p>Notes:</p><ul><li>best achievable relative error reduction is $(E\|x\|²)²/E\langle x_1,x_2\rangle²$</li><li>it is equal to $(\operatorname{tr}H)²/\operatorname{tr}H²$ where $H$ is the Hessian of full-batch objective $J$</li><li>flatter spectrum of H produces greater reduction in expected loss</li><li>this value can be seen as a smoothed count of the number of non-zero dimensions spanned by H</li></ul><p>Largest decrease in error requires infinite batch size. Which batch-size gets us halfway there?</p><p>For stochastic $x$, there’s a unique solution sometimes called a “critical batch size” $b_c$</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*MuceR5Zcrj51m4RR.png" /></figure><p>This quantity can be seen as a measure of “effective dimension” of the space of $x$. To see why, let $x$ be Gaussian distributed centered at zero with covariance matrix $\Sigma$</p><p>Using Gaussian expectation formulas, we can rewrite $b_c$ as follows</p><h3>Effective Degrees of Freedom</h3><p>The quantity $d_\text{eff}$ has been <a href="https://i.stack.imgur.com/BcZES.png">called</a> “effective degrees of freedom” (Encyclopedia of Statistical Sciences, vol 3). It has also been called the “effective rank R” by Bartlett (Definition 3 of “benign overfitting” <a href="https://arxiv.org/pdf/1906.11300.pdf">paper</a>)</p><p>One can consider $d_\text{eff}$ as a “smoothed” way of counting dimensions of the space occupied by our observations $x$. When the space is isotropic, $d_\text{eff}=d$. When some dimensions have less mass than others, they are counted as “fractional” dimensions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*VZd_PjK4ExggkwM0.png" /></figure><h3>Special case: d=1</h3><p>Why does the formula have $d_\text{eff}+3$ rather than $d_\text{eff}$? Consider the case of Gaussian observations in 1 dimension, which gives batch-size 4 as the critical batch size. One might think that in case of 1 dimension, having more than one observation per batch doesn’t help.</p><p>However, because we use uniform step size (independent of observation), using same step size formula for batch-size 1 as in full-batch case may cause divergence. In particular for, when the largest convergent step size in full-batch case is 1, then fully stochastic step size should be at most $\frac{1}{3}$ to avoid divergence. This means we need to use batch size of at least 3 to match gradient descent rate. See <a href="http://yaroslavvb.com/convergence.pdf">convergence.pdf</a> for details.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bd1768fadf14" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[optimal learning rate for Gradient Descent on a high-dimensional quadratic]]></title>
            <link>https://yaroslavvb.medium.com/mediumoptimal-learning-rate-for-high-dimensional-quadratic-5f89b7c5269d?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/5f89b7c5269d</guid>
            <category><![CDATA[neural-networks]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Mon, 27 Dec 2021 17:14:04 GMT</pubDate>
            <atom:updated>2021-12-28T00:22:08.811Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>A better formatted version of this article is on Ghost, which has proper Latex support: </strong><a href="https://machine-learning-etc.ghost.io/optimal-learning-rate-for-high-dimensional-quadratic/"><strong>https://machine-learning-etc.ghost.io/optimal-learning-rate-for-high-dimensional-quadratic/</strong></a></p><p>Suppose our problem is to minimize a quadratic y=cx2 by using gradient descent. Gradient descent has a learning rate parameter α, also known as <strong>step size</strong>, what value should we use? For the problem above, you can find that α=1/c takes you directly to the minimum regardless of starting position, hence it is the <strong>optimal step size</strong> in this setting. Meanwhile the <strong>largest convergent step size</strong>, ie, the value for which gradient fails to converge, is 2/c.</p><p>What about higher dimensions?</p><p>In two dimensions, you can see that the location of the starting point matters, but distance to the minimum doesn’t. Hence, we can restrict ourselves to to starting on the unit circle.</p><p>Consider two dimensional quadratic:</p><p>λ1x2+λ2y2</p><p>Since we can converge in a single step, limit ourselves to a single section defined by the starting point and 0. This gives us a 1-dimensional quadratic, whose curvature is between λ1 and λ2 depending on the starting point. Hence the “optimal” step size is between 1/λ1 and 1/λ2, and to get the average value we take expectation over possible starting points.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*u7QVn2QYxqpDwvL1.gif" /></figure><p>For instance take λ1=1 and λ2=0.5. Optimal step size is between 1 and 2, and ≈1.261 on average. You can get a formula in terms of λ1,λ2, but it’s not pretty (see notebook in the bottom).</p><p>In higher dimensions we have the following objective:</p><p>λ1x2+λ2y2+λ3z2+…</p><p>What should we use for coefficient values λi?</p><p>Roger Grosse looked at quadratic approximation of deep learning objectives, and found λi to be proportional to 1/i for some practical problems, see Section 3.5 of their Noisy Quadratic Model <a href="https://arxiv.org/abs/1907.04164">paper</a>. Additionally, eigenvalues of some random Hermitian matrices decay similar to 1/i. Since the scale of the problem doesn’t matter, normalize the problem so that largest coefficient is =1, which makes the largest convergent step size=2.</p><p>We can <a href="https://math.stackexchange.com/a/4234759/998">use numerical integration</a> to plot the optimal step size as a function of dimensionality. Since our largest coefficient is 1, largest convergent learning rate is 2. Meanwhile the average optimal step size approaches 2 for large number of dimensions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/662/0*V9o_avxjHY-2mAx-.png" /></figure><p>Mathematica <a href="https://www.wolframcloud.com/obj/yaroslavvb/newton/forum-average-ratio-math.nb">notebook</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5f89b7c5269d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How many matmuls are needed to compute Hessian-vector products?]]></title>
            <link>https://yaroslavvb.medium.com/how-many-matmuls-are-needed-to-compute-hessian-vector-products-e8dbb0059d3e?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/e8dbb0059d3e</guid>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Wed, 15 Dec 2021 21:46:05 GMT</pubDate>
            <atom:updated>2021-12-15T21:46:05.814Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/968/1*bWBuZSvbFHSbai8ETusdpQ.png" /></figure><p>Suppose you have a simple composition of d dense functions. Computing Jacobian needs d matrix multiplications. What about computing Hessian vector product?</p><p>You can calculate it manually by differentiating function composition twice, grouping shared work together in temporary messages, and then counting the number of matrix multiplications. One trick is that equations when differentiating with the full multivariate chain rule are equivalent to those in the scalar case, provided you don’t treat multiplication as commutative. So then you can simply do the derivative in the scalar case, and the number of multiplications you obtain corresponds to the number of matrix multiplications in the matrix case.</p><p>Here’s the calculation worked out on a simple example above:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TphluvCpxcDTvfwNcH_sEg.png" /></figure><p>You can see there are up D temporary messages, and computing computing all the messages requires 5 multiplications, marked in purple in computation above.</p><p><a href="https://colab.research.google.com/drive/1LohvdgKPcEsZZx0KfroPFtBN303du53h#scrollTo=9WYbRZHA6uYx">Compare this</a> against in PyTorch — create linear neural network with many layers, forward pass would require d matrix multiplications, whereas HVP would need 5*d. In practice, it takes 5-5.3x longer than forward pass, which is close to what’s expected.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e8dbb0059d3e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to do matrix derivatives]]></title>
            <link>https://yaroslavvb.medium.com/how-to-do-matrix-derivatives-bbadb93e3cf9?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/bbadb93e3cf9</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Fri, 09 Jul 2021 19:02:01 GMT</pubDate>
            <atom:updated>2021-07-09T19:06:57.096Z</atom:updated>
            <content:encoded><![CDATA[<p>Suppose you have the following scalar function of matrix variable W.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/149/1*qgrdE6H4HBlK5gioq09GYA@2x.png" /></figure><p>What’s the derivative with respect to matrix W? Define“matrix derivative” Df as “the thing that you subtract from your variable to go in the steepest descent direction”. IE, your gradient descent update would use Df as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*hSj5NxbVRqGIdy78_bRPyQ@2x.png" /></figure><p>The old-school approach is to write out objective as a sum, differentiate, then stare at the result until you can see the corresponding matrix notation. This was the approach we used in Andrew Ng’s <a href="http://deeplearning.stanford.edu/tutorial/">UFLDL</a> course taught at Google (this course led to the formation of the Google Brain team)</p><p>Taking this approach, convert to summation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/240/1*apCLfAmeHoakSuOgk3VNSg@2x.png" /></figure><p>Differentiate and convert back to matrix form by visually identifying the matrix form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/388/1*ZVap4qFq-wNqFXkgNeb8JQ@2x.png" /></figure><p>However, this visual identification approach doesn’t scale. What if we wanted derivative of the following function in matrix notation?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/321/1*x5f0pcq0c27N-X2XPEYqjw@2x.png" /></figure><p>We know that the derivative is the following (p.201 of Magnus’ Matrix Calculus <a href="https://onlinelibrary.wiley.com/doi/book/10.1002/9781119541219">book</a>)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/1*OBOlmB62gEpgxp5-Rhh5PQ@2x.png" /></figure><p>How do we derive this expression?</p><p>Converting to summation and back is cumbersome. Fortunately, there’s a much better procedure. An end-to-end example motivated by neural network training is in <a href="https://math.stackexchange.com/a/4190194/998">my answer</a> on math.SE forum, but to summarize, you need to:</p><ol><li>Compute differential instead of derivative.</li><li>Manipulate the differential into one of several standard forms</li><li>Extract the derivative from the differential by looking up standard form in the “identification table” (p. 199, p.215 in Magnus)</li></ol><p>Differential is closely related to derivative. In the Taylor series expansion, differential is the second term of the series, while the derivative is the coefficient in front of the second term.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/674/1*Ze35vmgJH9cCVUzJIXAuTg@2x.png" /></figure><p>Because it’s closely related, rules like derivative chain-rule have corresponding differential versions. The reason to use differentials, is that in the expansion above, derivative is a rank-4 tensor, while differential is a matrix, hence dealing with differentials keeps you in familiar matrix land.</p><p>As to standard identification forms, the only entry in the identification table you probably need is the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*dad1oX-JEllVFzOGtebL_A@2x.png" /></figure><p>You can also use Mathematica’s matrix differentiation package to compute this expression automatically: <a href="https://www.wolframcloud.com/obj/yaroslavvb/newton/matrix-derivative-example.nb">example</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bbadb93e3cf9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Using “Evolved Notation” to derive the Hessian of cross-entropy loss]]></title>
            <link>https://yaroslavvb.medium.com/using-evolved-notation-to-derive-the-hessian-of-cross-entropy-loss-195f8c7b3a92?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/195f8c7b3a92</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[pytorch]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Fri, 30 Aug 2019 02:37:10 GMT</pubDate>
            <atom:updated>2019-08-31T09:58:28.124Z</atom:updated>
            <content:encoded><![CDATA[<p>I was recently reminded of a lesson learned at Stephen Boyd’s Convex Optimization class at Stanford a few years ago, back when Google was paying for random classes taken by employees.</p><p>The lesson is that you should rely on context to drop redundant information from mathematical notation. It may feel less precise, but a good choice of context makes things unambiguous while keeping derivations concise.</p><p>His concrete example was around positive definiteness. We can start by being explicit and writing something like this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/328/1*4rEl9dsHPrlV12XKGoyWKQ@2x.png" /></figure><p>This is a bit verbose, so we could use a special operator to denote this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/103/1*QEuEihso2IqH8kxt4Esn9g@2x.png" /></figure><p>However, we can go one step further and use “Evolved Notation”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/103/1*INzwJX6igd-4YvRNVXCQfw@2x.png" /></figure><p>The reason we can do this is that &gt; is an ordering operator, and in a typical setting, positive-definiteness is the canonical way of defining partial order on the space of matrices.</p><p>I was reminded of this when I needed to estimate the Hessian of cross entropy loss and making the mistake of starting with “devolved” notation and stumbling into cumbersome algebra. The “evolved” notation could instead go something like this —</p><p>Treat logits theta as the parameter and class x as the random variable in one-hot encoding, then softmax can be written as probability of x in exponential family form</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/346/1*dY9vN4OMOSjrHDgZljaPyg@2x.png" /></figure><p>The reason for exponential family form is that we we can reuse known formulas for A’ and A’’ when differentiating loss. The following is derived in many places, ie Wainwright’s <a href="https://people.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf">survey</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/214/1*p3KvmmRa9gFjv4thz6hQyg@2x.png" /></figure><p>With soft labels as empirical distribution q, we can write cross entropy loss as expectation</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/232/1*TkustC70qYwnFpRHuFqy2A@2x.png" /></figure><p>Having just one random variable and one parameter variable makes it unambiguous to drop variable specs from our definitions of functions, derivatives and expectations.</p><p>Now differentiate J, apply chain rule, and reuse mean interpretation of A’ for gradient. Differentiate again, and reuse covariance interpretation of A’’ for the Hessian. You can skip most algebra by reasoning what the mean and the covariance should be when the distribution consists of k one-hot vectors with explicit probabilities p1…pk. After simplifying, we get the following for gradient and Hessian of cross-entropy loss:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/289/1*vtnrGj1c9ofpV13334QE9w@2x.png" /></figure><p>For implementation, you have to come down from the the tower of Evolved Notation© and fill in the details. In PyTorch we can double check the result against autodiff engine:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ab6eb64693d7a8038be976a9e3dca5d9/href">https://medium.com/media/ab6eb64693d7a8038be976a9e3dca5d9/href</a></iframe><p>This uses “hessian” <a href="https://gist.github.com/apaszke/226abdf867c4e9d6698bd198f3b45fb7">utility</a> from Adam Paszke for autodiff and outer(p) for pp’ — <a href="https://colab.research.google.com/drive/1ZdAFrHkT_jYFfiWdYztqG-RBcKE2--Ft#scrollTo=HTTdKGJx7VUq">colab</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=195f8c7b3a92" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Large-scale AI and sharing of models]]></title>
            <link>https://yaroslavvb.medium.com/large-scale-ai-and-sharing-of-models-4622ba59ec18?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/4622ba59ec18</guid>
            <category><![CDATA[ethics]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ai]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Sun, 21 Jul 2019 03:19:02 GMT</pubDate>
            <atom:updated>2019-07-21T04:40:00.286Z</atom:updated>
            <content:encoded><![CDATA[<h3>Background</h3><p>In “<a href="https://openai.com/blog/ai-and-compute/">AI and Compute</a>”, OpenAI reported that the cost of training AI models has been growing exponentially, observing a doubling period of 3.5 months.</p><p>At the current rate, in 4 years, training the largest model will cost more than launching a rocket into orbit. If the trend continues, it would change the way progress is achieved. Instead of many individual players training models, we will have a few places launching AI rockets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*uK0vcLzllWD_epRj" /><figcaption>GPT-5 training facility</figcaption></figure><p>AI research could become more like high-energy physics or astronomy where individuals develop their models “on paper” and wait in line for a shot on a particle accelerator or a telescope. In these fields, research is publicly funded and there’s a strong culture of sharing. Countries don’t need to launch their own space telescope, they can reuse data from the Hubble.</p><p>For AI research to continue at an optimal pace it would help to have a similarly robust culture of sharing. In addition to sharing methods or code, it’s useful to share model weights as well.</p><p>The reason is that we are seeing an increase in architectures which build on top of existing weights. For instance, object detection models often use <a href="https://github.com/cybertronai/imagenet18">Imagenet-trained</a> classification network as a backbone; text applications <a href="https://github.com/atselousov/transformer_chatbot">build</a> on top of trained checkpoints of GPT or Bert.</p><p>Training such models from scratch can be expensive. For instance, recently released XLNet was <a href="https://www.reddit.com/r/MachineLearning/comments/c59ikz/r_it_costs_245000_to_train_the_xlnet_model512_tpu/">estimated</a> to be $245k to train. Being able to reuse such models lowers the bar for research higher up the stack.</p><h3>Downsides</h3><p>The problem with a technology being widely available is “the bad guys get it”. It makes sense to keep the costs of dealing with them in mind. For instance weapon design technology is restricted — mainly bad uses. General manufacturing technology is shared despite bad uses — positive applications outweigh the negative.</p><p>An example of the cost incurred by sharing AI technology was from when I was on Google’s OCR team.</p><p>Our team was in charge of Tesseract, an open-source OCR product. An internal reorg had merged OCR team with reCAPTCHA team and we started looking at the effectiveness of reCAPTCHA. To our surprise, we discovered that users had been using our own OCR tool against us. In one case the team was puzzled how to respond to a user report of Tesseract failure on what was obviously a reCAPTCHA image.</p><p>Tesseract accuracy was below human but above random, so an automated solution could keep reloading the images until the OCR succeeded. This need to reload was also the weakness of the attack and the defense was easy to implement.</p><p>When vision networks started taking off, <a href="https://medium.com/u/3702e41f3813">Julian Ibarz</a> ran an experiment to study the feasibility of convnets breaking reCAPTCHA. The result was &gt;99.9% accuracy for a neural net vs ≈80% for a human — captcha success was no longer a reliable indicator. Developing a defense was more involved. Google did not release the “reCAPTCHA breaking model.”</p><p>There’s a similar situation happening with text models right now — just like vision-based captchas before it, text based content filters are likely to become ineffective. We could soon be in a position where it would be impossible to distinguish human generated text from AI generated text.</p><p>An SEO shop could use such language model to flood the internet with autogenerated reviews and drive customers to businesses without good human reviews. Like with captchas before it, this would require investment in alternative solutions — for instance, relying more on provenance information and less on the content.</p><h3>The Balance</h3><p>Ultimately, the impact of information sharing comes down to the balance between negative and positive uses. There’s no sense in sharing “captcha breaking model” — what are the good uses? On the other hand, a generic language embedding has positive uses in addition to negative, so sharing decisions should consider the balance. A recent <a href="https://medium.com/huggingface/ethical-analysis-of-the-open-sourcing-of-a-state-of-the-art-conversational-ai-852113c324b2">post</a> from <a href="https://medium.com/huggingface">@Huggingface</a> goes over the analysis they used to find the balance for their recent release.</p><p><em>Thanks to </em><a href="https://medium.com/u/33ebef5d1079"><em>Ben Mann</em></a><em> and </em><a href="https://twitter.com/Miles_Brundage"><em>Miles Brundage</em></a><em> for feedback on earlier draft of this post.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4622ba59ec18" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ICLR Optimization papers III]]></title>
            <link>https://yaroslavvb.medium.com/iclr-optimization-papers-iii-1e1edc050ba6?source=rss-5511064b4364------2</link>
            <guid isPermaLink="false">https://medium.com/p/1e1edc050ba6</guid>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Yaroslav Bulatov]]></dc:creator>
            <pubDate>Tue, 25 Jun 2019 03:02:55 GMT</pubDate>
            <atom:updated>2019-06-25T03:05:18.067Z</atom:updated>
            <content:encoded><![CDATA[<h3>Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions</h3><p>(<a href="https://medium.com/@yaroslavvb/iclr-optimization-papers-i-fluctuation-dissipation-relations-for-sgd-a638ad9964cc">part I</a>, <a href="https://medium.com/@yaroslavvb/iclr-optimization-papers-ii-44f03b98dc5f">part II</a>)</p><p>Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, Roger Grosse</p><p><a href="https://arxiv.org/abs/1903.03088">https://arxiv.org/abs/1903.03088</a></p><p>One approach to hyper-parameter choice is to apply gradient descent in the hyper-parameter space. For each setting of hyper-parameters, you run your optimization to convergence, get resulting loss, and then backprop through these steps to get the gradient. This is expensive.</p><p>What if instead you had a function, also known as the “best response function”, which was cheap to compute and gave you final values of neural network parameters, <strong>without</strong> having to run the optimization procedure?</p><p>Obviously this function would have to be very approximate (or we would just use it in place of SGD itself), but perhaps it’s a good enough approximation of gradient descent in hyper-parameter space.</p><p>Inspiration for the form of best-response function comes from a linear regression problem, where they observe that best response is a simple function of the weight decay hyper-parameter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*b31hiO4ynbDLRrXWEFF4aQ.png" /></figure><p>To simplify things further, they drop the sigmoid and model the best-response function as a linear function of hyper-parameters.</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*b31hiO4ynbDLRrXWEFF4aQ.png" /></figure><p>Now you can fit the parameters of the best-response function to statistics observed during optimization, and do gradient descent in hyper-parameter space, which gives a non-constant hyperparameter schedule. An encouraging observation was that these schedules transferred between optimization tasks, outperforming manually tuned constant schedules.</p><p>The “best-response” approach feels similar in spirit to hyper-networks and “synthetic gradient” papers — taking an expensive computation and approximating it with something that seems too simple to ever work.</p><p>I’m curious if these schedules will be useful in the large data setting, for example, by outperforming a constant learning rate schedule.</p><h3>Meta-Learning Update Rules for Unsupervised Representation Learning</h3><p>Luke Metz, Niru Maheswaranathan, Brian Cheung, Jascha Sohl-Dickstein</p><p><a href="https://arxiv.org/abs/1804.00222">https://arxiv.org/abs/1804.00222</a></p><p><a href="https://s3.amazonaws.com/postersession.ai/70ea3385-0d61-4294-add0-5824e9f1446c.jpg">https://s3.amazonaws.com/postersession.ai/70ea3385-0d61-4294-add0-5824e9f1446c.jpg</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*eP1pnGZ9m4roD1JJ" /></figure><p>They parameterize “learning procedure” in a way that covers SGD, but also other, hereto unknown learning methods, and then learn parameters of this procedure by back-propagating the loss on target tasks through steps of the procedure.</p><p>The result is a set of parameters which gives you a way to learn the parameters of a network in a way that is more robust than SGD. For instance, they show that their resulting procedure can learn to fit a network with step function non-linearity, which is not possible with SGD.</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*b31hiO4ynbDLRrXWEFF4aQ.png" /></figure><p>It feels like this procedure could learn similar methods to those proposed by “Biologically Plausible” learning literature, which also try to do away with gradients.</p><h3>Local SGD Converges Fast and Communicates Little</h3><p>Sebastian U. Stich</p><p><a href="https://openreview.net/forum?id=S1g2JnRcFX">https://openreview.net/forum?id=S1g2JnRcFX</a></p><p>What if you averaged parameter values instead of averaging gradients between workers? This would be the same for one step, but give you something different if you let workers go for several steps between averaging.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-K057fYqvp_jI1Fb" /></figure><p>In this work they prove for the finite-sum convex setting, that this method method converges at the same rate as regular SGD, with communication delays O(1/(batch size)). This is a mathematical follow up on a paper from the same group which evaluates this method on CIFAR dataset.</p><p>I was interested in this paper because I was trying to find something that would let me schedule batch sizes more efficiently. A minibatch-SGD step with batch of size B could be viewed as B workers performing B SGD steps before communicating, so allowing larger communication delay should also allow you to use a larger batch size.</p><p>Batch size tuning was an important part of my “Imagenet in 18 minutes” <a href="https://github.com/cybertronai/imagenet18">project</a>. Convergence improved when we started with smaller batches, and grew them over time. There’s a batch-size effect beyond what can be explained by linear learning rate scaling.</p><p>Following up on this work I discovered the paper in the next section below.</p><h3>Communication trade-offs for synchronized distributed SGD with large step size</h3><p>Kumar Kshitij Patel, Aymeric Dieuleveut</p><p><a href="https://arxiv.org/abs/1904.11325">https://arxiv.org/abs/1904.11325</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*NpZ4nphK61f64Pvb" /></figure><p>They show that for logistic regression, you can reduce communication frequency as you get closer to the solution. IE, the allowable delay grows in inverse proportion to distance to the final result</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/0*9GyQOXPDD_pMm0Sc" /></figure><p>C communications, indexed by t</p><p>N_t = number of no-communication SGD steps after t’th communication</p><p>T = total number of examples (also number of steps, since workers use batch_size=1)</p><p>P workers</p><p>\nu=learning rate</p><p>\mu= strong convexity parameter</p><p>M = upper bound on third derivative of loss</p><p>This is in line with empirical observation that as optimization approaches its tail end, you can increase global batch size/number of machines.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1e1edc050ba6" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>