If I have $n$ training observations, $m$ number of features per observation, and my neural network has $x$ neurons in the 1st layer, $y$ neurons in the 2nd layer, and 1 output neuron, what is the runtime of finding the parameters for my neural network? Using backpropagation? Using the best algorithm out there to do so?

I've looked over a lot of places on the Internet and can't seem to find anyone who's done a derivation of this. I'm very certain it's lower bounded by $O(mf)$ but I don't know how to incorporate $x$ or $y$. I'm asking this because I have a dataset of a certain size I want to try to apply neural nets to, and I'm trying to find a sense of if my dataset is too big for it.

  • 2
    $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. When posting a question, make sure to give enough context, and show how you tried to answer it on your own, so as to be very precise regarding your problem, and what is the difficulty you encounter. This helps better answers. $\endgroup$ – babou Aug 12 '15 at 0:00
  • 1
    $\begingroup$ What research have you done? What self-study have you done? What are your thoughts? We expect you to do a significant amount of research and self-study before asking, and to show us in the question what you've tried. As it stands it is not clear what your specific confusion is. What is the best answer you know of? What's the best you could come up with? It will likely depend upon the training procedure. Are you using auto encoders to train each layer, one layer at a time? $\endgroup$ – D.W. Aug 12 '15 at 0:49
  • 2
    $\begingroup$ The difficult part here is estimating how many iterations are needed for the weights to converge. It depends on your convergence criterion, naturally. $\endgroup$ – Yuval Filmus Aug 13 '15 at 18:10
  • $\begingroup$ in machine-learning its more about if the algorithm can find features in the data to leverage, ie converge/ learn, and less about performance of the learning algorithm. complexity of learning algorithms is not analyzed all that much, nor can it be because its data-dependent. $\endgroup$ – vzn Aug 13 '15 at 23:19

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.