Online Learning Perceptron Mistake Bound
Consider the modification of Perceptron algorithm with the following update rule: $$ w_t+1 ← w_t + η_ty_tx_t $$ whenever $\hat{y_t } \neq y_t$ ($w_t+1 ← w_t$ otherwise).for $η_t = 1 /\sqrt{t}$ i need to prove that the bound of mistake number is $$4/γ *\log^2(1/γ)$$ can for simplicity assume $ ∥x_t∥ = 1 $for all t. and the algorithm makes M mistakes at the first M rounds, after which it has no mistakes.
my try first i notice that the following can be written as $w_i = -\sum^{i-1}_{j=1}\frac{1}{\sqrt{t}}x_i$ and i proved that for some m3 $$\sum^{m}_{j=1}\frac{1}{\sqrt{t}} \leq 2\sqrt{M}-1 $$ After M mistakes: $w_{M}w^* \geq \sum^M_{t=1}\frac{\gamma}{\sqrt{t}}$.\
now $||x_t||_2^2$ upper bounded same as perceptron after m iteration$||x_t||_2^2\leq M$ $$\gamma\sum^M_{t=1}\frac{1}{\sqrt{t}} \leq w_tw^* \leq ||x_t||_2 \leq \sqrt{M}$$ but I'm kind of struggle to generate such m that lead to the following bound, and not relay sure how can i bound this kind of vector, to be honest I'm kind of new to machine learning su maybe I'm not going in the right way here...
Topic perceptron online-learning machine-learning
Category Data Science