Dangerous Liaisons of Convex Learning and Non-Affine Aggregation
This work provides a unified theoretical explanation for failure modes in modern convex learning systems that use non-affine gradient aggregation, which is crucial for practitioners designing robust, private, or fair algorithms.
The paper proves that monotonicity of aggregated gradients is preserved only for positively affine aggregation rules, showing that non-affine aggregation (e.g., in adaptive, private, or fair learning) prevents steady convergence and degrades algorithmic stability. It quantifies these drawbacks and identifies sufficient conditions to restore monotonicity.
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.