Smoothed analysis was first proposed in [1]} as a way to explain the success of the simplex algorithm of [2]} by combining the polynomial time bounds of an average-case analysis with the verisimilitude of a worst-case analysis. Since then, smoothed analysis has been applied to explain the empirical success of many algorithms [3]}. In the learning setting, [4]} proposed smoothed adversaries and proved regret bounds for linear thresholds in \(\mathbb {R}^d\) ; their proof, however, was nonconstructive and did not achieve logarithmic regret in the realizable setting. The use of smoothed adversaries was essential due to the hardness results discussed above. In a series of works [5]}, [6]} generalized [4]} and showed the regret depending on the VC dimension was possible in the smoothed online learning setting, albeit with computationally inefficient algorithms.
