Implicit Regularization of Bregman Proximal Point Algorithm on Separable Data: Sharp Alignment Bounds and Kullback-Leibler Geometries

The Bregman proximal point algorithm (BPPA) has witnessed emerging machine learning applications such as knowledge distillation, policy optimization and fine-tuning, where the divergence is a design choice whose effect is not understood. We study this effect for linear classifiers trained on separable data with the exponential loss. The loss then vanishes along infinitely many directions, so the algorithm alone selects the classifier, which we judge by its margin. We first bound the margin by the alignment between the steps of the iterates and of their mirror images, which follow the negative gradient. If the alignment in a chosen norm stays above a constant and the divergence satisfies mild growth and curvature conditions, BPPA attains at least that constant times the maximum margin in that norm. The bound needs no strong convexity and recovers the condition-number bound of earlier work. It is tight: for every quadratic divergence and every norm, a one-point dataset attains the constant exactly. We then study two Kullback-Leibler (KL) geometries where the alignment has no positive lower bound, arising in exponentiated gradient and self-distillation. With KL on the parameters, for every constant stepsize the normalized ${\ell }_1$-margin converges to its maximum, a discrete counterpart of a known mirror-flow result, whereas the Euclidean divergence selects the maximum ${\ell }_2$-margin classifier. With KL on the predictions, when the samples are linearly independent and each proximal step is solved by gradient descent, BPPA converges in direction to the minimum-norm interpolator of the labels, a discrete analogue of a known natural-gradient-flow result. This limit maximizes the ${\ell }_2$-margin if and only if every sample lies on the margin. Results for strongly convex and smooth divergences extend to mirror descent, and numerical experiments illustrate each result.