5
$\begingroup$

Can anyone see how to get a tight upper bound for the function defined in terms of the inverse Laplace transform below? $$g_\text{sgd}(t)=\mathcal{L}^{-1}\left[\left(\frac{s}{2}+\frac{5 \sqrt{\frac{2}{3}} \sqrt{s}}{2 \tan ^{-1}\left(\frac{\sqrt{\frac{2}{3}}}{\sqrt{s}}\right)}\right)^{-1}\right].$$

Dieter Kadelka's numerical simulation suggests $g_\text{sgd}(t)\approx 0.434 t^{-\frac{1}{2}}$, which appears to model this function very well...where does $O(t^{-\frac{1}{2}})$ form come from?

enter image description here Notebook

This function describes loss trajectory for stochastic gradient descent (SGD) on a linear least squares problem with covariance eigenvalues $1,\frac{1}{4},\frac{1}{9},\dotsc$. Expression comes when treating SGD as a continuous time problem which requires solving a particular differential equation

$\endgroup$
7
  • $\begingroup$ Looks like $s \to g_{sgd}(s)∗\sqrt s$ is increasing and $\lim_{s \to \infty} g_{sgd}(s)∗\sqrt s$ about 0.433. $\endgroup$ Commented May 10, 2023 at 22:36
  • $\begingroup$ Why do you not calculate $g_{sgd}$ with numerical methods directly, as mentioned in the above link "a particular"? Wolfram Notebook should do it. The resulting function looks similar as that of $g_{gd}$ and in particular $g_{sgd}(0.1)=0.3272708709647729$ and $g_{sgd}(20)=0.095291845071114367$ Is the upper bound for theoretical purposes? (Calculations done with my program). $\endgroup$ Commented May 10, 2023 at 22:45
  • $\begingroup$ Yes, for theoretical purposes. Proving bounds on the limit in your comment would be a very nice result. This would show that SGD stays within a small constant factor of GD for this problem, ie, that it has the same "convergence rate" $\endgroup$ Commented May 11, 2023 at 6:17
  • 1
    $\begingroup$ @DieterKadelka btw, the 0.433 constant appears to be $\sqrt{\frac{3\pi}{50}}$ $\endgroup$ Commented May 11, 2023 at 13:20
  • $\begingroup$ Seems to be correct. I got $g_{gsd}(1e10)*1e5 = 0.434160752718722$. And for $s=1e20$ the difference is $-1.665..10^{-16}$. How did you identify this constant? Very interestingly. $\endgroup$ Commented May 11, 2023 at 16:25

1 Answer 1

3
$\begingroup$

Partial answer. If $g$ is known to be a non-negative function, Karameta Tauberian theorem relates the behavior of $G = \int_0^\cdot g$ at infinity (resp. at 0) to the behavior of $\mathcal{L}g$ at $0$ (resp. at infinity). Reference: William Feller's book Probability.

In particular, $G(t) \sim 2ct^{1/2}$ as $t \to \infty$ if and only if $\mathcal{L}g(s) \sim \Gamma(1/2)c s^{-1/2}$ as $s \to 0$.

From $G(t) \sim 2ct^{1/2}$ as $t \to \infty$, one needs regularity assumptions on $g$ to derive $g(t) \sim ct^{-1/2}$ as $t \to \infty$, Assuming that $g$ is non-increasing is sufficient.

Indeed, if $g$ is non-increasing, then for all $r \in~]0,1[$ and $t>0$, $$\frac{G(t)-G(t-rt)}{rt} \ge g(t) \ge \frac{G(t+rt)-G(t)}{rt}.$$ $$\frac{2ct^{1/2}-2c(t-rt)^{1/2}+O(t^{1/2})}{rt^{1/2}} \ge t^{1/2}g(t) \ge \frac{2c(t+rt)^{1/2}-2ct^{1/2}+O(t^{1/2})}{rt^{1/2}}.$$ $$\frac{2c-2c(1-r)^{1/2}}{r} \ge \limsup_{t \to \infty} t^{1/2}g(t) \ge \liminf_{t \to \infty} t^{1/2}g(t) \ge \frac{2c(1+r)^{1/2}-2c}{r}.$$ Letting $r$ go to $0$ yields $$\lim_{t \to \infty} t^{1/2}g(t) = c.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .