Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling
This addresses a fundamental bottleneck in machine learning optimization for classification, offering potential improvements in generalization, though it appears incremental in the context of gradient-based methods.
The paper tackles the slow margin maximization in gradient-based classification of linearly separable data by proposing Progressive Rescaling Gradient Descent (PRGD), which achieves exponential rate margin maximization, in contrast to existing algorithms that only achieve polynomial rates.
In this work, we investigate the margin-maximization bias exhibited by gradient-based algorithms in classifying linearly separable data. We present an in-depth analysis of the specific properties of the velocity field associated with (normalized) gradients, focusing on their role in margin maximization. Inspired by this analysis, we propose a novel algorithm called Progressive Rescaling Gradient Descent (PRGD) and show that PRGD can maximize the margin at an {\em exponential rate}. This stands in stark contrast to all existing algorithms, which maximize the margin at a slow {\em polynomial rate}. Specifically, we identify mild conditions on data distribution under which existing algorithms such as gradient descent (GD) and normalized gradient descent (NGD) {\em provably fail} in maximizing the margin efficiently. To validate our theoretical findings, we present both synthetic and real-world experiments. Notably, PRGD also shows promise in enhancing the generalization performance when applied to linearly non-separable datasets and deep neural networks.