4
$\begingroup$

Let’s say I have a neural net doing classification and I’m doing stochastic gradient descent to train it. If I know that my current approximation is a decent approximation, can I conclude that my gradient is a decent approximation of the gradient of the true classifier everywhere?

Specifically, suppose that I have a true loss function, $f$, and an estimation of it, $f_k$. Is it the case that there exists a $c$ (dependent on $f_k$) such that for all $x$ and $\epsilon > 0$ if $|f(x)-f_k(x)|<\epsilon$ then $|\nabla f(x) - \nabla f_k(x)|<c\epsilon$? This isn’t true for general functions, but it may be true for neural nets. If this exact statement isn’t true, is there something along these lines that is? What if we place some restrictions on the NN?

The goal I have in mind is that I’m trying to figure out how to calculate how long I can use a particular sample to estimate the gradient without the error getting too bad. If I am in a context where resampling is costly, it may be worth reusing the same sample many times as long as I’m not making my error too large. My long-term goal is to come up with a bound on how much error I have if I use the same sample $k$ times, which doesn’t seem to be something in the literature as far as I’ve found.

$\endgroup$
5
$\begingroup$

In general $|f(x) - f_k(x)| \leq \epsilon$ doesn't ensure $|\nabla f(x) - \nabla f_k(x)| \leq c\epsilon$. And for neural networks there is no reason to believe it will happen either.

You can also look at Sobolev Training Paper (https://arxiv.org/abs/1706.04859). In particular, note that Sobolev training was better than critic training, which indirectly may indicate approximating function may not be the same as approximating gradient and function. In Sobolev training, the network is trained to match gradient and function whereas in critic training network is trained to match function. They produce quite different results which might give us some hints about the above problem.

In general, if two functions are arbitrary close, they might not be close in gradients.

Edit: (Trying to come up with a negative example) Consider $f(x) = g(x) + \epsilon \sin (\frac {kx} {\epsilon}) $. $g(x)$ is some neural network. Now, we train some another neural network $h(x)$ to fit $f(x)$ and after training we get $h(x) = g(x)$ ($h(x)$ and $g(x)$ have same weights precisely). However, $\nabla f_x =\nabla g_x + k\cos (\frac {kx} {\epsilon})$ is not arbitarariy close $\nabla g_x$.

I hope this example is enough to prove that a neural network that nicely approximates the function may not nicely approximate the gradients and no such result can be proved mathematically rigorously. However, considering the paper in the discussion, you might think for practical purposes it works. However, if you have both function and grad information available that is expected to work better.

$\endgroup$
  • $\begingroup$ I’m not sure I buy that the linked paper is evidence the way you are saying. Can you elaborate on why you think that the linked paper indicates that approximating a gradient and approximating a gradient might not be the same thing? $\endgroup$ – Stella Biderman Sep 22 '18 at 4:23
  • $\begingroup$ I updated the answer more, lets see if that makes my point clear? $\endgroup$ – Umang Gupta Sep 22 '18 at 5:38
  • $\begingroup$ Why do you claim that they produce quite different results? The numbers in Figure 1 are actually quite close together. The most they differ by across all the tested data sets is $0.8\%$! $\endgroup$ – Stella Biderman Sep 22 '18 at 13:05
  • $\begingroup$ Yes, but it is a significant difference and tells us that the two things are different. Yes you need approximation in "deep-learning" sense it is fine, but you still can't prove the strict $\epsilon$ relationship as mentioned above. $\endgroup$ – Umang Gupta Sep 22 '18 at 17:28
  • 1
    $\begingroup$ I don’t see how the results in the paper disqualifies the hypothesis that the very small (but statistically significant) difference just be explained as that in fact they are doing more-or-less the same thing, conceptually, except that the critic training doesn’t make full use of the gradient bounds that it implicitly obtains? The results tell us that explicitly training on the gradient produces a very small gain. That seems to imply to me that the information in the gradient is “already known by the critic” by and large, just not utilized to the best of its ability. $\endgroup$ – Stella Biderman Sep 22 '18 at 17:34

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.