Dangerous Liaisons of Convex Learning and Non-Affine Aggregation Thomas Boudou THOMAS . BOUDOU @ INRIA . FR PreMeDICaL team, Inria, Idesp, Inserm, Université de Montpellier, Montpellier, France Batiste Le Bars
BATISTE . LE - BARS @ INRIA . FR
arXiv:2606.28123v1 [cs.LG] 26 Jun 2026
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France
Nirupam Gupta
NIGU @ DI . KU . DK
Department of Computer Science, University of Copenhagen, Copenhagen, Danemark
Aurélien Bellet
AURELIEN . BELLET @ INRIA . FR PreMeDICaL team, Inria, Idesp, Inserm, Université de Montpellier, Montpellier, France
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. Keywords: convex learning; first-order optimization; aggregation rules; last-iterate convergence; algorithmic stability.
1 Introduction Most modern learning algorithms rely on iterative first-order optimization to minimize the expected risk R(θ) := Ez∼p [ℓ(θ; z)] of a loss ℓ over an unknown distribution p, typically accessible only through a finite sample (Bottou and Bousquet, 2007). At their core, these methods compute update directions by aggregating gradient information. Gradients may be obtained directly from p (stochastic optimization), estimated from samples (empirical risk minimization), or perturbed from the nominal distribution (robust optimization, transfer learning). We abstract away these distinctions, as the specific source of gradients is secondary to our main result. Formally, given d, n, T ∈ N \ {0}, we consider algorithms that update model parameters θt ∈ Rd at step t ∈ [T ] := {1, . . . , T } via an aggregation rule F : (Rd )n → Rd applied to input vectors {gi (θt )}i∈[n] ,
θt+1 = θt − γF (g1 (θt ), . . . , gn (θt )), where θ0 ∈ Rd , γ > 0. ©2026 Thomas Boudou, Batiste Le Bars, Nirupam Gupta, Aurélien Bellet. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/.
(1)
B OUDOU , L E BARS , G UPTA , AND B ELLET
We denote F : Rd → Rd , θ 7→ F (g1 (θ), . . . , gn (θ)) the induced operator. Typically, the gradients take the form gi (θ) = ∇θ ℓ(θ; zi ) for some data zi , and n abstracts the relevant scale depending on context (e.g., number of samples, batch size, client count). While a standard choice of F is simple averaging, as in mini-batch stochastic gradient descent (SGD), this framework also captures many modern learning paradigms in which F is a non-affine aggregation rule designed to enforce application-specific constraints. Examples include: (1) Adaptive optimization: Kingma and Ba (2015) reduce tuning overhead via coordinate-wise adaptive 1 P learning rates, F (g1 , . . . , gn ) = diag(v(g1 , . . . , gn ))− 2 i∈[n] gni ; (2) Robust (distributed) learning: Allouah et al. (2023a); Diakonikolas and Kane (2023) mitigate outliers via non-linear filtering (cf. Definition 10); (3) Privacy-preserving learning: AbadiPet al. (2016) control aggregate sensitivity via individual gradient clipping, F (g1 , . . . , gn ) = n1 i∈[n] gi min(1, ∥gCi ∥2 ); (4) Fairness and multi-objective learning: Hashimoto et al. (2018) adaptively reweight gradients, F (g1 , . . . , gn ) = Pn w g where wi depends on {gi }i∈[n] or the model state; (5) Communication-efficient learni=1 i i Pn ing: Bernstein et al. (2018) compress gradients to their signs F (g1 , . . . , gn ) = sign( i=1 sign(gi )). In convex learning, where inputs gi are gradients of a convex loss function (definitions deferred to Appendix A), strong theoretical guarantees of the last-iterate expected risk of the update rule (1) hinge on the monotonicity of F. Specifically, F is monotone if ∀θ, ω ∈ Rd ,
⟨θ − ω, F (θ) − F(ω)⟩ ≥ 0.
(2)
This property extends the notion of convexity to general operators, generalizing the fact that convex scalar functions have monotone gradients (Bauschke and Combettes, 2011, Proposition 17.10). When F is the arithmetic mean (as in mini-batch SGD) and the inputs gi are monotone, the resulting operator F preserves this monotonicity. In contrast, while non-affine aggregation rules are motivated by important learning objectives, as illustrated above, it remains unclear whether they can achieve these goals without compromising the monotonicity of updates. Main result. Our main result is of theoretical nature and can be summarized by the following (informal) impossibility theorem, explicitly stated and proved in Section 2. Theorem 1 (informal) Only positively affine aggregation universally preserves monotonicity. Here, universal refers to an aggregation rule that preserves the monotonicity of any set of monotone input gradients. Theorem 1 shows that for every non-affine aggregation, there exist monotone input gradients gi such that the induced operator F violates monotonicity. In other words, only affine aggregation guarantees monotonicity without imposing additional assumptions on the inputs. This result answers negatively the open question of whether a non-affine aggregation rule can preserve monotonicity for arbitrary input gradient vectors. Consequently, theoretical guarantees for updates using non-affine aggregation generally cannot be derived directly from those for monotone updates. We highlight three consequences of Theorem 1 for algorithms following update (1) under nonaffine aggregation: (I) it explains why these algorithms do not enjoy last-iterate convergence guarantees, unless one make additional assumptions; (II) it implies an additional algorithmic instability; and (III) it offers insights into designing non-affine rules that preserve monotonicity for restricted convex inputs. While some of these points were previously noted in specific contexts, our result provides a unified theory for these scattered observations (cf. the discussion of related work in Section 5). 2
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Consequence I: Last-iterate convergence failures (cf. Section 3.1). Last-iterate convergence, i.e., the convergence of the update (1), is a strong theoretical property (Bach, 2024; Zamani and Glineur, 2025; Preobrazhenskaia et al., 2026; Kornowski and Shamir, 2026) that, unlike convergence of averaged iterates, better aligns with practical implementations and preserves structural properties such as parameter sparsity. While averaged convergence can be obtained even for nonmonotonic updates, last-iterate convergence of first-order methods for convex losses rely on the update’s ability to monotonically decrease the distance to the optimum—or equilibrium, i.e., a stationary point of F (Bauschke and Combettes, 2011; Ryu and Boyd, 2016). However, in the absence of monotonicity, the operator may locally push the iterate away from the equilibrium θeq . Specifically, we demonstrate in Theorem 4 that there exists a cone K emanating from θeq such that ∀θ0 ∈ K, ⟨F(θ0 ), θ0 − θeq ⟩ < 0. Consequently, for any step-size γ > 0, the update step θ1 = θ0 − γF (θ0 ) strictly increases the distance to the equilibrium ∥θ1 − θeq ∥22 = ∥θ0 − θeq ∥22 + γ 2 ∥F(θ0 )∥22 − 2γ⟨F(θ0 ), θ0 − θeq ⟩ > ∥θ0 − θeq ∥22 . This inequality invalidates descent arguments central to last-iterate convergence, highlighting that non-affine aggregations are prone to pathological behavior, even in deterministic settings. Our analysis provides a geometric perspective that is distinct from, and orthogonal to, the phenomena of unavoidable bias and variance-induced oscillations. For instance, even an affine aggregation rule may be biased (pointing away from the desired solution, i.e., the solution with simple averaging), and yet still be monotone, thereby preserving stable convergence. Similarly, stochastic gradient noise induces oscillations while the update operator remains monotone (Dieuleveut et al., 2020), enabling convergence via step-size decay (Moulines and Bach, 2011) or variance-reduction methods (Defazio et al., 2014). In contrast, violations of monotonicity fundamentally alter the update geometry: even a deterministic update can produce spurious fixed points (Reddi et al., 2018) or stable limit cycles (Lessard et al., 2016, Figure 6), failures that cannot be remedied by step-size decay or variance reduction. Consequence II: Degraded algorithmic stability (cf. Section 3.2). From a learning theory perspective, when we consider a finite sample S drawn from p, the update (1) usually aims to minimize 1 P b an empirical risk R(θ) = |S| z∈S ℓ(θ; z) as a proxy for minimizing the true risk R(θT ). The b T ) can be controlled via algorithmic stability (Bousquet and Elisgeneralization error R(θT ) − R(θ seeff, 2002; Bousquet et al., 2020), a framework that has proven particularly effective across a wide range of learning problems and algorithms (Hardt et al., 2016; Bassily et al., 2019; Schliserman and Koren, 2022; Boudou et al., 2025). Algorithmic stability quantifies the worst-case sensitivity of an algorithm to changes in its training data. Formally, this requires bounding the divergence between two trajectories produced by the algorithm on adjacent datasets (differing by a single sample). This crucially hinges on the non-expansiveness (Hardt et al., 2016, Definition 2.3) of (1), a property ensured when F is co-coercive, i.e., when there exists LF > 0 such that ∀θ, ω ∈ Rd ,
⟨θ − ω, F (θ) − F(ω)⟩ ≥
1 ∥F(θ) − F(ω)∥22 . LF
(3)
This condition is a stronger form of monotonicity that holds for gradients of convex, Lipschitzsmooth functions (e.g., Bach, 2024, Proposition 5.4). However, extending Theorem 1, we prove that non-affine aggregation violates co-coercivity (Theorem 3). Hence, for any learning rate γ > 0 3
B OUDOU , L E BARS , G UPTA , AND B ELLET
and parameters θ, θ′ that violate co-coercivity (3), the update rule (1) is strictly expansive, ∥θ − γF(θ) − (θ′ − γF(θ′ ))∥22 = ∥θ − θ′ ∥22 + γ 2 ∥F(θ) − F(θ′ )∥22 − 2γ⟨θ − θ′ , F(θ) − F (θ′ )⟩ > ∥θ − θ′ ∥22 . This strict inequality invalidates stability proofs based on non-expansiveness. Furthermore, due to this expansiveness, we show in Theorem 6 and Lemma 8 that non-affine aggregations incur an additional stability penalty relative to positively affine rules. Under mild conditions, this implies that their overall instability is strictly larger. This demonstrates that non-affine aggregations degrade stability and, consequently, weaken the generalization guarantees that hold for positively affine aggregation rules. Consequence III: Non-affine monotone aggregations for restricted inputs (cf. Section 4). Beyond establishing a fundamental limit of non-affine aggregation, the proof of Theorem 1 also provides a recipe for identifying non-affine aggregations that preserve monotonicity when the input gradients are derived from a restricted class of convex functions. First, it establishes a testable condition that delineates the boundary: valid non-affine rules exist only if the underlying loss functions prevent arbitrary rank-1 symmetric p.s.d. matrix as Hessians. Second, the proof is constructive, allowing us to reverse-engineer the properties required for such rules. We illustrate this approach by identifying the Coordinate-Wise Trimmed Mean (CWTM, Yin et al., 2018) as a monotonicitypreserving rule when the input gradients are coordinate-wise separable (cf. Section 4). Overall, this analysis bridges our impossibility theorem with prior work reporting positive results for nonaffine aggregation under restricted inputs (cf. Section 5). Specifically, our framework explains these exceptions and allows to uncover new situations where non-affine rules can preserve monotonicity.
2 Only Positively Affine Aggregation Universally Preserves Monotonicity In this section, we present our main result, Theorem 1, answering whether a non-affine aggregation rule can preserve monotonicity of any monotone input vectors. We focus here on the properties of the induced operator F; their implications for learning algorithms are discussed in Section 3. We denote, for a v ∈ Rd , cone(v) := {λv; λ ≥ 0}. Theorem 1 Let d > 1, and consider the model update rule (1). F is a monotonic operator for all gradients {gi (·)}i∈[n] induced by convex functions if and only if F is a positively affine aggregation, i.e., there exists α ∈ Rn+ and C ∈ Rd , such that for any input vectors (g1 , . . . , gn ) ∈ (Rd )n , F (g1 , . . . , gn ) =
n X
αk gk + C.
k=1
If F is also permutation-invariant and idempotent (F (g, . . . , g) = g), then F is the arithmetic mean. Proof If F is a positively affine aggregation, it is immediate that F preserves monotonicity. We now turn to the converse. The proof has three steps. First, Step 1 proves a rigid alignment condition: any variation in a single input vector must yield a variation of the aggregation output in the exact same direction. We prove this by contradiction, showing that if this property is violated, one can construct valid inputs {gi (·)}i∈[n] such that monotonicity (2) is violated. Then, Steps 2 and 3 deduce the necessary algebraic form of F from this constraint, proceeding first input-wise and then globally. 4
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Step 1. We prove that any variation in a single input vector must result in an output shift that is a non-negative scalar multiple of that variation. Fix an index i ∈ [n] and an arbitrary vector g−i := (. . . , gi−1 , gi+1 , . . .) ∈ (Rd )n−1 . Consider the partial function fg−i (u) := F (g1 , . . . , u, . . . , gn ). Let u, v ∈ Rd be arbitrary vectors. We claim that if (2) is satisfied, fg−i (u) − fg−i (v) ∈ cone(u − v) If u = v, or fg−i (u) = fg−i (v), the claim is trivial. Otherwise, the proof proceeds by contradiction. Suppose that fg−i (u) − fg−i (v) ∈ / cone(u − v). We define δ as the bisector of the angle between (u − v) and −(fg−i (u) − fg−i (v)), δ :=
fg−i (u) − fg−i (v) u−v − . ∥u − v∥2 ∥fg−i (u) − fg−i (v)∥2
As directions differ, the strict Cauchy-Schwarz inequality applies and implies the separation ⟨fg−i (u) − fg−i (v), δ⟩ < 0
and
⟨u − v, δ⟩ > 0.
(4)
Next, we construct convex functions whose gradients at 0 and δ match these input configurations. ⊺
♠ For index i, define ℓi (θ) = 12 θ⊺ Hθ + v ⊺ θ, with H = (u−v)(u−v) ⟨u−v,δ⟩ . Since ⟨u − v, δ⟩ > 0, Hi is symmetric p.s.d. and ℓi is convex. Note that ∇ℓi (0) = v and ∇ℓi (δ) = Hδ + v = u. ♣ For indices j ̸= i, define ℓj (θ) = gj⊺ θ. Then ∇ℓj (0) = ∇ℓj (δ) = gj . Therefore, we get F(δ) = F (∇ℓ1 (δ), . . . , ∇ℓn (δ)) = fg−i (u) and F(0) = F (∇ℓ1 (0), . . . , ∇ℓn (0)) = fg−i (v). Due to the monotonicity condition (2), we have ⟨F(δ) − F(0), δ − 0⟩ = ⟨fg−i (u) − fg−i (v), δ⟩ ≥ 0.
(5)
However, inequality (5) contradicts (4). Thus, for all u ̸= v ∈ Rd , there exists λ(u, v) ≥ 0 such that fg−i (u) − fg−i (v) = λ(u, v)(u − v).
(6)
Step 2. We demonstrate that the rigid geometric constraint of preserving input-wise update directions forces the aggregation F to be affine with respect to each individual input vector. Evaluating (6) with v = 0 yields, for all u ∈ Rd \ {0}, fg−i (u) = λ(u, 0)u + fg−i (0). We only require to prove that u 7→ λ(u, 0) is a constant. Rearranging the terms in (6) yields, for all u ̸= v ∈ Rd , the following linear equation (λ(u, 0) − λ(u, v))u + (λ(u, v) − λ(v, 0))v = 0.
(7)
Case 1: linearly independent inputs. Let any fixed linearly independent vectors u, v ∈ Rd . By linear independence, the coefficients in (7) must be 0, i.e., λ(u, 0) = λ(u, v) = λ(v, 0). 5
B OUDOU , L E BARS , G UPTA , AND B ELLET
Case 2: linearly dependent inputs. If u = 0 ̸= v ∈ Rd , (7) implies λ(v, 0) = λ(0, v). Now, let u ̸= v ∈ Rd \ {0} be non-zero collinear vectors. Since d ≥ 2, there exists a vector z ∈ Rd \ {0} linearly independent of u, and hence linearly independent of v. Applying the result from Case 1, λ(u, 0) = λ(z, 0) and λ(v, 0) = λ(z, 0). By transitivity, λ(u, 0) = λ(v, 0). Consequently, for any pair of vectors u ̸= v ∈ Rd , λ(u, 0) = λ(v, 0). Hence λ(·, 0) is a constant function. Let α ∈ R denote this constant, we have proven that fg−i (u) = αu + fg−i (0), for all u ∈ Rd .
(8)
Step 3. We synthesize these input-wise affineness results, proving that the aggregation F must be a globally affine map over the joint domain. We derived (8) for an arbitrary fixed index i ∈ [n] and configuration g−i ∈ (Rd )n−1 . Therefore, F is input-wise affine, that is, for all i ∈ [n], all g−i ∈ (Rd )n−1 , we have for all gi ∈ Rd , F (g1 , . . . , gn ) = αi (g−i )gi + bi (g−i ),
where bi (g−i ) := fg−i (0).
(9)
We first show that for any pair of distinct indices i ̸= j ∈ [n], αi is independent of gj . Without loss of generality, consider indices 1 and 2 and fix ḡ := (g3 , . . . , gn ) ∈ (Rd )n−2 . Equating the representations from (9) yields α1 (g2 , ḡ)g1 + b1 (g2 , ḡ) = α2 (g1 , ḡ)g2 + b2 (g1 , ḡ).
(10)
Evaluating (10) at g1 = 0 yields b1 (g2 , ḡ) = α2 (0, ḡ)g2 +b2 (0, ḡ), and further evaluating the relation at g2 = 0 gives b1 (0, ḡ) = b2 (0, ḡ). Similarly, b2 (g1 , ḡ) = α1 (0, ḡ)g1 + b1 (0, ḡ). Substituting this back into (10), and rearranging terms to isolate g1 and g2 , we have for all (g1 , . . . , gn ) ∈ (Rd )n , (α1 (g2 , ḡ) − α1 (0, ḡ))g1 = (α2 (g1 , ḡ) − α2 (0, ḡ))g2 .
(11)
Fix any g2 ̸= 0. Since α1 (g2 , ḡ) − α1 (0, ḡ) is independent of g1 , and d ≥ 2, we can select a vector g1′ linearly independent of g2 in (11), so that (α1 (g2 , ḡ) − α1 (0, ḡ))g1′ is collinear to (α2 (g1′ , ḡ) − α2 (0, ḡ))g2 . The only vector collinear with (α2 (g1′ , ḡ) − α2 (0, ḡ))g2 in the direction of g1′ is 0. Thus α1 (g2 , ḡ) = α1 (0, ḡ) for all g2 ∈ Rd , i.e., α1 is independent of g2 . By symmetry, for all (g1 , . . . , gn ) ∈ (Rd )n and each i ∈ [n], αi is independent of gj for all j ̸= i, and is therefore constant. Now, define the following residual function, for all (g1 , . . . , gn ) ∈ (Rd )n , R(g1 , . . . , gn ) = F (g1 , . . . , gn ) −
Pn
i=1 αi gi .
(12)
We prove R is a constant vector. Fix j ∈ [n]. Substituting (9) into (12) yields R(g1 , . . . , gn ) = αj gj + bj (g−j ) −
Pn
i=1 αi gi = bj (g−j ) −
P
i̸=j αi gi .
(13)
The right-hand side of (13) depends only on g−j , thus R is independent of gj . By symmetry, this holds for every j ∈ [n], i.e., the residual R is independent of its inputs and is therefore a constant vector. Denote this constant by C := R(0, . . . , 0) = F (0, . . . , 0). We have thus shown that F (g1 , . . . , gn ) =
Pn
d n k=1 αk gk + C, for all (g1 , . . . , gn ) ∈ (R ) .
6
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
d Suppose in addition that F is idempotent and, in fact, it suffices Pn that there exist uP̸=n v ∈ R such that F (u, . . . , u) = u and F (v, . . . , v) = v. Then u − v = ( i=1 αi )(u − v), i.e. i=1 αi = 1. If, moreover, F is permutation-invariant, all coefficients are equal: α = ( n1 , . . . , n1 )⊺ .
Derived from first principles, Theorem 1 requires no assumption on F beyond structure (1), and shows that only positively affine aggregation universally preserves monotonicity over the set of convex functions. That is, for any non-affine aggregation, there exist convex functions such that the induced operator violates monotonicity. The proof above relies on the fact that if F is universally monotone for all convex functions, then it should be monotone for the specific ones constructed in step 1, namely quadratic function with rank-one hessians. The proof then proceeds with a contradiction argument. Remark 2 In Appendix B, we extend Theorem 1 to strong monotonicity (akin to strong convexity) and hypomonotonicity (monotonicity violation is bounded). F is said ρ-hypomonotone if there exists ρ > 0, such that ⟨θ − ω, F(θ) − F (ω)⟩ ≥ −ρ∥θ − ω∥22 ,
for all θ, ω ∈ Θ.
We show that under the assumption of Theorem 1, the same conclusion holds for ρ-hypomonotone operator, for any ρ > 0, in Theorem 19. That is, monotonicity violation is unbounded under the assumption of Theorem 1. However, assuming L-Lipschitz continuous inputs caps this violation whenever F is ΛF -Lipschitz continuous; that is, F is ΛF L-hypomonotone and ΛF L-Lipschitz continuous. Together, these additional results provide a complete picture of universal monotonicity preservation and the extent of its violation. Furthermore, our analysis generalizes to the setting of co-coercive operators. Theorem 3 Let d > 1, L > 0, and consider (1). F is co-coercive for all gradients {gi (·)}i∈[n] induced by convex and L-Lipschitz smooth functions if and only if F is a positively affine aggregation. Proof In the proof of Theorem 1, we only used convex and Lipschitz-smooth loss functions. Specif⊺ ∥u−v∥22 (u−v)(u−v)⊺ ically, in (♠) we set M := L⟨u−v,δ⟩ > 0, δM = M δ and H := (u−v)(u−v) . With M ⟨u−v,δ⟩ = L ∥u−v∥22 this choice, ∥H∥op ⪯ LI. The remainder of the argument proceeds unchanged. We note that Theorems 1 and 3 hold regardless of whether the gi ’s are stochastic (e.g., in SGD). In algorithms such as randomized coordinate descent (RCD), projecting onto a subset of coordinates breaks monotonicity (or co-coercivity) at the level of individual iterates. However, because the expectation is taken over a fixed sampling distribution, the expected operator EF remains affine. Monotonicity (or co-coercivity) is thus recovered in expectation, which is typically sufficient for obtaining in-expectation guarantees. Importantly, Theorem 1 does not rule out the possibility that a non-affine aggregation rule may preserve monotonicity for a restricted class of convex functions. In fact, our proof is constructive and yields actionable insights for identifying non-affine aggregations that preserve monotonicity under structural restrictions on the input gradients. We further develop this important implication of our main result in Section 4, after first discussing the general consequences of Theorems 1 and 3 for learning algorithms in the following Section 3. 7
B OUDOU , L E BARS , G UPTA , AND B ELLET
3 Consequences for Learning Algorithms Theorems 1 and 3 trigger several strong implications for learning algorithms, as one cannot introduce non-affine aggregation rules without distorting the convex geometry of the problem. In this section, we show that violating monotonicity affects convergence dynamics (cf. Section 3.1) and degrades algorithmic stability (cf. Section 3.2). 3.1 Consequences for the Last-Iterate Convergence of Learning Algorithms When aggregation rules fail to preserve monotonicity, the resulting optimization dynamics depart from the classical convex setting. In particular, the loss of monotonicity precludes guarantees of lastiterate convergence (i.e, finding a fixed-point of F ). In the following, we formalize this perspective. Inspired by the proof of Theorem 1, we formalize a property, shared by a broad class of practical aggregation rules, that precludes last-iterate convergence. We say F : (Rd )n → Rd is not positively affine at g1 , . . . , gn ∈ Rd , if there exist i ∈ [n] and δ ∈ Rd \ {0} such that F (g1 , . . . , gi + δ, . . . , gn ) − F (g1 , . . . , gi , . . . , gn ) ̸∈ cone(δ).
(14)
Any non-affine aggregation must exhibit at least one such configuration; otherwise, it would reduce to a positively affine mapping. When this behavior occurs at a stationary configuration, that is, a configuration satisfying F (g1 , . . . , gn ) = 0, we show that it prevents last-iterate convergence. Crucially, most practical non-affine aggregations feature this non-positive affineness for at least one stationary configuration. This includes point-wise clipping (Abadi et al., 2016) and AdaGrad (Duchi et al., 2011)—for which symmetric, non-zero inputs can be constructed to cancel each other out while still triggering the rule’s non-linearity—as well as translation-equivariant robust aggregation schemes (Allouah et al., 2023b; Diakonikolas and Kane, 2023), where any non-affine configuration can be shifted to the origin. Note that if an aggregation rule is positively affine, the condition (14) cannot be satisfied. Moreover, a non-affine aggregation rule can still violate (14) for all stationary configuration, e.g., global clipping (Koloskova et al., 2023, Theorem 2.3). In which case, the algorithm may still converge monotonically to a stationary point. The proof is deferred to Appendix C. Theorem 4 Let d > 1, and F : (Rd )n → Rd be such that there exists (g1 , . . . , gn ) ∈ (Rd )n for which F (g1 , . . . , gn ) = 0 and at which F is not positively affine. Then, there exist convex functions, θeq ∈ {z | F (z) = 0} ̸= ∅, and an open set C ⊂ Sd−1 := {u ∈ Rd ; ∥u∥2 = 1} γF such that for any θ0 ∈ K := {θeq + αc | c ∈ C, α > 0}, the update step (1), I− θ1 θeq C for any γ > 0, strictly increases the distance to the equilibrium θ0
∥θ1 − θeq ∥2 > ∥θ0 − θeq ∥2 .
K
Theorems 1 and 4 elucidate why existing literature often settles for the weaker averaged iterates convergence guarantees rather than the stronger last-iterate convergence of the update (1) when using non-affine aggregations in convex optimization, even under deterministic settings. This barrier stems from the non-positively affine nature of existing stationary configurations. While the trivial (0, . . . , 0) stationary configuration is positively affine for most aggregation rules, practical optimization rarely converges to this ideal state due to data heterogeneity or gradient variance. Consequently, to circumvent this limitation and guarantee strong convergence guarantees, existing literature frequently relies on assumptions to avoid non-positively affine stationary configurations. This includes imposing limiting structural constraints on the problem or aggregation rule (see, e.g., Song et al., 8
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
2021, Lemma 5.1; Koloskova et al., 2023, Theorem 2.3; Preobrazhenskaia et al., 2026, Corollary 4.3). Furthermore, the strong growth condition (or interpolation regime, Schmidt and Roux, 2013; Ma et al., 2018; Liu and Zhou, 2024; Attia et al., 2026, and reference therein) has shown particular efficacy for randomized algorithms. Such additional assumptions have also proven useful in the study of other pathological phenomena, including limit cycles and degraded or improved convergence rates, even when considering only averaged iterates convergence (see, e.g., Karimireddy et al., 2022, Theorem IV; Allouah et al., 2025a, Theorem 5.2). Our theory therefore offers a concrete motivation for studying these pathological aggregation-induced convergence phenomena in the future. We defer a broader discussion of the literature to Section 5. 3.2 Consequences for the Algorithmic Stability of Learning Algorithms From a learning theory perspective, the objective is not only to find or approximate a stationary b in most settings, but also to control the generalization error, i.e., point of F, i.e., a minimizer of R b R(θT ) − R(θT ), of the resulting model. Algorithmic stability has emerged as a central framework for characterizing generalization, particularly in convex optimization. Most existing analysis focus on either uniform argument stability (Hardt et al., 2016; Bassily et al., 2019; Zhang et al., 2022a) or on-average argument stability (Lei and Ying, 2020; Schliserman and Koren, 2022; Le Bars et al., 2024). Formally a learning algorithm A is said ε-uniformly argument stable if Stab(A) := sup ∥A(S) − A(S ′ )∥2 ≤ ε,
(15)
S∼S ′
where S ∼ S ′ denotes a pair of neighboring datasets differing in at most one sample. The generalization error is upper bounded by the stability parameter ε, and can even scale proportionally with it (Boudou et al., 2025, Lemma 4.1). The stability analysis entails bounding the divergence between two parameter trajectories produced by (1) on datasets that differ by only one sample. Classical stability bounds rely on the update (1) being non-expansive (Hardt et al., 2016, Definition 2.3), together with a notion of sensitivity capturing the effect of the sample perturbation. We denote B(0, C) := {x ∈ Rd ; ∥x∥2 < C} and B(0, C) := {x ∈ Rd ; ∥x∥2 ≤ C}. Definition 5 Let F : (B(0, C))n → Rd be an aggregation rule. The sensitivity of F is defined, for an allowed worst-case input perturbation ρ, as Sn,C (F, ρ) := max i∈[n]
∥F (. . . , gi , . . . ) − F (. . . , gi′ , . . . )∥2 .
sup g∈B(0,C)n ,
(16)
gi′ ∈B(0,C), ∥gi −gi′ ∥2 ≤ρ
In this section, we formalize that the loss of co-coercivity induced by non-affineness (Theorem 3) leads to a strictly weaker stability guarantee than those achievable with positively affine aggregation rules. For proving this rigorously, we first show that the algorithmic stability of (1) must account for the expansivity. The proofs of this section are deferred to Appendix D. Theorem 6 Assume the setting of Theorem 3, with gradients norm bounded by C > 0 and neighboring datasets inducing gradient perturbations of at most ρ > 0. Let AF denote the algorithm that outputs θT after T ≥ 1 iterations of (1) with aggregation rule F and step size γ ≤ 1/L. Then, Stab(AF ) ≤ γT Sn,C (F, ρ) + I(F ), 9
(17)
B OUDOU , L E BARS , G UPTA , AND B ELLET
P −1 ∥θt − γF(θt ) − (θt′ − γF(θt′ ))∥2 − ∥θt − θt′ ∥2 . Moreover, there where I(F ) := supS∼S ′ Tt=1 exist convex, L-smooth, and C-Lipschitz loss functions such that Stab(AF ) ≥ 13 (γT Sn,C (F, ρ) + I(F )) .
(18)
In this tight characterization of algorithmic stability, I(F ) quantifies the cumulative effect of the (non-)expansivity of the update (1) when using F . Non-expansivity is guaranteed by the cocoercivity of F, i.e., for positively affine aggregation rules I(F ) ≤ 0, as long as γ ≤ L1 (Hardt et al., 2016, Lemma 3.6). Moreover, for any positively affine aggregation rule, there exists loss functions such that I(F ) = 0 (cf. Zhang et al., 2022a, Theorem 1, or the proof of Theorem 6). However, as shown in Theorem 3, non-affine aggregation rules violate co-coercivity, resulting in an expansive update. Corollary 7 Let d > 1, L > 0. Update (1) is non-expansive for all gradients {gi (·)}i∈[n] induced by convex and L-Lipschitz smooth functions if and only if F is a positively affine aggregation. Proof By Theorem 3, there exist parameters θ, θ′ that violate co-coercivity (3). Thus, for any γ > 0 ∥θ − γF(θ) − (θ′ − γF(θ′ ))∥22 = ∥θ − θ′ ∥22 + γ 2 ∥F(θ) − F(θ′ )∥22 − 2γ⟨θ − θ′ , F(θ) − F (θ′ )⟩ > ∥θ − θ′ ∥22 . Corollary 7 already invalidates standard uniform or on-average argument stability proofs based on non-expansiveness. Indeed, for non-affine aggregation rules, Corollary 7 precludes a direct conclusion that I(F ) ≤ 0. Nevertheless, it does not directly imply I(F ) > 0. To bridge this gap, we derive a one-step lower bound showing that I(F ) > 0 for continuous non-affine aggregation rules. This implies that practical non-affine aggregations necessarily incur an additional stability penalty. While the sensitivity term Sn,C (F, ρ) can decay with more data, I(F ) remains a bottleneck which can scale poorly with hyperparameters such as T (cf. discussion at the end of this section). Assumption 1 There exist i ∈ [n], g−i ∈ B(0, C)n−1 , and p ∈ B(0, C) where fg−i (·) := F (. . . , gi−1 , ·, gi+1 , . . .) is continuous in a neighborhood of p with realizable non-affineness. Specifically, for any r > 0 there exists q, b0 ∈ B(p, r)∩B(0, C) such that d satisfying fg−i (b0 )−fg−i (p) = d is a separating vector for p − q and fg−i (p) − fg−i (q).1 Assumption 1 basically requires the aggregation rule to simultaneously exhibit non-affineness and have a sufficiently rich image so as to trigger expansivity between near-identical trajectories of the update (1). Ultimately, the key message is that violations of co-coercivity inevitably give rise to an additional term in algorithmic stability and must therefore be accounted for. Lemma 8 Assume the setting of Theorem 6 and Assumption 1, with T = 2. Then, for any θ0 ∈ Rd , there exist convex, L−smooth and C−Lipschitz loss functions {ℓj }j∈[n] , ℓ′i such that I(F ) > 0. The construction of Lemma 8, deferred in Appendix D, is necessary to prove degraded stability for continuous aggregation rules, as they typically have a similar sensitivity than their affine counterparts. In contrast, this construction is not necessary for discontinuous aggregation rules, which 1. A vector d is said to be a separating vector for two vectors u and v if ⟨u, d⟩ > 0 and ⟨v, d⟩ < 0. Basically, d represents the normal of a hyperplane separating u and v.
10
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
degrade stability even without violating co-coercivity, although such violations can still occur. Indeed, discontinuities can prevent the sensitivity term Sn,C (F, ρ) from decaying as the amount of data increases, yielding a bottleneck that dominates the sensitivity of their positively affine counterparts. Such discontinuities naturally arise in robust aggregation rules (Diakonikolas et al., 2019; Blanchard et al., 2017; Allouah et al., 2023a,b, 2025b). Together, our framework encompasses practical non-affine aggregation rules and accounts for degraded algorithmic stability. Corollary 9 Let NonAff and Aff be non-affine and positively affine aggregation rules. Then, Stab(ANonAff ) > Stab(AAff ), provided that (1) NonAff verifies Assumption 1, while having comparable baseline sensitivity (e.g., Sn,C (NonAff, ρ) = Sn,C (Aff, ρ)); or (2) NonAff is discontinuous, with a discontinuity jump2 outscaling the baseline sensitivity Sn,C (Aff, ρ) (e.g., it does not decay with the dataset size). Theorem 6, Lemma 8 and Corollary 9 collectively show that the update rule (1), when equipped with a practical non-affine aggregation rule, necessarily incurs an additional instability term. Quantifying the order of this penalty is problem-specific and is left to future work tailored to particular applications. This penalty is consistent with and explains similar instability overheads reported in the literature. In robust distributed learning, Boudou et al. (2025, Theorem 3.4) show an unavoidable stability penalty which outscales the affine baseline. Similarly, for (S)GD with momentum, Ramezani-Kebrya et al. (2024, Theorem 3) identify an additional instability term that grows unfavorably with the number of steps, consistent with lower bounds for accelerated methods (Attia and Koren, 2021). Finally, Bassily et al. (2019) establish a tight instability overhead when nonsmoothness precludes co-coercivity, even under positively affine aggregation. Because this overhead accumulates over iterations, it likely contributes to degraded generalization performance. We postpone a broader review of prior related work in Section 5.
4 Designing Non-Affine Aggregations for Restricted Inputs—A Positive Result The impossibility result of Section 2 relies on the construction of convex loss functions with symmetric positive semidefinite rank-1 Hessians. When such functions are excluded from the set of possible convex loss functions, monotonicity-preserving non-affine rules may become possible. In Appendix E, we provide an alternative proof of Theorem 1 that replaces the contradiction-based argument with an algebraic characterization (Lemma 26), which gives further actionable insights for identifying non-affine rules that preserve monotonicity for restricted classes of convex functions. Specifically, once the class of admissible convex functions is fixed (and thus the associated Hessian family H), solving the algebraic condition from Lemma 26 yields necessary conditions that an aggregation rule must satisfy to preserve monotonicity. That is, the Jacobian of F must be of the following form.
2. More precisely, its maximal discontinuity jump ∆ = maxi∈[n] supg∈B(0,C)n limδ→0+ supx,y∈B(gi ,δ) ∥fg−i (x) − fg−i (y)∥2 scales poorly with problem parameters relative to the baseline sensitivity Sn,C (Aff, ρ).
11
B OUDOU , L E BARS , G UPTA , AND B ELLET
Algebraic condition from Lemma 26. Given a matrix set H ⊂ Rd×d ,find D such that ⊺ ∀H ∈ H, DH ⪰ 0. That is, ∀H ∈ H, ∀v ∈ Rd , v ⊺ DHv = v ⊺ DH+(DH) v ≥ 0. 2 This leads to the following general recipe: (1) Check whether the function class admits arbitrary rank-1 p.s.d. Hessians; (2) If not, solve the algebraic condition in Lemma 26 under the restricted set of functions; (3) Use the resulting characterization to derive constraints on aggregation rules that preserve monotonicity. As an illustration, consider problems where gradients are coordinate-wise separable, such as P standard least-squares objectives. These functions take the form ℓ = dk=1 ℓk , where each ℓk is a univariate function acting solely on the k-th coordinate, k ∈ {1, . . . , d}. In this case, admissible Hessians are diagonal, which excludes arbitrary rank-1 p.s.d. matrices. Solving the algebraic condition from Lemma 26 for this restricted Hessian class shows that the admissible aggregation Jacobians are diagonal. Therefore, any monotonicity-preserving aggregation must operate coordinate-wise. Consistent with this prediction, we show below that Coordinate-Wise Trimmed Mean (CWTM) preserves monotonicity under coordinate-wise separability. CWTM is particularly useful in robust learning as an instance of (f, κ)-robust aggregation with an optimal asymptotic robustness coefficient (Allouah et al., 2023a, Definition 2 & Proposition 2). Definition 10 Given n ∈ N, f < n/2, and real values x1 , . . . , xn , let σ be a permutation such that xσ(1) ≤ · · · ≤ xσ(n) , with Sx = {i ∈ [n]; f + 1 ≤ σ(i) ≤ n − f }, then n−f X X 1 1 TM(x1 , . . . , xn ) = xσ(i) = xi n − 2f n − 2f i=f +1
i∈Sx
Denote [·]k the k−th coordinate. We define CWTM for vectors x1 , . . . , xn ∈ Rd as the coordinatewise application of TM. That is CWTM(x1 , . . . , xn ) is the vector whose k − th coordinate is [CWTM(x1 , . . . , xn )]k = TM([x1 ]k , . . . , [xn ]k ) Lemma 11 For input gradients induced by coordinate-wise separable convex functions, CWTM is monotone. If, in addition, the functions are L-smooth, then CWTM is L1 -co-coercive. Proof Let θ, ω ∈ Rd and z (1) , . . . , z (n) ∈ Z. We denote ℓ′ (·) the derivative of ℓ(·). Because the functions are coordinate-wise separable, the d-dimensional case follows directly from the scalar case. Therefore, it suffices to prove the result for d = 1. In this case, we can leverage the co-coercivity property of the loss function. In fact, due to Lemma 33 (whose proof is deferred to Appendix F), there exist indices α, β ∈ {1, . . . , n} such that ℓ′β (θ) − ℓ′β (ω) ≤ TM(ℓ′1 (θ), . . . , ℓ′n (θ)) − TM(ℓ′1 (ω), . . . , ℓ′n (ω)) ≤ ℓ′α (θ) − ℓ′α (ω).
(19)
Therefore, there exists i ∈ {α, β} such that (θ − ω) TM(ℓ′1 (θ), . . . , ℓ′n (θ)) − TM(ℓ′1 (ω), . . . , ℓ′n (ω)) ≥ (θ − ω)(ℓ′i (θ) − ℓ′i (ω)) ≥ 0, (20) 12
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
where we used the monotonicity of ℓ′i . Again, due to (19), there exists j ∈ {α, β} such that 2 TM(ℓ′1 (θ), . . . , ℓ′n (θ)) − TM(ℓ′1 (ω), . . . , ℓ′n (ω)) ≤ |TM(ℓ′1 (θ), . . . , ℓ′n (θ)) − TM(ℓ′1 (ω), . . . , ℓ′n (ω))||ℓ′j (θ) − ℓ′j (ω)| ≤ L|TM(ℓ′1 (θ), . . . , ℓ′n (θ)) − TM(ℓ′1 (ω), . . . , ℓ′n (ω))||θ − ω| = L TM(ℓ′1 (θ), . . . , ℓ′n (θ)) − TM(ℓ′1 (ω), . . . , ℓ′n (ω)) (θ − ω) , where we now used the smoothness of ℓj , alongside (20). Consequently, under coordinate-wise separable convex and smooth objectives, update (1) with CWTM inherits the strong algorithmic stability guarantees of Hardt et al. (2016). The update also enjoys last-iterate convergence and fast O( T1 ) rates. This contrasts with the general convex and smooth setting, where, as illustrated in Remark 34 and established in Corollary 7, non-expansiveness of the update cannot be guaranteed. Finally, in Appendix F, we further prove that CWTM is Lipschitz continuous, a property that can be exploited in light of Remark 2. Leveraging this result, in Appendix G we derive algorithmic stability guarantees for robust distributed learning in smooth nonconvex settings that improve upon existing bounds (Boudou et al., 2025, Appendix E).
5 Implications of Monotonicity Violations in Related Work Below, we review the extensive literature in which our main theoretical result has an impact and how the violation of monotonicity manifests in those domains. Accelerated and adaptive optimization methods. Adaptive methods like Adam (Kingma and Ba, 2015) employ non-linear scaling to accelerate training, yet they are known to fail to converge even on simple convex problems (Reddi et al., 2018; Luo et al., 2019; Zhang et al., 2022b). Interestingly, the loss of monotonicity has been explicitly noted for the original AdaGrad algorithm (Li and Orabona, 2019, Example 1). While he authors argue that the loss of monotonicity can be handled under convexity, this is only due to their focus on a weaker notion of convergence, namely that of the (weighted) average of the iterates over all iterations Li and Orabona (2019, Theorem 3). Preobrazhenskaia et al. (2026, Theorem 2.3 and references therein) show that the last iterate generated by AdaGrad-Norm may fail to converge, unless the hyperparameters are carefully tuned using the total number of iterations (the more iteration, the lesser the learning rate). Likewise, accelerated methods such as the heavy-ball method can converge to a limit cycle instead of the optimum, even for strongly convex objectives (Lessard et al., 2016, Figure 6). These methods have also been shown to be algorithmically unstable, with stability bounds that scale poorly with the number of iterations (Wilson et al., 2017; Attia and Koren, 2021; Ramezani-Kebrya et al., 2024; Sun et al., 2024). Our results provide a unified explanation for these phenomena and suggest similar behavior in other adaptive schemes, such as dynamic importance sampling (Zhao and Zhang, 2015). While prior work by Needell et al. (2014) leverages importance sampling to accelerate SGD for smooth and strongly convex objectives, their use of a static sampling distribution ensures the aggregation remains affine. In contrast, our work provides a complementary perspective tailored to dynamic reweighting. Gradient clipping and differentially private learning. Gradient clipping is arguably the most ubiquitous non-affine aggregation rule. While often treated as a heuristic to “stabilize” training (Zhang et al., 2020), our analysis indicates that clipping alters the optimization landscape by 13
B OUDOU , L E BARS , G UPTA , AND B ELLET
violating monotonicity. This aligns with and generalizes recent findings on the influence of clipping (Koloskova et al., 2023; Zeng and Lei, 2026, and related work therein), most notably in the context of private machine learning with DP-SGD (Abadi et al., 2016; Papernot et al., 2021; Bagdasaryan et al., 2019). Chen et al. (2020); Qian et al. (2021) provide further geometric insights into clipping’s impact on convergence. Importantly, our work clarifies the limitations of recent positive results. For instance, Song et al. (2021) prove that for Generalized Linear Models (GLMs), clipped-DP-SGD minimizes a surrogate convex objective. We show this is an exception, not the rule: GLMs possess a specific gradient structure (constrained to be parallel to the data vector) that precludes (♠) in our proof. Similarly, Koloskova et al. (2023) rely on the collinearity between clipped and true gradients to prove convergence in deterministic settings. Finally, optimal DP guarantees in convex learning under Lipschitzness assumption (Altschuler et al., 2024) rely on non-expansiveness (which relies on co-coercivity), further highlighting the scope of our theory. Robust (distributed) learning. In robust distributed learning, a central learner aggregates gradients from multiple workers, some of which may be corrupted, while the majority are drawn from the true data distribution. Robust aggregation rules necessarily introduce non-linearity to filter out outliers (Blanchard et al., 2017; Diakonikolas and Kane, 2023). The oscillations and non-vanishing error observed in the literature (Karimireddy et al., 2021; Allouah et al., 2023a) are typical phenomena that occur when an operator loses monotonicity, as our analysis predicts. Moreover, a significant implication of Theorem 3, which settles an open problem stated by Boudou et al. (2025) in the negative, is that no robust aggregation rule can universally preserve monotonicity or co-coercivity. Corollary 12 No robust aggregation rule, i.e., an aggregation rule for which a minority fraction of inputs cannot force it to output an arbitrary vector, universally preserves monotonicity of convex functions or co-coercivity of convex, smooth functions. Proof By Theorem 1, any such rule must be affine. However, affine aggregators are non-robust in the sense that a single input can arbitrarily skew the output (Blanchard et al., 2017, Lemma 1). Combined with our findings in Section 3.2, this further indicates that robust distributed learning inherently incurs additional instability. This stands in contrast to Chatterjee (2020), who suggest that robust aggregation can improve on-average stability, albeit under specific, data-dependent assumptions. Investigating these differences presents a promising avenue for future work, potentially revealing the conditions under which robust aggregation can achieve favorable stability.
6 Discussion We provide a unifying perspective on why algorithms using non-affine aggregations generally fail to preserve the theoretical guarantees of their affine counterparts in convex first-order optimization. Theorem 1 reveals that non-affine aggregation breaks monotonicity. Consequently, seemingly benign algorithmic designs used for robustness, privacy, or adaptivity inevitably generate non-monotone vector fields. These dynamics are prone to non-convergent behavior and incur additional instability, even in smooth, convex settings. Recognizing this breakdown, we additionally identify situations where monotonicity can be preserved. In light of our findings, a key avenue for future research is to identify the minimal structural assumptions necessary to restore restricted forms of monotonicity. Another promising avenue for 14
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
future work is studying alternative update rules beyond the scope of (1). For simplicity of exposition, we assumed the aggregation operator F to be fixed across iterations. However, because Theorems 1, 3 4, 6, Lemma 8 and Corollaries 7, 9 are, or can be reduced to single-step results, our framework naturally extends to time-varying operators Ft . Consequently, the update rule (1) captures any step involving a non-affine aggregation of the current gradients, including momentumbased aggregations, by simply evaluating a step-dependent operator at each iteration. One compelling direction is to shift the theoretical perspective from classical minimization to equilibrium computation (variational inequality problems, cf. Facchinei and Pang, 2007). This framework is better equipped to handle the non-monotone dynamics induced by practical learning constraints, a capability well-demonstrated by the success of extragradient methods in saddle-point problems like generative adversarial training (Gidel et al., 2019; Mertikopoulos et al., 2019). Moreover, while Section 3.2 settles the question of added instability for deterministic learning algorithms, existing workarounds generally fall into two categories: optimization-based dynamics or algorithmic randomization. The former paradigm, such as the framework by Charles and Papailiopoulos (2018), however crucially relies on the convergence of (1) to a global optimum, together with additional technical assumptions on the set of minimizers. This condition is far from obvious when using nonaffine aggregation, as discussed in Section 3.1, thereby precluding the application of their technique. The latter paradigm leverages randomization. For instance, connections between differential privacy and stability (Wang et al., 2016, Lemma 23) demonstrate that any (ε, δ)−differentially private algorithm (see Wang et al., 2016, Definition 20) achieves uniform argument stability. Specifically, over a parameter space with diameter D, such an algorithm is D(eε − 1 + δ)-uniformly argument stable. This offers an alternative route to stability without co-coercivity, where randomization acts as a stabilizing force. We leave for future work the question of how these two approaches—based respectively on non-expansivity and on statistical indistinguishability—can be unified or compared.
Acknowledgments and Disclosure of Funding The work of Thomas Boudou and Aurélien Bellet is supported by grant ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR under the France 2030 program.
Appendix A. Regularity Assumptions To analyze iterative optimization algorithms, we typically rely on regularity assumptions on the loss function. Definition 13 (Regularity assumptions) Let ℓ : Θ → R differentiable, Θ ⊂ Rd a convex set. (i) ℓ is C−Lipschitz-continuous (or C−Lipschitz) if there exists C > 0 such that, ∀u, v ∈ Θ,
|ℓ(u) − ℓ(v)| ≤ C∥u − v∥2 .
This property is equivalent to the norm of the gradient of ℓ being uniformly bounded by C. (ii) ℓ is L−Lipschitz-smooth (or L−smooth) if its gradient is L−Lipschitz. This is equivalent to the following smoothness inequality L ∀u, v ∈ Θ, ℓ(u) ≤ ℓ(v) + ⟨∇ℓ(v), u − v⟩ + ∥u − v∥22 . (21) 2 15
B OUDOU , L E BARS , G UPTA , AND B ELLET
(iii) ℓ is convex if and only if, ∀u, v ∈ Θ,
⟨∇ℓ(u) − ∇ℓ(v), u − v⟩ ≥ 0.
(22)
Moreover it is µ−strongly convex if there exists µ > 0 such that, ∀u, v ∈ Θ,
ℓ(u) ≥ ℓ(v) + ⟨∇ℓ(v), u − v⟩ +
µ ∥u − v∥22 . 2
(23)
We note that for a strongly convex function to have bounded gradients, it must be defined on a convex compact set, which then implies boundedness of both the loss and the gradient. To ensure this, we can either penalize the problem or restrict the parameter domain and apply an Euclidean projection at every step. Throughout the paper, we will tacitly assume this when referring to strongly convex functions, which does not limit the applicability of our analysis since the projection does not increase the distance between projected points. Notably, convex and L-smooth functions satisfy an important property known as co-coercivity (e.g., Bach, 2024, Proposition 5.4). Lemma 14 (Co-coercivity) Let ℓ : Θ → R differentiable, Θ ⊂ Rd . If ℓ is a convex and L−smooth function, then it satisfies the co-coercivity inequality, ∀u, v ∈ Θ,
⟨∇ℓ(u) − ∇ℓ(v), u − v⟩ ≥
1 ∥∇ℓ(u) − ∇ℓ(v)∥22 . L
(24)
We recall the concept of absolute continuity. Definition 15 A function f : [a, b]P → Rd is said to be absolutely continuous on [a, b] if for every ) − f (ak )∥2 < ϵ whenever {(ak , bk )}N ϵ > 0, there exists δ > 0 such that N k=1 ∥f (bkP k=1 is a finite N collection of disjoint subintervals of [a, b] with k=1 (bk − ak ) < δ. An equivalent characterization is that f is continuous, differentiable almost everywhere, its derivative f ′ is integrable, and Z x f (x) = f (a) + f ′ (t) dt for all x ∈ [a, b]. a
In the multivariate setting, we work with functions that are absolutely continuous on lines (ACL). Definition 16 Let D, d ∈ N. The map F : RD → Rd , is absolutely continuous on lines (ACL) if for each k ∈ [D], the functions t 7→ F (. . . , xk−1 , t, xk+1 , . . .) are locally absolutely continuous in t on R, i.e., absolutely continuous (cf. Definition 15) on compact subsets of R, for almost every x−k := (. . . , xk−1 , xk+1 , . . .) ∈ RD−1 . This notion originates in the analysis of Sobolev functions, where ACL plays a key role in relating weak and pointwise differentiability. In fact, it provides a characterization of the Sobolev spaces for locally integrable functions (cf. Leoni, 2017, Theorem 11.45). 1,1 Definition 17 Let D, d ∈ N and Ω ⊂ RD an open set. The local Sobolev space Wloc (Ω; Rd ) consists of functions u ∈ L1loc (Ω; Rd ) such that their weak partial derivatives exist and belong to L1loc (Ω; Rd ), Z 1 d d Lloc (Ω; R ) = {f : Ω 7→ R measurable s.t. ∥f (x)∥2 dx < ∞ for every compact K ⊂ Ω}. K
16
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Finally, we formally define the notion of input-wise monotonicity. Definition 18 Let d, n ∈ N. The map F is input-wise monotone if for every input vector index j ∈ [n] and every fixed configuration of other inputs g−j ∈ (Rd )n−1 , the partial map fj : Rd → Rd defined by fj (u) := F (. . . , gj−1 , u, gj+1 , . . .) satisfies the monotonicity condition ⟨fj (u) − fj (v), u − v⟩ ≥ 0
for all u, v ∈ Rd .
Appendix B. Extension of Theorem 1 If we do not assume any smoothness, we can make the violation of monotonicity arbitrarily large. This claim leads to a generalization of the theorem under even milder monotonicity assumptions. For instance, we consider the ρ-hypomonotonicity notion (relating to weak-convexity), Theorem 19 Assume the setting of Theorem 1. F is hypomonotone, i.e. there exists ρ > 0, such that ⟨θ − ω, F(θ) − F (ω)⟩ ≥ −ρ∥θ − ω∥22 ,
for all θ, ω ∈ Θ,
(25)
if and only if F is an affine aggregator. Proof Suppose F is ρ-hypomonotone on the class of L-smooth convex loss functions. Suppose L > 0 and ρ < L ν(F ), where D E fg−i (u) − fg−i (v) E D u − v ,δ ,δ , (26) ν(F ) = max sup ∥u − v∥2 ∥u − v∥2 i∈[n] u̸=v∈Rd , g ∈(Rd )n−1 , −i δ∈Dsep (u,v,fg−i )
n o and Dsep (u, v, fg−i ) := δ ∈ Sd−1 s. t. ⟨u − v, δ⟩ > 0 > ⟨fg−i (u) − fg−i (v), δ⟩ . The proof is identical as Theorem 1 until (4). Specifically, we define the same functions as in (♣) for ∥u−v∥22 indices j ̸= i and for i, instead of (♠), we set M := L⟨u−v,δ⟩ > 0 and ℓi (θ) = 12 θ⊺ Hθ + v ⊺ θ, with ⊺
⊺
(u−v)(u−v) H := (u−v)(u−v) . We verify the properties of ℓi : it is convex (M ⟨u − v, δ⟩ > M ⟨u−v,δ⟩ = L ∥u−v∥22 0), smooth (∥H∥op = L), ∇ℓi (0) = v and ∇ℓi (M δ) = u. Due to the ρ−hypomonotonicity condition (25), we have
⟨fg−i (u) − fg−i (v), M δ⟩ = ⟨F(M δ) − F(0), M δ − 0⟩ ≥ −ρM 2 ∥δ∥22 , which yields |⟨fg−i (u) − fg−i (v), δ⟩|⟨u − v, δ⟩ ρ := νi (u, v, g−i ). ≥ L ∥δ∥22 ∥u − v∥22
(27)
This leads to a contradiction. Indeed, by the definition of the supremum in (26), the assumption ∗ ) ∈ ν(F ) > Lρ guarantees the existence of an index i∗ ∈ [n] and a configuration (u∗ , v ∗ , g−i ∗ ρ d d d (n−1) ∗ ∗ ∗ R × R × (R ) such that νi∗ (u , v , g−i∗ ) > L , condradicting (27). Consequently, we have the following conclusions. (1) If L can be arbitrary (i.e., we consider general convex loss functions), then we must have ν(F ) = 0, and the rest of the proof is identical, i.e., F must be affine for any ρ ∈ R.3 |⟨fg−i (u)−fg−i (v),δ⟩|⟨u−v,δ⟩ 3. We can directly prove the contradiction with ℓi (θ) = max ⟨v, θ⟩, ⟨u, θ⟩ − . 2ρ∥δ∥2 2
17
B OUDOU , L E BARS , G UPTA , AND B ELLET
(2) If L is fixed, for F to be potentially ρ−hypomonotone, we must have ν(F ) ≤ Lρ , i.e., at least a necessary condition is that ν(F ) < ∞.
Importantly, we remark that ν(F ) ≤ max
sup
i∈[n] u̸=v∈Rd , g−i ∈(Rd )n−1
∥fg−i (u) − fg−i (v)∥2 ∥u − v∥2
= max
sup
i∈[n] g−i ∈(Rd )n−1
Lip(fg−i ).
That is, a sufficient condition for ν(F ) to be bounded is that F is Lipschitz continuous. In fact, we prove it is a sufficient condition for F to be hypomonotone. Theorem 20 Let d, n ≥ 1, and L > 0. If F : Rd → Rd is Λ−Lipschitz continuous (e.g., CWTM) and the loss functions are L-smooth, then F satisfies Λ−hypomonotonicity. Moreover, by Lemma 32, F must be Lipschitz continuous and Λ ≤ ΛF L, where X ∂F X ΛF := ess sup (g1 , . . . , gn ) ≤ sup Lip(fg−i ). (28) ∂gi (g1 ,...,gn )∈(Rd )n g−i ∈(Rd )n−1 sp i∈[n]
i∈[n]
Proof Using the Cauchy–Schwarz inequality yields ⟨θ − ω, F(θ) − F (ω)⟩ ≥ −∥θ − ω∥2 ∥F(θ) − F(ω)∥2 . Substituting the Lipschitz continuity bound ∥F(θ) − F (ω)∥2 ≤ Λ∥θ − ω∥2 , we have ⟨θ − ω, F(θ) − F (ω)⟩ ≥ −Λ∥θ − ω∥2 . Moreover, by Lemma 32, F must be Lipschitz continuous. Let consider the maximum sum of input-wise Lipschitz constants (28). Let {ℓi }i∈[n] be L−smooth functions. By the chain rule, for almost every θ ∈ Rd , ∇F(θ) =
n X ∂F i=1
∂gi
(∇ℓ1 (θ), . . . , ∇ℓn (θ)) ∇2 ℓi (θ).
(29)
From (29), using supθ∈Rd ∥∇2 ℓi (θ)∥sp ≤ L, the triangular and Cauchy-Schwarz inequality, we have for almost every all θ ∈ Rd ∥∇F(θ)∥sp ≤ L
n X ∂F (∇ℓ1 (θ), . . . , ∇ℓn (θ)) ∂gi sp i=1
Hence, Lip(F) = ess supθ∈Rd ∥∇F(θ)∥sp ≤ LΛF .
Remark 21 The proof extends verbatim if we instead consider hypo–co-coercive ⟨θ − ω, F(θ) − F (ω)⟩ ≥ −ρ∥F(θ) − F(ω)∥22 . The only modification is that we obtain the condition ρL ≥
∥u − v∥22 |⟨fg−i (u) − fg−i (v), δ⟩| . ⟨u − v, δ⟩ ∥fg−i (u) − fg−i (v)∥22
Hence, smaller values of L make the contradiction easier to achieve. 18
(30)
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
The proof extends to strong monotonicity setting, with {gi }i∈[n] µ−strongly montone gradients, adapting the reasoning with a limit argument. For simplicity, we assume F continuous (monotone implies almost everywhere continuous, so the argument should be valid with a careful derivation). Theorem 22 Assume the setting of Theorem 1, additionally assuming the gradients are µ−strongly monotone and that F is continuous. F is µF −strongly monotone, i.e. there exists µF > 0 such that ⟨θ − ω, F(θ) − F (ω)⟩ ≥ µF ∥θ − ω∥22 ,
for all θ, ω ∈ Θ,
(31)
if and only if F is an affine aggregator. Proof Suppose F is µF -strong monotone on the class of µ-strongly convex loss functions. The proof is identical as Theorem 1 until (4). However we require to adapt (♠) to be µ−stongly convex and we cannot use the linear losses (♣). We instead consider the following functions. 1 • For index i, define ℓi (θ) = 21 θ⊺ Hϵ θ + v ⊺ θ, where Hϵ = µI + ⟨z,δ⟩ , and zz ⊺ , 0 < ϵ < ⟨u−v,δ⟩ µ∥δ∥2 2
z = 1ϵ (u − v) − µδ. As ⟨z, δ⟩ = 1ϵ ⟨u − v, δ⟩ − µ∥δ∥22 > 0 and zz ⊺ is rank 1 matrix, Hϵ ⪰ µI. Moreover, ∇ℓi (0) = v and ∇ℓi (ϵδ) = Hϵ ϵδ + v = µϵδ + ϵz + v = u. • For indices j ̸= i, define ℓj (θ) = gj⊺ θ + µ2 ∥θ∥22 . Then ∇ℓj (0) = 0 and ∇ℓj (ϵδ) = gj + ϵµδ. We have, F(0) = F (g1 , . . . , v, . . . , gn ) = F (v, g−i ), and F(ϵδ) = F (g1 + ϵµδ, . . . , u, . . . , gn + ϵµδ) = F (u, g−i + ϵµδ). The strong monotonicity condition implies ϵ⟨F (u, g−i + ϵµδ) − F (v, g−i ), δ⟩ = ⟨F(ϵδ) − F(0), ϵδ⟩ ≥ ϵ2 ρ∥δ∥2 .
(32)
Taking the limit ϵ → 0 of (32) yields the contradiction lim ⟨F (u, g−i + ϵµδ) − F (v, g−i ), δ⟩ = ⟨fg−i (u) − fg−i (v), δ⟩ ≥ 0 = lim ϵρ∥δ∥2 .
ϵ→0
ϵ→0
Appendix C. Deferred proof of Section 3.1 This appendix contains the proof of Theorem 4, which was deferred from Section 3.1. Theorem 4 Let d > 1, and F : (Rd )n → Rd be such that there exists (g1 , . . . , gn ) ∈ (Rd )n for which F (g1 , . . . , gn ) = 0 and at which F is not positively affine. Then, there exist convex functions, θeq ∈ {z | F (z) = 0} ̸= ∅, and an open set C ⊂ Sd−1 := {u ∈ Rd ; ∥u∥2 = 1} γF such that for any θ0 ∈ K := {θeq + αc | c ∈ C, α > 0}, the update step (1), I− θ1 θeq C for any γ > 0, strictly increases the distance to the equilibrium θ 0
∥θ1 − θeq ∥2 > ∥θ0 − θeq ∥2 . 19
K
B OUDOU , L E BARS , G UPTA , AND B ELLET
Proof For any i ∈ [n], any (g1 , . . . , gi−1 , gi+1 , . . . , gn ) ∈ (Rd )n−1 , and any vector w ∈ Rd , we define an operator fg−i (w) = F (g1 , . . . , gn ) where the i-th vector gi = w. By assumption, there exists n vectors g1 , . . . , gn ∈ Rd , i ∈ [n] and u ∈ Rd \ {0} such that fg−i (v) = F (g1 , . . . , gn ) = 0
fg−i (u) − fg−i (v) ̸∈ cone(u − v).
and
Define the unit vector −1
fg−i (u) u−v − c= ∥u − v∥2 ∥fg−i (u)∥2
2
fg−i (u) u−v − ∥u − v∥2 ∥fg−i (u)∥2
. ⊺
For an arbitrary α > 0, let δ = αc. Since ⟨u − v, δ⟩ > 0, the matrix H = (u−v)(u−v) is positive ⟨u−v, δ⟩ semi-definite. Consider the following set of convex loss functions. • For index i, define ℓi (θ) = 21 (θ − θeq )⊺ H (θ − θeq ) + v ⊺ θ. Then, ∇ℓi (θeq ) = v and ∇ℓi (θeq + δ) = Hδ + v = u. • For indices j ̸= i, define ℓj (θ) = gj⊺ θ. Then, ∇ℓj (θeq ) = ∇ℓj (θeq + δ) = gj . In this particular setting, we indeed have F (θeq ) = fg−i (v) = 0 and F (θeq + δ) = fg−i (u). In the following, set θ0 = θeq + δ = θeq + αc. We obtain that ⟨F (θ0 ) , θ0 − θeq ⟩ = fg−i (u), δ fg−i (u) u−v =α − ∥u − v∥2 ∥fg−i (u)∥2
−1 2
fg−i (u), u − v − ∥fg−i (u)∥2 ∥u − v∥2
! < 0. (33)
Consider one step update θ1 = θ0 − γF(θ0 ). We have ∥θ1 − θeq ∥22 = ∥θ0 − θeq ∥22 − γ ⟨F (θ0 ), θ0 − θeq ⟩ + γ 2 ∥F(θ0 )∥22 ≥ ∥θ0 − θeq ∥22 − γ ⟨F (θ0 ), θ0 − θeq ⟩ > ∥θ0 − θeq ∥22 . (33)
This construction holds for any c′ separating vector of u − v and fg−i (u), i.e., fg−i (u), c′ < 0 < ⟨u − v, c′ ⟩. In particular, it holds for every c′ ∈ C := {c′ ∈ Sd−1 ; ∥c′ − c∥2 < ω}, where s fg−i (u) fg−i (u) u−v 1 1 u−v ω = c, = − c, = − , ∥u − v∥2 ∥fg−i (u)∥2 2 2 ∥u − v∥2 ∥fg−i (u)∥2 Since fg−i (u) ̸∈ cone(u − v), we have ω > 0. Hence C is a non-empty open set of Sd−1 , and every c′ ∈ C separates u − v and fg−i (u). Indeed, u−v u−v u−v ′ ′ c, = c, + c − c, ≥ ω − ∥c′ − c∥2 > 0, ∥u − v∥2 ∥u − v∥2 ∥u − v∥2 and similarly, fg−i (u) fg−i (u) fg−i (u) ′ ′ c, = c, + c − c, ≤ −ω + ∥c′ − c∥2 < 0. ∥fg−i (u)∥2 ∥fg−i (u)∥2 ∥fg−i (u)∥2 20
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Appendix D. Deferred proofs of Section 3.2 This appendix contains the proof of Theorem 6 and Lemma 8, which was deferred from Section 3.2. Theorem 6 Assume the setting of Theorem 3, with gradients norm bounded by C > 0 and neighboring datasets inducing gradient perturbations of at most ρ > 0. Let AF denote the algorithm that outputs θT after T ≥ 1 iterations of (1) with aggregation rule F and step size γ ≤ 1/L. Then, Stab(AF ) ≤ γT Sn,C (F, ρ) + I(F ), (34) PT −1 where I(F ) := supS∼S ′ t=1 ∥θt − γF (θt ) − (θt′ − γF (θt′ ))∥2 − ∥θt − θt′ ∥2 . Furthermore, there exist convex, L-smooth, and C-Lipschitz loss functions such that Stab(AF ) ≥ 31 (γT Sn,C (F, ρ) + I(F )) .
(35)
Proof Let {θt }Tt=0 and {θt′ }Tt=0 be coupled trajectories initialized at θ0 = θ0′ , generated by neighbor′ ing datasets S ∼ S ′ . The iterates evolve according to θt+1 = θt − γF (θt ) and θt+1 = θt′ − γF ′ (θt′ ), where F and F ′ differ in a single gradient input. This difference is bounded in magnitude by at most ρ, as specified in Definition 5. For t ∈ {0, . . . , T − 1}, define the sensitivity term sF,t = ∥F ′ (θt′ ) − F (θt′ )∥2 ≤ Sn,C (F, ρ),
(36)
and the expansivity term σF,t = ∥θt − γF(θt ) − (θt′ − γF(θt′ ))∥2 − ∥θt − θt′ ∥2 . We evaluate the distance between trajectories at step t + 1 ′ ∥θt+1 − θt+1 ∥2 = ∥[θt − γF(θt ) − (θt′ − γF(θt′ ))] + γ(F(θt′ ) − F ′ (θt′ ))∥2 .
(37)
We then use the triangular inequality and reverse triangular inequality to upper and lower bound (37), ′ ∥θt+1 − θt+1 ∥2 ≤ ∥θt − γF(θt ) − (θt′ − γF(θt′ ))∥2 + γsF,t = ∥θt − θt′ ∥2 + σF,t + γsF,t ,
and ′ ∥θt+1 − θt+1 ∥2 ≥ ∥θt − γF(θt ) − (θt′ − γF(θt′ ))∥2 − γsF,t = ∥θt − θt′ ∥2 + σF,t − γsF,t ,
Summing over t = 0 to T − 1, and using the bounded sensitivity assumption (36) yields ∥θT − θT′ ∥2 ≤
T −1 X
σF,t + γ
t=0
and ∥θT − θT′ ∥2 ≥
T −1 X
T −1 X
sF,t ≤
t=0
σF,t − γ
t=0
T −1 X
T −1 X
σF,t + γT Sn,C (F, ρ),
(38)
σF,t − γT Sn,C (F, ρ).
(39)
t=0
sF,t ≥
t=0
T −1 X t=0
Taking the supremum over all neighboring datasets S ∼ S ′ in (38) and (39), noting that γT Sn,C (F, ρ) is independent of S, S ′ , we recover the definition of I(F ) and obtain the following upper bound T X ′ Stab(AF ) = sup ∥θT − θT ∥2 ≤ γT Sn,C (F ) + sup σF,t = γT Sn,C (F ) + I(F ), S∼S ′ S∼S ′ t=0
and the following lower bound Stab(AF ) ≥ sup
T −1 X
S∼S ′ t=0
σF,t − γT Sn,C (F, ρ) = I(F ) − γT Sn,C (F, ρ).
21
(40)
B OUDOU , L E BARS , G UPTA , AND B ELLET
Second lower bound. Moreover, by definition of Sn,C (F, ρ), for any arbitrarily small η > 0, there exist i ∈ [n] and gradients g1 , . . . , gn , gi′ ∈ B(0, C) such that ∥gi − gi′ ∥ ≤ ρ and ∥F (. . . , gi , . . . ) − F (. . . , gi′ , . . . )∥2 ≥ Sn,C (F, ρ) − η. We define ℓj (·) = ⟨gj , ·⟩ for j ̸= i, and for the differing i−th functions, we set ℓi (·) = ⟨gi , ·⟩ and ℓ′i (·) = ⟨gi′ , ·⟩. These functions are convex, L-smooth (with L = 0), and C-Lipschitz. Because the gradients are constant, the induced operators F and F ′ are constant and, for any θ0 ∈ Rd and t ≥ 1, ∥θT − θT′ ∥2 = ∥γT F (. . . , gi , . . . ) − F (. . . , gi′ , . . . ) ∥2 ≥ γT (Sn,C (F, ρ) − η). Because Stab(AF ) is the supremum over all neighboring datasets, it must be that Stab(AF ) ≥ γT (Sn,C (F, ρ) − η). Since this holds for all η > 0, we conclude Stab(AF ) ≥ γT Sn,C (F, ρ). Combining the lower bounds.
(41)
Finally, summing the two lower bounds (41) and (40) yields
3 Stab(AF ) = Stab(AF ) + 2 Stab(AF ) ≥ (I(F ) − γT Sn,C (F, ρ)) + 2γT Sn,C (F, ρ) = I(F ) + γT Sn,C (F, ρ). While I(F ) = 0 for positively affine aggregation rules, we show that this property does not hold for non-affine aggregation rules under mild assumptions. Indeed, building on the techniques of Theorems 1 and 3, we formalize below mild conditions capturing practical non-affine aggregations under which the expansivity of the update provably degrade algorithmic stability. The core difficulty in proving these lower bounds arises from the constraints of the stability analysis. While Corollary 7 establishes expansivity for specific input pairs, stability analysis requires expansivity to occur along two coupled trajectories {θt }Tt=1 and {θt′ }Tt=1 , with common initialization θ0 = θ0′ , generated by the update (1) whose inputs differ only through the i-th gradient, a difference induced by a singlesample perturbation. Formally, for the first step, we require θ1 −θ1′ = γ(fg−i (gi (θ0 ))−fg−i (gi′ (θ0 ))) to be a separating vector of gi (θ1 ) − gi (θ1′ ) and fg−i (gi (θ1 )) − fg−i (gi (θ1′ )). This means the hyperplane normal to θ1 − θ1′ separates these two vectors, ⟨gi (θ1 ) − gi (θ1′ ), θ1 − θ1′ ⟩ > 0 and ⟨fg−i (gi (θ1 )) − fg−i (gi (θ1′ )), θ1 − θ1′ ⟩ < 0. The set of separating vectors is non-empty if and only if fg−i (gi (θ1 ))−fg−i (gi (θ1′ )) ̸∈ cone(gi (θ1 )− gi (θ1′ )), a condition guaranteed for some gradient configurations since F is non-affine. However, constructing a setup where the specific vector θ1 − θ1′ is a separating vector is non-trivial. This complex construction is necessary to prove degraded stability for continuous aggregation rules, as they typically have a similar sensitivity than their affine counterparts. In contrast, discontinuous aggregation rules degrade stability even without violating co-coercivity. Indeed, a discontinuity induces the sensitivity term Sn,C (F, ρ) to not decay nicely with more data, and hence remains a bottleneck independent of the total dataset size. Lemma 8 Assume the setting of Theorem 6 and Assumption 1, with T = 2. Then, for any θ0 ∈ Rd , there exist convex, L−smooth and C−Lipschitz loss functions {ℓj }j∈[n] , ℓ′i such that I(F ) > 0. Proof We proceed constructively and fix the initialization to θ0 = 0 for convenience. 22
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Setup & loss functions. By Assumption 1, there exist i ∈ [n], g−i ∈ B(0, C)n−1 , p ∈ B(0, C) and δ̃ ̸= 0 such that for any rb > 0, there exist ϵ > 0, b0 ∈ B(p, rb ) ∩ B(0, C) such that ϵδ̃ = fg−i (b0 ) − fg−i (p). Moreover, for any rq > 0, there exists q ∈ B(p, rq ) ∩ B(0, C) ⟨p − q, δ̃⟩ > 0
and
⟨fg−i (p) − fg−i (q), δ̃⟩ < 0,
(42)
i.e., fg−i (p) − fg−i (q) ̸∈ cone(p − q). We set b1 := p, δ := ϵδ̃. Because ⟨p − q, δ⟩ > 0, there exists a symmetric matrix4 H1 ≻ 0 such that γH1 δ = p − q. Moreover, we can ensure λmax (H1 ) ≤ L2 by choosing rq sufficiently small. For θ ∈ Rd , we define for j ̸= i, ℓj (θ) = gj⊺ θ so ∇ℓj (θ) = gj , and the following quadratics5 1 ℓi (θ) = θ⊺ H1 θ + b⊺1 θ, thus gi (θ) = H1 θ + b1 , 2 1 ℓ′i (θ) = θ⊺ H0 θ + b⊺0 θ, thus gi′ (θ) = H0 θ + b0 . 2 θ −θ′
At θ0 = 0, gi (0) = b1 and gi′ (0) = b0 . Hence θ1 = −γfg−i (b1 ), θ1′ = −γfg−i (b0 ) and δ = 1 γ 1 . We set H0 so that gi′ (θ1′ ) = gi (θ1′ ) = b1 − γH1 fg−i (b0 ). As gi′ (θ1′ ) = b0 − γH0 fg−i (b0 ), we require γ(H0 − H1 )fg−i (b0 ) = b0 − b1 . Let x := γfg−i (b0 ) and y := b0 − b1 . We satisfy this by setting H0 = H1 + ∆, where ∆ is the ⊺ +xy ⊺ symmetric rank-2 matrix ∆ = yx∥x∥ − ⟨x,y⟩ xx⊺ . We can ensure H0 ≻ 0 and λmax (H0 ) ≤ L by 2 ∥x∥4 chosing rb sufficiently small such that such that ∥∆∥2 < min L2 , λmin (H1 ) = λmin (H1 ). Separation at T = 1.
Our construction yield the following identity. gi (θ1 ) = b1 − γH1 fg−i (b1 ) = p − γH1 fg−i (p).
(43)
gi (θ1′ ) = gi′ (θ1′ ) = b1 − γH1 (fg−i (b1 ) + δ) = gi (θ1 ) − γH1 δ = gi (θ1 ) − (p − q)
(44)
We next evaluate the separation property. We already have ⟨gi (θ1 ) − gi (θ1′ ), δ⟩ = ⟨γH1 δ, δ⟩ > 0. Then, to ensure the second inequality we rely on the continuity of fg−1 in the neighborhood of p. To do so, we analyze the limit of gi (θ1 ) and gi (θ1′ ) as q approaches p. Notice that we can choose H1 such that limrq →0 ∥H1 ∥2 = 0, therefore limrq →0 gi (θ1 ) = p and limrq →0 gi (θ1′ ) = q. Hence, lim ⟨fg−i (gi (θ1 )) − fg−i (gi (θ1′ )), δ⟩ = ⟨fg−i (p) − fg−i (q), δ⟩ < 0.
rq →0
(42)
⊺
⊺
δδ 4. Explicitly, H1 = γ1 (p−q)(p−q) + ι I − ∥δ∥ 2 ⟨p−q,δ⟩
for sufficiently small ι > 0.
′ 5. Formally, to ensure ℓi and ℓ′i represent empirical risks over adjacent datasets Pm S and S of size m, we define the ⊺ 1 ⊺ 1 individual sample loss as ℓ(θ; (H, b)) = 2 θ Hθ + b θ. Set ℓi (θ) = m k=1 ℓ(θ; (H1 , b1 )) = ℓ(θ; (H1 , b1 )) and ℓ′i (θ) = m−1 ℓ(θ; (H1 , b1 )) + ℓ(θ; (H ′ , b′ )) with H ′ = H1 + m∆ and b1 + m(b0 − b1 ). To preserve convexity, m 1 L-smoothness and C−Lipschitzness, we must bound ∥∆∥2 < m λmin (H1 ) and ∥b0 +m(b0 −b1 )∥2 < C, which can be done by shrinking rq and rb . We also enforce the C−Lipchitz continuous constraint for all θ ∈ Rd by truncating the quadratics outside the neighborhood where the proof is established.
23
B OUDOU , L E BARS , G UPTA , AND B ELLET
Consequence. A single step of update (1) yields (i) strict trajectories expansivity σF,1 > 0, with (ii) no triangular inequality slack ξF,1 = 0. (ii)
By (44), we have F ′ (θ1′ ) = fg−i (gi′ (θ1′ )) = fg−i (gi (θ1′ )) = F(θ1′ ). This proves ξF,1 = ∥θ2 − θ2′ ∥2 − ∥θ1 − γF(θ1 ) − (θ1′ − γF(θ1′ ))∥2 + γ∥F ′ (θ1′ ) − F (θ1′ )∥2 = 0.
(i) Moreover, we prove σF,1 = ∥θ1 − γF(θ1 ) − (θ1′ − γF(θ1′ ))∥2 − ∥θ1′ − θ1 ∥2 > 0. In fact, squaring ∥θ1 − γF(θ1 ) − (θ1′ − γF(θ1′ ))∥2 and isolating the dot product, we have −2γ⟨F(θ1′ ) − F (θ1 ), θ1′ − θ1 ⟩ = 2γ 2 ⟨fg−i (gi (θ1′ )) − fg−i (gi (θ1 )), δ⟩ > 0 Overall, we have ∥θ2 − θ2′ ∥2 = σF,1 + γ∥δF,0 ∥2 > σF,1 .
Appendix E. Alternative proof of Theorem 1 In what follows, we present an alternative proof of Theorem 1 based on an analysis of the Jacobian of the induced operator F. Our first step is to establish that F is differentiable almost everywhere, a property that carries over to the aggregation rule F itself. While this approach yields comparable insights, it comes with a notable drawback: the argument requires integrating back the Jacobians to recover global properties of F . In full generality, this integration step necessitates additional, albeit mild, regularity assumptions on F (the weakest being absolute continuity on lines), as well as careful manipulation of sets of Lebesgue measure zero and extensions of properties of monotone operators to input-wise monotone operators. While these technical requirements are artifacts of the proof technique rather than intrinsic to the result, we present the derivation because it provides a different perspective, even if similar, and the extension of known monotone operator properties to input-wise monotone operators are of independent interest. Theorem 25 Let f : Rd → Rd be a monotone operator defined on the entire space. Then f is differentiable almost everywhere (with respect to the Lebesgue measure). Proof Since f is monotone, Zorn’s Lemma guarantees the existence of a maximal monotone operator f˜ : Rd → P(Rd ) that extends f (Bauschke and Combettes, 2011, Theorem 20.21). This means that the graph of f is contained in the graph of f˜, Graph(f ) ⊆ Graph(f˜) := {(x, y) ∈ Rd × Rd | y ∈ f˜(x)}, which is maximal with respect to graph inclusion among monotone operators. In other words, f (x) ∈ f˜(x) for all x ∈ Rd . From Alberti and Ambrosio (1996, Theorem 3.2), any maximal monotone operator on an open domain is differentiable almost everywhere. Let D ⊂ Rd be the set of points where f˜ is differentiable. We know that Rd \ D has Lebesgue measure zero. Fix a point x0 ∈ D. By the definition of differentiability for a set-valued operator: (1) f˜(x0 ) must be a singleton and, with a slight abuse of notation, we identify this set with its unique element; (2) There exists a linear map (Jacobian) Lx0 : Rd → Rd such that lim
x→x0 y∈f˜(x)
∥y − f˜(x0 ) − Lx0 (x − x0 )∥2 = 0. ∥x − x0 ∥2 24
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Since Graph(f ) ⊆ Graph(f˜), the condition y ∈ f˜(x) is satisfied by y = f (x). Furthermore, since f˜(x0 ) is a singleton, f (x0 ) = f˜(x0 ). Substituting these into the limit expression, we restrict the limit to points in the graph of f : lim
x→x0
∥f (x) − f (x0 ) − Lx0 (x − x0 )∥2 = 0. ∥x − x0 ∥2
This is exactly the definition of Fréchet differentiability for the single-valued function f at x0 . Since f is differentiable at every point in D, and Rd \ D has Lebesgue measure zero, f is differentiable almost everywhere. The central condition for the monotonicity of the induced aggregator is that for any admissible loss Hessian, the Jacobian of the induced aggregator must be positive semi-definite. Crucially, this condition implies structure over the partial Jacobians of the underlying aggregation rule used. d , DH is Lemma 26 Let d ≥ 2, and D ∈ Rd×d a matrix. If for all symmetric p.s.d. matrix H ∈ S+ p.s.d., that is ⊺ d d ⊺ ⊺ DH + (DH) ∀H ∈ S+ , ∀v ∈ R , v DHv = v v ≥ 0, 2
then there exists α ∈ R such that D = αI. Proof In what follows, we restrict our attention to the case d = 2 without loss of generality. Indeed, our analysis only requires verifying whether a given matrix is positive semi-definite, a property that can be falsified by examining its 2 × 2 principal submatrices. Specifically, a matrix is positive semi-definite if and only if all principal submatrices of its symmetric part are positive semi-definite. Consequently, establishing a violation of positive semi-definiteness in dimension d = 2 immediately extends to all dimensions d ≥ 2, by considering matrices H and vectors v that act nontrivially on only two coordinates and vanish ones. More precisely, on the remaining D D aa ab ∈ R2×2 denote the principal let a, b ∈ [d] be distinct indices, a < b, and D(2) := Dba Dbb 2 and v (2) ∈ R2 , we construct submatrix of D restricted to these coordinates. For any H (2) ∈ S+ d d (2) (2) H ∈ S+ and v ∈ R by embedding H and v at indices a, b and setting all other entries to (2) (2) (2) zero, i.e., Hk,l = Hl,k = 0, ∀k, l ∈ / {a, b}, Haa = H11 , Hbb = H22 , Hab = Hba = H12 , and (2) (2) vk = 0, ∀k ∈ / {a, b}, va = v1 , vb = v2 . The condition v ⊺ DHv ≥ 0 simplifies to v ⊺ DHv =
X i,j∈{a,b}
vi
X
Dik Hkj vj = v (2)⊺ D(2) H (2) v (2) ≥ 0.
k∈{a,b}
We conclude by applying the following derivation to all combinaison of a, b ∈ [d]. Consider the 2 × 2 submatrix D(2) defined above, and let S :=
D(2) + D(2)⊺ , 2
A :=
D(2) − D(2)⊺ 2
denote its symmetric and anti-symmetric parts, respectively, where we omit the superscript for readability. We work in the rotated coordinate system that diagonalizes S (i.e., ṽ = Qv, where 25
B OUDOU , L E BARS , G UPTA , AND B ELLET
Q is some orthogonal matrix). By the spectral theorem, there exists an orthogonal matrix Q such that λ1 0 ⊺ S = QS̃Q , where S̃ = , λ1 , λ2 ∈ R. 0 λ2 Moreover, since orthogonal transformations map orthonormal bases to orthonormal bases and preserve anti-symmetry, the transformed matrix à remains anti-symmetric and therefore admits the following canonical representation à = Q⊺ AQ =
0 −α , α 0
where
α ∈ R.
2 , we test this condition using two specific choices, Since D̃(2) H must be p.s.d. for all H ∈ S+
⊺ 1 1 1 1 H1 = = 1 1 1 1
H2 =
and
⊺ 1 1 1 −1 = . −1 −1 −1 1
Specifically, for each choice, we compute the determinant of the symmetric part of D̃(2) H to verify positive semi-definiteness. (1) For H1 , we have D̃
(2)
λ1 − α λ 1 − α 1 1 λ1 −α . = H1 = (S̃ + Ã)H1 = λ2 + α λ 2 + α 1 1 α λ2
Thus, the symmetric part is D̃(2) H1 + (D̃(2) H1 )⊺ = 2
λ1 +λ2 2
λ1 − α λ1 +λ2 2
λ2 + α
.
Taking the determinant yields det
D̃(2) H1 + (D̃(2) H1 )⊺ 2
!
= (λ1 − α)(λ2 + α) −
λ1 + λ2 2
= −α2 + α(λ1 − λ2 ) + "
λ1 − λ2 = − α − 2α + 2 λ1 − λ2 2 =− α− . 2 2
2
λ1 λ2 −
λ1 − λ2 2
λ1 + λ2 2 2 #
2 !
(2) For H2 , we have D̃
(2)
H2 = (S̃ + Ã)H2 =
λ1 −α α λ2
26
1 −1 −1 1
λ1 + α −λ1 − α = . α − λ2 λ2 − α
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Thus, the symmetric part is D̃(2) H2 + (D̃(2) H2 )⊺ = 2
λ1 + α 2 − λ1 +λ 2
2 − λ1 +λ 2 λ2 − α
.
Taking the determinant yields det
D̃(2) H2 + (D̃(2) H2 )⊺ 2
!
= (λ1 + α)(λ2 − α) −
λ1 + λ2 2
2
2
λ1 λ2 −
"
= −α − α(λ1 − λ2 ) + λ1 − λ2 + 2 λ1 − λ2 2 =− α+ . 2
= − α2 + 2α
λ1 − λ2 2
λ1 + λ2 2 # 2
2 !
For D̃(2) H1 and D̃(2) H2 to be p.s.d. in both case, i.e., the determinants to be non-negative, we must have λ1 − λ2 = 0 (isotropy), α = 0 (symmetry). This implies that the considered principal submatrix of D̃(2) = λI (2) of D is a scalar multiple of the identity matrix in the rotated basis. Since the identity matrix is rotation-invariant, D(2) = Q⊺ D̃(2) Q = Q⊺ λI (2) Q = λQ⊺ Q = λI (2) is a scalar multiple of the identity in the original basis. As this result holds for any pair of indices a, b ∈ [d], we conclude that D = λI for a λ ∈ R+ . This structure, together with the assumed regularity assumptions, enables one to conclude, by integration, that the aggregation rule must be affine. To prove that the result holds under the weak regularity assumption of absolute continuity on lines, we establish the following technical lemmas. Lemma 27 Let F : (Rd )n → Rd be a input-wise monotone function. Then F is locally bounded. Proof We proceed by induction on the number of inputs n. Base Case (n = 1). F is a standard monotone operator defined on the entire space Rd , therefore F is locally bounded (Borwein and Fitzpatrick, 1989, Theorem 2). Inductive Step. Assume local boundedness holds for n − 1 inputs. Let K be a compact subset of (Rd )n . Let K1 denote the projection of K onto the first input’s coordinate, and K−1 the projection onto the remaining coordinates. We construct a “cage” P = {p1 , . . . , pm } ⊂ Rd consisting of m ≥ d + 1 affinely independent points, such that K1 is contained in the interior of the convex hull of P . We rely on the rwo geometric quantity determined by P and K. • The maximum radius, R := maxk∈[m] maxg1 ∈K1 ∥pk − g1 ∥2 < ∞. 27
B OUDOU , L E BARS , G UPTA , AND B ELLET
• The minimum unormalized cosine measure, representing the ability of the cage to bound all directions, γ := min ucm(g1 ), where ucm(g1 ) := min g1 ∈K1
max
⟨v, pk − g1 ⟩.
∥v∥2 =1 k∈{1,...,m}
The condition that K1 ⊂ int(conv(P )) ensures that for any g1 ∈ K1 , the vectors {pk − g1 }k∈[m] positively span Rd , or equivalently, that ucm(g1 ) > 0 for all g1 ∈ K1 (Conn et al., 2009, Theorem 2.3). Finally, since ucm is continuous and stricly positive on the compact K1 , it attains a minimum, which is strictly positive γ > 0. Consider any configuration g = (g1 , g−1 ) ∈ K. If F (g) = 0, the bound ∥F (g)∥2 = 0 holds trivially. Assume henceforth that ∥F (g)∥2 > 0. For each vertex pk ∈ P , monotonicity in the first variable implies ⟨F (g) − F (pk , g−1 ), g1 − pk ⟩ ≥ 0. Rearranging terms, ⟨F (g), pk − g1 ⟩ ≤ ⟨F (pk , g−1 ), pk − g1 ⟩.
(45)
(g) By the definition of γ, there exists an index k ∗ such that ⟨ ∥FF(g)∥ , pk∗ − g1 ⟩ ≥ γ. Multiplying by 2 ∥F (g)∥2 , we get ⟨F (g), pk∗ − g1 ⟩ ≥ γ∥F (g)∥2 . (46)
Combining the lower bound 46 with the upper bound 45 gives ∥F (g)∥2 ≤
1 ⟨F (pk∗ , g−1 ), pk∗ − g1 ⟩. γ
(47)
For each fixed pk , fpk := F (pk , ·) depends on n − 1 variables and is input-wise monotone. By the inductive hypothesis, it is locally bounded. Since K−1 is compact, there exists a constant ′ )∥ ≤ M ′ ∈K Mn−1 < ∞ such that maxk∈[m] supg−1 ∥F (pk , g−1 2 n−1 . Consequently, applying the −1 Cauchy–Schwarz inequality to (46) yields ∥F (g)∥2 ≤
R Mn−1 , γ
where R, γ and Mn−1 are constants independent of g. Since g ∈ K was fixed arbitrarily, this proves uniform boundedness of F on K. Finally, as K was an arbitrary compact subset of (Rd )n , F is locally bounded on (Rd )n . By showing that the ACL assumption, along with the other hypotheses, ensures Sobolev regularity of the aggregation, we deduce that it coincides almost everywhere with an affine aggregator. Lemma 28 Let d ≥ 2 and F : (Rd )n → Rd be ACL (cf. Definition 16), input-wise monotone and input-wise almost everywhere differentiable (cf. Definition 18). If F has input-wise constant partial Jacobians almost everywhere (i.e., for all i ∈ [n], for all g−i ∈ (Rd )n−1 , and for a.e. gi ∈ Rd , Di F (g1 , . . . , gn ) = αi Id , where α ∈ Rn ), then P F is input-wise affine almost everywhere (i.e., for a.e. (g1 , . . . , gn ) ∈ (Rd )n , F (g1 , . . . , gn ) = nj=1 αj gj + C, where C ∈ Rd ). 28
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
P Proof Define the linear function A : (Rd )n → Rd , g = (g1 , . . . gn ) 7→ nj=1 αj gj . Consider the difference function R := F − A. Since A is linear and F is ACL, the difference R is ACL. By linearity of the derivative, the input-wise partial Jacobians of R satisfies, for i ∈ [n], Di R = Di F − Di A = αi Id − αi Id = 0
almost everywhere.
In other words, all partial derivatives of R vanish almost everywhere. To demonstrate that R is constant almost everywhere, we establish that it belongs to the Sobolev 1,1 space Wloc ((Rd )n ; Rd ) (cf. Definition 17). First, we observe that R ∈ L1loc ((Rd )n ; Rd ) because F ∈ L1loc ((Rd )n ; Rd ), as ensured by Lemma 27. We now apply the characterization of Sobolev spaces via the ACL property. According to Leoni (2017, Theorem 11.45, applied locally), a function (1,1) belongs to Wloc ((Rd )n ; Rd ) if and only if it is locally integrable and admits an ACL representative whose classical partial derivatives are locally integrable. This condition is satisfied by R, which is ACL and has classical partial derivatives equal to zero almost everywhere (implying the are trivially 1,1 ((Rd )n ; Rd ). Finally, since the domain (Rd )n is connnected, locally integrable). Thus R ∈ Wloc and observing that the weak partial derivatives of R coincide with its classical derivaties almost everywhere (Leoni, 2017, Theorem 11.45), the fact that these derivatives vanish almost everywhere implies that R is constant almost everywhere (see, e.g., Leoni, 2017, Exercise 10.28). The following measure-theoretic slicing property is a direct consequence of Fubini’s theorem and will be instrumental in our subsequent arguments. Lemma 29 Let E ⊂ (Rd )n be a set of full Lebesgue measure. Let g ∈ (Rd )n be decomposed as g = (g1 , g−1 ), where g1 ∈ Rd and g−1 ∈ (Rd )n−1 . Then, for almost every g−1 ∈ (Rd )n−1 , the slice Eg−1 = {u ∈ Rd | (u, g−1 ) ∈ E} has full Lebesgue measure in Rd . Proof Let λ(k) denote the Lebesgue measure on the product space Rk , k ∈ N. Consider the indicator function 1(Rd )n \E : (Rd )n → {0, 1}. Then, Z (Rd )n
1(Rd )n \E (g) dλ(dn) (g) = λ(dn) ((Rd )n \ E) = 0.
Since 1(Rd )n \E is non-negative and measurable, Fubini’s Theorem (Leoni, 2017, Theorem B.58) allows us to compute this integral as an iterated integral Z Z (d) 1(Rd )n \E (g1 , g−1 ) dλ (g1 ) dλ(d(n−1)) (g−1 ) = 0. (48) (Rd )n−1
Rd
Define the function h : (Rd )n−1 → [0, ∞] by the inner integral, Z h(g−1 ) := 1(Rd )n \E (g1 , g−1 ) dλ(d) (g1 ) = λ(d) (Rd \ Eg−1 ). Rd
Substituting h back into (48), we have Z
h(g−1 ) dλ(d(n−1)) (g−1 ) = 0.
(Rd )n−1
29
B OUDOU , L E BARS , G UPTA , AND B ELLET
We have a non-negative function h whose integral is zero, hence h must be zero almost everywhere. As a result, for almost every g−1 ∈ (Rd )n−1 , λ(d) (Rd \ Eg−1 ) = 0. Finally, we upgrade the almost-everywhere equality to equality everywhere by combining the input-wise monotonicity of one function with the continuity of the other. Lemma 30 Let F : (Rd )n → Rd be a input-wise monotone function (cf. Definition 18) and A : (Rd )n → Rd be a continuous function. If F = A almost everywhere, then F = A everywhere. Proof We proceed by induction on the number of inputs n. Base Case (n = 1). The function F is monotone on Rd (with only one input, input-wise monotonicity is standard monotonicity). Let E = {g ∈ Rd : F (g) = A(g)}. Since the equality holds almost everywhere, Rd \ E has measure zero, implying E is dense in Rd . Fix an arbitrary point g ′ ∈ Rd . By the monotonicity of F , for any g ∈ E, ⟨F (g) − F (g ′ ), g − g ′ ⟩ = ⟨A(g) − F (g ′ ), g − g ′ ⟩ ≥ 0.
(49)
Fix an arbitrary unit vector v ∈ Rd and a scalar ϵ > 0. By the density of E, there exists a sequence {gk }k∈N ⊂ E converging to g ′ + ϵv. Substituting gk into (49), taking the limit k → ∞, and using the continuity of A, ⟨A(g ′ + ϵv) − F (g ′ ), (g ′ + ϵv) − g ′ ⟩ = ϵ⟨A(g ′ + ϵv) − F (g ′ ), v⟩ ≥ 0. Dividing by ϵ > 0 and taking the limit ϵ → 0, again using the continuity of A, ⟨A(g ′ ) − F (g ′ ), v⟩ ≥ 0. Since v was arbitrary, we can repeat the argument for −v to get ⟨A(g ′ )−F (g ′ ), −v⟩ ≥ 0. Therefore, ⟨A(g ′ ) − F (g ′ ), v⟩ = 0 for all unit vector v ∈ Rd , implying F (g ′ ) = A(g ′ ). Inductive Step. Assume the theorem holds for n − 1 inputs. Let g = (g1 , . . . , gn ) ∈ (Rd )n be decomposed as (g1 , g−1 ), where g1 ∈ Rd is the first input’s input and g−1 ∈ (Rd )n−1 represents the remaining inputs. Let E ⊂ (Rd )n be the set of full measure where F = A. Step 1 (Extension along the first input, i.e., fixing g−1 ). By Fubini’s Theorem (cf. Lemma 29 for full details), there exists a set Ω ⊂ (Rd )n−1 of full Lebesgue measure such that for any fixed configuration g−1 ∈ Ω, the section Eg−1 = {u ∈ Rd : (u, g−1 ) ∈ E} has full measure in Rd . Fix an arbitrary g−1 ∈ Ω. Define the partial function fg−1 : Rd → Rd , u 7→ F (u, g−1 ). The function fg−1 is monotone (by input-wise monotonicity of F ) and equals the continuous function u 7→ A(u, g−1 ) almost everywhere (specifically on Eg−1 ). By the base case n = 1 above, fg−1 (u) = A(u, g−1 ) for all u ∈ Rd . Thus, F (g1 , g−1 ) = A(g1 , g−1 ) holds for all g1 ∈ Rd whenever g−1 ∈ Ω. Step 2 (Extension to the remaining inputs, i.e., fixing g1 ). Now, fix an arbitrary g1 ∈ Rd . Define the partial function Fg1 : (Rd )n−1 → Rd , g−1 7→ F (g1 , g−1 ). The function Fg1 inherits inputwise monotonicity from F . From the result of Step 1, we know that Fg1 (g−1 ) = A(g1 , g−1 ) for all g−1 ∈ Ω. Since Ω has full measure in (Rd )n−1 , Fg1 matches the continuous function g−1 7→ A(g1 , g−1 ) almost everywhere. By the inductive hypothesis on n − 1 inputs, applied to Fg1 , Fg1 must match A(g1 , ·) everywhere. Therefore, Fg1 (g−1 ) = A(g1 , g−1 ) for all g−1 ∈ (Rd )n−1 . Since g1 was arbitrary, we conclude F = A. 30
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Finally, we present an alternative proof of Theorem 1, by leveraging the lemmas established above. In this proof, because we differentiate both the aggregation rule and the induced operator almost everywhere and then integrate back expressions involving the Jacobians of F , we require F to be absolutely continuous on lines (ACL): for each coordinate, the restriction F to compact intervals must be absolutely continuous for almost every fixed choice of the remaining coordinates (cf. Definition 15). The ACL property is standard in real and functional analysis and is satisfied by broad classes of functions including Sobolev and locally Lipschitz functions. It originates in the analysis of Sobolev functions, where ACL plays a key role in relating weak and pointwise differentiability (cf. Leoni, 2017, Section 11.3). In particular, the ACL assumption is required only to justify the very last integration step in the proof, since monotonicity alone only guarantees bounded variations but does not rule out singular behaviors such as Cantor-type singular functions (cf. Alberti and Ambrosio, 1996, Paragraph 5.6). Theorem 31 Let d > 1, and consider the model update rule (1) with F : (Rd )n → Rd an absolute continuous on lines (ACL) aggregation rule. F is a monotonic operator for all gradients {gi (·)}i∈[n] induced by convex functions if and only if F is an affine aggregator, i.e., there exists α ∈ Rn+ and C ∈ Rd , independent of the inputs, such that for any input vectors (g1 , . . . , gn ) ∈ (Rd )n , F (g1 , . . . , gn ) =
n X
αk gk + C.
k=1
Proof In what follows, we only use differentiability in the Fréchet sense, and consider the Lebesgue measure over the Borel σ-algebra. First, if F is an affine aggregator, it is immediate that F preserves monotonicity. We now turn to the converse. The proof proceeds in three steps. Step 1. F must be differentiable almost everywhere and its Jacobian, when it exists, must be positive semi-definite. Indeed, by Lemma 25, F is almost everywhere differentiable for any set of convex function {ℓi }i∈[n] . Hence, fixing an arbitrary set of functions {ℓi }i∈[n] , for almost every θ ∈ Rd , F admits the following Taylor expansion for arbitrary u ∈ Rd and ε ∈ R, F(θ + εu) − F(θ) = ε∇F(θ)u + r(εu), 2 where the remainder r satisfies limε→0 ∥r(εu)∥ = 0. Then, by the monotonicity of F, we have ε
⟨εu, ε∇F(θ)u + r(εu)⟩ = ε2 ⟨u, ∇F(θ)u⟩ + ε⟨u, r(εu)⟩ ≥ 0.
(50)
Hence, by dividing (50) by ε2 and taking the limit as ε → 0, we obtain ⟨u, ∇F(θ)u⟩ ≥ 0. That is, the jacobian ∇F (θ) is positive semi-definite but not necessarily symmetric. Equivalently, its symmetric part verifies ∇F(θ) + ∇F(θ)⊺ ⪰ 0. (51) 2 31
B OUDOU , L E BARS , G UPTA , AND B ELLET
Step 2. For any input index i ∈ [n] and any configuration g−i := (. . . , gi−1 , gi+1 , . . .) ∈ (Rd )n−1 , the partial mapping fi (θ) := F (. . . , gi−1 , θ, gi+1 , . . .) must be monotone and differentiable almost everywhere. We refer to a function satisfying these conditions as input-wise monotone and inputwise almost everywhere differentiable. Indeed, fix an arbitrary index i ∈ [n] and arbitrary vectors g−i ∈ (Rd )n−1 . Define the functions 1 ℓi (θ) = θ⊺ θ 2
and for j ̸= i,
ℓj (θ) = gj⊺ θ.
We have, F (θ) = fi (θ). Therefore, fi inherits properties from F, i.e., it is monotone and almost everywhere differentiable. Step 3.
F must be an affine aggregator.
(i) We now study the implications of Step 1 and Step 2. At any point θ where F is differentiable and F admits partial Jacobians at (∇ℓ1 (θ), . . . , ∇ℓn (θ)), the chain rule gives ∇F(θ) =
n X
Di F (∇ℓ1 (θ), . . . , ∇ℓn (θ)) ∇2 ℓi (θ),
(52)
i=1
where, for i ∈ [n], Di F is the d × d partial Jacobian of F with respect to its i-th input gi . Fix an arbitrary index i ∈ [n] and an arbitrary configuration g−i ∈ (Rd )n−1 . Let gi ∈ Rd be chosen from the set of full measure where the partial Jacobian of F with respect to the i-th input exists. Let H be an arbitrary symmetric p.s.d. matrix, chosen independently from (g1 , . . . , gn ). Define the following convex loss functions, ℓj (θ) = gj⊺ θ
for j ∈ [n] \ {i},
and
1 ℓi (θ) = gi⊺ θ + θ⊺ Hθ. 2
At θ = 0 and for each j ∈ [n], ∇ℓj (0) = gj and ∇2 ℓj (0) = 0 for j ̸= i or H for j = i. Since Di F (g1 , . . . , gn ) exists and ∇2 ℓj (0) = 0 for j ̸= i, eq. 52 implies that F is differentiable at 0, with derivative given by ∇F(0) = Di F (g1 , . . . , gn )H.
(53)
Consequently Di F (g1 , . . . , gn )H must be positive semi-definite, an implication that holds for any symmetric p.s.d. H. Therefore, by Lemma 26, for every i ∈ [n], every configuration g−i ∈ (Rd )n−1 , there must exist a scalar function αi such that for almost every gi ∈ Rd , Di F (g1 , . . . , gn ) = αi (g1 , . . . , gn )Id .
(54)
(ii) Let F = (F1 , . . . , Fd )⊺ the d scalar component functions of F and gi = (gi1 , . . . , gid )⊺ , where we denote gik the k−th component of the vector gi . The (k, l)-th entry of the d × d d n k matrix Di F is ∂F ∂gil . (54) implies that for almost every (g1 , . . . , gn ) ∈ (R ) , k (a) for off-diagonal (l ̸= k) terms: ∂F ∂gil (g1 , . . . , gn ) = 0;
∂Fk (b) for diagonal (l = k) terms: ∂g (g1 , . . . , gn ) = αi (g1 , . . . , gn ). ik
32
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
From (a) and i ∈ [n], the k-th component Fk does not depend on the l-th component of gi when l ̸= k. Since this holds for all i, Fk can only depend on the k-th component of all input vectors, i.e., (g1k , . . . , gnk ). This means F is a component-wise aggregator, i.e., there exist functions ϕk : Rn → R such that, almost everywhere Fk (g1 , . . . , gn ) = ϕk (g1k , . . . , gnk ).
(55)
From (b) and eq. 55 we have, for i ∈ [n], k ̸= l ∈ [d], and almost every (g1 , . . . , gn ) ∈ (Rd )n , ∂ϕk ∂ϕl (g1k , . . . , gnk ) = αi (g1 , . . . , gn ) = (g1l , . . . , gnl ). ∂gik ∂gil Since the left-hand side only depends on the variables {gik }i∈[n] and the right-hand side depends exclusively on the disjoint set {gil }i∈[n] both terms must be independent of their respective arguments. Therefore, αi (g1 , . . . , gn ) must be a constant function (we denote this constant αi , slightly overloading notation). Therefore, for almost every (g1 , . . . , gn ) ∈ (Rd )n Di F (g1 , . . . , gn ) = αi Id .
(56)
P (iii) Let denote A : (Rd )n → Rd , (g1 , . . . , gn ) 7→ ni=1 αi gi + C, where C := F (0, . . . , 0) ∈ Rd . Under the ACL assumption, (56) together with the input-wise montonicity of F imply, via Lemma 28, that F = A almost everywhere, and Lemma 30 upgrades this to equality everywhere.
Notably, and as mentioned in Section 2, an additional structural assumption to make the preservation of monotonicity (and co-coercive inequality) possible with non-affine aggregation rule is that the loss function is coordinate-wise separable (e.g., CWTM, cf. Lemma 4). We recover the underlying reason also in the alternative proof: the key step (53) relies on the ability to choose arbitrary symmetric p.s.d. matrices as Hessians of the underlying loss function. When the structure of the loss function restricts this flexibility—for example, when it is coordinate-wise separable and thus admits only diagonal Hessians—the argument no longer applies. More generally, the condition stated in Lemma 26 can be of great value for two reasons. First, it provide insights into the necessary assumptions that a loss function must satisfy to guarantee that monotonicity could be preserved by any aggregation rule. Second, it also shed light on the structural properties that candidate aggregation rules must exhibit to preserve monotonicity under these assumptions when integrated. Interestingly, the alternative proof extend to the case when we consider the co-coercivity inequality. That is, the aggregated operator F(θ) = F (g1 (θ), . . . , gn (θ)), preserves the co-coercive inequality of every convex and L-smooth loss function gradients {gi }i∈[n] , i.e., there exists LF > 0 such that for all θ, ω ∈ Θ: ⟨θ − ω, F(θ) − F (ω)⟩ ≥
1 ∥F(θ) − F(ω)∥22 , LF
if and only F is an affine aggregator. Indeed, in our proof, we only used convex and smooth loss functions. Moreover, we no longer require to assume F ACL as, by the Cauchy-Schwarz inequality, F is LF −Lipschitz continuous, a property that extend to F . 33
B OUDOU , L E BARS , G UPTA , AND B ELLET
Lemma 32 Let d > 1, and consider the model update rule (1). If the aggregated operator F is Lipschitz continuous for every input gradients {gi }i∈[n] induced by L-smooth functions, then F is itself Lipschitz continuous. Proof Let us show this by contradiction. Assume F is not Lipschitz continuous. This implies that F must be non-Lipschitz with respect to at least one of its arguments. In fact, if F were separately Lipschitz in all arguments, it would be globally Lipschitz. This is due to the fact that, we can construct a telescoping path from any vector G = (g1 , . . . , gn ) to any other vector G′ = (g1′ , . . . , gn′ ), with G(i) = (g1 , . . . , gi′ , . . . , gn′ ), i ∈ [n], ∥F (G) − F (G′ )∥2 = ∥
n X
F (G(i−1) ) − F (G(i) )∥2 ≤
i=1
≤
n X
∥F (G(i−1) ) − F (G(i) )∥2
i=1
Li ∥G(i−1) − G(i) ∥2 ≤ max Li i∈[n]
i=1
n X
n X
∥gi − gi′ ∥2 = max Li
i=1
i∈[n]
≤
n q X ∥gi − gi′ ∥22 i=1
√
n max Li ∥G − G′ ∥2 i∈[n]
Let’s assume F is not Lipschitz in its i-th argument. This means that there exist a set of n − 1 vector g−i := (g1 , . . . , gi−1 , gi+1 , . . . , gn ) such that Fg−i : g → F (g1 , . . . , gi−1 , g, gi+1 , . . . , gn ) is not Lipschitz i.e., ∀M > 0, ∃gi , gi′ with ∥F (G) − F (G′ )∥2 = ∥Fg−i (gi ) − Fg−i (gi′ )∥ > M ∥gi − gi′ ∥2 = M ∥G − G′ ∥2 ,
(57)
where G = (g1 , . . . , gi , . . . , gn ) and G′ = (g1 , . . . , gi′ , . . . , gn ). Based on g−i , we can construct the following set of L-smooth convex functions: for j ̸= i, let ℓj (θ) = gjT θ, and ℓi (θ) = L2 ∥θ∥22 . Using these functions, the aggregated operator F(θ) becomes F(θ) = F (g1 , . . . , Lθ, . . . , gn ). From Step 1, we know that there exist a constant LF such that F is LF -Lipschitz. Fix M = LLF and let gi , gi′ be the associated vector from the condition (57). By the LF -Lipschitz condition on F we have 1 1 LF ∥F (G) − F (G′ )∥2 = ∥F( gi ) − F ( gi′ )∥2 ≤ ∥gi − gi′ ∥2 . L L L Combining this with (57), we get LF LF ∥gi − gi′ ∥2 < ∥F (G) − F (G′ )∥2 ≤ ∥gi − gi′ ∥2 , L L which simplifies to LF LF < . L L This is a contradiction, proving that F must be Lipschitz continuous.
34
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Appendix F. Component-Wise Trimmed Mean Properties In this section, we establish properties of the Component-Wise Trimmed Mean aggregation rule (CWTM) useful for analyzing algorithmic stability of the update (1) when F = CWTM. To establish non-expansiveness under coordinate-wise separable loss functions, we rely on the following technical lemma, which is central to the proof of Lemma 11. Lemma 33
Let x, x′ ∈ Rn . There exist indices α, β ∈ {1, . . . , n} such that: x − x′ β ≤ TM(x) − TM(x′ ) ≤ x − x′ α .
Proof Let n ∈ N, f ∈ {0, . . . , ⌊ n2 ⌋}, and x, x′ ∈ Rn (i) Suppose TM(x) = TM(x′ ). We then consider two cases: – If there exists an index i ∈ {1, . . . , n} such that xi = x′i , the lemma is trivially true with α = β = i. – Otherwise, xi ̸= x′i , ∀i ∈ {1, . . . , n}. In this case, there must be at least one index β where [x − x′ ]β < 0 and at least one index α where [x − x′ ]α > 0. If all differences were strictly positive or strictly negative, this would contradict the assumption that TM(x) = TM(x′ ). (ii) Suppose TM(x) ̸= TM(x′ ). Here, we invoke the translation equivariance property of the trimmed mean. Specifically, let 1 = (1, . . . , 1) ∈ Rn , and define the translation operator Ta1 (x) := x − a1 for any a ∈ R. Then, for any a ∈ R, the trimmed mean satisfies: TM(Ta1 (x)) = TM(x − a1) = TM(x) − a Substituting a = TM(x) − TM(x′ ), we have TM(Ta1 (x)) − TM(x′ ) = 0. We then invoke the first case: there exist indices α, β ∈ {1, . . . , n} such that: Ta1 (x) − x′ β ≤ TM(Ta1 (x)) − TM(x′ ) ≤ Ta1 (x) − x′ α , =⇒ x − x′ β − a ≤ TM(x) − TM(x′ ) − a ≤ x − x′ α − a, =⇒ x − x′ β ≤ TM(x) − TM(x′ ) ≤ x − x′ α . This concludes the proof. Lemma 11 contrasts with the general convex and strongly convex smooth settings, where, as illustrated in Remark 34, a non-expansive update cannot, in general, be guaranteed. Remark 34 To establish, in general, a non-expansivity result for the CWTM update rule, it would be necessary that the scalar product in (θ) − GCWTM (ω)∥22 ∥GCWTM γ γ = ∥θ − ω∥22 + γ 2 ∥CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω))∥22 − 2γ⟨CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω)), θ − ω⟩ 35
B OUDOU , L E BARS , G UPTA , AND B ELLET
is strictly positive, that is the CWTM preserve the co-coercivity of the underlying loss function. As we will illustrate bellow, this is false in general. This is because the sets of selected indices differ across dimensions—that is S (k) ̸= S (k)′ with k ∈ {1, . . . , d}—which disrupts the alignment needed to preserve the co-coercivity property. Below, we present an example illustrating that CWTM does not preserve the co-coercivity property of an underlying convex and smooth loss function. Specifically, let d = 2, n = 3 and f = 1. We explicitly construct the example illustrated in Figure 1. We consider: • the convex and smooth loss function: √ ∀w ∈ Rd , (x, y) ∈ B(0, L) × R :
1 2 ℓ(w, (x, y)) = (wT x − y) 2 ∇ℓ(w, (x, y)) = (wT x − y)x
∗ L ∈ R+
0 ⪯ ∇2 ℓ(w, (x, y)) = xxT ⪯ LId √ • the sample pool composed by z1 = (v, 0), z2 = (x, 0) and z3 = (x, 1) for x, v ∈ B(0, L). • the parameters θ = Lx and ω = 0. y [g1 ]2
g1
Rθ
θ
g2
[g2 ]2 x [g3 ]2
g3
⊥θ [g1 ]1
[g3 ]1
[g2 ]1
Figure 1: CWTM does not preserve the co-coercive inequality of smooth and convex functions. We formally have: g1 = θT vv, g2 = θT xx = ∥x∥22 θ and g3 = (∥x∥22 − L) θ. We next exam| {z } <0
ine the conditions under which the CWTM aggregation rule does not preserve the co-coercivity inequality. Specifically, we denote: Rθ = CWTM (g1 , g2 , g3 ) and Rω = CWTM (0, 0, −x) = 0: ⟨θ − ω, Rθ − Rω ⟩ = ⟨θ, Rθ ⟩ < 0 Instances of such v, x yielding this inequality are illustrated in Figure 1 (v is colinear to g1 and x colinear to g2 ). 36
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Next, we analyze the Lipschitz continuity of the Trimmed Mean (TM) operation on the real line, which is useful for showing the expansivity property of CWTM robust update. Lemma 35
√
1 The trimmed mean operation is n−2f -Lipschitz continuous with respect to the ∥ · ∥1
n norm, and n−2f -Lipschitz continuous with respect to the ∥ · ∥2 norm.
Proof We recall the definition of the trimmed mean operation: given f, n ∈ N, f < n/2, and real values x1 , . . . , xn , we denote by σ a permutation on {1, . . . , n} that sorts the values in nondecreasing order xσ(1) ≤ · · · ≤ xσ(n) . Let Sx = {i ∈ [n]; f + 1 ≤ σ(i) ≤ n − f }, the trimmed mean is given by: n−f X X 1 1 TM(x1 , . . . , xn ) = xσ(i) = xi n − 2f n − 2f i∈Sx
i=f +1
We first consider two sets of real numbers that differ in exactly one entry ι ∈ {1, . . . , n}: x1 , . . . , xι , . . . , xn and x′1 , . . . , x′ι , . . . , x′n such that xj = x′j for all j ̸= ι. Let Sx and Sx′ denote the sets of selected indices in each case. We necessarily have |Sx′ \ Sx | ≤ 1. In the figure below, we illustrate different scenarios to provide an intuition for our proof. ι
ι
x1
x2
x3 TM(x) x4
x5
x1
x2
x3
TM(x′ )
x5
x1
x2 TM(x′ ) x3
x4
x5
x6
x4 ̸= x′4 x6 ̸= x′6 x′6
x′4
x6
Figure 2: Example with n = 6, f = 2 and the differing point being either x6 or x4 . Horizontal dashed lines represent either trimmed mean differences or changed-point differences. Green points indicate the contributors to the trimmed-mean, while red points denote those excluded from the computation. We consider the two possible cases. • Case (i) |Sx′ \ Sx | = 1. Let xι and xι be the boundary elements not included in Sx . That is, if we denote by σ a permutation on {1, . . . , n} that sorts the values in non-decreasing order xσ(1) ≤ · · · ≤ xσ(n) , then ι and ι are defined as follow: σ(ι) = f and σ(ι) = n − f + 1. ◦ If ι ∈ / Sx and ι ∈ / Sx′ , then with {j} = Sx \ Sx′ , we have two sub-cases: Sub-case (a) xι > xι and x′ι < xι . In this case, Sx′ \ Sx = {xι }. Therefore, 1 1 1 |TM(x) − TM(x′ )| = n−2f |xj − xι | ≤ n−2f |xι − xι | ≤ n−2f |xι − x′ι |.
Sub-case (b) xι < xι and x′ι > xι . In this case, Sx′ \ Sx = {xι }. Therefore, 1 1 1 |TM(x) − TM(x′ )| = n−2f |xι − xj | ≤ n−2f |xι − xι | ≤ n−2f |xι − x′ι |.
37
B OUDOU , L E BARS , G UPTA , AND B ELLET
◦ If ι ∈ Sx but ι ∈ / Sx′ then we have the following two sub-cases: Sub-case (c) xι ∈ Sx′ . In this case, x′ι ≤ xι . Therefore, 1 1 |xι − xι | ≤ n−2f |x′ι − xι |. |TM(x) − TM(x′ )| = n−2f
Sub-case (d) xι ∈ Sx′ . In this case, x′ι ≥ xι . Therefore, 1 1 |TM(x) − TM(x′ )| = n−2f |xι − xι | ≤ n−2f |x′ι − xι |.
◦ By symmetry, we obtain the same result for the case when ι ∈ / Sx but ι ∈ Sx′ . • Case (ii) |Sx′ \ Sx | = 0. The lemma is trivially true in this case. 1 From above, we obtain that |TM(x) − TM(x′ )| ≤ n−2f ∥x − x′ ∥1 . We can generalize this bound to two sets of n real numbers that can differ in all the entries, using triangle inequality. Specifically,
|TM(x) − TM(x′ )| = |TM(x) − TM(x1 , . . . , xn−1 , x′n ) + TM(x1 , . . . , xn−1 , x′n ) − TM(x1 , . . . , xn−2 , x′n−1 , x′n ) + · · · + TM(x1 , x′2 , . . . , x′n ) − TM(x′ )| ≤ |TM(x) − TM(x1 , . . . , xn−1 , x′n )| + · · · + |TM(x1 , x′2 , . . . , x′n ) − TM(x′ )| √ n 1 n 1 X ′ ′ |xi − xi | = ∥x − x ∥1 ≤ ∥x − x′ ∥2 ≤ n − 2f n − 2f n − 2f i=1
Lemma 35 and 33 enable to establish the expansivity of the CWTM update in the case of smooth and nonconvex loss functions, as shown in the following result. Lemma 36 Define the robust gradient update (1) when F = CWTM with learning rate γ > 0, for arbitrary z (i) ∈ Z, any i ∈ {1, . . . , n}, and any coordinate k ∈ {1, . . . , d}, as follows. GCWTM (θ) = θ − γCWTM(∇ℓ(θ; z (1) ), . . . , ∇ℓ(θ; z (n) )). γ n , Assume ∀z ∈ Z, ℓ(·, z) : Θ → R is L-smooth. Then GCWTM is (1 + γL min{ n−2f γ expansive (Hardt et al., 2016, Definition 2.3).
√
√ n, d})-
Proof Let θ, ω ∈ Rd and z (1) , . . . , z (n) ∈ Z. For convenience, we occasionally adopt the shorthand notation: ℓ(·; z (i) ) = ℓi (·). Using Lemma 35 and the L-smoothness assumption, we obtain that ∥CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω))∥22 =
d X
(TM([∇ℓ1 (θ)]k , . . . , [∇ℓn (θ)]k ) − TM([∇ℓ1 (ω)]k , . . . , [∇ℓn (ω)]k ))2
k=1 d X n ≤ ∥([∇ℓ1 (θ)]k , . . . , [∇ℓn (θ)]k ) − ([∇ℓ1 (ω)]k , . . . , [∇ℓn (ω)]k )∥22 (n − 2f )2 k=1 d X n n X X n n 2 = ([∇ℓi (θ)]k − [∇ℓi (ω)]k ) = ∥∇ℓi (θ) − ∇ℓi (ω)∥22 2 2 (n − 2f ) k=1 i=1 (n − 2f ) i=1 n X n n2 L2 2 2 ≤ L ∥θ − ω∥ = ∥θ − ω∥22 . 2 (n − 2f )2 i=1 (n − 2f )2
38
(58)
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Alternatively, we can invoke Lemma 33, which states that ∀k ∈ {1, . . . , d}, there exists ik ∈ {1, . . . , n} such that: ∥CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω))∥22 =
≤
d X k=1 d X
(TM([∇ℓ1 (θ)]k , . . . , [∇ℓn (θ)]k ) − TM([∇ℓ1 (ω)]k , . . . , [∇ℓn (ω)]k ))2 [∇ℓik (θ) − ∇ℓik (ω)]2k .
k=1
From above, we obtain the following: P P P 1. Since dk=1 [∇ℓik (θ) − ∇ℓik (ω)]2k ≤ dk=1 ni=1 [∇ℓi (θ) − ∇ℓi (ω)]2k ≤ nL2 ∥θ − ω∥22 , ∥CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω))∥22 ≤ nL2 ∥θ − ω∥22 . 2. Since
Pd
Pd 2 2 k=1 [∇ℓik (θ) − ∇ℓik (ω)]k ≤ k=1 ∥∇ℓik (θ) − ∇ℓik (ω)∥2 ,
∥CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω))∥22 ≤ dL2 ∥θ − ω∥22 . Therefore, ∥CWTM(∇ℓ1 (θ), . . . , ∇ℓn (θ)) − CWTM(∇ℓ1 (ω), . . . , ∇ℓn (ω))∥22 ≤ min{n, d}L2 ∥θ − ω∥22 . (59) The bound in (59) has a tighter dependence on the number of input vectors than the bound in (58), especially in the regime when f approaches n2 . We conclude the proof by combining (58) and (59), and by applying the triangle inequality, yielding √ √ n CWTM CWTM ∥Gγ (θ) − Gγ (ω)∥2 ≤ 1 + γL min , n, d ∥θ − ω∥2 . n − 2f
Appendix G. Non-Affine Aggregations Can Preserve Smoothness: Consequence for the Algorithmic Stability of Robust Distributed Learning To broaden our analysis, we show how the smoothness of the loss function (i.e., the Lipschitzcontinuity of its gradient) can be leveraged to derive sharper stability guarantees for robust SGD under data poisoning in the nonconvex setting. This motivates CWTM (cf. Definition 10), as it is an instance of an aggregation rule that preserves the loss function’s smoothness (cf. Appendix F), due to the Lipschitz continuity of the trimmed mean operation (cf. Lemma 35) or its translation equivariance property (cf. Lemma 33). Lemma 37 Let d, n ∈ N \ {0}. The aggregated operator F = CWTM(∇ℓ1 (·), . . . , ∇ℓn (·)) preserves the smoothness inequality of every L-smooth loss functions {ℓi }i∈[n] , i.e., for all θ, ω ∈ Rd ∥F(θ) − F(ω)∥ ≤ min{
√ √ n , n, d}L∥θ − ω∥22 . n − 2f 39
B OUDOU , L E BARS , G UPTA , AND B ELLET
Consequence for robust distributed nonconvex and smooth learning To illustrate the practical benefit of preserving smoothness, we provide an enhanced uniform algorithmic stability analysis for SGD under data poisoning. Specifically, we consider the robust setting where updates represent gradients of a loss ℓ, a fraction nf of which are computed on arbitrarily corrupted data. Lemma 37 enables the following stability upper bounds established in Appendix G.
Theorem 38 Consider the setting described in Section 1 under data poisoning. Let A = SGD, with CWTM. Suppose A is run for T ∈ N \ {0} iterations and that there exist ν > 0 constant such that n ≥ (2+ν)f — that is, f /n is strongly bounded away from 1/2. Let we assume ∀z ∈ Z, ℓ(·; z) bounded by ℓ∞ , nonconvex, C-Lipschitz and L-smooth. Then, with a monotonically non-increasing ν c ′ learning rate, γt ≤ 2+ν Lt , t ∈ {0, . . . , T − 1}, c > 0, we have for any neighboring datasets S, S :
2C 2 ν 2 sup EA [|ℓ(A(S); z) − ℓ(A(S ); z)|] ≤ 2 (2 + ν)2 L z∈Z
′
1 c+1
c T ℓ∞ c+1 √ 1 m n c+1
(60)
Proof Let denote {θt }t∈{0,...,T −1} and {θt′ }t∈{0,...,T −1} the optimization trajectories resulting from two neighboring datasets S, S ′ , for T iterations of SGD with aggregation rule CWTM and learning rate schedule {γt }t∈{0,...,T −1} . Importantly, poisoned vectors are treated as legitimate gradients, despite being computed on arbitrary data. In the following, we draw a growth recursion for the sensitivity of the parameters to the perturbation introduced. Let a, b ∈ H × {1, . . . , m} the indices of the differing samples. For t ∈ {0, . . . , T − 1}, we denote:
(i) zt =
(i)
( an arbitrary poisoned data point, z
(i) (i,Jt )
if i ∈ /H
(i) , Jt sampled uniformly from {1, . . . , m}
(i)
(1)
if i ∈ H
,
(n)
δt = ∥θt − θt′ ∥2 , gt = ∇ℓ(θt , zt ), GCWTM (θt ) = θt − γt CWTM(gt , . . . , gt ), and the prime γt notation (·)′ denotes the corresponding quantities for S ′ . The proof leverages the expansivity property of the robust aggregation update without directly comparing it to the honest stochastic gradient update. Specifically, we either directly apply the 1 ): expansivity result Lemma 36 with probability (1 − m
∥GCWTM (θt ) − G′CWTM (θt′ )∥2 ≤ (1 + γt L min{ γ γ 40
√ √ n , n, d})∥θt − θt′ ∥2 n − 2f
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
1 or perform the following calculation with probability m : (1)
′(1)
(n)
′(n)
∥CWTM(gt , . . . , gt ) − CWTM(gt , . . . , gt )∥22 d h i 2 h i h i h i X ′(n) ′(1) (n) (1) ) , . . . , gt ) − T M ( gt = , . . . , gt T M ( gt k=1
≤
k
k
k
k
d h i h i h i h i X n ′(n) ′(1) (n) (1) )∥22 , . . . , g ) − ( g , . . . , g ∥( g t t t t k k k k (n − 2f )2 k=1
d X n h h i 2 i X n ′(i) (i) = − g g t t k k (n − 2f )2 k=1 i=1
=
n X n (i) ′(i) ∥∇ℓ(θt ; zt ) − ∇ℓ(θt′ ; zt )∥22 (n − 2f )2 i=1
n X n ∥∇ℓ(θt ; z (i) )−∇ℓ(θt′ ; z (i) )∥22 +∥∇ℓ(θt ; z (a,b) )−∇ℓ(θt′ ; z ′(a,b) )∥22 = 2 (n − 2f ) i=1,i̸=a n 2 2 ′ 2 ≤ 2 4C + (n − 1)L ∥θt − θt ∥2 (n − 2f )
!
where we used Lemma 35 in the first inequality. Using the sub-additivity of the square root we 1 prove that we have with probability m : p √ n(n − 1) γ L 2γt C n t ′ CWTM ′CWTM ′ )∥θt − θt ∥2 + . ∥Gγ (θt ) − Gγ (θt )∥2 ≤ (1 + n − 2f n − 2f Consequently, with t0 ∈ {0, . . . , T − 1}, we obtain the following recursion: √ γt Ln 2γt C n EA [δt+1 |δt0 = 0] ≤ (1 + )EA [δt |δt0 = 0] + n − 2f (n − 2f )m γt L(2 + ν) c ≤ (1 + )EA [δt |δt0 = 0] + σf,m,n ν Lt c c = (1 + )EA [δt |δt0 = 0] + σf,m,n . t Lt √
2Cν n n where we used that as n ≥ (2 + ν)f , then n−2f ≤ 2+ν ν . and defined σf,m,n = (2+ν)(n−2f )m ≤ 2 2Cν√ ν c x . For 0 ≤ t0 ≤ min(m, T ), t ∈ {t0 , . . . , T − 1}, γt ≤ 2+ν Lt , c > 0, we use 1 + x ≤ e , (2+ν)2 nm
unroll the recursion and then invoke Lemma E.2 from Boudou et al. (2025) T −1 T −1 cσf,m,n X 1 Y c σf,m,n T c EA [δT |δt0 = 0] ≤ es ≤ L t=t t L t0 0
s=t+1
Substituting our derivation into the bound from Lemma E.1 from Boudou et al. (2025) yields t0 ℓ∞ σf,m,n C T c EA [|ℓ(θT ; z) − ℓ(θT′ ; z)|] ≤ min + L t0 0≤t0 ≤min(m,T ) m c 2 2 2C ν T t 0 ℓ∞ ≤ min + . √ 2 0≤t0 ≤min(m,T ) m (2 + ν) L nm t0 41
B OUDOU , L E BARS , G UPTA , AND B ELLET
We approximately minimize the expression with respect to t0 by balancing the two terms, i.e., setting them equal: 0 ≤ te0 =
mσf,m,n C Lℓ∞
1
c+1
c
T c+1
≤ for sufficiently large T≥
T. mσf,m,n C Lℓ∞
Finally, we obtain the result by directly substituting te0 into the bound: 1 c σf,m,n C c+1 ℓ∞ T c+1 L m 1 1 c c+1 c+1 c 2C 2 ν 2 2C 2 ν 2 ℓ∞ T c+1 1 c+1 = 2 =2 (ℓ T ) √ ∞ 1 . √ 2 2 m (2 + ν) L nm (2 + ν) L m n c+1
EA [|ℓ(θT ; z) − ℓ(θT′ ; z)|] ≤ 2
√ For f = 0, (60) yields a suboptimal n dependence instead of n (Le Bars et al., 2024)—a proof artifact, as this gap does not appear in Boudou et al. (2025, Theorem E.3), which also applies to our data poisoning setting. We next compare our bound with the one obtained using an aggregation rule that does not preserve the smoothness inequality, such as the SMEA rule introduced in Alpoisoning louah et al. (2023b). For f > 0, let εSMEA denote the upper bound from Boudou et al. (2025, poisoning poisoning poisoning Theorem E.3), and εCWTM the bound with CWTM from (60). We compare: εSMEA /εCWTM = 1 √ √ (2+ν)2 n n c+1 . Interestingly, by leveraging the smoothness-preserving property of n−f + f m n−f ν2 poisoning
CWTM, we obtain an improved dependence on m: as m grows unbounded, εCWTM decreases poisoning faster than εSMEA .
References Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), CCS’16. ACM, 2016. Giovanni Alberti and Luigi Ambrosio. A geometrical approach to monotone functions in Rn . Math. Zeit., 230 (1999):259–316, 1996. Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In AISTATS, 2023a. Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. On the privacy-robustness-utility trilemma in distributed learning. In ICML, 2023b. Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Ahmed Jellouli, Geovani Rizk, and John Stephan. Adaptive gradient clipping for robust federated learning. In ICLR, 2025a. Youssef Allouah, Rachid Guerraoui, and John Stephan. Towards trustworthy federated learning with untrusted participants. In ICML, 2025b. 42
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Jason M. Altschuler, Jinho Bok, and Kunal Talwar. On the privacy of noisy stochastic gradient descent for convex optimization. SIAM Journal on Computing, 53(4):969–1001, 2024. Amit Attia and Tomer Koren. Algorithmic instabilities of accelerated gradient descent. NeurIPS, 2021. Amit Attia, Matan Schliserman, Uri Sherman, and Tomer Koren. Fast last-iterate convergence of sgd in the smooth interpolation regime. NeurIPS, 2026. F. Bach. Learning Theory from First Principles. Adaptive Computation and Machine Learning series. MIT Press, 2024. Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. NeurIPS, 2019. Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. NeurIPS, 2019. Heinz H. Bauschke and Patrick L. Combettes. Convex analysis and monotone operator theory in hilbert spaces. In CMS Books in Mathematics, 2011. Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In ICML, 2018. Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In NeurIPS, 2017. Jonathan Michael Borwein and Simon Fitzpatrick. Local boundedness of monotone operators under minimal hypotheses. Bulletin of the Australian Mathematical Society, 39:439 – 441, 1989. Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. In NeurIPS, 2007. Thomas Boudou, Batiste Le Bars, Nirupam Gupta, and Aurélien Bellet. Byzantine failures harm the generalization of robust distributed learning algorithms more than data poisoning. arXiv preprint arXiv:2506.18020v2, 2025. Olivier Bousquet and André Elisseeff. Stability and generalization. JMLR, 2:499–526, 2002. Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In COLT, 2020. Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In ICML, 2018. Satrajit Chatterjee. Coherent gradients: An approach to understanding generalization in gradient descentbased optimization. In ICLR, 2020. Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. NeurIPS, 2020. A.R. Conn, K. Scheinberg, and L.N. Vicente. Introduction to Derivative-Free Optimization. MOSSIAM Series on Optimization. Society for Industrial and Applied Mathematics, 2009. 43
B OUDOU , L E BARS , G UPTA , AND B ELLET
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. NeurIPS, 2014. Ilias Diakonikolas and Daniel M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press, 2023. Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742–864, 2019. Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals of Statistics, 48(3):1348–1382, 2020. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. JMLR, 12(7), 2011. F. Facchinei and J.S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2007. Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In ICLR, 2019. Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In ICML, 2016. Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In ICML, 2018. Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In ICML, 2021. Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In ICLR, 2022. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015. Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In ICML, 2023. Guy Kornowski and Ohad Shamir. Gradient descent’s last iterate is often (slightly) suboptimal. arXiv preprint arXiv:2604.13870, 2026. Batiste Le Bars, Aurélien Bellet, Marc Tommasi, Kevin Scaman, and Giovanni Neglia. Improved stability and generalization guarantees of the decentralized SGD algorithm. In ICML, 2024. Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In ICML, 2020. Giovanni Leoni. A first course in Sobolev spaces. American Mathematical Society, 2017. 44
DANGEROUS L IAISONS OF C ONVEX L EARNING AND N ON -A FFINE AGGREGATION
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57–95, 2016. Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In AISTATS, 2019. Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In ICLR, 2024. Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In ICLR, 2019. Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In ICML, 2018. Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR, 2019. Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, NeurIPS, volume 24, 2011. Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. NeurIPS, 2014. Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In AAAI, 2021. Margarita Preobrazhenskaia, Makar Sidorov, Igor Preobrazhenskii, and Eduard Gorbunov. Last iterate convergence of adagrad-norm for convex non-smooth optimization. arXiv preprint arXiv:2604.10728, 2026. Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clipping in incremental gradient methods. In AISTATS, 2021. Ali Ramezani-Kebrya, Kimon Antonakopoulos, Volkan Cevher, Ashish Khisti, and Ben Liang. On the generalization of stochastic gradient descent with momentum. JMLR, 25(22):1–56, 2024. Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR, 2018. Ernest Ryu and Stephen Boyd. A primer on monotone operator methods. Applied and computational mathematics, 15:3–43, 01 2016. Matan Schliserman and Tomer Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In COLT, 2022. Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370, 2013. 45
B OUDOU , L E BARS , G UPTA , AND B ELLET
Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In AISTATS, 2021. Zhenyu Sun, Xiaochun Niu, and Ermin Wei. Understanding generalization of federated learning via stability: Heterogeneity matters. In AISTATS, 2024. Yu-Xiang Wang, Jing Lei, and Stephen E Fienberg. Learning with differential privacy: Stability, learnability and the sufficiency and necessity of erm principle. JMLR, 17(183):1–40, 2016. Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. NeurIPS, 2017. Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In ICML, 2018. Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 35(3):2182–2201, 2025. Shuang Zeng and Yunwen Lei. Stochastic gradient methods: Bias, stability and generalization. JMLR, 27(6):1–55, 2026. Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In ICLR, 2020. Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of SGD: Tightness analysis and improved bounds. In UAI, 2022a. Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. NeurIPS, 2022b. Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In ICML, 2015.
46