<p>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.</p>

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

<p><a href="http://ttic.uchicago.edu/~shai/papers/ShalevSi07_mlj.pdf" rel="noreferrer">http://ttic.uchicago.edu/~shai/papers/ShalevSi07_mlj.pdf</a></p>

CC BY-SA 2.5
2010-08-19T21:09:12.097Z
2010-08-23T21:57:22.247Z
2010-08-23T21:57:22.247Z
Moritz
<p>The reference Moritz cited basically shows that the online learning algorithms can be seen this way too, i.e., maximizing the dual objective (of the regularized loss function) instead of minimizing the primal objective.</p>

<p>The primal-dual perspective is useful because it lets you see how the dual objective is improving with each round, how it relates to other notions used to analyze online learning algorithms (such as the minimizing the total number of mistakes), and therefore also leads to ways of designing and analyzing some new online learning algorithms.</p>

CC BY-SA 2.5
2010-08-23T21:46:45.453Z
2010-08-23T21:46:45.453Z
spinxl39
<p>It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?</p>

CC BY-SA 2.5
2010-08-19T21:00:37.030Z
It might be helpful to provide some background on what exactly the perceptron update is...
Suresh Venkat
CC BY-SA 2.5
2010-08-23T23:09:56.770Z
This question seems more suited to the data analysis site: http://stats.stackexchange.com/; or the machine learning proposal on Area51.
Shane
CC BY-SA 2.5
2010-08-23T23:12:00.200Z
Seems perfectly fine as a learning theory question which is definitely a part of theoretical computer science.
Moritz
<lg.learning><online-learning><primal-dual>
Online learning: Perceptron updates
Parasaran
# Online learning: Perceptron updates

(Asked by: username_0 on 2010-08-19)

It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?

**Tags:** lg.learning, online-learning, primal-dual
> **Comments:**
> **username_1**: It might be helpful to provide some background on what exactly the perceptron update is...  
> **username_2**: This question seems more suited to the data analysis site: http://stats.stackexchange.com/; or the machine learning proposal on Area51.  
> **username_3**: Seems perfectly fine as a learning theory question which is definitely a part of theoretical computer science.  

---

## 2 answers

### Answer by username_3 on 2010-08-19. Score: 10

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>


---

### Answer by username_4 on 2010-08-23. Score: 6

The reference Moritz cited basically shows that the online learning algorithms can be seen this way too, i.e., maximizing the dual objective (of the regularized loss function) instead of minimizing the primal objective.

The primal-dual perspective is useful because it lets you see how the dual objective is improving with each round, how it relates to other notions used to analyze online learning algorithms (such as the minimizing the total number of mistakes), and therefore also leads to ways of designing and analyzing some new online learning algorithms.


---

