Consider the following mathematical model of training a neural net : Suppose $f_{w} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a neural net whose weights are $w$. Suppose during the training the adversary is sampling $x \sim {\cal D}$ from some distribution ${\cal D}$ on $\mathbb{R}^n$ and sending in training data of the form $(x, \theta(x) + f_{w^*}(x))$ i.e the adversary is corrupting the true labels generated by $f_{w^*}$ (for some fixed $w^*$) by adding a real number to it.

Now suppose we want to have an algorithm which will use such corrupted training data as above and try to get as close to $w*$ as possible i.e despite getting data corrupted the above way the algorithm is trying to minimize (over $w$) the "original risk" $\mathbb{E}_{x \sim {\cal D}} \left [ \frac{1}{2} \left ( f_w (x) - f_{w*}(x) \right )^2 \right ]$ as best as possible.

  • Is there a real life deep-learning application which comes close to the above framework or can motivate the above algorithmic aim?
  • 1
    $\begingroup$ Assuming $\theta$ can depend on $x$, this problem is impossible to solve. For example, an adversary can choose $\theta(x) = -f_{w^*}(x)$ and thus the data point will be $(x,0)$ for every $x$ $\endgroup$ – nir shahar Feb 16 at 19:25
  • 1
    $\begingroup$ You need some sort of constraints on $\theta$ that will make sure this kind of behavior is not allowed, otherwise you wont be able to do anything. Such a constraint can be done in the extreme case by only allowing one $\theta$ for every $x$. You can have other constraints, like $\theta$ must be a normal distribution, where the adversary is allowed to choose the parameters - but it will be harder to analyze. $\endgroup$ – nir shahar Feb 16 at 19:28
  • $\begingroup$ Sure! I am in the algorithmic proof going to make assumptions on $\theta$. Mostly I am going to assume a constant bound on $\theta$ and all guarantees will be in terms of this bound. I do not want to assume any fixed distribution on $\theta$ since that makes it a noise and not an attack. With noise model this becomes a more standard question with known standard solutions. What I am looking for are references for real world usecases which can motivate such a mathematical model. $\endgroup$ – gradstudent Feb 16 at 19:31
  • $\begingroup$ Is boundness the only assumption you make? it seems not strong enough for some problems, however in such problems your loss will still be small - the problems that are entirely contained in the bounds you have will have the same attack. Since they are bounded, a constant function that returns any value within the bounds will not be too far away from the actual function you are learning. This however probably does not sound like something you would want, even though it can work. $\endgroup$ – nir shahar Feb 16 at 19:37
  • $\begingroup$ Assuming the bound is small enough (and significantly smaller than the actual ranges the function can get), I think you should look at the LWE (Learning With Errors) problem, since (if I remember correctly) it gives a similar model to what you are describing. $\endgroup$ – nir shahar Feb 16 at 19:39

Your Answer

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

Browse other questions tagged or ask your own question.