- How is it possible to 'estimate' [...] the parameters when no. of parameters (P) > no. of data points (K). [...]
What your optimizer does it iteratively "improves" the parameters in such way that minimizes the loss. You usually start with randomly initialized parameters, then the optimizer makes a suggestion on how they could be changed so that the loss decreases. Next, you compute the loss given new parameter values and use this to correct the current parameters, etc.
I'm purposefully not going into technical details in here, because there is many different optimizers, that achieve their objective in different ways. Optimizer takes a function and tries it's best with finding the best parameters to minimize the function. It doesn't matter what the function is, so also what your data is. In fact, common strategy with building neural networks is first training them with single sample, or a bunch of samples, just to see if they could learn anything.
- Is it not wise to only use a NN configuration (no. of hidden layers and nodes in each hidden layer) that has P<K so that we don't apply any
regularization technique and get an accurate and simple NN.
Yes, but actually no. The common wisdom in machine learning is that there is a bias-variance trade-off, so models start overfitting with growing complexity. The more complicated your model is, the more complicated patterns it can learn, but at some point it would be able to memorize the data and fit perfectly to train set, but not the unseen test set. This is what you would read in many textbooks, however there are some recent results showing that for neural networks and some other models, we can have models with $P \gg K$ that perform better then the smaller models. There is no good explanation for that, but the hypothesis is that huge models can self-regularize.
Also, if you want to have simple and robust model, you would usually not use a neural network. Neural networks start flourishing when you have a lot of data, and usually many parameters, what makes them flexible. Of course, if you have thousands of samples, then your network would have much less parameters then the datapoints, since bigger network would not fit your RAM.
- One of the main reasons for Q2 is that certain metrics such as AIC penalize a complex model with larger number of parameters than an
equally good model with fewer parameters. So if we want to apply AIC
to compare different ML models, a deep NN would always be penalized
heavily and wont be recommended by AIC?
AIC assumes that the model with less parameters is "better" by definition. So yes, choosing to penalize number of parameters is more harsh for models that have more parameters.
Notice however that AIC is not the "one size fits all" criteria. For example, say that you have two models, regular multivariate regression and regularized multivariate regression with LASSO penalty. Say that they both have same number of parameters, but should they have same penalty for the number of parameters? The answer is no, because LASSO can shrink some parameters to zeros, so they will not be participating in the final solution, and the regularized model has much less active parameters. Same applies to other models. The take away message is that number of parameters does not have to reflect the model complexity. It gets even more complicated with neural networks, where the parameters interact with each other, you have things like re-used parameters (convolutional, or RNN networks), or network layers with no parameters et all (pooling layers, skip connections), etc., so it is hard to say what to count.
