2
$\begingroup$

One of the discussed nice aspects of the procedure that Vowpal Wabbit uses for updates to sgd pdf is so-called weight invariance, described in the linked as:

"Among these updates we mainly focus on a novel set of updates that satisfies an additional invariance property: for all importance weights of h, the update is equivalent to two updates with importance weight h/2. We call these updates importance invariant."

What does this mean and why is it useful?

$\endgroup$
2
$\begingroup$

Often different data samples have different weighting ( eg the costs of misclassification error for one group of data is higher than for other classes). Most error metrics are of the form $\sum_i e_i$ where e_i is the loss ( eg squared error) on data point $i$. Therefore weightings of the form $\sum_i w_i e_i$ are equivalent to duplicating the data w_i times (eg for w_i integer).

One simple case is if you have repeated data - rather than keeping all the duplicated data points, you just "weight" your one repeated sample by the number of instances.

Now whilst this is easy to do in a batch setting, it is hard in vowpal wabbits online big data setting: given that you have a large data set, you do not just want to represent the data n times to deal with the weighting ( because it increases your computational load). Similarly, just multiplying the gradient vector by the weighting - which is correct in batch gradient descent - will cause big problems for stochastic/online gradient descent: essentially you shoot off in one direction ( think of large integer weights) then you shoot off in the other - causing significant instability. SGD essentially relies on all the errors to be of roughly the same order ( so that the learning rate can be set appropriately). So what they propose is to ensure that the update for training sample x_i with weight n is equivalent to presenting training sample x_i n times consecutively.

The idea being that presenting it consecutively reduces the problem because the error gradient (for that single example $x_i$) reduces for each consecutive presentation and update (as you get closer & closer to the minimum for that specific example). In other words the consecutive updates provides a kind of feedback control.

To me it sounds like you would still have instabilities (you get to zero error on x_i, then you get to zero error on x_i+1,...). the learning rate will need to be adjusted to take into account the size of the weights.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this response. I am still a tad confused: 1) About consecutive updates - why is this better than seeing the same observation the same number of times, but out of order? and 2) I dont get the phrase used regarding "for all importance weights of h, the update is equivalent to two updates with importance weight h=2". It seems like what is important is that the process is equivalent to h updates with weight =1. $\endgroup$ – B_Miner Oct 1 '14 at 17:24
  • $\begingroup$ consecutive updates- its not that its better ( it isn't), but that it doesn't fit in the online "memory-less" setting of vowpal-wabbit ( in order to reorder the data you need to store the data). second is a typo? In the abstract it says: "that updating twice with importance weight h is equivalent to updating once with importance weight 2h" $\endgroup$ – seanv507 Oct 1 '14 at 17:34
  • $\begingroup$ Sorry, I read your response: "The idea being that presenting it consecutively reduces the problem because the error gradient... " as saying that if you were relying on adding a record with weight n, n times (with weight 1), ignoring the computational burden, it was better to present the record to the algorithm n-times consecutively. So, this was the "goal" VW is trying to achieve, but with something equivalent that only requires a record to be present 1 times in the data. $\endgroup$ – B_Miner Oct 1 '14 at 18:22
  • $\begingroup$ Regarding the typo, YES, seems I should have typed "...h/2". I changed the question. This is stated in this fashion the way you added in the comment and as the question now states, later in the paper. Even with this new wording, I fail to see what the point it...likely obvious, I am just not latching onto it yet. $\endgroup$ – B_Miner Oct 1 '14 at 18:26
  • 1
    $\begingroup$ yes that's right $\endgroup$ – seanv507 Feb 8 '15 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.