Regularity-Aware Stochastic MGDA with Adaptive Conflict-Avoidant Update Direction Control

• URL: http://arxiv.org/abs/2607.15412v1
• Date: Thu, 16 Jul 2026 19:34:00 GMT
• Title: Regularity-Aware Stochastic MGDA with Adaptive Conflict-Avoidant Update Direction Control
• Abstract summary: Multi-gradient descent algorithm (MGDA) is a workhorse that iteratively updates along a common descent oravoidant (CA) direction across objectives.<n>In this paper, we show that the CA direction is $1/2$Holder continuous with respect to the Jacobian matrix rate, and the $1/2$ cannot be improved in the worst case.<n>We propose a regularity multi-task (MoRe) method that exploits the Lipschitz continuity of the CA direction.
• Score: 6.349897655422752
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-objective learning (MOL) aims to optimize multiple objectives simultaneously. The multi-gradient descent algorithm (MGDA) is a workhorse that iteratively updates along a common descent or conflict-avoidant (CA) direction across objectives. In stochastic settings, however, the vanilla stochastic MGDA method, SMG, lacks a fast convergence rate because mini-batch sampling introduces noise in the gradients. This causes bias in the update direction, which is controlled by the CA direction continuity. In this paper, we show that the CA direction is $1/2$-Holder continuous with respect to the Jacobian matrix, and the exponent $1/2$ cannot be improved in the worst case. This leads to a suboptimal convergence rate for vanilla stochastic MGDA in prior works. Nevertheless, under additional regularity conditions, we show this can be improved to Lipschitz continuity. Based on this insight, we propose a stochastic multi-objective regularity-aware (MoRe) method that exploits the Lipschitz continuity of the CA direction when the subproblem is regular, and switches to a fixed scalarization weight otherwise. Intuitively, the proposed algorithm employs CA direction update when the gradient conflict is large, and linear scalarization update otherwise. Theoretically, our method improves the convergence rate of SMG in the nonconvex setting from $\widetilde{\mathcal O}(T^{-1/4})$ to $\widetilde{\mathcal O}(T^{-1/2})$, where $\widetilde{\mathcal O}(\cdot)$ hides logarithmic factors. Meanwhile, we also establish the per-iterate conflict-avoidance guarantees. Empirically, experiments demonstrate its effectiveness in multi-task performance and verify convergence behavior consistent with the established theoretical rate.

Related papers

• Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization [15.2286904549704]
  We show that the dual-anchor mechanism, namely the dual-anchor mechanism, extends to the iteration setting without such error accumulation.<n>For strongly monotone operators, the same algorithm attains a sharper complexity, nearly matching the lower bound in terms of $$-dependence.
  arXiv  Detail & Related papers  (2026-08-12T13:25:55Z)
• Accelerated and Stable Convergence with Anchored Optimistic Method [39.242061448272615]
  We study first-order methods for solving monotone variational inequalities arising in min-max optimization.<n>We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration.
  arXiv  Detail & Related papers  (2026-06-19T15:26:10Z)
• High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
  We study high-probability (HP) convergence guarantees in decentralized optimization.<n>Our results establish the same conditions on the horizon as in achieving comparable times.
  arXiv  Detail & Related papers  (2026-04-30T22:45:21Z)
• Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction [9.294518380204154]
  We study online inference and covariance estimation for the gradient descent (SGD) algorithm.<n>Our method employs a bias-reduction technique to achieve a convergence rate of $n(-1)/2 sqrtlog n$, outperforming existing Hessian-free alternatives.
  arXiv  Detail & Related papers  (2026-04-23T01:48:08Z)
• Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression [12.805268849262243]
  We study online covariance matrix estimation for Polyak-Ruppert averaged gradient descent (SGD)<n>The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.
  arXiv  Detail & Related papers  (2026-04-12T20:49:33Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning.<n>Recent works provide some effective algorithms with theoretical analysis but they are limited by the standard $L$-smooth or bounded-gradient assumptions.<n>We study a more general and realistic class of generalized $ell$-smooth loss functions, where $ell$ is a general non-decreasing function of gradient norm.
  arXiv  Detail & Related papers  (2024-05-29T18:36:59Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)

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.