Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

• URL: http://arxiv.org/abs/2606.28123v1
• Date: Fri, 26 Jun 2026 14:24:11 GMT
• Title: Dangerous Liaisons of Convex Learning and Non-Affine Aggregation
• Abstract summary: Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator.<n>Non-affine aggregation prevents steady convergence and substantially degrades algorithmic stability.<n>Our results provide a unified theoretical framework explaining the disparate failure modes observed in modern learning systems.
• Score: 19.624245500772027
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• High-Probability Convergence of SGD via Batched Updates [4.862625283098196]
  Batched SGD is a simple variant that iterates online epochs into optimizations.<n>Our main contribution demonstrates that this mechanism enables a surprisingly simple high-probability analysis.
  arXiv  Detail & Related papers  (2026-09-11T12:17:18Z)
• Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions [7.408148824204063]
  This work delivers two key contributions one to efficient feature selection in reinforcement learning (RL) and the other to the theory of non-monotone inclusions.
  arXiv  Detail & Related papers  (2026-07-06T12:25:47Z)
• Learning Context-conditioned Gaussian Overbounds for Convolution-Based Uncertainty Propagation [4.891998873486944]
  We propose a unified learning framework that trains neural networks to produce context-aware Gaussian overbounds.<n>We provide a scoped analysis of discrete-to-continuous conservatism and compact-domain objective regularity.<n>The framework is modality-agnostic and applicable to learning systems that require conservative, feature-conditioned uncertainty estimates.
  arXiv  Detail & Related papers  (2026-05-15T09:47:05Z)
• Convergence and Generalization of Anti-Regularization for Parametric Models [0.0]
  Anti-regularization introduces a reward term with a reversed sign into the loss function.<n>We formalize spectral safety conditions and trust-region constraints.<n>We design a lightweight safeguard that combines a projection operator with gradient clipping to guarantee stable intervention.
  arXiv  Detail & Related papers  (2025-08-24T15:34:17Z)
• Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness [50.78508362183774]
  Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance.<n>Most require the Lipschitz condition, which is often not met in common machine learning schemes.
  arXiv  Detail & Related papers  (2025-07-11T15:36:48Z)
• On the Convergence of Gradient Descent for Large Learning Rates [55.33626480243135]
  We show that convergence is impossible when a fixed step size is used.<n>We provide a proof of this in the case of linear neural networks with a squared loss.<n>We also prove the impossibility of convergence for more general losses without requiring strong assumptions such as Lipschitz continuity for the gradient.
  arXiv  Detail & Related papers  (2024-02-20T16:01:42Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria. We provide explicit convergence guarantees for both deterministic and deterministic environments.
  arXiv  Detail & Related papers  (2023-12-27T15:21:25Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Interpolation can hurt robust generalization even when there is no noise [76.3492338989419]
  We show that avoiding generalization through ridge regularization can significantly improve generalization even in the absence of noise. We prove this phenomenon for the robust risk of both linear regression and classification and hence provide the first theoretical result on robust overfitting.
  arXiv  Detail & Related papers  (2021-08-05T23:04:15Z)
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics [13.4379473119565]
  We analyze the generalization dynamics to derive algorithm-dependent bounds, e.g., stability. Inspired by the observation that neural networks show a slow convergence rate when fitting noise, we propose decomposing the excess risk dynamics. Under the decomposition framework, the new bound accords better with the theoretical and empirical evidence compared to the stability-based bound and uniform convergence bound.
  arXiv  Detail & Related papers  (2021-06-11T03:42:45Z)
• Implicit Regularization in ReLU Networks with the Square Loss [56.70360094597169]
  We show that it is impossible to characterize the implicit regularization with the square loss by any explicit function of the model parameters. Our results suggest that a more general framework may be needed to understand implicit regularization for nonlinear predictors.
  arXiv  Detail & Related papers  (2020-12-09T16:48:03Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  We consider monotone inclusion problems where the operators may be expectation-valued. A direct application of splitting schemes is complicated by the need to resolve problems with expectation-valued maps at each step. We propose an avenue for addressing uncertainty in the mapping: Variance-reduced modified forward-backward splitting scheme.
  arXiv  Detail & Related papers  (2020-08-26T02:33:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.