A Modern Introduction to Online Learning | Hacker News Reader

A Modern Introduction to Online Learning

arxiv.org

149 pointsyarapavan13 comments

This is nice to have. The classic reference on online learning is "Prediction, Learning and Games" but it's not ML focused and it predates pretty much everything on online convex optimization. I'm looking forward to seeing a more modern introduction.

What's the difference between ML and online convex optimization? I remember presenting on the Multiplicative Weights algorithm, and someone told me not to introduce it from a learning theory perspective and instead from more of a basic theoretical CS perspective -- that part was confusing, because they seemed to me to be the same.

Take a look at https://ocobook.cs.princeton.edu/OCObook.pdf, and in particular section 1.2. The online shortest path problem is a good example of an online optimization problem that's not related to machine learning.

The title of the paper and the link here might lead people to think this is about educating oneself in the quagmire of MOOCs and the like available to us all today. It's not. Killer explanation from the first part of the paper:

"This framework is pretty powerful, and it allows to reformulate a bunch of different problems in machine learning and optimization as similar games. More in general, with the regret framework we can analyze situations in which the data are not independent and identically distributed from a distribution, yet I would like to guarantee that the algorithm is “learning” something. For example, online learning can be used to analyze

• Click prediction problems;

• Routing on a network;

• Convergence to equilibrium of repeated games.

It can also be used to analyze stochastic algorithms, e.g., Stochastic Gradient Descent, but the adversarial nature of the analysis might give you suboptimal results. For example, it can be used to analyze momentum algorithms, but the adversarial nature of the losses essentially forces you to prove a convergence guarantee that treats the momentum term as a vanishing disturbance that does not help the algorithm in any way."

Looks pretty interesting, and I'll be coming back to it as a paper, but don't head in there looking for advice on how to score that Udemy course at a deep discount! :)

I was going to say I was surprised that someone could be so narrowly specialized to not know "online learning" is a common term. On second thought, I'd say it is darn near impossible that the author of the paper never Googled "online learning" and had to scroll past hundreds of results before seeing anything related to machine learning. So, maybe the title was misleading on purpose.

Online learning is a term of art.

It's just a term of art, see also supervised learning, etc etc

As someone who has worked on online learning (the machine learning discipline), and who is young enough to have taken a few Coursera classes in high school, I must dispute your claim :)

To me, "online learning" has nothing to do with classes on the internet. I still think of those as "MOOCs". I don't think it's a stretch to say that the author wasn't aware of the other usage, as I'm certainly not.

"Online learning" is actually a pretty established term in theoretical computer science and specifically learning theory. I don't think that it's meant to be misleading at all but rather to connect the work to the extensive previous work on this subject. "Online" is used in general in theoretical computer science to describe problems where data arrives in a stream and the algorithm has to make decisions as it observes the data (e.g. before observing all the data). There are "online" versions of just about every problem in theoretical computer science. For example, there are "online traveling salesman" and "online facility location" problems both of which have published research. "Online" obviously has a different meaning outside of computer science, but it conveys a very specific meaning in the math / computer theory context. I'm not sure when this term first appeared in research, but this line of work is often traced back to the 50s with the perceptron algorithm, David Blackwell, and James Hannan.

It's getting even more difficult though because now there is a quickly growing body of research into the effectiveness of the instructional kind of online learning, including for computer science and machine learning pedagogy.

Definitely some SEO issues even in peer reviewed research databases.

'Online machine learning' would avoid the confusion. https://en.wikipedia.org/wiki/Online_machine_learning

online learning as a term might actually predate any internet-based distance courses. Famous Freund and Schapire paper goes back at least to 1997 and uses the term in the title.

> Killer explanation from the first part of the paper:

> "This framework is pretty powerful, and it allows to reformulate a bunch of different problems in machine learning and optimization as similar games.

Agreed. I am economist doing DS and the framing used in the paper makes online learning much more intuitive for me.

Reply on news.ycombinator.com