What is the difference between offline and online learning? Is it just a matter of learning over the entire dataset (offline) vs. learning incrementally (one instance at a time)? What are examples of algorithms used in both?
Online learning means that you are doing it as the data comes in. Offline means that you have a static dataset.
So, for online learning, you (typically) have more data, but you have time constraints. Another wrinkle that can affect online learning is that your concepts might change through time.
Let's say you want to build a classifier to recognize spam. You can acquire a large corpus of e-mail, label it, and train a classifier on it. This would be offline learning. Or, you can take all the e-mail coming into your system, and continuously update your classifier (labels may be a bit tricky). This would be online learning.
The term "online" is overloaded, and therefore causes confusion in the domain of machine learning.
The opposite of "online" is batch learning. In batch learning, the learning algorithm updates its parameters after consuming the whole batch, whereas in online learning, the algorithm updates its parameters after learning from 1 training instance. Mini batch learning is the halfway point between batch learning on one end and online learning on the other extreme.
Also, "when" the data comes in, or whether it is capable of being stored or not, is orthogonal to online or batch learning.
Online learning is deemed to be slower to converge to a minima , when compared to batch learning. However, in cases where the entire dataset doesn't fit in memory, using online learning is an acceptable tradeoff.
Online learning (also called incremental learning): we consider a single presentation of the examples. In this case, each example is used sequentially in a manner as prescribed by the learning algorithm, and then thrown away. The weight changes made at a given stage depend specifically only on the (current) example being presented and possibly on the current state of the model. It is the natural procedure for time varying rules where the examples might not be available at all at once.
Offline learning: the weight changes depend on the whole (training) dataset, defining a global cost function. The examples are used repeatedly until minimization of this cost function is achieved.