<p>How about the simple squared loss function used in linear regression? That is, let <span class="math-container">$\ell(w(t), z) = \frac{1}{2n} \sum_{i=1}^n (z_i^\top w(t) - y_i)^2$</span> for data vectors <span class="math-container">$z_i \in \mathbb{R}^d$</span> and <span class="math-container">$y\in \mathbb{R}^n$</span>?</p>
<p>For the sake of this answer, I'll use the shorthand notation <span class="math-container">$Z \in \mathbb{R}^{d\times n}$</span>, where each column of <span class="math-container">$Z$</span> is the vector <span class="math-container">$z_i \in \mathbb{R}^d$</span>.</p>
<p>If you use this as the loss function, then the given differential equation is <span class="math-container">$$\frac{dw(t)}{dt} = -\eta (ZZ^\top) w(t) + Z y.$$</span> I think this can be solved to get the solution you seek, and I explain below.</p>
<p>Suppose <span class="math-container">$Z$</span> is rank-<span class="math-container">$n$</span>, and let <span class="math-container">$Z = \sum_{i = 1}^n s_i u_i v_i^\top$</span> be its singular value decomposition. Pre-multiplying the given ODE with any of the <span class="math-container">$u_i$</span> vectors yields the ODE <span class="math-container">$$ \frac{d}{dt} (u_i^\top w(t)) = - \frac{1}{n} s_i^2 u_i^\top w(t) + \frac{1}{n} s_i v_i^\top y.$$</span> This is a standard first-order constant coefficient ODE and can be solved  by, for instance, the method of integrating factors. Applying this technique gives <span class="math-container">$$ u_i^\top w(t) = \frac{1}{s_i} v_i^\top y + c_i (\frac{s_i}{n} v_i^\top y) e^{-\frac{s_i^2 t}{n}}, $$</span> where <span class="math-container">$c_i$</span> is a constant of integration. If you are given an initial condition, you can use it to obtain <span class="math-container">$c_i$</span>. Suppose you have <span class="math-container">$w_0 = 0$</span>. Then, this initial condition results in the rule <span class="math-container">$$u_i^\top w(t) = \frac{1}{s_i} (v_i^\top y) (1 - e^{-s_i^2 t/ n}), $$</span> for all <span class="math-container">$i \in [n]$</span>. Therefore, as <span class="math-container">$t\rightarrow \infty$</span>, we have for all <span class="math-container">$i \in [n]$</span> that <span class="math-container">$u_i^\top w(t) \rightarrow \frac{1}{s_i} v_i^\top y$</span>. This means the loss <span class="math-container">$\ell(w_t, z) \rightarrow 0$</span>, as you require.</p>

CC BY-SA 4.0
2021-03-09T08:23:07.290Z
Thanks :) By "non-trivial" I really meant that the predictor not be a linear function in the weights that one is training over. I think I can construct also an example where the predictor is a quadratic function of the weights but thats about it. And even with quadratics I am not sure that I can deal with say a predictor of the kind, $f(\vec{w},\vec{z}) = \langle \vec{w}, \vec{z} \rangle ^2$. This already looks unclear to me...
gradstudent
CC BY-SA 4.0
2021-03-01T17:20:17.913Z
2021-03-01T21:15:26.057Z
2021-03-01T21:15:26.057Z
walkerbacker
<p>If <span class="math-container">$\ell (\vec{w}, \vec{z})$</span> is the loss function at weights <span class="math-container">$\vec{w}$</span> and for data <span class="math-container">$\vec{z}$</span> then corresponding to a distribution <span class="math-container">${\cal D}$</span> we can consider doing gradient flow with step-length <span class="math-container">$\eta &gt;0$</span> to solve the corresponding risk minimization question,</p>
<p><span class="math-container">$$\frac{d \vec{w}}{dt} = -\eta \cdot \frac{\partial }{\partial \vec{w}} \mathbb{E}_{\vec{z} \sim {\cal D}} [\ell (\vec{w}, \vec{z}) ]$$</span></p>
<ul>
<li>Are there non-trivial examples of this for which the above ODE is exactly integrable and the risk gets minimized as <span class="math-container">$t \rightarrow \infty$</span> along the solution?</li>
</ul>

