Online learning: Perceptron updates
The perceptron algorithm as such is a simple case of Gradient Descent (which is widely used for convex optimization). It minimizes a convex function (here the sum of inner products of misclassified examples with the current hypothesis) by making a step in the direction of the gradient of the convex function. As such perceptron is not necessarily an online learning algorithm.

There is however work on primal dual interpretations of online learning algorithms that seem to be relevant to you:

http://ttic.uchicago.edu/~shai/papers/ShalevSi07_mlj.pdf