In line 7 (now line 8) of Algorithm 1, the formulation for calculating \hat{y} in the subgradient was mixed incorrectly with the predicted label \tilde{y}.

A correct formulation for \hat{y} would be the following:
\hat{y}_t=\argmax{y \not= y_t}\ \bbarw_t \cdot \bar{\phi}(\bx_t,y)