3
$\begingroup$

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?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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... $\endgroup$ Mar 9 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.