mlsanityData to 14 Oct 2026

Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

arXiv 2606.28123 ↗First posted 26 Jun 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator. While linear averaging preserves the monotonicity of gradient updates, this property is often violated when gradients are aggregated non-affinely, as in modern pipelines enforcing constraints like adaptivity, privacy, robustness or fairness. Whether it is possible to design non-affine aggregation rules that maintain monotonicity has remained an open question. We answer this question negatively: we prove that the monotonicity of aggregated gradients is preserved if and only if the aggregation rule is positively affine. Consequently, non-affine aggregation prevents steady convergence and substantially degrade algorithmic stability. We quantify these drawbacks and propose a path forward by identifying sufficient conditions under which monotonicity can be restored. Our results provide a unified theoretical framework explaining the disparate failure modes observed in modern learning systems.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 49 of its 68 references that are in the map. First posted on arXiv 26 Jun 2026.

Builds on

49 of 68 references.

References · 49

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2019On the Convergence of Adam and Beyondcited by 841
  3. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 711
  4. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  5. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  6. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  7. 2018Fairness Without Demographics in Repeated Loss Minimizationcited by 364
  8. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  9. 2019Differential Privacy Has Disparate Impact on Model Accuracycited by 316
  10. 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 250
  11. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  12. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
37 more
  1. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 183
  2. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  3. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  4. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  5. 2020Understanding Gradient Clipping in Private SGD: A Geometric Perspectivecited by 142
  6. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  7. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  8. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  9. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 128
  10. 2020Tempered Sigmoid Activations for Deep Learning with Differential Privacycited by 122
  11. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  12. 2022Adam Can Converge Without Any Modification On Update Rulescited by 114
  13. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  14. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  15. 2019Sharper bounds for uniformly stable algorithmscited by 93
  16. 2014Stochastic Optimization with Importance Samplingcited by 91
  17. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  18. 2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
  19. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 65
  20. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  21. 2020Coherent Gradients: An Approach to Understanding Generalization in Gradient Descent-based Optimizationcited by 41
  22. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  23. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  24. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  25. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  26. 2023Exact convergence rate of the last iterate in subgradient methodscited by 25
  27. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  28. 2018On the Generalization of Stochastic Gradient Descent with Momentumcited by 20
  29. 2015Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principlecited by 16
  30. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  31. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  32. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 11
  33. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  34. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  35. 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 4
  36. 2026Last Iterate Convergence of AdaGrad-Norm for Convex Non-Smooth Optimizationcited by 3
  37. 2025Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoningcited by 2

Built on by

Not cited yet.