Dangerous Liaisons of Convex Learning and Non-Affine Aggregation
Thomas Boudou, Batiste Le Bars, Nirupam Gupta, Aurélien Bellet
cs.LG, math.OC, stat.ML
Submitted: 2026-06-26
License: http://creativecommons.org/licenses/by/4.0/
The gist: Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator.
Terminology
Abstract
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.
Sources
- Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning
- Gradient Descent's Last Iterate is Often (slightly) Suboptimal
- Last Iterate Convergence of AdaGrad-Norm for Convex Non-Smooth Optimization
- Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks