2b:null 2c:["$","title",null,{"children":"PowerSGD Theory - Experiments and Proposed Approach | Thijs Vogels | Observable"}] 31:T7f0,texmd` ## Approximation quality after $k$ steps of power iteration Consider we are approximating an $n \times m$ ($n > m$) matrix $\mM$ using column vectors $\pp \in \R^{n}$ and $\qq \in \R^{m}$ as $\mM \approx \pp \qq^\top$. We will look at various ways of choosing $\pp$ and $\qq$. Notation: - $\hat \pp = \frac{\pp}{\norm{\pp}}$, - $\norm{\mX}^2 = \norm{\mX}^2_\text{Frob.}$. First, consider power iteration: $$\begin{aligned} \qq_0 &\sim \cN^n(0, 1), \\ \pp_i &= \mM \hat \qq_{i-1} \quad \text{for }i \text{ odd > 0}, \\ \qq_i &= \mM^\top \hat \pp_{i-1} \quad \text{for }i \text{ even > 0}, \\ \mA_i &= \mM \hat \qq_{i-1}\hat \qq_{i-1}^\top \quad \text{for }i \text{ odd > 0}, \\ \mA_i &= \hat \pp_{i-1}\hat \pp_{i-1}^\top \mM \quad \text{for }i \text{ even > 0}. \end{aligned}$$ We will study the approximation quality as $\norm{\mA_i - \mM}^2/\norm{\mM}^2$. ### Observation: we can assume $\mM$ is diagonal without loss of generality. We can use Singular Value Decomposition to write $\mM = \mU \mS \mV^\top$, where $\mU$ and $\mV$ are orthogonal and $\mS$ is diagonal. Define $\pp' = \mU^\top \pp$ and $\qq' = \mV^\top \qq$. Note that $\norm{\pp'}=\norm{\pp}$ and $\norm{\qq'}=\norm{\qq}$. For these vectors, we have an equivalent recursion: $$\begin{aligned} \qq'_0 &\sim \cN^n(0, 1), \\ \pp'_i &= \mS \hat \qq'_{i-1} \quad \text{for }i \text{ odd > 0}, \\ \qq'_i &= \mS^\top \hat \pp'_{i-1} \quad \text{for }i \text{ even > 0}, \\ \mA'_i &= \mS \hat \qq'_{i-1}\hat \qq'^\top_{i-1} \quad \text{for }i \text{ odd > 0}, \\ \mA'_i &= \hat \pp'_{i-1}\hat \pp'^\top_{i-1} \mS \quad \text{for }i \text{ even > 0}. \end{aligned}$$ and the approximation quality $$ \frac{\norm{\mS - \mA'_i}^2}{\norm{\mS}^2} = \frac{\norm{\mU\mS\mV^\top - \mU\mA'_i\mV^\top}^2}{\norm{\mM}^2} = \frac{\norm{\mM - \mA_i}^2}{\norm{\mM}^2}. $$ For the first step, this is only exactly correct if the dimension $n$ > $m$. If $m > n$, the norm changes if you right-multiply by $\mV$ in the manipulation of the norms. `32:T8f7,texmd` ### Approximation quality after $k$ iterations Using this result, we can easily analyze the approximation quality in terms of the diagonal entries of $\mS$ and $\qq'_0$. We will define $\mS = \text{diag}(\lambda_1, \ldots, \lambda_n)$ and $\qq'_0 = (q_0, \ldots, q_n)^\top$. We get the following results: Random projection ($\mA_1$): $$\begin{aligned} \frac{\norm{\mA_1 - \mM}^2}{\norm{\mM}^2} = \sum_{i=1}^n \frac{q_i^2}{\sum_j q_j^2} \left( 1 - \frac{\lambda^2_i}{\sum_j \lambda_j^2} \right) = 1 - \frac{\lin{\qq_0'^{2}, \bm{\lambda}^2}}{\norm{\qq_0'}^2\norm{\bm{\lambda}}^2}. \end{aligned}$$ In expectation, all $q^2_i$ are equal 👋, so we get $$\begin{aligned} \expect \frac{\norm{\mA_1 - \mM}^2}{\norm{\mM}^2} = 1 - \frac{1}{n}\sum_{i=1}^n \left( \frac{\lambda^2_i}{\sum_j \lambda_j^2} \right) = \frac{n-1}{n}. \end{aligned}$$ Two steps of power iteration ($\mA_2$): $$\begin{aligned} \frac{\norm{\mA_2 - \mM}^2}{\norm{\mM}^2} = \sum_{i=1}^n \frac{\lambda_i^2 q_i^2}{\sum_j \lambda_j^2 q_j^2} \left( 1 - \frac{\lambda^2_i}{\sum_j \lambda_j^2} \right) \end{aligned},$$ and in general: $$\begin{aligned} \frac{\norm{\mA_k - \mM}^2}{\norm{\mM}^2} = \sum_{i=1}^n \frac{\lambda_i^{2k-2} q_i^2}{\sum_j \lambda_j^{2k-2} q_j^2} \left( 1 - \frac{\lambda^2_i}{\sum_j \lambda_j^2} \right) = 1 - \frac{\lin{\qq_0'^{2} \circ \bm{\lambda}^{2k-2}, \bm{\lambda}^2}}{\norm{\bm{\lambda}^{k-1} \qq_0'}^2\norm{\bm{\lambda}}^2}. \end{aligned}$$ Again, considering that all $q_i^2$ are equal, we have $$\begin{aligned} \expect \frac{\norm{\mA_k - \mM}^2}{\norm{\mM}^2} = \sum_{i=1}^n \frac{\lambda_i^{2k-2}}{\sum_j \lambda_j^{2k-2}} \left( 1 - \frac{\lambda^2_i}{\sum_j \lambda_j^2} \right). \tag{k-quality} \end{aligned}$$ For $k=2$, this expression looks quite nice and could be an assumption on $\mM$: $$\expect \frac{\norm{\mA_2 - \mM}^2}{\norm{\mM}^2} = \sum_{i=1}^n \hat \lambda_i^2 \left( 1 - \hat \lambda_i^2 \right) = 1 - \frac{\sum_{i=1}^n {\lambda_i^4}}{\left( \sum_{i=1}^n {\lambda_i^2}\right)^2}.\tag{delta-star}$$ This could be much better than $\frac{n-1}{n}$ if the spectrum of $\mM$ is not uniform. We can also see that as $k\to \infty$, ${eqnref( "k-quality" )} converges to the optimal rank-1 approximation quality $$1 - \frac{\max_i \lambda_i^2}{\sum_j \lambda_j^2}.$$ `33:T60c,texmd` ### PowerSGD *with* warm start We will now analyze how warm start can provide an improved bound. Abuse of notation: - We will only consider one specific iteration $t$ that corresponds to a right matrix multiplication power step. - We call the projection vector from the previous timestep $\qq_{t-1}$. We will treat this as a constant vector. It may be better than that, but there is not reason it should be worse! 👋 (it could be, but when?) Unrolling two time steps, we have: $$\begin{aligned} \mE_t &= \mP_t (\mI - \hat \qq_{t-1} \hat \qq_{t-1}^\top), \\ \mE_{t+1} &= (\mI - \hat \pp_t \hat \pp_t^\top) \mP_{t+1} \\ &= (\mI - \hat \pp_t \hat \pp_t^\top) \mU_{t+1} + (\mI - \hat \pp_t \hat \pp_t^\top) \mE_t \\ &= (\mI - \hat \pp_t \hat \pp_t^\top) \mU_{t+1} + (\mI - \hat \pp_t \hat \pp_t^\top) \mP_t (\mI - \hat \qq_{t-1} \hat \qq_{t-1}^\top), \\ \mP_{t+2} &= \underbrace{\mU_{t+2}}_{\norm{\cdot}^2 \leq \gamma^2\sigma^2} + \underbrace{(\mI - \hat \pp_t \hat \pp_t^\top) \mU_{t+1}}_{\norm{\cdot}^2 \leq \frac{n-1}{n}\gamma^2 \sigma^2} + \underbrace{(\mI - \hat \pp_t \hat \pp_t^\top) \mP_t}_{\norm{\cdot}^2 \leq (1-\delta^\star) \norm{\mP_{t}}^2 } \underbrace{(\mI - \hat \qq_{t-1} \hat \qq_{t-1}^\top)}_{\norm{\cdot}_\text{Spec.} \leq 1}, \\ \end{aligned}$$ where $\hat \pp_t$ is not uniform anymore: $\hat \pp_t = \frac{\mP_t \hat \qq_{t-1}}{\norm{\mP_t \hat \qq_{t-1}}}$. We can use a better contraction parameter $\delta^\star$ ${eqnref( "delta-star" )} that depends on the spectrum of $\mP_t$. `34:T838,texmd` To turn this into a bound on $\norm{\mP_t}^2$, we will first crudely bound $$ \expect \norm{\mU_{t+2} + (\mI - \hat \pp_t \hat \pp_t^\top) \mU_{t+1}}^2 \leq 4\gamma^2\sigma^2.$$ We will also bound $$\expect \norm{(\mI - \hat \pp_t \hat \pp_t^\top) \mP_t (\mI - \hat \qq_{t-1} \hat \qq_{t-1}^\top)}^2 \leq \expect \norm{(\mI - \hat \pp_t \hat \pp_t^\top) \mP_t}^2 \leq (1-\delta^\star) \expect \norm{\mP_t}^2, $$ using the fact that the spectral norm of $(\mI - \hat \qq_{t-1} \hat \qq_{t-1}^\top) \leq 1$ for the first step. Now we can use the same steps from Lemma 3 of Karimireddy et al. (2019). Praneeth tought me how to choose $\eta$ in the inequality $\norm{a+b}^2\leq (1+\eta)\norm{a}^2 + (1+1/\eta)\norm{b}^2$ 🙂: (dropping expectations 👋) $$\begin{aligned} \norm{\mP_{t+2}}^2 &\leq 4\gamma^2\sigma^2(1+1/\eta) + (1-\delta^\star) (1 + \eta) \norm{\mP_t}^2 \\ &= 4\gamma^2\sigma^2(1+1/\eta) \sum_{i=0}^{(t+2)/2} ((1-\delta^\star) (1+\eta))^i \\ &\leq 4\gamma^2\sigma^2(1+1/\eta) \sum_{i=0}^\infty ((1-\delta^\star) (1+\eta))^i \\ &= \frac{4 (1 + 1/\eta) }{1-(1-\delta^\star) (1+\eta)} \gamma^2 \sigma^2 \\ \end{aligned}$$ Setting $\eta = \frac{\delta^\star}{2(1 - \delta^\star)}$, this yields: $$ \norm{\mP_{t+2}}^2 \leq {\color{red}{8}} \gamma^2 \sigma^2 \frac{{\color{red}2} - \delta^{\color{red}\star}}{\delta^{{\color{red}\star} 2}}.$$ And this bound should amount to the same thing as a bound on $\norm{\mE_t}^2$. (Edit: I also managed to work out this inequality for the errors now.) Terms that are different from the normal bound are marked in red. The $\color{red}2-$ instead of $1-$ implies that, if we don't assume anything about $\delta$ (without star), this bound does not necessarily go to zero as $\delta^\star$ goes to 1, to recover the uncompressed rate. It's fine, because we can take the minimum of the original bound and this bound to construct a new bound. I'm getting this bound from mathematica on the frobenius norm of the error buffer:
${await FileAttachment("image.png").image()} `35:T4ee,texmd` ### Experiments Here you see that warm start helps a lot when the data lies in a small subspace. The experiment is linear least-squares regression with many inputs and many outputs. The dataset size is 1000, there is a little noise, and we run one epoch of SGD. On the $x$-axis, we vary the number of PowerSGD steps per gradient step. The 'histograms' over the $y$-axis indicate the spread of repeated experiments.

Something similar, but now changing the batch size (and the compression rank instead of number of PowerSGD steps):

`36:T596,texmd` 3rd Iteration $$ \begin{aligned} \mP_3 &= \mE_{2} + \mU_3, \\ \mE_{3} &= \mP_{3} - \mP_{3} \hat \qq_3 \hat \qq_3^\top, \\ \qq_4 &= \mP_3 \hat \qq_{3} = (\mE_{2} + \mU_3) \hat\qq_{3} \\ &= (\mP_{2} - \mP_{2} \hat \qq_2 \hat \qq_2^\top + \mU_3) \hat\qq_{3} \\ &= (\mE_{1} + \mU_2) \hat \qq_{3} - ((\mE_{1} + \mU_2)\hat \qq_2 \hat \qq_2^\top ) \hat\qq_{3} + \mU_3 \hat\qq_{3} \\ & = (\mP_{1} - \mP_{1} \hat \qq_1 \hat \qq_1^\top) \hat \qq_{3} + \mU_2 \hat \qq_{3} - (\mP_{1} - \mP_{1} \hat \qq_1 \hat \qq_1^\top) \qq_3 \hat \qq_3^\top \hat\qq_{4} - \mU_2 \qq_3 \hat \qq_3^\top \hat \qq_{4} + \mU_3 \hat\qq_{4} \\ & = \mU_{1} \hat \qq_{2} - \mU_{1} \qq_1 \hat \qq_1^\top \hat \qq_{3} + \mU_{2} \hat \qq_{3} - \mU_{1} \qq_2 \hat \qq_2^\top \hat\qq_{3} + \mU_{1} \qq_1 \hat \qq_1^\top \qq_2 \hat \qq_2^\top \hat\qq_{3} - \mU_2 \qq_2 \hat \qq_2^\top \hat \qq_{3} + \mU_3 \hat\qq_{3} \\ & = \mU_{1} (I - \hat \qq_1 \hat \qq_1^\top) (I - \hat \qq_2 \hat \qq_2 ^\top) \hat\qq_{3} + \mU_{2} (I - \hat \qq_2 \hat \qq_2^\top) \hat\qq_{3} + \mU_{3} \hat\qq_{3} \end{aligned} $$ Zero Grad Update: $$ \begin{aligned} \qq_4 &= \mU_{1} \hat \qq_{3} - \mU_{1} \qq_1 \hat \qq_1^\top \hat \qq_{3} - \mU_{1} \qq_2 \hat \qq_2^\top \hat\qq_{3} + \mU_{1} \qq_1 \hat \qq_1^\top \qq_2 \hat \qq_2^\top \hat\qq_{3}\\ & = \mU_{1} (I - \hat \qq_1 \hat \qq_1^\top) (I - \hat \qq_2 \hat \qq_2 ^\top) \hat\qq_{3} \end{aligned} $$ `37:T599,texmd` General Update: $$ \begin{aligned} \mP_t & = \mU_{1} (I - \hat \qq_0 \hat \qq_0^\top) (I - \hat \qq_1 \hat \qq_1^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top)\\ & + \mU_{2} (I - \hat \qq_1 \hat \qq_1^\top) (I - \hat \qq_2 \hat \qq_2^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \\ & + \mU_{3} (I - \hat \qq_2 \hat \qq_2^\top) (I - \hat \qq_3 \hat \qq_3^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \\ & + \dots \\ & + \mU_{t - 1} (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \\ \qq_t & = \mU_{1} (I - \hat \qq_0 \hat \qq_0^\top) (I - \hat \qq_1 \hat \qq_1^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \hat\qq_{t - 1} \\ & + \mU_{2} (I - \hat \qq_1 \hat \qq_1^\top) (I - \hat \qq_2 \hat \qq_2^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \hat\qq_{t - 1} \\ & + \mU_{3} (I - \hat \qq_2 \hat \qq_2^\top) (I - \hat \qq_3 \hat \qq_3^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \hat\qq_{t - 1} \\ & + \dots \\ & + \mU_{t - 1} (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \hat\qq_{t - 1} \end{aligned} $$ General Zero Grad Update: $$ \begin{aligned} \mP_t & = \mU_{1} (I - \hat \qq_0 \hat \qq_0^\top) (I - \hat \qq_1 \hat \qq_1^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \\ \qq_t & = \mU_{1} (I - \hat \qq_0 \hat \qq_0^\top) (I - \hat \qq_1 \hat \qq_1^\top) \dots (I - \hat \qq_{t - 2} \hat \qq_{t - 2}^\top) \hat\qq_{t - 1} \end{aligned} $$ `38:[{"id":"c63406c4e0268c5af05e39200d2ed4676120aee930c314143ca02d38e84741e81cde5fce95016942ed9ce559791e5b2afb6b00d85b93a18bc80db8fd58cb7ecc","href":"https://static.observableusercontent.com/files/c63406c4e0268c5af05e39200d2ed4676120aee930c314143ca02d38e84741e81cde5fce95016942ed9ce559791e5b2afb6b00d85b93a18bc80db8fd58cb7ecc","name":"image.png","type":"image/png","lastModified":1637937347144.172,"size":15177},{"id":"d17ac2b5db7a73a666e7bdfea7406514164e2fea24a7f83768d7d3e241f7c10db276dd57a13aec1579835ff7f63b391cd6d26cbde51c59ce3ab2c3864703fb6b","href":"https://static.observableusercontent.com/files/d17ac2b5db7a73a666e7bdfea7406514164e2fea24a7f83768d7d3e241f7c10db276dd57a13aec1579835ff7f63b391cd6d26cbde51c59ce3ab2c3864703fb6b","name":"image@1.png","type":"image/png","lastModified":1638374928190.827,"size":412280},{"id":"d5106dd5ecc45ad3f449a9cbae9dbcdbfde391cd715d560f7432ab9aa3c7b96365129d2b29186576640c65a5c13d330173d910a949b161422f8a6e0d8af28f0d","href":"https://static.observableusercontent.com/files/d5106dd5ecc45ad3f449a9cbae9dbcdbfde391cd715d560f7432ab9aa3c7b96365129d2b29186576640c65a5c13d330173d910a949b161422f8a6e0d8af28f0d","name":"d100-100classes-100dim-bs20.png","type":"image/png","lastModified":1637760943380.627,"size":120902},{"id":"ddbf6a19858f2072f3303727dfe535621e99dfcd7c4dae8ac08240021f93f5f179d62ae9c8bcc1a592575900dd4632eb854c7ccbc7873f5216a8caeefafc485d","href":"https://static.observableusercontent.com/files/ddbf6a19858f2072f3303727dfe535621e99dfcd7c4dae8ac08240021f93f5f179d62ae9c8bcc1a592575900dd4632eb854c7ccbc7873f5216a8caeefafc485d","name":"d100-100classes-10dim-bs20.png","type":"image/png","lastModified":1637760943349.288,"size":93311},{"id":"1ca59f9bfce63d381d47903e99721551f04abf155a495faea41cdb93b52d016c397c554e100adafd4cbdeb1a4ccd83d2383c238e2ef857d73c329f6bd2bc9b15","href":"https://static.observableusercontent.com/files/1ca59f9bfce63d381d47903e99721551f04abf155a495faea41cdb93b52d016c397c554e100adafd4cbdeb1a4ccd83d2383c238e2ef857d73c329f6bd2bc9b15","name":"batch-d100-100classes-100dim-bs20.png","type":"image/png","lastModified":1637761481824.59,"size":126694},{"id":"a3e325097df3dc3ebc4a0b8468baf8dc005eeb2a69a17a5a4ac5b1cde8cc1cd21779aeb10dc45cb8472265d59b1019416a0e2687bab9e600055a430ab900a53b","href":"https://static.observableusercontent.com/files/a3e325097df3dc3ebc4a0b8468baf8dc005eeb2a69a17a5a4ac5b1cde8cc1cd21779aeb10dc45cb8472265d59b1019416a0e2687bab9e600055a430ab900a53b","name":"batch-d100-100classes-100dim-bs3.png","type":"image/png","lastModified":1637761410086.669,"size":113656}] 2f:{"id":"31d2eb7e6054c1fd","slug":"powersgd-theory","title":"PowerSGD Theory - Experiments and Proposed Approach","thumbnail":"91f2b45ff8e60502fa217b6d7af4470bdd001b08f94c8e85b5cf60f5c8e9ff03","access_level":"public","create_time":"$D2021-11-24T08:11:10.575Z","update_time":"$D2023-02-07T15:00:49.747Z","view_time":null,"first_public_time":"$D2022-11-09T13:35:45.679Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"63d4ae9351b957f2","login":"tvogels","name":"Thijs Vogels","avatar_url":"https://avatars-next.observableusercontent.com/caecb0802edbb2531d0d2883357c53d701439f3641bbc772df9d728d289a6905","tier":"starter_2024"},"version":641,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7ebda7165bbc067e","login":"tvogels","name":"Thijs Vogels","avatar_url":"https://avatars-next.observableusercontent.com/caecb0802edbb2531d0d2883357c53d701439f3641bbc772df9d728d289a6905","tier":null}],"members":[{"type":"individual","id":"7ebda7165bbc067e","login":"tvogels","name":"Thijs Vogels","avatar_url":"https://avatars-next.observableusercontent.com/caecb0802edbb2531d0d2883357c53d701439f3641bbc772df9d728d289a6905","tier":null,"role":"editor"},{"type":"individual","id":"dbf75c8b02945a6c","login":"dbf75c8b02945a6c","name":"Ashkan Soleymani","avatar_url":"https://avatars-next.observableusercontent.com/68f190f34a563fcaccc323861a4f0ae2322d6aeea3e64741cff530d0139f2a62","tier":null,"role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"PowerSGD Theory - Experiments and Proposed Approach","cells":[{"id":0,"value":"# PowerSGD Theory - Experiments and Proposed Approach\n\nI spent some time this week thinking about the question ‘when is warm-start useful’ and ‘how to capture it with theory’? I'm sharing my findings in this document.\n\nThe emoji 👋 indicates ‘hand-waivy’ and ‘requires some attention’.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":172,"value":"texmd`\n### PowerSGD *without* warm start\n\nWe consider an error-feedback SGD algorithm with the following notation:\n- We use a compressor $\\cC: (n \\times n) \\to (n \\times n).$\n- Each step, we want to do an update $\\mU_t$ assumed to be bounded by $\\norm{\\mU}^2 \\leq \\gamma^2 \\sigma^2$.\n- We define $\\mP_t = \\mE_{t-1} + \\mU_t$, where $\\mE$ is the ‘error buffer’.\n- We update the error buffer as $\\mE_t = \\mP_t - \\cC(\\mP_t).$\n\nWe can analyze rank-1 PowerSGD with one power-iteration per SGD step and no-warm start easily. \nThis case amounts to random projections, and we have:\n\n$$ \\expect \\norm{\\mE_t}^2 = \\expect \\norm{\\mP_t - \\cC_\\text{rand. proj.}(\\mP_t)}^2 \\leq \\expect \\frac{n-1}{n}\\norm{\\mE_{t-1} + \\mU_t}^2. $$\n\nand we can use Lemma 3 of Karimireddy et al. (2019) to bound this to\n\n$$\\expect \\norm{\\mE_t}^2 \\leq 4n(n-1)\\gamma^2 \\sigma^2.$$\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":288,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"texmd`\n### Reasons to assume the error buffer has a peaky spectrum\n\nFor an $n \\times m$ matrix $\\mM$ of a linear layer $\\xx \\to \\yy = \\mM \\xx$, the gradient looks like: \n$$ \\frac{d\\ell}{d\\mM} = \\sum_{b \\in \\text{batch}} \\underbrace{\\frac{d\\ell}{d\\yy_b}}_{n \\times 1} \\underbrace{\\xx_b^\\top}_{1 \\times m}.$$\n\nThis gradient is expected to be low rank (easily compressible) if:\n\n- $n$ and $m$ are very different (👋)\n- The batch size is smaller than $n$ and $m$.\n- The inputs $\\xx$ to the layer lie in some linear subspace of $\\R^m$ (or almost 👋)\n- The output gradients lie in some linear subspace of $\\R^n$. In a neural net for classification this can happen (👋) if there are fewer classes than $n$.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":381,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":384,"value":"texmd`\n### To do\n- Figure out how *exactly* $\\delta^\\star$ behaves, depending on the criteria above. (Remove the 👋)\n- Study experimentally how much better $\\delta^\\star$ is than $\\delta$.\n- Argue that starting vectors won't be worse than random.\n- (=) be precise in terms of q: analyze the dynamics. Could q be very bad? Why / why not?\n- Remove randomness, just write it as assumptions on $\\qq$.\n- See if we can get a bound on $\\norm{\\mE}^2$ instead of $\\norm{\\mP}^2$ so we can replace Lemma 3 in Karimireddy et al. (2019). + Is the \"2 -\" instead of \"1 - \" bad?\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":638,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":476,"value":"md`# Adding noise to the gradients`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":474,"value":"FileAttachment(\"image@1.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":527,"value":"texmd`\n# Ashkan's new analysis idea (9 Feb 2022):\n\n## Try to split all the chains\n\nForgetting about left/ringt steps here:\n\n$$\n\\begin{aligned}\n \\mP_t &= \\mE_{t-1} + \\mU_t, \\\\\n \\mE_{t} &= \\mP_{t} - \\mP_{t} \\hat \\qq_{t-1} \\hat \\qq_{t-1}^\\top, \\\\\n \\qq_t &= \\mP_t \\hat \\qq_{t-1},\n\\end{aligned}\n$$`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":544,"value":"texmd`\n0th Iteration:\n$$\n\\begin{aligned}\n \\qq_1 &\\sim \\cN(0, I_{n\\times n}) \\\\\n \\mE_0 &= 0\n\\end{aligned}\n$$`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":542,"value":"\ntexmd`\n1st Iteration:\n$$\n\\begin{aligned}\n \\mP_{1} &= \\mU_{1}, \\\\\n \\mE_{1} &= \\mP_{1} - \\mP_{1} \\hat \\qq_1 \\hat \\qq_1^\\top, \\\\ \n \\qq_2 &= \\mP_1 \\hat \\qq_{1} = \\mU_{1} \\hat \\qq_{1},\n\\end{aligned}\n$$\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":480,"value":"texmd`\n2nd Iteration\n$$\n\\begin{aligned}\n \\mP_2 &= \\mE_{1} + \\mU_2, \\\\\n \\mE_{2} &= \\mP_{2} - \\mP_{2} \\hat \\qq_2 \\hat \\qq_2^\\top, \\\\\n \\qq_3 &= \\mP_2 \\hat \\qq_{2} = (\\mE_{1} + \\mU_2) \\hat\\qq_{2} = \\mU_{1} \\hat\\qq_{2} - \\mU_{1} \\hat \\qq_1 \\hat \\qq_1^\\top \\hat\\qq_{2} + \\mU_2 \\hat\\qq_{1}, \n\\end{aligned}\n$$\n\nZero grad Update:\n$$\n\\begin{aligned}\n \\mP_2 &= \\mE_{1}, \\\\\n \\mE_{2} &= \\mP_{2} - \\mP_{2} \\hat \\qq_2 \\hat \\qq_2^\\top, \\\\\n \\qq_3 &= \\mP_2 \\hat \\qq_{2} = \\mE_{1} \\hat\\qq_{2} = \\mU_{1} \\hat\\qq_{2} - \\mU_{1} \\hat \\qq_1 \\hat \\qq_1^\\top \\hat\\qq_{2} = \\mU_{1} (I - \\hat \\qq_1 \\hat \\qq_1^\\top) \\qq_{2}\\\\\n\\end{aligned}\n$$\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":548,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":604,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"import { texmd, eqnref, eqnupdate } from \"@tvogels/tex-utilities\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"eqnupdate","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1","titling":"auto"}} 30:"$2f:body"