I was wondering what percentage of Machine Learning Algorithms are iterative in nature; i.e. I can run them sequentially, on different set of data and the model refines itself. Are there any algorithms which support this mathematically, moreover, is there some tradeoff in runtime or accuracy of these models.
Iteration here not to be confused with : What does iteration in Machine Learning mean?
what percentage of Machine Learning Algorithms are iterative in nature; i.e. I can run them sequentially
from deep learning book ch5, SGD
A recurring problem in machine learning is that large training sets are necessary for good generalization, but large training sets are also more computationally expensive.
Prior to the advent of deep learning, the main way to learn nonlinear models was to use the kernel trick in combination with a linear model. Many kernel learning algorithms require constructing an m×m matrix. Constructing this matrix has computational cost O(m^2), which is clearly undesirable for datasets with billions of examples.
Gradient descent, in general, has often been regarded as slow or unreliable. In the past, the application of gradient descent to non-convex optimization problems was regarded as foolhardy or unprincipled, The optimization algorithm may not be guaranteed to arrive at even a local minimum in a reasonable amount of time, but it often finds a very low value of the cost function quickly enough to be useful
Gradient Descent-based methods, the basic premise is that you estimate the gradient based on a random small set of the training data (batch) and update the weights accordingly, the algorithm will iteratively keep alternating between the two steps until some objective has been satisfied (find a good local minima in the parameter space), the procedure is called stochastic gradient descent (The insight of SGD is that the gradient is an expectation. The expectation may be approximately estimated using a small set of samples).
In the extreme case, the gradient is estimated based on one single example, (online learning)
see Practical Recommendations for Gradient-Based Training of Deep
Architectures
is there some tradeoff in runtime or accuracy of these models
For a fixed model size, the cost per SGD update does not depend on the training set size m. In practice, we often use a larger model as the training set size increases, but we are not forced to do so. The number of updates required to reach convergence usually increases with training set size. However, as m approaches infinity, the model will eventually converge to its best possible test error before SGD has sampled every example in the training set. Increasing m further will not extend the amount of training time needed to reach the model’s best possible test error. From this point of view, one can argue that the asymptotic cost of training a model with SGD is O(1) as a function of m.
