Online Learning Algorithms

Online Learning

Online learning provide an efficient solution for large-scale problems in modern applications.

The learning framework for online algorithms is in stark contrast to the PAC learning or stochastic models.

• Instead of learning from a training set and then testing on a test set, the online learning scenario mixes the training and test phases
• PAC learning follows the key assumption that the distribution over data points is fixed over time, both for training and test points, and that points are sampled in an i.i.d. fasion

Online Learning Framework

Online learning framework is very intuitive and simple:

• for
  • receive question
  • predict
  • receive true answer
  • suffer loss

There is no statisical assumption regrading the origin of the sequence of examples it could be adversarially adaptive to the learner's own behavior. How to measure the behavior of the algorithm:

Hope , it means that grows sub-linearly.

References

[1]

@book{mohri2018foundations, title={Foundations of machine learning}, author={Mohri, Mehryar and Rostamizadeh, Afshin and Talwalkar, Ameet}, year={2018} }

[2] https://www.youtube.com/watch?v=e37nlms7Zi0

[3] https://stats.stackexchange.com/questions/142906/what-does-pac-learning-theory-mean