Technical Summary: Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

Problem Statement

Modern machine learning pipelines frequently employ non-affine aggregation rules to enforce critical constraints such as adaptivity (e.g., Adam, AdaGrad), robustness against outliers (e.g., trimmed means, geometric medians), privacy (e.g., gradient clipping), and fairness. While these rules are motivated by practical necessities, their theoretical behavior in convex first-order optimization remains poorly understood.

Standard convergence guarantees for convex learning, particularly last-iterate convergence and algorithmic stability, rely fundamentally on the monotonicity of the update operator. Specifically, for an update rule $\theta_{t+1} = \theta_t - \gamma F(g_1(\theta_t), \dots, g_n(\theta_t))$, the operator $F$ must be monotone (i.e., $\langle \theta - \omega, F(\theta) - F(\omega) \rangle \geq 0$) to ensure that the distance to the optimum decreases monotonically. It is well-established that linear averaging preserves monotonicity. However, it has remained an open question whether non-affine aggregation rules can preserve this monotonicity property for arbitrary convex inputs, or if they inherently disrupt the convergence geometry.

Methodology

The authors approach this problem through a rigorous theoretical analysis of the structural properties of aggregation operators. The core methodology involves:

1. Formalizing the Operator: Defining the aggregation rule $F: (\mathbb{R}^d)^n \to \mathbb{R}^d$ and analyzing the induced operator $F(\theta) = F(g_1(\theta), \dots, g_n(\theta))$ where $g_i$ are gradients of convex loss functions.
2. Constructive Contradiction: To prove impossibility results, the authors construct specific counterexamples. They demonstrate that if an aggregation rule is not positively affine, one can construct a set of convex functions (specifically, quadratic functions with rank-one Hessians) such that the resulting operator violates monotonicity.
3. Geometric Analysis: The proof relies on analyzing the geometric alignment between input variations and output shifts. It establishes that for an operator to be universally monotone, any variation in a single input vector must result in an output shift that is a non-negative scalar multiple of that variation.
4. Extension to Stability: The analysis extends from monotonicity to co-coercivity (a stronger condition required for non-expansiveness) and algorithmic stability, quantifying how the violation of these properties leads to instability.
5. Restricted Class Analysis: The authors investigate whether monotonicity can be preserved under structural restrictions on the input gradients (e.g., coordinate-wise separability), deriving algebraic conditions (via Jacobian analysis) for such cases.

Key Contributions and Results

1. Impossibility Theorem for Universal Monotonicity

The central result is Theorem 1, which provides a negative answer to the open question:

Theorem 1: An aggregation rule $F$ preserves the monotonicity of any set of monotone input gradients (induced by convex functions) if and only if $F$ is a positively affine aggregation (i.e., $F(g_1, \dots, g_n) = \sum \alpha_k g_k + C$ with $\alpha_k \geq 0$).

Consequently, for every non-affine aggregation rule, there exist convex loss functions such that the induced operator is not monotone. This implies that theoretical guarantees derived for monotone updates cannot be directly applied to non-affine settings without additional assumptions.

2. Consequences for Last-Iterate Convergence

The violation of monotonicity has direct implications for convergence dynamics (Section 3.1):

• Failure of Last-Iterate Convergence: Without monotonicity, the update operator may locally push iterates away from the equilibrium. The authors prove (Theorem 4) that for non-affine rules, there exists a cone of starting points from which the distance to the equilibrium strictly increases in the first step, regardless of the step size $\gamma$.
• Pathological Behavior: This geometric breakdown explains why non-affine methods (like Adam or clipped SGD) often exhibit limit cycles, spurious fixed points, or failure to converge in the last iterate, phenomena that cannot be remedied by step-size decay or variance reduction alone.

3. Degraded Algorithmic Stability

The paper quantifies the impact on generalization via algorithmic stability (Section 3.2):

• Violation of Co-coercivity: Theorem 3 extends the impossibility result to co-coercivity, showing that non-affine aggregations violate this property for convex, smooth functions.
• Strict Expansiveness: Because co-coercivity is violated, the update rule becomes strictly expansive ($\|\theta - \gamma F(\theta) - (\theta' - \gamma F(\theta'))\| > \|\theta - \theta'\|$).
• Stability Penalty: Theorem 6 and Corollary 9 demonstrate that non-affine rules incur an additional instability term ($I(F) > 0$) compared to affine rules. This term accumulates over iterations, leading to strictly worse generalization bounds. This explains observed instability in robust distributed learning and momentum-based methods.

4. Positive Results for Restricted Inputs

While the general case is negative, the authors identify conditions where non-affine rules can preserve monotonicity (Section 4):

• Algebraic Characterization: If the class of admissible convex functions excludes arbitrary rank-1 positive semi-definite Hessians (e.g., coordinate-wise separable functions), non-affine rules may preserve monotonicity.
• Coordinate-Wise Trimmed Mean (CWTM): As a concrete example, the authors show that CWTM preserves monotonicity and co-coercivity when inputs are coordinate-wise separable. This bridges the gap between the impossibility theorem and existing positive results in robust learning literature.

Significance and Claims

The paper claims to provide a unified theoretical framework explaining disparate failure modes observed in modern learning systems. Its significance lies in:

1. Fundamental Limit: It establishes a fundamental theoretical barrier: non-affine aggregation rules cannot universally preserve the geometric properties (monotonicity/co-coercivity) required for strong convergence and stability guarantees in convex learning.
2. Explanation of Empirical Phenomena: It offers a geometric explanation for why adaptive, robust, and private learning algorithms often fail to converge in the last iterate or exhibit instability, attributing these issues to the inherent violation of monotonicity rather than just noise or bias.
3. Design Guidelines: By identifying the specific structural constraints (e.g., coordinate-wise separability) under which non-affine rules can work, the paper provides a "recipe" for designing aggregation rules that maintain theoretical guarantees in restricted settings.
4. Clarification of Literature: The results clarify why certain positive results in the literature (e.g., for Generalized Linear Models or specific robust aggregation schemes) are exceptions rather than the rule, often relying on specific gradient structures that preclude the construction of the counterexamples used in the proof.

The authors conclude that while non-affine aggregation is necessary for many practical constraints, practitioners must recognize that these designs inevitably break the convex geometry of the problem, necessitating alternative theoretical perspectives (such as equilibrium computation or variational inequalities) or specific structural assumptions to recover guarantees.