<machine-learning><lg.learning><st.statistics>
Examples of learning via exactly integrable gradient flows
gradstudent
# Examples of learning via exactly integrable gradient flows

(Asked by: username_0 on 2021-02-26)

If $\ell (\vec{w}, \vec{z})$ is the loss function at weights $\vec{w}$ and for data $\vec{z}$ then corresponding to a distribution ${\cal D}$ we can consider doing gradient flow with step-length $\eta >0$ to solve the corresponding risk minimization question,

$$\frac{d \vec{w}}{dt} = -\eta \cdot \frac{\partial }{\partial \vec{w}} \mathbb{E}\_{\vec{z} \sim {\cal D}} [\ell (\vec{w}, \vec{z}) ]$$

* Are there non-trivial examples of this for which the above ODE is exactly integrable and the risk gets minimized as $t \rightarrow \infty$ along the solution?

**Tags:** machine-learning, lg.learning, st.statistics


---

## 1 answers

### Answer by username_1 on 2021-03-01. Score: 1

How about the simple squared loss function used in linear regression? That is, let $\ell(w(t), z) = \frac{1}{2n} \sum\_{i=1}^n (z\_i^\top w(t) - y\_i)^2$ for data vectors $z\_i \in \mathbb{R}^d$ and $y\in \mathbb{R}^n$?

For the sake of this answer, I'll use the shorthand notation $Z \in \mathbb{R}^{d\times n}$, where each column of $Z$ is the vector $z\_i \in \mathbb{R}^d$.

If you use this as the loss function, then the given differential equation is $$\frac{dw(t)}{dt} = -\eta (ZZ^\top) w(t) + Z y.$$ I think this can be solved to get the solution you seek, and I explain below.

Suppose $Z$ is rank-$n$, and let $Z = \sum\_{i = 1}^n s\_i u\_i v\_i^\top$ be its singular value decomposition. Pre-multiplying the given ODE with any of the $u\_i$ vectors yields the ODE $$ \frac{d}{dt} (u\_i^\top w(t)) = - \frac{1}{n} s\_i^2 u\_i^\top w(t) + \frac{1}{n} s\_i v\_i^\top y.$$ This is a standard first-order constant coefficient ODE and can be solved by, for instance, the method of integrating factors. Applying this technique gives $$ u\_i^\top w(t) = \frac{1}{s\_i} v\_i^\top y + c\_i (\frac{s\_i}{n} v\_i^\top y) e^{-\frac{s\_i^2 t}{n}}, $$ where $c\_i$ is a constant of integration. If you are given an initial condition, you can use it to obtain $c\_i$. Suppose you have $w\_0 = 0$. Then, this initial condition results in the rule $$u\_i^\top w(t) = \frac{1}{s\_i} (v\_i^\top y) (1 - e^{-s\_i^2 t/ n}), $$ for all $i \in [n]$. Therefore, as $t\rightarrow \infty$, we have for all $i \in [n]$ that $u\_i^\top w(t) \rightarrow \frac{1}{s\_i} v\_i^\top y$. This means the loss $\ell(w\_t, z) \rightarrow 0$, as you require.

> **Comments:**
> **username_0**: Thanks :) By "non-trivial" I really meant that the predictor not be a linear function in the weights that one is training over. I think I can construct also an example where the predictor is a quadratic function of the weights but thats about it. And even with quadratics I am not sure that I can deal with say a predictor of the kind, $f(\vec{w},\vec{z}) = \langle \vec{w}, \vec{z} \rangle ^2$. This already looks unclear to me...  

---

