Csdrhrt

EDIT: Thanks to the first answer I'm lighting some assumptions:

I'm trying to understand the basics of machine learning, and I have this theoretical question:

I have a one layer linear neural network $ f: mathbb{R}^d rightarrow mathbb{R}^2 $ and two classes to learn, hence we are talking about binary classification.

Assume that, during training, I just show my network datapoints sampled from a simple distribution $D$ which lies on a circle with radius $r$ and nothing else. Furthermore, let's assume that these points all have the same label $0$. After training with S.G.D, I want my network to perform well just on this circle, I don't care how does it behave on data sampled outside (I assume it would be close to random classification, since it only sees data from inside this circle).

How many iterations will SGD need in order to converge to a good local minimum?

How can I prove it?

My intuition is that the algorithm should be rather fast, since a function which would achieve 100% accuracy is very simple: it's the boundary of the circle itself, so we just need the network to approximate any closed curve around it and output $0$ for every point inside it. But I may be wrong.

Thank you very much!

This question cannot be answered. There are several issues with it that you need to be more precise about:

1. To achieve zero training error that means that the data is perfectly described by your network. This isn't unreasonable to assume that a data set could be made this way, since after all neural networks (as you've defined them) are really just cascades of function composition. In order to get zero training error, you simply need to take your neural network, completely untrained, and use it to generate your training set. Immediately you'll get zero training error.




2. Presuming that you didn't want to do that, then it would depend way too strongly on the data itself, and therein lies the major issue with this question - if you knew how many neurons you needed to get zero training error, then you'd already know enough about the data to not need to learn anything about it. Zero training error means that you can generate a perfect neural network to describe the (training) data. If you could do that in the first place, then you'd know so much about your data that learning is pointless.

I think you need to re-frame your question to be a lot more specific, and more possible. Also, there is in general no way to know before training how good your training error will be. This is the same as point 2 above - if you knew that you could get your training error down to X with your particular neural network, then you'd already know enough about your data to not need to learn from it.