Abstract
Consider $n$ points $x_1$,\ldots,$x_n$ in finite-dimensional euclidean space,each having one of two colors. Suppose there exists a separating hyperplane(identified with its unit normal vector $w)$ for the points, i.e a hyperplanesuch that points of same color lie on the same side of the hyperplane. Wemeasure the quality of such a hyperplane by its margin $\gamma(w)$, defined asminimum distance between any of the points $x_i$ and the hyperplane. In thispaper, we prove that the margin function $\gamma$ satisfies a nonsmoothKurdyka-Lojasiewicz inequality with exponent $1/2$. This result hasfar-reaching consequences. For example, let $\gamma^{opt}$ be the maximumpossible margin for the problem and let $w^{opt}$ be the parameter for thehyperplane which attains this value. Given any other separating hyperplane withparameter $w$, let $d(w):=\|w-w^{opt}\|$ be the euclidean distance between $w$and $w^{opt}$, also called the bias of $w$. From the previous KL-inequality, wededuce that $(\gamma^{opt}-\gamma(w)) / R \le d(w) \le2\sqrt{(\gamma^{opt}-\gamma(w))/\gamma^{opt}}$, where $R:=\max_i \|x_i\|$ isthe maximum distance of the points $x_i$ from the origin. Consequently, for anyoptimization algorithm (gradient-descent or not), the bias of the iteratesconverges at least as fast as the square-root of the rate of their convergenceof the margin. Thus, our work provides a generic tool for analyzing theimplicit bias of any algorithm in terms of its margin, in situations where aspecialized analysis might not be available: it is sufficient to establish agood rate for converge of the margin, a task which is usually much easier.