mlsanityData to 7 Oct 2026

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

arXiv 2108.06808 ↗First posted 15 Aug 2021cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 35 of its 61 references that are in the map. First posted on arXiv 15 Aug 2021.

Builds on

35 of 61 references.

References · 35

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  4. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  5. 2015Distilling the Knowledge in a Neural Networkcited by 10,076
  6. 2018MobileNetV2: Inverted Residuals and Linear Bottleneckscited by 4,773
  7. 2016Overcoming catastrophic forgetting in neural networkscited by 4,718
  8. 2015Trust Region Policy Optimizationcited by 2,503
  9. 2016Learning without Forgettingcited by 2,465
  10. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  11. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  12. 2018ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Designcited by 1,132
23 more
  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  2. 2018Born Again Neural Networkscited by 539
  3. 2020Overfitting in adversarially robust deep learningcited by 504
  4. 2018Bag of Tricks for Image Classification with Convolutional Neural Networkscited by 430
  5. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  6. 2017Don't Decay the Learning Rate, Increase the Batch Sizecited by 313
  7. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  8. 2019SMART: Robust and Efficient Fine-Tuning for Pre-trained Natural Language Models through Principled Regularized Optimizationcited by 253
  9. 2020Revisiting Few-sample BERT Fine-tuningcited by 237
  10. 2018A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decaycited by 223
  11. 2020The large learning rate phase of deep learning: the catapult mechanismcited by 206
  12. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  13. 2019Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networkscited by 162
  14. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  15. 2018Convergence of Gradient Descent on Separable Datacited by 108
  16. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  17. 2020Gradient descent follows the regularization path for general lossescited by 57
  18. 2013Margins, Shrinkage, and Boostingcited by 35
  19. 2018Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularizationcited by 29
  20. 2019Revisiting Knowledge Distillation via Label Smoothing Regularizationcited by 29
  21. 2019Inductive Bias of Gradient Descent based Adversarial Training on Separable Datacited by 12
  22. 2021Implicit Regularization in Matrix Sensing via Mirror Descentcited by 11
  23. 2019Distillation Strategies for Proximal Policy Optimizationcited by 7

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 3.

6 papers.

  1. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  2. 2022Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficientlycited by 25
  3. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  4. 2023A Unified Approach to Controlling Implicit Regularization via Mirror Descentcited by 13
  5. 2023Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learningcited by 7
  6. 2023Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methodscited by 0