Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

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.