WNGrad

Inspired by unit-sphere weight normalization where orthogonal tangent steps satisfy ||v_{k+1}||_2^2 = ||v_k||_2^2 + (eta^2 / ||v_k||_2^2) ||P_{v_k^perp}(nabla f)||_2^2 (Equation 4), WNGrad updates the inverse step size via b_{k+1} = b_k + ||g_k||_2^2 / b_k (so b_{k+1}^2 = b_k^2 + 2 ||g_k||_2^2 + ||g_k||_2^4 / b_k^2 without square roots) and is strictly invariant to objective rescaling f -> lambda f when b_1 = C ||nabla f(x_1)||_2 (Remark 2.2).

For L-smooth non-convex functions in the batch setting with b_1 = delta L >= ||nabla f(x_1)||_2, Lemmas 2.4-2.6 and Theorem 2.3 prove that if b_k crosses L at step k_0 then b_{k_0} <= 3L + 2L^2 / b_1 and b_k stabilizes bounded above by b_{k_0} + 8(f(x_{k_0}) - f^*) for all k >= k_0, reaching min_{k<=T} ||nabla f(x_k)||_2^2 <= epsilon in O(1/epsilon) steps; in the stochastic convex setting with E||g_k||_2^2 <= G^2 and ||g_k||_2 >= gamma, Lemma 3.3 and Theorem 3.1 prove b_k >= gamma sqrt(k) and E[f(x_bar_k) - f^*] <= G^2 (D^2 + 2) / (gamma sqrt(k)) + b_1 ||x_1 - x^*||_2^2 / (2k).

Applied with one inverse step-size accumulator b_j per neuron across two-layer MLPs on MNIST, five-layer CNNs on CIFAR-10, and (via WNGrad-Momentum and WN-Adam, Algorithm 4) ResNet-18 on CIFAR-10, WNGrad remains stable across four orders of magnitude of initial learning-rate / Lipschitz scale lambda in [10^{-4}, 10^1] where standard SGD and Adam diverge.

Because b_k is monotonically non-decreasing, an extremely small initialization b_1 = delta L << L causes a large initial transient bound O(L^2 / (delta^2 epsilon)) in Theorem 2.3 Case 2 before b_k reaches L, and in non-stationary deep learning tasks b_k cannot increase the effective learning rate 1/b_k once accumulated.