Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data

Abstract

Bregman proximal point algorithm (BPPA) has witnessed emerging machine learning applications, yet its theoretical understanding has been largely unexplored. We study the computational properties of BPPA through learning linear classifiers with separable data, and demonstrate provable algorithmic regularization of BPPA. For any BPPA instantiated with a fixed Bregman divergence, we provide a lower bound of the margin obtained by BPPA with respect to an arbitrarily chosen norm. The obtained margin lower bound differs from the maximal margin by a multiplicative factor, which inversely depends on the condition number of the distance-generating function measured in the dual norm. We show that the dependence on the condition number is tight, thus demonstrating the importance of divergence in affecting the quality of the learned classifiers. We then extend our findings to mirror descent, for which we establish similar connections between the margin and Bregman divergence, together with a non-asymptotic analysis. Numerical experiments on both synthetic and real-world datasets are provided to support our theoretical findings. To the best of our knowledge, the aforementioned findings appear to be new in the literature of algorithmic regularization.

References in corpus (18)

• Adam: A Method for Stochastic Optimization
• Distilling the Knowledge in a Neural Network
• Trust Region Policy Optimization
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results
• A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decay
• Don't Decay the Learning Rate, Increase the Batch Size
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Gradient descent aligns the layers of deep linear networks
• The large learning rate phase of deep learning: the catapult mechanism
• Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization
• Margins, Shrinkage, and Boosting
• Characterizing the implicit bias via a primal-dual analysis
• Distillation Strategies for Proximal Policy Optimization
• Gradient descent follows the regularization path for general losses