A triple (x, y, z) is said to be a violation in training scenario S = D, Φ, C with respect to weight vector w if (x, y, z) ∈ C and w • ∆Φ(x, y, z) ≤ 0.
intuitively, this means model w is possible to mislabel example x (though not necessarily to z) since y is not its single highest scoring label under w. z ∈ Y(x) and z = y, so This lemma basically says exact search guarantees violation in each update, but as we will see in the convergence proof, violation itself is more fundamental than search exactness.