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

# Regularity-Aware Stochastic MGDA with Adaptive Conflict-Avoidant Update Direction Control
Source: [https://arxiv.org/html/2607.15412](https://arxiv.org/html/2607.15412)
Chentong Huang, Lisha ChenDept\. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627 E\-mails: chuang80@ur\.rochester\.edu, lisha\.chen@rochester\.edu

###### 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\[[11](https://arxiv.org/html/2607.15412#bib.bib3)\], 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 is1/21/2\-Hölder continuous with respect to the Jacobian matrix, and the exponent1/21/2cannot 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\[[11](https://arxiv.org/html/2607.15412#bib.bib3),[1](https://arxiv.org/html/2607.15412#bib.bib20)\]in the nonconvex setting from𝒪~​\(T−1/4\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/4\}\)to𝒪~​\(T−1/2\)\\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\.

## IINTRODUCTION

Multi\-objective learning \(MOL\) has emerged as an important paradigm in modern machine learning\. Representative applications include multi\-task learning\[[13](https://arxiv.org/html/2607.15412#bib.bib9)\], meta learning\[[19](https://arxiv.org/html/2607.15412#bib.bib11),[2](https://arxiv.org/html/2607.15412#bib.bib7)\], and learning under multiple constraints\[[21](https://arxiv.org/html/2607.15412#bib.bib10)\]\.

In this work, we consider the empirical MOL problem defined on a training sample sequenceS=\(z1,…,zn\)∈𝒵nS=\(z\_\{1\},\\dots,z\_\{n\}\)\\in\\mathcal\{Z\}^\{n\}\. Let\[M\]≔\{1,…,M\}\[M\]\\coloneqq\\\{1,\\ldots,M\\\}, whereM≥2M\\geq 2\. For each objectivem∈\[M\]m\\in\[M\], letfz,m​\(x\)f\_\{z,m\}\(x\)denote themm\-th objective function evaluated at modelx∈ℝpx\\in\\mathbb\{R\}^\{p\}on a data pointzz, and define its empirical counterpart byfS,m​\(x\)≔n−1​∑i=1nfzi,m​\(x\)f\_\{S,m\}\(x\)\\coloneqq n^\{\-1\}\\sum\_\{i=1\}^\{n\}f\_\{z\_\{i\},m\}\(x\)\. The empirical MOL problem is formulated as the optimization of the vector\-valued objective:

minx∈ℝp⁡FS​\(x\)≔\(fS,1​\(x\),…,fS,M​\(x\)\)⊤\.\\min\_\{x\\in\\mathbb\{R\}^\{p\}\}F\_\{S\}\(x\)\\coloneqq\\bigl\(f\_\{S,1\}\(x\),\\dots,f\_\{S,M\}\(x\)\\bigr\)^\{\\top\}\.\(1\)
Unlike single\-objective learning, MOL seeks a Pareto optimal or Pareto stationary solution rather than the minimizer of a scalar loss\. One of the central challenges is that the gradients of different objectives may conflict: a descent direction for one objective may increase another\. A widely used strategy by many methods\[[12](https://arxiv.org/html/2607.15412#bib.bib64),[10](https://arxiv.org/html/2607.15412#bib.bib71),[1](https://arxiv.org/html/2607.15412#bib.bib20)\]is to dynamically combine objective gradients to obtain a conflict\-avoidant \(CA\) direction\. Among the methods, a representative approach is MGDA\[[12](https://arxiv.org/html/2607.15412#bib.bib64),[7](https://arxiv.org/html/2607.15412#bib.bib67),[4](https://arxiv.org/html/2607.15412#bib.bib1)\], which computes a minimum\-norm convex combination of objective gradients and has motivated many variants for MOL\[[10](https://arxiv.org/html/2607.15412#bib.bib71),[6](https://arxiv.org/html/2607.15412#bib.bib5),[1](https://arxiv.org/html/2607.15412#bib.bib20)\]\. While the deterministic MGDA variants are relatively well studied, full\-batch gradients are typically too expensive to compute at every iteration in practice, especially for large machine learning models\. This has motivated stochastic variants of MGDA, such as the stochastic multi\-gradient \(SMG\) method\[[11](https://arxiv.org/html/2607.15412#bib.bib3)\], which replaces the full\-batch gradient matrix with stochastic gradient estimates computed from mini\-batches\.

However, directly extending the convergence analysis of MGDA to the stochastic setting is nontrivial\. Since the CA direction is a nonlinear function of the gradient matrix, replacing the full\-batch gradient matrix with a mini\-batch estimate can introduce direction bias: the mini\-batch CA direction may not be an unbiased or stable approximation of the full\-batch CA direction\. This sensitivity can be characterized byα\\alpha\-Hölder continuity of the direction mapping: for gradient matricesQ1,Q2∈ℝp×MQ\_\{1\},Q\_\{2\}\\in\\mathbb\{R\}^\{p\\times M\}, letdQ1d\_\{Q\_\{1\}\}anddQ2d\_\{Q\_\{2\}\}denote the corresponding CA directions\. Then,

‖dQ1−dQ2‖≤ℓH​‖Q1−Q2‖α,\\\|d\_\{Q\_\{1\}\}\-d\_\{Q\_\{2\}\}\\\|\\leq\\ell\_\{\\mathrm\{H\}\}\\\|Q\_\{1\}\-Q\_\{2\}\\\|^\{\\alpha\},\(2\)whereℓH\>0\\ell\_\{\\mathrm\{H\}\}\>0is the Hölder constant,α∈\(0,1\]\\alpha\\in\(0,1\], andα=1\\alpha=1corresponds to Lipschitz continuity; see also\[[1](https://arxiv.org/html/2607.15412#bib.bib20), Section 4\.2\]\. Despite its direct relevance to the stability and convergence of stochastic MGDA methods, exploration of this question remains limited in the existing literature\. Specifically,\[[14](https://arxiv.org/html/2607.15412#bib.bib4)\]proved that the CA direction is1/21/2\-Hölder continuous with respect to the model variablexx, and that the exponent1/21/2is sharp\. In addition,\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]showed a corresponding1/21/2\-Hölder continuity result with respect to the stochastic gradient matrix\. This motivates us to investigate when stronger regularity can hold, and to exploit such properties in the design of stochastic algorithms with improved convergence guarantees while preserving conflict\-avoidance behavior\.

### I\-ARelated work

Deterministic gradient\-based MOL\.A major line of work in MOL seeks a common update direction for all objectives using gradient information\. A foundational method in this direction is MGDA\[[12](https://arxiv.org/html/2607.15412#bib.bib64),[7](https://arxiv.org/html/2607.15412#bib.bib67),[4](https://arxiv.org/html/2607.15412#bib.bib1)\], which dynamically combines gradients to obtain a common descent direction\. Beyond MGDA, several gradient\-aggregation methods have been proposed to mitigate conflicts among objectives\. For example, PCGrad\[[20](https://arxiv.org/html/2607.15412#bib.bib70)\]projects conflicting task gradients, while CAGrad\[[10](https://arxiv.org/html/2607.15412#bib.bib71)\]seeks a conflict\-averse aggregated direction\. These methods highlight the importance of conflict\-aware gradient aggregation in MOL\. However, in large\-scale learning and modern deep learning applications, full\-batch gradients are typically too expensive to compute at every iteration\. Stochastic MOL\.Practical MOL algorithms usually require updates based on \(mini\-batch\) stochastic gradients, which has motivated stochastic extensions of MGDA\. For instance, SMG\[[11](https://arxiv.org/html/2607.15412#bib.bib3)\]extends MGDA to the stochastic setting and provides convergence guarantees\. Subsequent works further develop provably convergent stochastic MOL algorithms using different sampling, variance\-reduction, and preference\-guided mechanisms\[[22](https://arxiv.org/html/2607.15412#bib.bib8),[6](https://arxiv.org/html/2607.15412#bib.bib5),[1](https://arxiv.org/html/2607.15412#bib.bib20),[17](https://arxiv.org/html/2607.15412#bib.bib79),[3](https://arxiv.org/html/2607.15412#bib.bib27),[18](https://arxiv.org/html/2607.15412#bib.bib28),[5](https://arxiv.org/html/2607.15412#bib.bib77)\]\. For convergence analysis, a key obstacle lies in controlling update\-direction bias and conflict\-avoidance error: since the CA direction depends nonlinearly on the gradient matrix, stochastic gradient noise can create CA\-direction error\. This in turn affects the convergence analysis of the stochastic variants of MGDA, and may lead to suboptimal convergence rates, as discussed in\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\], and summarized in Table[I](https://arxiv.org/html/2607.15412#S1.T1)\. Continuity of the CA direction map\.The continuity of the CA direction mapping is important for stochastic MOL because it controls the CA direction error\. Earlier work studied the continuity of the CA direction with respect to the model variable and established a1/21/2\-Hölder continuity result\[[14](https://arxiv.org/html/2607.15412#bib.bib4)\]\. For stochastic MOL, Chen et al\.\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]prove a1/21/2\-Hölder continuity result with respect to the stochastic gradient matrix\. However, these results do not characterize when stronger Lipschitz continuity with respect to the gradient matrix is available, nor do they explore whether it can be exploited to obtain faster stochastic convergence and more stable CA directions\. Our work addresses this gap by identifying a nondegenerate Lipschitz regime of the direction map and exploiting it through a regularity\-aware stochastic algorithm\.

### I\-BOur contributions

Our contributions in this paper are summarized as follows\. Continuity analysis of the CA direction\.We provide a fine\-grained continuity analysis of the CA direction mapping\. Under a nondegeneracy condition in Definition[2](https://arxiv.org/html/2607.15412#Thmdefinition2), Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)proves Lipschitz continuity of the CA direction mapping, while Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)shows that without the nondegeneracy condition, the1/21/2\-Hölder continuity on bounded sets is sharp in the worst case\. Improved convergence guarantees\.Motivated by the above continuity properties, we develop a Multi\-objective Regularity\-aware \(MoRe\) algorithm that leverages the regularity of the CA direction in different regimes\. With mini\-batch sizes\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\)and step sizeα=Θ​\(T−1/2\)\\alpha=\\Theta\(T^\{\-1/2\}\), Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)gives the nonconvex empirical stationarity rate𝒪~​\(T−1/2\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\), improving the𝒪~​\(T−1/4\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/4\}\)SMG rate in\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]\. Theorem[2](https://arxiv.org/html/2607.15412#Thmtheorem2)further establishes a per\-iterate CA direction distance bound\. See Table[I](https://arxiv.org/html/2607.15412#S1.T1)for a comparison with existing methods\. Experiments on MTL applications\.We compare the proposed method with existing MOL algorithms, and the empirical results demonstrate its practical effectiveness in both model performance and convergence behavior\.

TABLE I:Comparison with prior stochastic MOL algorithms in batch size, convergence rate, and CA direction distance\. Here, Conv\. and CA Dist\. denote the convergence rate and CA direction distance, respectively, and𝒪~​\(⋅\)\\widetilde\{\\mathcal\{O\}\}\(\\cdot\)hides logarithmic factors\. Note that the result of MoDo\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]is obtained by optimally tuning the hyperparameters in the theorems therein\.AlgorithmBatch sizeConv\.CA Dist\.SMG\[[11](https://arxiv.org/html/2607.15412#bib.bib3)\]\[[1](https://arxiv.org/html/2607.15412#bib.bib20), Thms 7,8\]Θ​\(t\+1\)\\Theta\(t\+1\)𝒪~​\(T−14\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-\\frac\{1\}\{4\}\}\)per\-iterateCR\-MOGM\[[22](https://arxiv.org/html/2607.15412#bib.bib8), Thm 3\]Θ​\(1\)\\Theta\(1\)𝒪​\(T−12\)\\mathcal\{O\}\(T^\{\-\\frac\{1\}\{2\}\}\)\-MoCo\[[6](https://arxiv.org/html/2607.15412#bib.bib5), Thm 2\]Θ​\(1\)\\Theta\(1\)𝒪​\(T−110\)\\mathcal\{O\}\(T^\{\-\\frac\{1\}\{10\}\}\)averageMoDo\[[1](https://arxiv.org/html/2607.15412#bib.bib20), Thms 3,5\]Θ​\(1\)\\Theta\(1\)𝒪~​\(T−12\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-\\frac\{1\}\{2\}\}\)averageMoCo\+\[[5](https://arxiv.org/html/2607.15412#bib.bib77), Thms 1,2\]Θ​\(1\)\\Theta\(1\)𝒪​\(T−23\)\\mathcal\{O\}\(T^\{\-\\frac\{2\}\{3\}\}\)averageOurs, Thm[1](https://arxiv.org/html/2607.15412#Thmtheorem1),[2](https://arxiv.org/html/2607.15412#Thmtheorem2)Θ​\(t\+1\)\\Theta\(t\+1\)𝒪~​\(T−12\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-\\frac\{1\}\{2\}\}\)per\-iterate

## IIPROBLEM SETUP

In this section, we introduce some basic concepts in MOL problems\. We briefly introduce the corresponding population objectiveFFonly to state the standard notions of Pareto stationarity and Pareto optimality\. LetF​\(x\)≔\(f1​\(x\),…,fM​\(x\)\)⊤F\(x\)\\coloneqq\(f\_\{1\}\(x\),\\ldots,f\_\{M\}\(x\)\)^\{\\top\}, wherefm​\(x\)≔𝔼z​\[fz,m​\(x\)\]f\_\{m\}\(x\)\\coloneqq\\mathbb\{E\}\_\{z\}\[f\_\{z,m\}\(x\)\]\. Our optimization and convergence analysis focus on the empirical objectiveFSF\_\{S\}defined above\. The same definitions apply to the empirical problem after replacingFFbyFSF\_\{S\}\.

###### Definition 1\(Pareto optimal and Pareto stationary points\)\.

A pointx∗∈ℝpx^\{\*\}\\in\\mathbb\{R\}^\{p\}is called Pareto optimal if there does not exist anyx∈ℝpx\\in\\mathbb\{R\}^\{p\}withx≠x∗x\\neq x^\{\*\}such thatfm​\(x\)≤fm​\(x∗\)f\_\{m\}\(x\)\\leq f\_\{m\}\(x^\{\*\}\)for allm∈\[M\]m\\in\[M\]andfm′​\(x\)<fm′​\(x∗\)f\_\{m^\{\\prime\}\}\(x\)<f\_\{m^\{\\prime\}\}\(x^\{\*\}\)for at least onem′∈\[M\]m^\{\\prime\}\\in\[M\]\. It is called weakly Pareto optimal if there does not exist anyx∈ℝpx\\in\\mathbb\{R\}^\{p\}such thatfm​\(x\)<fm​\(x∗\)f\_\{m\}\(x\)<f\_\{m\}\(x^\{\*\}\)for allm∈\[M\]m\\in\[M\]\. A pointx∈ℝpx\\in\\mathbb\{R\}^\{p\}is called Pareto stationary if there existsλ∈ΔM\\lambda\\in\\Delta^\{M\}such that∇F​\(x\)​λ=0,\\nabla F\(x\)\\lambda=0,whereΔM≔\{λ∈ℝM∣𝟏⊤​λ=1,λ≥0\},\\Delta^\{M\}\\coloneqq\\\{\\lambda\\in\\mathbb\{R\}^\{M\}\\mid\\mathbf\{1\}^\{\\top\}\\lambda=1,\\ \\lambda\\geq 0\\\},and∇F​\(x\)≔\(∇f1​\(x\),∇f2​\(x\),…,∇fM​\(x\)\)∈ℝp×M\\nabla F\(x\)\\coloneqq\\bigl\(\\nabla f\_\{1\}\(x\),\\nabla f\_\{2\}\(x\),\\dots,\\nabla f\_\{M\}\(x\)\\bigr\)\\in\\mathbb\{R\}^\{p\\times M\}\.

By definition, a Pareto stationary point admits no common descent direction for all objectives\. For smooth objectives, a necessary and sufficient condition forxxto be Pareto stationary\[[15](https://arxiv.org/html/2607.15412#bib.bib2)\]isminλ∈ΔM⁡‖∇F​\(x\)​λ‖=0\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\\nabla F\(x\)\\lambda\\\|=0\. Therefore, the quantityminλ∈ΔM⁡‖∇F​\(x\)​λ‖\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\\nabla F\(x\)\\lambda\\\|can be used as a measure of Pareto stationarity\[[4](https://arxiv.org/html/2607.15412#bib.bib1),[6](https://arxiv.org/html/2607.15412#bib.bib5),[1](https://arxiv.org/html/2607.15412#bib.bib20)\]\. Accordingly, since our analysis is conducted on the empirical objectiveFSF\_\{S\}, we define the empirical Pareto\-stationarity measure

RS​\(x\)≔minλ∈ΔM⁡‖∇FS​\(x\)​λ‖2\.R\_\{S\}\(x\)\\coloneqq\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\\nabla F\_\{S\}\(x\)\\lambda\\\|^\{2\}\.\(3\)
### II\-AMulti\-gradient descent algorithm \(MGDA\)

To solve the multi\-objective problem, MGDA\[[4](https://arxiv.org/html/2607.15412#bib.bib1)\]constructs a common descent direction for all objectives\. At each iteration, MGDA seeks a directiond​\(x\)∈ℝpd\(x\)\\in\\mathbb\{R\}^\{p\}that improves all objectives simultaneously\. In particular, one solves

d​\(x\)=−∇FS​\(x\)​λ∗​\(x\)\\displaystyle d\(x\)=\-\\nabla F\_\{S\}\(x\)\\lambda^\{\*\}\(x\)\(4\)s\.t\.λ∗​\(x\)∈arg⁡minλ∈ΔM‖∇FS​\(x\)​λ‖2\.\\displaystyle\\text\{s\.t\.\}\\quad\\lambda^\{\*\}\(x\)\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\left\\\|\\nabla F\_\{S\}\(x\)\\lambda\\right\\\|^\{2\}\.\(5\)Here,λ∗​\(x\)\\lambda^\{\*\}\(x\)denotes the simplex\-constrained weight vector used to combine the objective gradients\. Thett\-th iterate is then updated by

xt\+1=xt\+αt​d​\(xt\),x\_\{t\+1\}=x\_\{t\}\+\\alpha\_\{t\}d\(x\_\{t\}\),\(6\)whereαt\>0\\alpha\_\{t\}\>0is the step size\. The resulting directiond​\(xt\)d\(x\_\{t\}\)is a common descent direction wheneverxtx\_\{t\}is not Pareto stationary\. Moreover, MGDA terminates when∇FS​\(xt\)​λ∗​\(xt\)=0\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)=0, in which casextx\_\{t\}is a Pareto stationary point\.

### II\-BStochastic multi\-objective gradient \(SMG\) method

A natural stochastic counterpart of MGDA is the SMG method\[[11](https://arxiv.org/html/2607.15412#bib.bib3)\], which replaces the full\-batch gradients by stochastic gradient estimates computed from sampled data\. Specifically, letZ=\(ζ1,…,ζ\|Z\|\)Z=\(\\zeta\_\{1\},\\ldots,\\zeta\_\{\|Z\|\}\)denote a mini\-batch sampled i\.i\.d\. uniformly fromSS, equivalently with replacement\. Define

∇FZ​\(x\)≔1\|Z\|​∑r=1\|Z\|∇Fζr​\(x\),\{\\nabla F\_\{Z\}\(x\)\\coloneqq\\frac\{1\}\{\|Z\|\}\\sum\_\{r=1\}^\{\|Z\|\}\\nabla F\_\{\\zeta\_\{r\}\}\(x\),\}\(7\)whereFz​\(x\)=\(fz,1​\(x\),…,fz,M​\(x\)\)F\_\{z\}\(x\)=\\big\(f\_\{z,1\}\(x\),\\ldots,f\_\{z,M\}\(x\)\\big\)collects the objective values evaluated at samplezz\. For notational simplicity, letQ∈ℝp×MQ\\in\\mathbb\{R\}^\{p\\times M\}denote the stochastic gradient matrix∇FZ​\(x\)\\nabla F\_\{Z\}\(x\),

Q≔∇FZ​\(x\)=\[qZ,1​\(x\),…,qZ,M​\(x\)\]∈ℝp×M,\\displaystyle\{Q\\coloneqq\\nabla F\_\{Z\}\(x\)=\[q\_\{Z,1\}\(x\),\\ldots,q\_\{Z,M\}\(x\)\]\\in\\mathbb\{R\}^\{p\\times M\},\}\(8\)whereqZ,m​\(x\)≔1\|Z\|​∑r=1\|Z\|∇fζr,m​\(x\)∈ℝpq\_\{Z,m\}\(x\)\\coloneqq\\frac\{1\}\{\|Z\|\}\\sum\_\{r=1\}^\{\|Z\|\}\\nabla f\_\{\\zeta\_\{r\},m\}\(x\)\\in\\mathbb\{R\}^\{p\}\. Define

gQ​\(λ\)≔‖Q​λ‖2,λ∈ΔM\.g\_\{Q\}\(\\lambda\)\\coloneqq\\\|Q\\lambda\\\|^\{2\},\\qquad\\lambda\\in\\Delta^\{M\}\.\(9\)Then SMG computes the stochastic descent direction as

dQ=−Q​λQ∗,s\.t\.λQ∗∈arg⁡minλ∈ΔM⁡gQ​\(λ\),\\displaystyle d\_\{Q\}=\-Q\\lambda\_\{Q\}^\{\*\},\\quad\\text\{s\.t\.\}\\quad\\lambda\_\{Q\}^\{\*\}\\in\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}g\_\{Q\}\(\\lambda\),\(10\)wheredQ∈ℝpd\_\{Q\}\\in\\mathbb\{R\}^\{p\}denotes the update direction associated withQQ, andλQ∗∈ΔM\\lambda\_\{Q\}^\{\*\}\\in\\Delta^\{M\}denotes an optimal simplex weight forQQ\.

To measure how well the update direction tracks the corresponding full\-batch CA direction, we further adopt the CA direction distance introduced in\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]\. The CA direction distance at thett\-th iteration is defined as

ℰca​\(t\)≔‖𝔼​\[dt−d​\(xt\)\]‖2,d​\(xt\)=−∇FS​\(xt\)​λ∗​\(xt\),\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)\\coloneqq\\left\\\|\\mathbb\{E\}\[d\_\{t\}\-d\(x\_\{t\}\)\]\\right\\\|^\{2\},~~d\(x\_\{t\}\)=\-\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\),\(11\)whereλ∗​\(xt\)∈arg⁡minλ∈ΔM‖∇FS​\(xt\)​λ‖2\\lambda^\{\*\}\(x\_\{t\}\)\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\left\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\right\\\|^\{2\}, anddtd\_\{t\}is the update direction at thett\-th iteration\. The expectation inℰca​\(t\)\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)is unconditional and is taken over the algorithmic randomness\. This quantity measures the discrepancy between the stochastic update directiondtd\_\{t\}and the full\-batch CA directiond​\(xt\)d\(x\_\{t\}\)\. It is therefore used to characterize the conflict\-avoidance ability of stochastic MOL algorithms\.

## IIIREGULARITY\-AWARE STOCHASTIC MGDA

In this section, we first study the continuity properties of the CA direction mapping, identifying the conditions under which it is Lipschitz continuous and the regimes in which only1/21/2\-Hölder continuity is available\. Motivated by these findings, we then develop a stochastic Multi\-objective Regularity\-aware \(MoRe\) algorithm and establish its convergence and conflict\-avoidance guarantees\.

### III\-AContinuity properties of the CA direction mapping

Although the optimizerλQ∗\\lambda\_\{Q\}^\{\*\}of the simplex subproblem \([10](https://arxiv.org/html/2607.15412#S2.E10)\) may not be unique, the resulting directiondQ=−Q​λQ∗d\_\{Q\}=\-Q\\lambda\_\{Q\}^\{\*\}is unique, since it is the minimum\-norm point in the convex hull of\{qZ,1​\(x\),…,qZ,M​\(x\)\}\\\{q\_\{Z,1\}\(x\),\\ldots,q\_\{Z,M\}\(x\)\\\}\. We show that the mappingQ↦dQQ\\mapsto d\_\{Q\}is Lipschitz continuous under a suitable nondegeneracy condition, but in general only1/21/2\-Hölder continuous on bounded sets\.

###### Definition 2\(μ\\mu\-nondegeneracy\)\.

LetP:=I−1M​𝟏𝟏⊤P:=I\-\\frac\{1\}\{M\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}be the orthogonal projector onto𝟏⟂:=\{v∈ℝM:𝟏⊤​v=0\}\\mathbf\{1\}^\{\\perp\}:=\\\{v\\in\\mathbb\{R\}^\{M\}:\\mathbf\{1\}^\{\\top\}v=0\\\}\. LetU∈ℝM×\(M−1\)U\\in\\mathbb\{R\}^\{M\\times\(M\-1\)\}be any matrix whose columns form an orthonormal basis of𝟏⟂\\mathbf\{1\}^\{\\perp\}, so thatU⊤​U=IU^\{\\top\}U=IandU​U⊤=PUU^\{\\top\}=P\. We say a matrixQ∈ℝp×MQ\\in\\mathbb\{R\}^\{p\\times M\}isμ\\mu\-nondegenerate if

μmin​\(U⊤​Q⊤​Q​U\)≥μ\.\\mu\_\{\\min\}\\\!\\left\(U^\{\\top\}Q^\{\\top\}QU\\right\)\\geq\\mu\.\(12\)Equivalently,‖Q​v‖2≥μ​‖v‖2\\\|Qv\\\|^\{2\}\\geq\\mu\\\|v\\\|^\{2\}for everyv∈𝟏⟂v\\in\\mathbf\{1\}^\{\\perp\}\.

Definition[2](https://arxiv.org/html/2607.15412#Thmdefinition2)imposes a uniform positive\-curvature condition on the dual subproblem \([10](https://arxiv.org/html/2607.15412#S2.E10)\) restricted to feasible simplex directions\. In particular,U⊤​Q⊤​Q​UU^\{\\top\}Q^\{\\top\}QUis the reduced curvature matrix on the tangent space of the simplex, and the lower boundμmin​\(U⊤​Q⊤​Q​U\)≥μ\\mu\_\{\\min\}\(U^\{\\top\}Q^\{\\top\}QU\)\\geq\\murules out degeneracy in this reduced space\. Equivalently, the quadratic objectivegQ​\(λ\)=‖Q​λ‖2g\_\{Q\}\(\\lambda\)=\\\|Q\\lambda\\\|^\{2\}is strongly convex on the affine hull of the simplex, i\.e\., along directions in𝟏⟂\\mathbf\{1\}^\{\\perp\}\. This reduced strong convexity yields uniqueness of the MGDA weight and allows perturbations of the optimality conditions to be controlled directly, which is the key ingredient used to establish Lipschitz continuity of the CA direction mapping\.

###### Lemma 1\(Lipschitz continuity ofdQd\_\{Q\}w\.r\.t\.QQ\)\.

SupposeQ1,Q2∈ℝp×MQ\_\{1\},Q\_\{2\}\\in\\mathbb\{R\}^\{p\\times M\}satisfy‖Qi‖F≤B\\\|Q\_\{i\}\\\|\_\{F\}\\leq Band areμ\\mu\-nondegenerate in the sense of Definition[2](https://arxiv.org/html/2607.15412#Thmdefinition2); that is,μmin​\(U⊤​Qi⊤​Qi​U\)≥μ\\mu\_\{\\min\}\\\!\\left\(U^\{\\top\}Q\_\{i\}^\{\\top\}Q\_\{i\}U\\right\)\\geq\\mu, fori=1,2i=1,2\. Then the mappingQ↦dQQ\\mapsto d\_\{Q\}is Lipschitz continuous\. In particular, there exists a constantℓd=1\+2​B2μ\\ell\_\{d\}=1\+\\frac\{2B^\{2\}\}\{\\mu\}such that

‖dQ1−dQ2‖≤ℓd​‖Q1−Q2‖\.\\\|d\_\{Q\_\{1\}\}\-d\_\{Q\_\{2\}\}\\\|\\leq\\ell\_\{d\}\\\|Q\_\{1\}\-Q\_\{2\}\\\|\.\(13\)Here∥⋅∥\\\|\\cdot\\\|denotes the spectral norm for matrices\. Since‖A‖≤‖A‖F\\\|A\\\|\\leq\\\|A\\\|\_\{F\}, the same bound also holds with‖Q1−Q2‖F\\\|Q\_\{1\}\-Q\_\{2\}\\\|\_\{F\}on the right\-hand side\.

Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)shows that, on any bounded set of matrices satisfying Definition[2](https://arxiv.org/html/2607.15412#Thmdefinition2), the CA direction depends Lipschitz continuously on the gradient matrix\. Consequently, mini\-batch noise inQQtranslates into controlled errors in the update directiondQd\_\{Q\}, which is essential for the convergence analysis of stochastic MGDA methods\. The proof of Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)is deferred to Appendix[B\-A](https://arxiv.org/html/2607.15412#A2.SS1)\.

###### Lemma 2\(Sharpness of the1/21/2\-Hölder exponent\)\.

For anyQ,Q′∈ℝp×MQ,Q^\{\\prime\}\\in\\mathbb\{R\}^\{p\\times M\}satisfying‖Q‖F≤B\\\|Q\\\|\_\{F\}\\leq Band‖Q′‖F≤B\\\|Q^\{\\prime\}\\\|\_\{F\}\\leq B, the mappingQ↦dQQ\\mapsto d\_\{Q\}is1/21/2\-Hölder continuous on this bounded set; moreover, without additional assumptions, no Hölder continuity with exponentη\>12\\eta\>\\tfrac\{1\}\{2\}holds in general\.

Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)indicates that the continuity result in Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)cannot be extended to the general case\. Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)also agrees with the1/21/2\-Hölder continuity of the CA direction mapping established in\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\], while further showing that the exponent12\\tfrac\{1\}\{2\}is sharp in the worst case\. This is analogous to the result in\[[14](https://arxiv.org/html/2607.15412#bib.bib4)\], which establishes1/21/2\-Hölder continuity of the CA direction with respect to the model variablexxand shows that the exponent is optimal\. Therefore, stochastic MGDA may behave differently in regular and degenerate regimes: in regular regimes, mini\-batch perturbations inQQinduce Lipschitz\-controlled changes indQd\_\{Q\}, whereas in degenerate regimes, only1/21/2\-Hölder control is available\. This distinction motivates the adaptive strategy developed in Algorithm[1](https://arxiv.org/html/2607.15412#alg1)\. The proof of Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)is deferred to Appendix[B\-B](https://arxiv.org/html/2607.15412#A2.SS2)\.

Algorithm 1MoRe: Multi\-objective Regularity\-aware method1:inputtraining data

S=\(z1,…,zn\)S=\(z\_\{1\},\\ldots,z\_\{n\}\), initial model

x0x\_\{0\}, step sizes

\{αt\}t=0T−1\\\{\\alpha\_\{t\}\\\}\_\{t=0\}^\{T\-1\}, batch sizes

\{\|Zt\|\}t=0T−1\\\{\|Z\_\{t\}\|\\\}\_\{t=0\}^\{T\-1\}, thresholds

\{μt\}t=0T−1\\\{\\mu\_\{t\}\\\}\_\{t=0\}^\{T\-1\}, fallback weight

λ0∈ΔM\\lambda\_\{0\}\\in\\Delta^\{M\}, and an orthonormal basis

U∈ℝM×\(M−1\)U\\in\\mathbb\{R\}^\{M\\times\(M\-1\)\}of

𝟏⟂\\mathbf\{1\}^\{\\perp\}\.

2:for

t=0,…,T−1t=0,\\dots,T\-1do

3:Sample

ZtZ\_\{t\}i\.i\.d\. uniformly from

SS
4:Compute

Qt=\[qZt,1​\(xt\),…,qZt,M​\(xt\)\]Q\_\{t\}=\[q\_\{Z\_\{t\},1\}\(x\_\{t\}\),\\dots,q\_\{Z\_\{t\},M\}\(x\_\{t\}\)\]
5:if

μmin​\(U⊤​Qt⊤​Qt​U\)≥μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)\\geq\\mu\_\{t\}then

6:Update

λt\\lambda\_\{t\}by \([14](https://arxiv.org/html/2607.15412#S3.E14)\)

7:else

8:set

λt=λ0\\lambda\_\{t\}=\\lambda\_\{0\}
9:endif

10:Update

xt\+1x\_\{t\+1\}by \([15](https://arxiv.org/html/2607.15412#S3.E15)\)

11:endfor

12:output

xTx\_\{T\}\.

![Refer to caption](https://arxiv.org/html/2607.15412v1/x1.png)Figure 1:Flowchart of the proposed MoRe algorithm\. The illustrations show the switching rule in the two\-objective case, whereμmin​\(U⊤​Qt⊤​Qt​U\)=12​‖qZt,1−qZt,2‖2\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)=\\frac\{1\}\{2\}\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|^\{2\}measures the distance or conflict between the two stochastic gradients\. Whenμmin​\(U⊤​Qt⊤​Qt​U\)≥μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)\\geq\\mu\_\{t\}, the algorithm uses the MGDA conflict\-avoidant update direction\. Otherwise, the stochastic gradient matrix is treated as nearly degenerate and the algorithm switches to the fixed\-weight scalarization directiondt=−Qt​λ0d\_\{t\}=\-Q\_\{t\}\\lambda\_\{0\}\.
### III\-BRegularity\-aware stochastic MGDA

Building on the continuity results above, we propose a regularity\-aware stochastic MGDA method\. In particular, Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)shows that the CA direction is Lipschitz continuous w\.r\.t\.QQunder a nondegeneracy condition\. Hence, mini\-batch noise inQQonly induces a proportionally controlled perturbation in the resulting update direction\. In contrast, Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)shows that such Lipschitz stability may fail in degenerate regimes where small stochastic perturbations ofQQcan lead to much larger changes in the CA direction\.

Motivated by this distinction, as shown in Figure[1](https://arxiv.org/html/2607.15412#S3.F1), Algorithm[1](https://arxiv.org/html/2607.15412#alg1)adaptively switches between the stochastic MGDA weight and a fixed scalarization weight according to the regularity of the stochastic gradient matrix\. When the stochastic MGDA subproblem is well\-conditioned, the algorithm uses the CA direction to exploit CA gradient aggregation\. When the subproblem is degenerate or nearly degenerate, the MGDA weight can be highly sensitive to mini\-batch noise; the algorithm therefore uses a fixed scalarization weightλ0\\lambda\_\{0\}, or static weighting, to avoid amplifying the noise in the optimizer of the simplex subproblem\. The fallback weightλ0\\lambda\_\{0\}can be chosen as any prescribed simplex vector reflecting a preferred scalarization; for example, in our experiments, we use the uniform choiceλ0=1M​𝟏\\lambda\_\{0\}=\\frac\{1\}\{M\}\\mathbf\{1\}\.

Specifically, at iterationtt, a mini\-batchZtZ\_\{t\}is drawn independently with replacement from the empirical distribution onSS\. We then form the stochastic gradient matrixQt=\[qZt,1​\(xt\),…,qZt,M​\(xt\)\]Q\_\{t\}=\\big\[q\_\{Z\_\{t\},1\}\(x\_\{t\}\),\\ldots,q\_\{Z\_\{t\},M\}\(x\_\{t\}\)\\big\], which collects the mini\-batch stochastic gradientsqZt,m​\(xt\)q\_\{Z\_\{t\},m\}\(x\_\{t\}\)form∈\[M\]m\\in\[M\]\. When the nondegeneracy conditionμmin​\(U⊤​Qt⊤​Qt​U\)≥μt\\mu\_\{\\min\}\\\!\\left\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\\right\)\\geq\\mu\_\{t\}holds, we compute the MGDA weight by solving

λt=λQt∗∈arg⁡minλ∈ΔM‖Qt​λ‖2\.\\lambda\_\{t\}=\\lambda\_\{Q\_\{t\}\}^\{\*\}\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\_\{t\}\\lambda\\\|^\{2\}\.\(14\)Otherwise, the algorithm falls back to a fixed simplex weightλt=λ0∈ΔM\\lambda\_\{t\}=\\lambda\_\{0\}\\in\\Delta^\{M\}\. In both cases, the model is updated by

xt\+1=xt−αt​Qt​λt\.x\_\{t\+1\}=x\_\{t\}\-\\alpha\_\{t\}Q\_\{t\}\\lambda\_\{t\}\.\(15\)That is, the proposed method uses the stochastic CA direction when the nondegeneracy condition holds, and switches to a fixed scalarization rule otherwise\. The threshold sequence\{μt\}t≥0\\\{\\mu\_\{t\}\\\}\_\{t\\geq 0\}controls how strict the algorithm is in declaring the stochastic MGDA subproblem to be well\-conditioned\. We set the threshold schedule\{μt\}t≥0\\\{\\mu\_\{t\}\\\}\_\{t\\geq 0\}so that0<μt≤μ¯0<\\mu\_\{t\}\\leq\\bar\{\\mu\}for some finite constantμ¯\\bar\{\\mu\}\.

This design exploits the continuity of the CA direction in nondegenerate regimes and avoids relying on it in degenerate regimes, where the update direction can be sensitive to mini\-batch noise\.

### III\-CTheoretical analysis

In this subsection, we provide theoretical guarantees for the proposed MoRe method\. We first introduce the assumptions used throughout the analysis, and then establish convergence in terms of the Pareto stationarity measure, together with bounds on the CA direction distance\.

###### Assumption 1\(Finite lower bounds\)\.

For eachm∈\[M\]m\\in\[M\],infxfS,m​\(x\)\>−∞\.\\inf\_\{x\}f\_\{S,m\}\(x\)\>\-\\infty\.

Assumption[1](https://arxiv.org/html/2607.15412#Thmassumption1)is mild and standard in convergence analysis\. It ensures that every fixed scalarization of the empirical objectives is bounded below\.

###### Assumption 2\(Unbiasedness and bounded variance\)\.

Letℱt\\mathcal\{F\}\_\{t\}be the sigma\-field generated by all randomness up to the beginning of iterationtt, before samplingZtZ\_\{t\}\. Conditional onℱt\\mathcal\{F\}\_\{t\},Zt=\(ζt,r\)r=1\|Zt\|Z\_\{t\}=\(\\zeta\_\{t,r\}\)\_\{r=1\}^\{\|Z\_\{t\}\|\}is sampled i\.i\.d\. uniformly fromSS\. There exists a constantσ\>0\\sigma\>0, independent oftt,mm, and the algorithmic trajectory, such that for everyttand everym∈\[M\]m\\in\[M\], almost surely,

𝔼​\[qZt,m​\(xt\)∣ℱt\]=∇fS,m​\(xt\),\\displaystyle\\mathbb\{E\}\[q\_\{Z\_\{t\},m\}\(x\_\{t\}\)\\mid\\mathcal\{F\}\_\{t\}\]=\\nabla f\_\{S,m\}\(x\_\{t\}\),\(16\)𝔼​\[‖qZt,m​\(xt\)−∇fS,m​\(xt\)‖2∣ℱt\]≤σ2\|Zt\|\.\\displaystyle\\mathbb\{E\}\\\!\\left\[\\\|q\_\{Z\_\{t\},m\}\(x\_\{t\}\)\-\\nabla f\_\{S,m\}\(x\_\{t\}\)\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\}\\right\]\\leq\\frac\{\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\.\(17\)

Assumption[2](https://arxiv.org/html/2607.15412#Thmassumption2)requires the stochastic gradients to be unbiased and to have bounded variance\. This is standard in stochastic optimization\[[11](https://arxiv.org/html/2607.15412#bib.bib3),[6](https://arxiv.org/html/2607.15412#bib.bib5)\], and will be used to control the stochastic error introduced by mini\-batch gradient estimation\.

###### Assumption 3\(Smoothness\)\.

There exists a constantℓf,1\>0\\ell\_\{f,1\}\>0such that, for everyλ∈ΔM\\lambda\\in\\Delta^\{M\}, the scalarized empirical objectivex↦λ⊤​FS​\(x\)x\\mapsto\\lambda^\{\\top\}F\_\{S\}\(x\)isℓf,1\\ell\_\{f,1\}\-smooth onℝp\\mathbb\{R\}^\{p\}\.

###### Assumption 4\(Bounded gradients\)\.

There exist finite positive constantsℓf\\ell\_\{f\}andℓF=M​ℓf\\ell\_\{F\}=\\sqrt\{M\}\\ell\_\{f\}such that, for everyx∈ℝpx\\in\\mathbb\{R\}^\{p\},z∈𝒵z\\in\\mathcal\{Z\}, andm∈\[M\]m\\in\[M\],‖∇fz,m​\(x\)‖≤ℓf\\\|\\nabla f\_\{z,m\}\(x\)\\\|\\leq\\ell\_\{f\}\. SinceqZ,m​\(x\)=\|Z\|−1​∑r=1\|Z\|∇fζr,m​\(x\)q\_\{Z,m\}\(x\)=\|Z\|^\{\-1\}\\sum\_\{r=1\}^\{\|Z\|\}\\nabla f\_\{\\zeta\_\{r\},m\}\(x\), the triangle inequality gives‖qZ,m​\(x\)‖≤ℓf\\\|q\_\{Z,m\}\(x\)\\\|\\leq\\ell\_\{f\}\. Therefore, for every mini\-batchZZ, everytt, and everyλ∈ΔM\\lambda\\in\\Delta^\{M\},

‖Qt​λ‖\\displaystyle\\\|Q\_\{t\}\\lambda\\\|≤ℓf,‖∇FS​\(xt\)​λ‖≤ℓf,\\displaystyle\\leq\\ell\_\{f\},\\quad\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|\\leq\\ell\_\{f\},‖Qt‖F\\displaystyle\\\|Q\_\{t\}\\\|\_\{F\}≤ℓF,‖∇FS​\(xt\)‖F≤ℓF\.\\displaystyle\\leq\\ell\_\{F\},\\quad\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\leq\\ell\_\{F\}\.\(18\)

Assumptions[3](https://arxiv.org/html/2607.15412#Thmassumption3)and[4](https://arxiv.org/html/2607.15412#Thmassumption4)are also standard in gradient\-based MOL analysis\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]\. Assumption[3](https://arxiv.org/html/2607.15412#Thmassumption3)is used to establish the descent property of the scalarized objective, while Assumption[4](https://arxiv.org/html/2607.15412#Thmassumption4)controls the magnitudes of both the empirical and stochastic gradients along the optimization trajectory\.

###### Theorem 1\.

Suppose Assumptions[1](https://arxiv.org/html/2607.15412#Thmassumption1),[2](https://arxiv.org/html/2607.15412#Thmassumption2),[3](https://arxiv.org/html/2607.15412#Thmassumption3), and[4](https://arxiv.org/html/2607.15412#Thmassumption4)hold\. Letαt=α\\alpha\_\{t\}=\\alphafor alltt, and let the threshold sequence satisfy0<μt≤μ¯0<\\mu\_\{t\}\\leq\\bar\{\\mu\}for a finite constantμ¯\\bar\{\\mu\}\. Then the iterates generated by Algorithm[1](https://arxiv.org/html/2607.15412#alg1)satisfy

𝔼\[min0≤t≤T−1RS\(xt\)\]≤𝒪\(1α​T\+α\+1T∑t=0T−11\|Zt\|\\displaystyle\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}R\_\{S\}\(x\_\{t\}\)\\right\]\\leq\\mathcal\{O\}\\\!\\Biggl\(\\frac\{1\}\{\\alpha T\}\+\\alpha\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\sqrt\{\|Z\_\{t\}\|\}\}\+1T∑t=0T−11μt​\|Zt\|\+1T∑t=0T−11\|Zt\|​μt3/2\)\\displaystyle\\qquad\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\mu\_\{t\}\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\}\\Biggr\)\.\(19\)Suppose the mini\-batch sizes and the constant step size satisfy

\|Zt\|=Θ​\(t\+1\),α=Θ​\(T−1/2\)\.\\displaystyle\{\|Z\_\{t\}\|=\\Theta\(t\+1\),\\qquad\\alpha=\\Theta\(T^\{\-1/2\}\)\.\}\(20\)Under this schedule, the following two consequences hold\. Ifμt=Θ​\(1\)\\mu\_\{t\}=\\Theta\(1\), then

𝔼​\[min0≤t≤T−1⁡RS​\(xt\)\]=𝒪​\(T−1/2\)\.\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}R\_\{S\}\(x\_\{t\}\)\\right\]=\\mathcal\{O\}\(T^\{\-1/2\}\)\.\(21\)If insteadμt=Θ​\(1log⁡\(e\+t\)\),\\mu\_\{t\}=\\Theta\\\!\\left\(\\frac\{1\}\{\\log\(e\+t\)\}\\right\),then

𝔼​\[min0≤t≤T−1⁡RS​\(xt\)\]=𝒪~​\(T−1/2\)\.\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}R\_\{S\}\(x\_\{t\}\)\\right\]=\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)\.\(22\)

Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)shows that the regularity thresholdμt\\mu\_\{t\}controls the convergence rate through the continuity of the CA direction mapping\. In particular, a uniformly positive threshold gives the exact𝒪​\(T−1/2\)\\mathcal\{O\}\(T^\{\-1/2\}\)rate, whereas a logarithmically decaying threshold preserves a𝒪~​\(T−1/2\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)rate while allowing the CA direction distance to decay\. The detailed proof is provided in Appendix[B\-C](https://arxiv.org/html/2607.15412#A2.SS3)\.

Beyond convergence in terms of Pareto stationarity, we also analyze how well the stochastic update direction aligns with the corresponding full\-batch CA direction\. The following theorem bounds the CA direction distance, thereby quantifying the conflict\-avoidance behavior of the proposed method\.

![Refer to caption](https://arxiv.org/html/2607.15412v1/figure/ca_convergence_tradeoff.png)Figure 2:Rate trade\-off under the choiceμt=Θ​\(\(t\+1\)−γ\)\\mu\_\{t\}=\\Theta\(\(t\+1\)^\{\-\\gamma\}\),0<γ<1/20<\\gamma<1/2, with linearly growing mini\-batch size\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\)and step sizeα=Θ​\(T−1/2\)\\alpha=\\Theta\(T^\{\-1/2\}\)\. MoRe achieves CA distance exponentmin⁡\{γ,1−2​γ\}\\min\\\{\\gamma,1\-2\\gamma\\\}and convergence exponent1/2−γ1/2\-\\gamma\. The additional term1/\(\|Zt\|​μt3/2\)1/\(\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\)in Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)contributes exponent1−3​γ/21\-3\\gamma/2, which is larger than1/2−γ1/2\-\\gammafor the plotted range and therefore is not rate\-limiting\. The SMG rates are shown as horizontal baselines since they are independent ofμt\\mu\_\{t\}\.###### Theorem 2\.

Suppose Assumptions[2](https://arxiv.org/html/2607.15412#Thmassumption2)and[4](https://arxiv.org/html/2607.15412#Thmassumption4)hold, and letM=2M=2\. Let the threshold sequence satisfy0<μt≤μ¯0<\\mu\_\{t\}\\leq\\bar\{\\mu\}for a finite constantμ¯\\bar\{\\mu\}\. Then the CA direction distance satisfies

ℰca​\(t\)=𝒪​\(1\|Zt\|​μt2\+1\|Zt\|\+μt\)\.\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\|Z\_\{t\}\|\\,\\mu\_\{t\}^\{2\}\}\+\\frac\{1\}\{\|Z\_\{t\}\|\}\+\\mu\_\{t\}\\right\)\.\(23\)In particular, if the mini\-batch size grows linearly, i\.e\.,\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\), andμt=Θ​\(1log⁡\(e\+t\)\)\\mu\_\{t\}=\\Theta\\\!\\left\(\\frac\{1\}\{\\log\(e\+t\)\}\\right\), then

ℰca​\(t\)=𝒪​\(1log⁡\(e\+t\)\)\.\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\\log\(e\+t\)\}\\right\)\.\(24\)

Theorem[2](https://arxiv.org/html/2607.15412#Thmtheorem2)shows that, in the two\-objective case, the CA direction distance is controlled by both the batch size\|Zt\|\|Z\_\{t\}\|and the regularity thresholdμt\\mu\_\{t\}\. The logarithmic choiceμt=Θ​\(1/log⁡\(e\+t\)\)\\mu\_\{t\}=\\Theta\(1/\\log\(e\+t\)\)matches the schedule used in Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1); it gives a vanishing CA distance while preserving the𝒪~​\(T−1/2\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)convergence guarantee\. Alternatively, if one prioritizes the CA distance, the choiceμt=Θ​\(\(t\+1\)−1/3\)\\mu\_\{t\}=\\Theta\(\(t\+1\)^\{\-1/3\}\)yields the sharper rateℰca​\(t\)=𝒪​\(\(t\+1\)−1/3\)\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)=\\mathcal\{O\}\(\(t\+1\)^\{\-1/3\}\)\. Thus, the choice ofμt\\mu\_\{t\}provides a trade\-off between conflict\-avoidance and convergence speed\. The proof of Theorem[2](https://arxiv.org/html/2607.15412#Thmtheorem2)is deferred to Appendix[B\-D](https://arxiv.org/html/2607.15412#A2.SS4)\.

Figure[2](https://arxiv.org/html/2607.15412#S3.F2)illustrates the rate trade\-off induced byμt=Θ​\(\(t\+1\)−γ\)\\mu\_\{t\}=\\Theta\(\(t\+1\)^\{\-\\gamma\}\)\. Increasingγ\\gammaimproves the CA direction distance up to the optimal choiceμt=Θ​\(\(t\+1\)−1/3\)\\mu\_\{t\}=\\Theta\(\(t\+1\)^\{\-1/3\}\), but decreases the convergence exponent from1/21/2to1/2−γ1/2\-\\gamma, slowing the convergence rate\. Thus,μt\\mu\_\{t\}acts as a tuning parameter between conflict\-avoidance and convergence speed\. In contrast, the SMG rates remain fixed because they are independent ofμt\\mu\_\{t\}\.

## IVEXPERIMENT

In this section, we empirically evaluate the proposed MoRe method on the Office\-Home benchmark, and compare it with several representative MOL baselines\.

### IV\-AExperiment setting

We follow the same experimental setting as in\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]and use the LibMTL framework\[[9](https://arxiv.org/html/2607.15412#bib.bib21)\]\. For each algorithm, we report both individual task performance and a holistic metricΔAid%\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%, defined as

ΔAid%=1M​∑m=1M\(−1\)ℓm​SA,m−SB,mSB,m×100,\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%=\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}\(\-1\)^\{\\ell\_\{m\}\}\\frac\{S\_\{A,m\}\-S\_\{B,m\}\}\{S\_\{B,m\}\}\\times 100,\(25\)whereMMis the number of tasks,SA,mS\_\{A,m\}denotes the performance of methodAAon taskmm, andSB,mS\_\{B,m\}denotes the performance of the corresponding independent single\-task learner\. Here,ℓm=1\\ell\_\{m\}=1if a larger value of the metric indicates better performance, andℓm=0\\ell\_\{m\}=0otherwise\. This metric captures the average performance degradation of an MOL algorithm relative to dedicated single\-task learners\. Therefore, a smallerΔAid%\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%indicates better overall multi\-task performance\.

### IV\-BOffice\-home benchmark

Next, we evaluate the proposed method on the Office\-Home benchmark\[[16](https://arxiv.org/html/2607.15412#bib.bib22)\], which is a four\-task image classification problem\. The four tasks correspond to four visual domains, namely*Art*,*Clipart*,*Product*, and*Real\-World*, with 65 object categories in each domain\. In our computation ofΔAid%\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%, the independent single\-task learner accuracies used asSB,mS\_\{B,m\}are66\.86%66\.86\\%,82\.02%82\.02\\%,91\.38%91\.38\\%, and81\.24%81\.24\\%for*Art*,*Clipart*,*Product*, and*Real\-World*, respectively\. These independent baselines are obtained under our experimental setting and may differ from those used in prior works; therefore, the resultingΔAid%\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%values may not be numerically identical to reported values in previous works\.

As shown in Table[II](https://arxiv.org/html/2607.15412#S4.T2), MoRe improves the performance on Art, Clipart, and Real\-World, and achieves a better holistic degradation metricΔAid%\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%\. Although it slightly sacrifices Product accuracy compared with MoDo, the overall results suggest that MoRe provides a favorable trade\-off across tasks and is effective for multi\-task image classification\. Figure[3](https://arxiv.org/html/2607.15412#S4.F3)shows the convergence behavior of the proposed method\. We evaluate the empirical Pareto\-stationarity measureRS​\(xt\)R\_\{S\}\(x\_\{t\}\)using full\-batch training gradients, matching the quantity analyzed in Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)\. Under the parameter settingα=Θ​\(T−1/2\)\\alpha=\\Theta\(T^\{\-1/2\}\),\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\), andμt=Θ​\(1\)\\mu\_\{t\}=\\Theta\(1\), the stationarity measure decreases steadily, with an empirical trend consistent with the𝒪​\(T−1/2\)\\mathcal\{O\}\(T^\{\-1/2\}\)rate in Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)\.

TABLE II:Test accuracy on the Office\-Home dataset\.MethodArtClipartProductReal\-WorldΔAid%↓\\Delta\_\{A\}^\{\\mathrm\{id\}\}\\%\\downarrowCAGrad\[[10](https://arxiv.org/html/2607.15412#bib.bib71)\]63\.7575\.9489\.0878\.274\.56MoCo\[[6](https://arxiv.org/html/2607.15412#bib.bib5)\]64\.1479\.8589\.6279\.572\.68MoDo\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]65\.5079\.4489\.7279\.652\.58Ours66\.7980\.1788\.4581\.841\.21![Refer to caption](https://arxiv.org/html/2607.15412v1/figure/conv.png)Figure 3:Convergence curve of the MoRe algorithm on Office\-Home\. The solid curve shows the empirical Pareto stationarity measureRS​\(xt\)R\_\{S\}\(x\_\{t\}\), while the dashed line shows the reference ratec/Tc/\\sqrt\{T\}\. The observed decay is consistent with the theoretical𝒪​\(T−1/2\)\\mathcal\{O\}\(T^\{\-1/2\}\)convergence rate established in Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)\.

## VCONCLUSION

This paper studied the continuity property of the MGDA update direction mapping in stochastic MOL and used this property to guide algorithm design\. We showed that the CA direction is1/21/2\-Hölder continuous on bounded sets, and this exponent is sharp in the worst case\. Furthermore, a stronger Lipschitz continuity property holds under a regular or nondegenerate condition\. Based on this insight, we proposed MoRe, an adaptive regularity\-aware stochastic MGDA method that uses CA direction updates in nondegenerate regimes, where mini\-batch perturbations can be controlled, and switches to a fixed scalarization weight in degenerate regimes\. By updating in this manner, we showed an improved convergence rate to Pareto stationarity over vanilla stochastic MGDA and a per\-iterate CA\-direction distance guarantee\. Experiments on the Office\-Home benchmark further demonstrated the effectiveness of the proposed method in both multi\-task performance and convergence behavior\. One limitation is that the per\-iterate CA\-direction distance analysis is restricted toM=2M=2\. Extending this analysis to the general multi\-objective settingM\>2M\>2is left for future work\.

## References

- \[1\]\(2024\)Three\-way trade\-off in multi\-objective learning: optimization, generalization and conflict\-avoidance\.Journal of Machine Learning Research25\(193\),pp\. 1–53\.Cited by:[§B\-B](https://arxiv.org/html/2607.15412#A2.SS2.1.p1.16),[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[§I\-B](https://arxiv.org/html/2607.15412#S1.SS2.p1.5),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1.10.8.3),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1.4.2.3),[§I](https://arxiv.org/html/2607.15412#S1.p3.1),[§I](https://arxiv.org/html/2607.15412#S1.p4.11),[§II\-B](https://arxiv.org/html/2607.15412#S2.SS2.p2.1),[§II](https://arxiv.org/html/2607.15412#S2.p2.4),[§III\-A](https://arxiv.org/html/2607.15412#S3.SS1.p4.7),[§III\-C](https://arxiv.org/html/2607.15412#S3.SS3.p4.1),[§IV\-A](https://arxiv.org/html/2607.15412#S4.SS1.p1.1),[TABLE II](https://arxiv.org/html/2607.15412#S4.T2.1.4.1)\.
- \[2\]L\. Chen, S\. T\. Jose, I\. Nikoloska, S\. Park, T\. Chen, and O\. Simeone\(2023\)Learning with limited samples: meta\-learning and applications to communication systems\.Foundations and Trends® in Signal Processing17\(2\),pp\. 79–208\.Cited by:[§I](https://arxiv.org/html/2607.15412#S1.p1.1)\.
- \[3\]L\. Chen, A\. F\. M\. Saif, Y\. Shen, and T\. Chen\(2024\)FERERO: a flexible framework for preference\-guided multi\-objective learning\.InProc\. Advances Neural Inf\. Process\. Syst\.,Vol\.37,Vancouver, Canada,pp\. 18758–18805\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2)\.
- \[4\]J\. Désidéri\(2012\)Multiple\-gradient descent algorithm \(mgda\) for multiobjective optimization\.Comptes Rendus\. Mathématique350\(5\-6\),pp\. 313–318\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[§I](https://arxiv.org/html/2607.15412#S1.p3.1),[§II\-A](https://arxiv.org/html/2607.15412#S2.SS1.p1.1),[§II](https://arxiv.org/html/2607.15412#S2.p2.4)\.
- \[5\]H\. Fernando, L\. Chen, S\. Lu, P\. Chen, M\. Liu, S\. Chaudhury, K\. Murugesan, G\. Liu, M\. Wang, and T\. Chen\(2024\)Variance reduction can improve trade\-off in multi\-objective learning\.InProc\. IEEE Int\. Conf\. Acoustics, Speech Signal Process\.,pp\. 6975–6979\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1.12.10.3)\.
- \[6\]H\. Fernando, H\. Shen, M\. Liu, S\. Chaudhury, K\. Murugesan, and T\. Chen\(2023\-05\)Mitigating gradient bias in multi\-objective learning: a provably convergent approach\.InProc\. Int\. Conf\. Learn\. Representations,Kigali, Rwanda\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1.8.6.3),[§I](https://arxiv.org/html/2607.15412#S1.p3.1),[§II](https://arxiv.org/html/2607.15412#S2.p2.4),[§III\-C](https://arxiv.org/html/2607.15412#S3.SS3.p3.1),[TABLE II](https://arxiv.org/html/2607.15412#S4.T2.1.3.1)\.
- \[7\]J\. Fliege and B\. F\. Svaiter\(2000\)Steepest descent methods for multicriteria optimization\.Mathematical methods of operations research51,pp\. 479–494\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[§I](https://arxiv.org/html/2607.15412#S1.p3.1)\.
- \[8\]R\. A\. Horn and C\. R\. Johnson\(2012\)Matrix analysis\.2 edition,Cambridge University Press\.Cited by:[§B\-C](https://arxiv.org/html/2607.15412#A2.SS3.1.p1.14)\.
- \[9\]B\. Lin and Y\. Zhang\(2023\)LibMTL: a python library for deep multi\-task learning\.Journal of Machine Learning Research24\(209\),pp\. 1–7\.Cited by:[§IV\-A](https://arxiv.org/html/2607.15412#S4.SS1.p1.1)\.
- \[10\]B\. Liu, X\. Liu, X\. Jin, P\. Stone, and Q\. Liu\(2021\-12\)Conflict\-Averse Gradient Descent for Multi\-task Learning\.InProc\. Advances Neural Inf\. Process\. Syst\.,Vol\.34,virtual,pp\. 18878–18890\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[§I](https://arxiv.org/html/2607.15412#S1.p3.1),[TABLE II](https://arxiv.org/html/2607.15412#S4.T2.1.2.1)\.
- \[11\]S\. Liu and L\. N\. Vicente\(2024\)The stochastic multi\-gradient algorithm for multi\-objective optimization and its application to supervised machine learning\.Annals of Operations Research339\(3\),pp\. 1119–1148\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1.4.2.3),[§I](https://arxiv.org/html/2607.15412#S1.p3.1),[§II\-B](https://arxiv.org/html/2607.15412#S2.SS2.p1.2),[§III\-C](https://arxiv.org/html/2607.15412#S3.SS3.p3.1)\.
- \[12\]H\. Mukai\(1980\)Algorithms for multicriterion optimization\.IEEE Transactions on Automatic Control25\(2\),pp\. 177–186\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[§I](https://arxiv.org/html/2607.15412#S1.p3.1)\.
- \[13\]O\. Sener and V\. Koltun\(2018\)Multi\-task learning as multi\-objective optimization\.InAdvances in Neural Information Processing Systems,Vol\.31\.Cited by:[§I](https://arxiv.org/html/2607.15412#S1.p1.1)\.
- \[14\]B\. F\. Svaiter\(2018\)The multiobjective steepest descent direction is not Lipschitz continuous, but is Hölder continuous\.Operations Research Letters46\(4\),pp\. 430–433\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[§I](https://arxiv.org/html/2607.15412#S1.p4.11),[§III\-A](https://arxiv.org/html/2607.15412#S3.SS1.p4.7)\.
- \[15\]H\. Tanabe, E\. H\. Fukuda, and N\. Yamashita\(2019\)Proximal gradient methods for multiobjective optimization and their applications\.Computational Optimization and Applications72\(2\),pp\. 339–361\.Cited by:[§II](https://arxiv.org/html/2607.15412#S2.p2.4)\.
- \[16\]H\. Venkateswara, J\. Eusebio, S\. Chakraborty, and S\. Panchanathan\(2017\-07\)Deep hashing network for unsupervised domain adaptation\.InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition,pp\. 5018–5027\.Cited by:[§IV\-B](https://arxiv.org/html/2607.15412#S4.SS2.p1.7)\.
- \[17\]P\. Xiao, H\. Ban, and K\. Ji\(2023\)Direction\-oriented multi\-objective learning: simple and provable stochastic algorithms\.InProc\. Advances Neural Inf\. Process\. Syst\.,Vol\.36,New Orleans, LA, USA,pp\. 4509–4533\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2)\.
- \[18\]H\. Yang and J\. T\. Kwok\(2025\-04\)Joint gradient balancing for data ordering in finite\-sum multi\-objective optimization\.InProc\. Int\. Conf\. Learn\. Representations,Singapore\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2)\.
- \[19\]F\. Ye, B\. Lin, Z\. Yue, P\. Guo, Q\. Xiao, and Y\. Zhang\(2021\)Multi\-objective meta learning\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 21338–21351\.Cited by:[§I](https://arxiv.org/html/2607.15412#S1.p1.1)\.
- \[20\]T\. Yu, S\. Kumar, A\. Gupta, S\. Levine, K\. Hausman, and C\. Finn\(2020\-12\)Gradient Surgery for Multi\-Task Learning\.InProc\. Advances Neural Inf\. Process\. Syst\.,Vol\.33,virtual,pp\. 5824–5836\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2)\.
- \[21\]M\. B\. Zafar, I\. Valera, M\. G\. Rogriguez, and K\. P\. Gummadi\(2017\-20–22 Apr\)Fairness constraints: mechanisms for fair classification\.InProceedings of the 20th International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.54,pp\. 962–970\.Cited by:[§I](https://arxiv.org/html/2607.15412#S1.p1.1)\.
- \[22\]S\. Zhou, W\. Zhang, J\. Jiang, W\. Zhong, J\. Gu, and W\. Zhu\(2022\)On the convergence of stochastic multi\-objective gradient manipulation and beyond\.InAdvances in Neural Information Processing Systems,S\. Koyejo, S\. Mohamed, A\. Agarwal, D\. Belgrave, K\. Cho, and A\. Oh \(Eds\.\),Vol\.35,pp\. 38103–38115\.Cited by:[§I\-A](https://arxiv.org/html/2607.15412#S1.SS1.p1.2),[TABLE I](https://arxiv.org/html/2607.15412#S1.T1.6.4.3)\.

## Appendix ANotation

A summary of notation used in this work is listed in Table[III](https://arxiv.org/html/2607.15412#A1.T3)for ease of reference\.

TABLE III:Notation and descriptions\.NotationDescriptionsx∈ℝpx\\in\\mathbb\{R\}^\{p\}Model parameter, or decision variablez∈𝒵z\\in\\mathcal\{Z\},SS,ZZData point, training sample sequence, and mini\-batch, respectively, whereS=\(z1,…,zn\)∈𝒵nS=\(z\_\{1\},\\ldots,z\_\{n\}\)\\in\\mathcal\{Z\}^\{n\},Z=\(ζ1,…,ζ\|Z\|\)Z=\(\\zeta\_\{1\},\\ldots,\\zeta\_\{\|Z\|\}\)is sampled with replacement fromSS\.fz,m​\(x\)f\_\{z,m\}\(x\),fS,m​\(x\)f\_\{S,m\}\(x\)A scalar\-valued objective function evaluated on data pointzz,withfz,m:ℝp→ℝf\_\{z,m\}:\\mathbb\{R\}^\{p\}\\to\\mathbb\{R\}, or on datasetSS,fS,mf\_\{S,m\}, withfS,m​\(x\)≔1n​∑i=1nfzi,m​\(x\)f\_\{S,m\}\(x\)\\coloneqq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}f\_\{z\_\{i\},m\}\(x\)Fz​\(x\)F\_\{z\}\(x\),FS​\(x\)F\_\{S\}\(x\),FZ​\(x\)F\_\{Z\}\(x\)A vector\-valued objective function evaluated on data pointzz,withFz​\(x\):ℝp→ℝMF\_\{z\}\(x\):\\mathbb\{R\}^\{p\}\\to\\mathbb\{R\}^\{M\}, or on datasetSS, withFS​\(x\)≔1n​∑i=1nFzi​\(x\)F\_\{S\}\(x\)\\coloneqq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}F\_\{z\_\{i\}\}\(x\)or on mini\-batchZZ, withFZ​\(x\)≔1\|Z\|​∑r=1\|Z\|Fζr​\(x\)F\_\{Z\}\(x\)\\coloneqq\\frac\{1\}\{\|Z\|\}\\sum\_\{r=1\}^\{\|Z\|\}F\_\{\\zeta\_\{r\}\}\(x\)∇FS​\(x\)\\nabla F\_\{S\}\(x\),∇FZ​\(x\)\\nabla F\_\{Z\}\(x\)Gradient matrices of the empirical objectiveFS​\(x\)F\_\{S\}\(x\)and the mini\-batch objectiveFZ​\(x\)F\_\{Z\}\(x\), respectivelyfm​\(x\)f\_\{m\}\(x\)A scalar\-valued population objective function,fm​\(x\)≔𝔼z​\[fz,m​\(x\)\]f\_\{m\}\(x\)\\coloneqq\\mathbb\{E\}\_\{z\}\[f\_\{z,m\}\(x\)\]∇fm​\(x\)\\nabla f\_\{m\}\(x\)Gradient offm​\(x\)f\_\{m\}\(x\), with∇fm​\(x\):ℝp→ℝp\\nabla f\_\{m\}\(x\):\\mathbb\{R\}^\{p\}\\to\\mathbb\{R\}^\{p\}F​\(x\)F\(x\)A vector\-valued population objective,F​\(x\)≔𝔼z​\[Fz​\(x\)\]F\(x\)\\coloneqq\\mathbb\{E\}\_\{z\}\[F\_\{z\}\(x\)\]∇F​\(x\)\\nabla F\(x\)Gradient ofF​\(x\)F\(x\), with∇F​\(x\):ℝp→ℝp×M\\nabla F\(x\):\\mathbb\{R\}^\{p\}\\to\\mathbb\{R\}^\{p\\times M\}QQ,qZ,m​\(x\)q\_\{Z,m\}\(x\)Stochastic gradient matrix and itsmm\-th column, respectively, whereQ=∇FZ​\(x\)=\[qZ,1​\(x\),…,qZ,M​\(x\)\]∈ℝp×MQ=\\nabla F\_\{Z\}\(x\)=\[q\_\{Z,1\}\(x\),\\ldots,q\_\{Z,M\}\(x\)\]\\in\\mathbb\{R\}^\{p\\times M\}qZ,m​\(x\)=1\|Z\|​∑r=1\|Z\|∇fζr,m​\(x\)∈ℝpq\_\{Z,m\}\(x\)=\\frac\{1\}\{\|Z\|\}\\sum\_\{r=1\}^\{\|Z\|\}\\nabla f\_\{\\zeta\_\{r\},m\}\(x\)\\in\\mathbb\{R\}^\{p\}λ∈ΔM\\lambda\\in\\Delta^\{M\}Weighting parameter in the\(M−1\)\(M\-1\)\-simplexλ∗​\(x\)∈ΔM\\lambda^\{\*\}\(x\)\\in\\Delta^\{M\}CA weight, optimal solution to \([5](https://arxiv.org/html/2607.15412#S2.E5)\)λQ∗∈ΔM\\lambda\_\{Q\}^\{\*\}\\in\\Delta^\{M\}Optimal simplex weight forQQ, solution to \([10](https://arxiv.org/html/2607.15412#S2.E10)\)dQd\_\{Q\},d​\(xt\)d\(x\_\{t\}\),dtd\_\{t\}dQ=−Q​λQ∗d\_\{Q\}=\-Q\\lambda\_\{Q\}^\{\*\}is the CA direction associated withQQ,d​\(xt\)=−∇FS​\(xt\)​λ∗​\(xt\)d\(x\_\{t\}\)=\-\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)is the full\-batch CA direction atxtx\_\{t\},anddt=−Qt​λtd\_\{t\}=\-Q\_\{t\}\\lambda\_\{t\}is the stochastic update direction used at iterationtt\.μt\\mu\_\{t\}Regularity threshold used by Algorithm[1](https://arxiv.org/html/2607.15412#alg1)to decide whether the stochastic subproblem is nondegenerate\.αt\\alpha\_\{t\}Step size for updating the model parameterxx
## Appendix BProof

### B\-AProof of Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)

###### Proof\.

Throughout this proof,∥⋅∥\\\|\\cdot\\\|denotes the spectral norm for matrices and the Euclidean norm for vectors\. By the boundedness condition in Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)and the inequality‖Qi‖≤‖Qi‖F\\\|Q\_\{i\}\\\|\\leq\\\|Q\_\{i\}\\\|\_\{F\}, we have‖Qi‖≤B\\\|Q\_\{i\}\\\|\\leq B,i=1,2i=1,2\. LetλQi∗∈arg⁡minλ∈ΔM‖Qi​λ‖2\\lambda\_\{Q\_\{i\}\}^\{\*\}\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\_\{i\}\\lambda\\\|^\{2\},Ai≔Qi⊤​QiA\_\{i\}\\coloneqq Q\_\{i\}^\{\\top\}Q\_\{i\},i=1,2i=1,2\. By the reduced nondegeneracy condition in Definition[2](https://arxiv.org/html/2607.15412#Thmdefinition2),μmin​\(U⊤​Qi⊤​Qi​U\)≥μ\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{i\}^\{\\top\}Q\_\{i\}U\)\\geq\\mu\. Hence, for anyδ∈𝟏⟂\\delta\\in\\mathbf\{1\}^\{\\perp\}, writingδ=U​z\\delta=Uz, we have

δ⊤​Ai​δ=z⊤​U⊤​Ai​U​z≥μ​‖z‖2=μ​‖δ‖2\.\\delta^\{\\top\}A\_\{i\}\\delta=z^\{\\top\}U^\{\\top\}A\_\{i\}Uz\\geq\\mu\\\|z\\\|^\{2\}=\\mu\\\|\\delta\\\|^\{2\}\.\(26\)Since any two points inΔM\\Delta^\{M\}differ by a vector in𝟏⟂\\mathbf\{1\}^\{\\perp\},gQi​\(λ\)=‖Qi​λ‖2g\_\{Q\_\{i\}\}\(\\lambda\)=\\\|Q\_\{i\}\\lambda\\\|^\{2\}is strongly convex on the affine hull of the simplex\. HenceλQi∗\\lambda\_\{Q\_\{i\}\}^\{\*\}is unique\. The optimality conditions give0∈2​Ai​λQi∗\+NΔM​\(λQi∗\)0\\in 2A\_\{i\}\\lambda\_\{Q\_\{i\}\}^\{\*\}\+N\_\{\\Delta^\{M\}\}\(\\lambda\_\{Q\_\{i\}\}^\{\*\}\), or equivalently,

⟨2​Ai​λQi∗,λ−λQi∗⟩≥0,∀λ∈ΔM\.\\langle 2A\_\{i\}\\lambda\_\{Q\_\{i\}\}^\{\*\},\\lambda\-\\lambda\_\{Q\_\{i\}\}^\{\*\}\\rangle\\geq 0,\\qquad\\forall\\lambda\\in\\Delta^\{M\}\.\(27\)Letδ=λQ1∗−λQ2∗\\delta=\\lambda^\{\*\}\_\{Q\_\{1\}\}\-\\lambda^\{\*\}\_\{Q\_\{2\}\}\. Takingλ=λQ2∗\\lambda=\\lambda^\{\*\}\_\{Q\_\{2\}\}fori=1i=1andλ=λQ1∗\\lambda=\\lambda^\{\*\}\_\{Q\_\{1\}\}fori=2i=2in \([27](https://arxiv.org/html/2607.15412#A2.E27)\) gives⟨A1​λQ1∗,δ⟩≤0\\langle A\_\{1\}\\lambda^\{\*\}\_\{Q\_\{1\}\},\\delta\\rangle\\leq 0and⟨A2​λQ2∗,δ⟩≥0\\langle A\_\{2\}\\lambda^\{\*\}\_\{Q\_\{2\}\},\\delta\\rangle\\geq 0, hence⟨A1​λQ1∗−A2​λQ2∗,δ⟩≤0\\langle A\_\{1\}\\lambda^\{\*\}\_\{Q\_\{1\}\}\-A\_\{2\}\\lambda^\{\*\}\_\{Q\_\{2\}\},\\delta\\rangle\\leq 0\. SinceA1​λQ1∗−A2​λQ2∗=A1​δ\+\(A1−A2\)​λQ2∗A\_\{1\}\\lambda^\{\*\}\_\{Q\_\{1\}\}\-A\_\{2\}\\lambda^\{\*\}\_\{Q\_\{2\}\}=A\_\{1\}\\delta\+\(A\_\{1\}\-A\_\{2\}\)\\lambda^\{\*\}\_\{Q\_\{2\}\}, we haveδ⊤​A1​δ\+⟨\(A1−A2\)​λQ2∗,δ⟩≤0\\delta^\{\\top\}A\_\{1\}\\delta\+\\langle\(A\_\{1\}\-A\_\{2\}\)\\lambda^\{\*\}\_\{Q\_\{2\}\},\\delta\\rangle\\leq 0\. Rearranging this inequality and applying Cauchy–Schwarz gives

δ⊤​A1​δ≤−⟨\(A1−A2\)​λQ2∗,δ⟩≤‖A1−A2‖​‖λQ2∗‖​‖δ‖\.\\displaystyle\\delta^\{\\top\}A\_\{1\}\\delta\\leq\-\\langle\(A\_\{1\}\-A\_\{2\}\)\\lambda^\{\*\}\_\{Q\_\{2\}\},\\delta\\rangle\\leq\\\|A\_\{1\}\-A\_\{2\}\\\|\\,\\\|\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\\,\\\|\\delta\\\|\.\(28\)BecauseλQ2∗∈ΔM\\lambda^\{\*\}\_\{Q\_\{2\}\}\\in\\Delta^\{M\},‖λQ2∗‖≤1\\\|\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\\leq 1\. Also,δ∈𝟏⟂\\delta\\in\\mathbf\{1\}^\{\\perp\}, so \([26](https://arxiv.org/html/2607.15412#A2.E26)\) givesδ⊤​A1​δ≥μ​‖δ‖2\\delta^\{\\top\}A\_\{1\}\\delta\\geq\\mu\\\|\\delta\\\|^\{2\}\. Therefore, combining it with \([28](https://arxiv.org/html/2607.15412#A2.E28)\) yields

‖δ‖=‖λQ1∗−λQ2∗‖≤1μ​‖A1−A2‖\.\\\|\\delta\\\|=\\\|\\lambda^\{\*\}\_\{Q\_\{1\}\}\-\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\\leq\\frac\{1\}\{\\mu\}\\\|A\_\{1\}\-A\_\{2\}\\\|\.\(29\)Moreover,A1−A2=Q1⊤​\(Q1−Q2\)\+\(Q1−Q2\)⊤​Q2A\_\{1\}\-A\_\{2\}=Q\_\{1\}^\{\\top\}\(Q\_\{1\}\-Q\_\{2\}\)\+\(Q\_\{1\}\-Q\_\{2\}\)^\{\\top\}Q\_\{2\}, and hence

‖A1−A2‖≤\(‖Q1‖\+‖Q2‖\)​‖Q1−Q2‖≤2​B​‖Q1−Q2‖\.\\\|A\_\{1\}\-A\_\{2\}\\\|\\leq\(\\\|Q\_\{1\}\\\|\+\\\|Q\_\{2\}\\\|\)\\\|Q\_\{1\}\-Q\_\{2\}\\\|\\leq 2B\\\|Q\_\{1\}\-Q\_\{2\}\\\|\.\(30\)Combining \([29](https://arxiv.org/html/2607.15412#A2.E29)\) and \([30](https://arxiv.org/html/2607.15412#A2.E30)\), we get

‖λQ1∗−λQ2∗‖≤2​Bμ​‖Q1−Q2‖\.\\\|\\lambda^\{\*\}\_\{Q\_\{1\}\}\-\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\\leq\\frac\{2B\}\{\\mu\}\\\|Q\_\{1\}\-Q\_\{2\}\\\|\.\(31\)Finally, sincedQ=−Q​λQ∗d\_\{Q\}=\-Q\\lambda^\{\*\}\_\{Q\}, we havedQ1−dQ2=−Q1​\(λQ1∗−λQ2∗\)−\(Q1−Q2\)​λQ2∗d\_\{Q\_\{1\}\}\-d\_\{Q\_\{2\}\}=\-Q\_\{1\}\(\\lambda^\{\*\}\_\{Q\_\{1\}\}\-\\lambda^\{\*\}\_\{Q\_\{2\}\}\)\-\(Q\_\{1\}\-Q\_\{2\}\)\\lambda^\{\*\}\_\{Q\_\{2\}\}\. Using‖Q1‖≤B\\\|Q\_\{1\}\\\|\\leq B,‖λQ2∗‖≤1\\\|\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\\leq 1, and \([31](https://arxiv.org/html/2607.15412#A2.E31)\), we obtain

‖dQ1−dQ2‖≤‖Q1‖​‖λQ1∗−λQ2∗‖\+‖Q1−Q2‖​‖λQ2∗‖≤B​‖λQ1∗−λQ2∗‖\+‖Q1−Q2‖≤\(1\+2​B2μ\)​‖Q1−Q2‖\.\\displaystyle\\\|d\_\{Q\_\{1\}\}\-d\_\{Q\_\{2\}\}\\\|\\leq\\\|Q\_\{1\}\\\|\\,\\\|\\lambda^\{\*\}\_\{Q\_\{1\}\}\-\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\+\\\|Q\_\{1\}\-Q\_\{2\}\\\|\\,\\\|\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\\leq B\\\|\\lambda^\{\*\}\_\{Q\_\{1\}\}\-\\lambda^\{\*\}\_\{Q\_\{2\}\}\\\|\+\\\|Q\_\{1\}\-Q\_\{2\}\\\|\\leq\\left\(1\+\\frac\{2B^\{2\}\}\{\\mu\}\\right\)\\\|Q\_\{1\}\-Q\_\{2\}\\\|\.\(32\)This proves the claim\.

∎

### B\-BProof of Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)

###### Proof\.

Recall thatdQ=−Q​λQ∗d\_\{Q\}=\-Q\\lambda\_\{Q\}^\{\*\}, whereλQ∗∈arg⁡minλ∈ΔM‖Q​λ‖2\.\\lambda\_\{Q\}^\{\*\}\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|^\{2\}\.AlthoughλQ∗\\lambda\_\{Q\}^\{\*\}may not be unique, the vectorQ​λQ∗Q\\lambda\_\{Q\}^\{\*\}is unique, since it is the minimum\-norm point in the compact convex setconv⁡\{qZ,1,⋯,qZ,M\}\\operatorname\{conv\}\\\{q\_\{Z,1\},\\cdots,q\_\{Z,M\}\\\}\. Therefore,dQd\_\{Q\}is well\-defined\. LetQ,Q′∈ℝp×MQ,Q^\{\\prime\}\\in\\mathbb\{R\}^\{p\\times M\}, and let

λQ∗∈arg⁡minλ∈ΔM‖Q​λ‖2,λQ′∗∈arg⁡minλ∈ΔM‖Q′​λ‖2\.\\lambda\_\{Q\}^\{\*\}\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|^\{2\},\\qquad\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|^\{2\}\.\(33\)Using the optimality ofQ′​λQ′∗Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}as the projection of the origin ontoconv⁡\{qZ,1′,⋯,qZ,M′\}\\operatorname\{conv\}\\\{q^\{\\prime\}\_\{Z,1\},\\cdots,q^\{\\prime\}\_\{Z,M\}\\\}, we have

⟨Q′​λQ′∗,Q′​λQ′∗−Q′​λQ∗⟩≤0\.\\left\\langle Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\},Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\-Q^\{\\prime\}\\lambda\_\{Q\}^\{\*\}\\right\\rangle\\leq 0\.\(34\)Expanding the quadratic term and using \([34](https://arxiv.org/html/2607.15412#A2.E34)\), we obtain

‖dQ−dQ′‖2=‖Q​λQ∗−Q′​λQ′∗‖2\\displaystyle\\\|d\_\{Q\}\-d\_\{Q^\{\\prime\}\}\\\|^\{2\}=\\\|Q\\lambda\_\{Q\}^\{\*\}\-Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\\\|^\{2\}=‖Q​λQ∗‖2−‖Q′​λQ′∗‖2\+2​⟨Q′​λQ′∗,Q′​λQ′∗−Q​λQ∗⟩\\displaystyle=\\\|Q\\lambda\_\{Q\}^\{\*\}\\\|^\{2\}\-\\\|Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\\\|^\{2\}\+2\\left\\langle Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\},Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\-Q\\lambda\_\{Q\}^\{\*\}\\right\\rangle=‖Q​λQ∗‖2−‖Q′​λQ′∗‖2\+2​⟨Q′​λQ′∗,Q′​λQ′∗−Q′​λQ∗⟩\\displaystyle=\\\|Q\\lambda\_\{Q\}^\{\*\}\\\|^\{2\}\-\\\|Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\\\|^\{2\}\+2\\left\\langle Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\},Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\-Q^\{\\prime\}\\lambda\_\{Q\}^\{\*\}\\right\\rangle\+2​⟨Q′​λQ′∗,Q′​λQ∗−Q​λQ∗⟩\\displaystyle\\quad\+2\\left\\langle Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\},Q^\{\\prime\}\\lambda\_\{Q\}^\{\*\}\-Q\\lambda\_\{Q\}^\{\*\}\\right\\rangle≤minλ∈ΔM⁡‖Q​λ‖2−minλ∈ΔM⁡‖Q′​λ‖2\+2​‖Q′​λQ′∗‖​‖\(Q′−Q\)​λQ∗‖\.\\displaystyle\\leq\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|^\{2\}\-\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|^\{2\}\+2\\\|Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\\\|\\,\\\|\(Q^\{\\prime\}\-Q\)\\lambda\_\{Q\}^\{\*\}\\\|\.\(35\)It remains to bound the difference of optimal values\. We do so by comparing the two quadratic objectives uniformly overΔM\\Delta^\{M\}

minλ∈ΔM⁡‖Q​λ‖2−minλ∈ΔM⁡‖Q′​λ‖2\\displaystyle\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|^\{2\}\-\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|^\{2\}≤maxλ∈ΔM⁡\|‖Q​λ‖2−‖Q′​λ‖2\|\\displaystyle\\leq\\max\_\{\\lambda\\in\\Delta^\{M\}\}\\left\|\\\|Q\\lambda\\\|^\{2\}\-\\\|Q^\{\\prime\}\\lambda\\\|^\{2\}\\right\|≤supλ∈ΔM‖\(Q−Q′\)​λ‖​\(supλ∈ΔM‖Q​λ‖\+supλ∈ΔM‖Q′​λ‖\)\.\\displaystyle\\leq\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\(Q\-Q^\{\\prime\}\)\\lambda\\\|\\left\(\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|\+\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|\\right\)\.\(36\)Combining \([35](https://arxiv.org/html/2607.15412#A2.E35)\) and \([36](https://arxiv.org/html/2607.15412#A2.E36)\), and using‖Q′​λQ′∗‖≤supλ∈ΔM‖Q′​λ‖\\\|Q^\{\\prime\}\\lambda\_\{Q^\{\\prime\}\}^\{\*\}\\\|\\leq\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|, gives

‖dQ−dQ′‖2≤4​max⁡\{supλ∈ΔM‖Q​λ‖,supλ∈ΔM‖Q′​λ‖\}​supλ∈ΔM‖\(Q−Q′\)​λ‖\.\\\|d\_\{Q\}\-d\_\{Q^\{\\prime\}\}\\\|^\{2\}\\leq 4\\max\\left\\\{\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|,\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|\\right\\\}\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\(Q\-Q^\{\\prime\}\)\\lambda\\\|\.\(37\)This is the1/21/2\-Hölder bound established in\[[1](https://arxiv.org/html/2607.15412#bib.bib20)\]\. On the bounded set considered in Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2),QQandQ′Q^\{\\prime\}satisfy‖Q‖≤B\\\|Q\\\|\\leq Band‖Q′‖≤B\\\|Q^\{\\prime\}\\\|\\leq B\. Hence,

supλ∈ΔM‖Q​λ‖≤B,supλ∈ΔM‖Q′​λ‖≤B,supλ∈ΔM‖\(Q−Q′\)​λ‖≤‖Q−Q′‖\.\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\\lambda\\\|\\leq B,\\qquad\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q^\{\\prime\}\\lambda\\\|\\leq B,\\qquad\\sup\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\(Q\-Q^\{\\prime\}\)\\lambda\\\|\\leq\\\|Q\-Q^\{\\prime\}\\\|\.\(38\)Therefore, \([37](https://arxiv.org/html/2607.15412#A2.E37)\) implies

‖dQ−dQ′‖2≤4​B​‖Q−Q′‖,‖dQ−dQ′‖≤2​B​‖Q−Q′‖1/2\.\\\|d\_\{Q\}\-d\_\{Q^\{\\prime\}\}\\\|^\{2\}\\leq 4B\\\|Q\-Q^\{\\prime\}\\\|,\\quad\\\|d\_\{Q\}\-d\_\{Q^\{\\prime\}\}\\\|\\leq 2\\sqrt\{B\}\\,\\\|Q\-Q^\{\\prime\}\\\|^\{1/2\}\.\(39\)HenceQ↦dQQ\\mapsto d\_\{Q\}is generally1/21/2\-Hölder continuous on any bounded set of gradient matrices\. It remains to show that the exponent1/21/2is sharp\. We prove the claim by an explicit counterexample\. Fort∈\(0,π/2\)t\\in\(0,\\pi/2\), define

Qy​\(t\)≔\[q1y​\(t\),q2y​\(t\)\],Qz​\(t\)≔\[q1z​\(t\),q2z​\(t\)\],Q\_\{y\}\(t\)\\coloneqq\[q\_\{1\}^\{y\}\(t\),q\_\{2\}^\{y\}\(t\)\],\\qquad Q\_\{z\}\(t\)\\coloneqq\[q\_\{1\}^\{z\}\(t\),q\_\{2\}^\{z\}\(t\)\],\(40\)whereq1y​\(t\)=\(cos2⁡t,sin⁡t​cos⁡t\)q\_\{1\}^\{y\}\(t\)=\(\\cos^\{2\}t,\\sin t\\cos t\),q2y​\(t\)=\(1,0\)q\_\{2\}^\{y\}\(t\)=\(1,0\)andq1z​\(t\)=\(1,cos⁡t​sin⁡t\)q\_\{1\}^\{z\}\(t\)=\(1,\\cos t\\sin t\),q2z​\(t\)=\(1,0\)\.q\_\{2\}^\{z\}\(t\)=\(1,0\)\.We first identify the corresponding CA directions\. Observe that

q1y​\(t\)−q2y​\(t\)=\(−sin2⁡t,sin⁡t​cos⁡t\)\.q\_\{1\}^\{y\}\(t\)\-q\_\{2\}^\{y\}\(t\)=\(\-\\sin^\{2\}t,\\sin t\\cos t\)\.\(41\)A direct computation gives

\(q1y​\(t\)−q2y​\(t\)\)⊤​q1y​\(t\)\\displaystyle\\bigl\(q\_\{1\}^\{y\}\(t\)\-q\_\{2\}^\{y\}\(t\)\\bigr\)^\{\\top\}q\_\{1\}^\{y\}\(t\)=\(−sin2⁡t,sin⁡t​cos⁡t\)⊤​\(cos2⁡t,sin⁡t​cos⁡t\)\\displaystyle=\(\-\\sin^\{2\}t,\\sin t\\cos t\)^\{\\top\}\(\\cos^\{2\}t,\\sin t\\cos t\)=−sin2⁡t​cos2⁡t\+sin2⁡t​cos2⁡t\\displaystyle=\-\\sin^\{2\}t\\cos^\{2\}t\+\\sin^\{2\}t\\cos^\{2\}t=0\.\\displaystyle=0\.\(42\)Henceq1y​\(t\)−q2y​\(t\)q\_\{1\}^\{y\}\(t\)\-q\_\{2\}^\{y\}\(t\)is orthogonal toq1y​\(t\)q\_\{1\}^\{y\}\(t\)\. Consequently,q1y​\(t\)q\_\{1\}^\{y\}\(t\)is the projection of the origin ontoconv⁡\{q1y​\(t\),q2y​\(t\)\}\\operatorname\{conv\}\\\{q\_\{1\}^\{y\}\(t\),q\_\{2\}^\{y\}\(t\)\\\}, and the CA direction associated withQy​\(t\)Q\_\{y\}\(t\)has the following explicit form\.

dQy​\(t\)=−q1y​\(t\)=−\(cos2⁡t,sin⁡t​cos⁡t\)\.d\_\{Q\_\{y\}\(t\)\}=\-q\_\{1\}^\{y\}\(t\)=\-\(\\cos^\{2\}t,\\sin t\\cos t\)\.\(43\)Similarly,q1z​\(t\)−q2z​\(t\)=\(0,sin⁡t​cos⁡t\)q\_\{1\}^\{z\}\(t\)\-q\_\{2\}^\{z\}\(t\)=\(0,\\sin t\\cos t\)is orthogonal toq2z​\(t\)=\(1,0\)q\_\{2\}^\{z\}\(t\)=\(1,0\), and henceq2z​\(t\)q\_\{2\}^\{z\}\(t\)is the projection of the origin ontoconv⁡\{q1z​\(t\),q2z​\(t\)\}\\operatorname\{conv\}\\\{q\_\{1\}^\{z\}\(t\),q\_\{2\}^\{z\}\(t\)\\\}\. Thus

dQz​\(t\)=−q2z​\(t\)=−\(1,0\)\.d\_\{Q\_\{z\}\(t\)\}=\-q\_\{2\}^\{z\}\(t\)=\-\(1,0\)\.\(44\)Therefore, the two CA directions differ by

‖dQy​\(t\)−dQz​\(t\)‖\\displaystyle\\\|d\_\{Q\_\{y\}\(t\)\}\-d\_\{Q\_\{z\}\(t\)\}\\\|=‖q1y​\(t\)−q2z​\(t\)‖=‖\(sin2⁡t,−sin⁡t​cos⁡t\)‖=sin⁡t\.\\displaystyle=\\\|q\_\{1\}^\{y\}\(t\)\-q\_\{2\}^\{z\}\(t\)\\\|=\\\|\(\\sin^\{2\}t,\-\\sin t\\cos t\)\\\|=\\sin t\.\(45\)On the other hand, the two matrices differ only in the first coordinate of their first column, since

Qy​\(t\)−Qz​\(t\)=\[−sin2⁡t000\],‖Qy​\(t\)−Qz​\(t\)‖=sin2⁡t\.\\displaystyle Q\_\{y\}\(t\)\-Q\_\{z\}\(t\)=\\begin\{bmatrix\}\-\\sin^\{2\}t&0\\\\ 0&0\\end\{bmatrix\},\\qquad\\\|Q\_\{y\}\(t\)\-Q\_\{z\}\(t\)\\\|=\\sin^\{2\}t\.\(46\)Combining \([45](https://arxiv.org/html/2607.15412#A2.E45)\) and \([46](https://arxiv.org/html/2607.15412#A2.E46)\), for anyη\>12\\eta\>\\tfrac\{1\}\{2\}we have

‖dQy​\(t\)−dQz​\(t\)‖‖Qy​\(t\)−Qz​\(t\)‖η=sin⁡t\(sin2⁡t\)η=\(sin⁡t\)1−2​η→\+∞as​t→0\+\.\\displaystyle\\frac\{\\\|d\_\{Q\_\{y\}\(t\)\}\-d\_\{Q\_\{z\}\(t\)\}\\\|\}\{\\\|Q\_\{y\}\(t\)\-Q\_\{z\}\(t\)\\\|^\{\\eta\}\}=\\frac\{\\sin t\}\{\(\\sin^\{2\}t\)^\{\\eta\}\}=\(\\sin t\)^\{1\-2\\eta\}\\to\+\\infty\\quad\\text\{as \}t\\to 0^\{\+\}\.\(47\)Thus no local Hölder bound with exponentη\>12\\eta\>\\tfrac\{1\}\{2\}can hold uniformly for the mappingQ↦dQQ\\mapsto d\_\{Q\}\. This proves the sharpness of the exponent12\\tfrac\{1\}\{2\}in the worst case\.

We remark that this is consistent with Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)\. The Frobenius norms ofQy​\(t\)Q\_\{y\}\(t\)andQz​\(t\)Q\_\{z\}\(t\)are uniformly bounded, for instance byB=2B=2\. However, forU=\(1,−1\)⊤/2U=\(1,\-1\)^\{\\top\}/\\sqrt\{2\},

μmin​\(U⊤​Qy​\(t\)⊤​Qy​\(t\)​U\)=12​‖q1y​\(t\)−q2y​\(t\)‖2=12​sin2⁡t→0as​t→0\+,\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{y\}\(t\)^\{\\top\}Q\_\{y\}\(t\)U\)=\\frac\{1\}\{2\}\\\|q\_\{1\}^\{y\}\(t\)\-q\_\{2\}^\{y\}\(t\)\\\|^\{2\}=\\frac\{1\}\{2\}\\sin^\{2\}t\\to 0\\quad\\text\{as \}t\\to 0^\{\+\},\(48\)and the same degeneration holds forQz​\(t\)Q\_\{z\}\(t\)\. Thus no uniformμ\>0\\mu\>0in Definition[2](https://arxiv.org/html/2607.15412#Thmdefinition2)covers the family, and the loss of higher\-order Hölder regularity occurs exactly where the nondegeneracy condition fails\. ∎

### B\-CProof of Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)

###### Proof\.

Letλ∗​\(xt\)∈arg⁡minλ∈ΔM‖∇FS​\(xt\)​λ‖2\\lambda^\{\*\}\(x\_\{t\}\)\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|^\{2\}, so that‖∇FS​\(xt\)​λ∗​\(xt\)‖2=minλ∈ΔM⁡‖∇FS​\(xt\)​λ‖2\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}=\\min\_\{\\lambda\\in\\Delta^\{M\}\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|^\{2\}\. DefineHt≔U⊤​Qt⊤​Qt​UH\_\{t\}\\coloneqq U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U,H¯t≔U⊤​∇FS​\(xt\)⊤​∇FS​\(xt\)​U\\bar\{H\}\_\{t\}\\coloneqq U^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)U\. We divide the analysis into two cases according to the update rule of Algorithm[1](https://arxiv.org/html/2607.15412#alg1)\. Case 1:μmin​\(U⊤​Qt⊤​Qt​U\)≥μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)\\geq\\mu\_\{t\}\.Then the algorithm usesλt∈arg⁡minλ∈ΔM‖Qt​λ‖2\\lambda\_\{t\}\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\\Delta^\{M\}\}\\\|Q\_\{t\}\\lambda\\\|^\{2\}and updatesxt\+1=xt−αt​Qt​λtx\_\{t\+1\}=x\_\{t\}\-\\alpha\_\{t\}Q\_\{t\}\\lambda\_\{t\}\. The conditionμmin​\(Ht\)≥μt\\mu\_\{\\min\}\(H\_\{t\}\)\\geq\\mu\_\{t\}gives nondegeneracy for the stochastic gradient matrixQtQ\_\{t\}\. To compare the stochastic CA direction with the corresponding full\-batch direction, we also need the full\-batch matrix∇FS​\(xt\)\\nabla F\_\{S\}\(x\_\{t\}\)to be nondegenerate\. We therefore define the good perturbation event𝒢t≔\{‖Ht−H¯t‖≤μt2\}\\mathcal\{G\}\_\{t\}\\coloneqq\\left\\\{\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|\\leq\\frac\{\\mu\_\{t\}\}\{2\}\\right\\\}, on which the reduced full\-batch curvature is close to its stochastic counterpart\. On𝒢t\\mathcal\{G\}\_\{t\}, sinceHtH\_\{t\}andH¯t\\bar\{H\}\_\{t\}are symmetric matrices, Weyl’s inequality\[[8](https://arxiv.org/html/2607.15412#bib.bib25)\]gives

μmin​\(H¯t\)≥μmin​\(Ht\)−‖Ht−H¯t‖≥μt−μt2=μt2\.\\mu\_\{\\min\}\(\\bar\{H\}\_\{t\}\)\\geq\\mu\_\{\\min\}\(H\_\{t\}\)\-\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|\\geq\\mu\_\{t\}\-\\frac\{\\mu\_\{t\}\}\{2\}=\\frac\{\\mu\_\{t\}\}\{2\}\.\(49\)Therefore, on this event, bothQtQ\_\{t\}and∇FS​\(xt\)\\nabla F\_\{S\}\(x\_\{t\}\)satisfy the nondegeneracy condition with curvature lower bound12​μt\\frac\{1\}\{2\}\\mu\_\{t\}required by Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1), which can be used to comparedQtd\_\{Q\_\{t\}\}andd∇FS​\(xt\)d\_\{\\nabla F\_\{S\}\(x\_\{t\}\)\}\. It remains to control the complement𝒢tc≔\{‖Ht−H¯t‖\>μt2\}\\mathcal\{G\}\_\{t\}^\{c\}\\coloneqq\\left\\\{\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|\>\\frac\{\\mu\_\{t\}\}\{2\}\\right\\\}\. LetEt≔Qt−∇FS​\(xt\)E\_\{t\}\\coloneqq Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\. Then

Ht−H¯t=U⊤​\(Qt⊤​Qt−∇FS​\(xt\)⊤​∇FS​\(xt\)\)​U=U⊤​\(Qt⊤​Et\+Et⊤​∇FS​\(xt\)\)​U\.H\_\{t\}\-\\bar\{H\}\_\{t\}=U^\{\\top\}\(Q\_\{t\}^\{\\top\}Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)\)U=U^\{\\top\}\\left\(Q\_\{t\}^\{\\top\}E\_\{t\}\+E\_\{t\}^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)\\right\)U\.\(50\)Using‖U‖=1\\\|U\\\|=1and the submultiplicativity of the spectral norm, we obtain

‖Ht−H¯t‖≤‖Qt⊤​Et\+Et⊤​∇FS​\(xt\)‖≤‖Qt⊤​Et‖\+‖Et⊤​∇FS​\(xt\)‖≤‖Qt‖​‖Et‖\+‖Et‖​‖∇FS​\(xt\)‖\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|\\leq\\\|Q\_\{t\}^\{\\top\}E\_\{t\}\+E\_\{t\}^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\\leq\\\|Q\_\{t\}^\{\\top\}E\_\{t\}\\\|\+\\\|E\_\{t\}^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\\leq\\\|Q\_\{t\}\\\|\\\|E\_\{t\}\\\|\+\\\|E\_\{t\}\\\|\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\(51\)By Assumption[4](https://arxiv.org/html/2607.15412#Thmassumption4)and \([18](https://arxiv.org/html/2607.15412#S3.E18)\), we have‖Qt‖≤‖Qt‖F≤ℓF\\\|Q\_\{t\}\\\|\\leq\\\|Q\_\{t\}\\\|\_\{F\}\\leq\\ell\_\{F\}and‖∇FS​\(xt\)‖≤‖∇FS​\(xt\)‖F≤ℓF\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\\leq\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\leq\\ell\_\{F\}\. ThusℓF\\ell\_\{F\}directly replaces the bound in all one\-step estimates\. Thus, combining it with \([51](https://arxiv.org/html/2607.15412#A2.E51)\), we obtain

‖Ht−H¯t‖≤2​ℓF​‖Qt−∇FS​\(xt\)‖≤2​ℓF​‖Qt−∇FS​\(xt\)‖F\.\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|\\leq 2\\ell\_\{F\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\\leq 2\\ell\_\{F\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\.\(52\)Conditioning onℱt\\mathcal\{F\}\_\{t\}, Assumption[2](https://arxiv.org/html/2607.15412#Thmassumption2)gives𝔼​\[‖Qt−∇FS​\(xt\)‖F2∣ℱt\]≤M​σ2\|Zt\|\.\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\\mid\\mathcal\{F\}\_\{t\}\\right\]\\leq\\frac\{M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\.Taking total expectation and using \([52](https://arxiv.org/html/2607.15412#A2.E52)\),

𝔼​\[‖Ht−H¯t‖2\]≤4​ℓF2​M​σ2\|Zt\|\.\\mathbb\{E\}\\\!\\left\[\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|^\{2\}\\right\]\\leq\\frac\{4\\ell\_\{F\}^\{2\}M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\.\(53\)By Markov’s inequality,

ℙ​\(𝒢tc\)=ℙ​\(‖Ht−H¯t‖\>μt2\)≤𝔼​\[‖Ht−H¯t‖2\]μt2/4≤16​ℓF2​M​σ2\|Zt\|​μt2\.\\mathbb\{P\}\(\\mathcal\{G\}\_\{t\}^\{c\}\)=\\mathbb\{P\}\\\!\\left\(\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|\>\\frac\{\\mu\_\{t\}\}\{2\}\\right\)\\leq\\frac\{\\mathbb\{E\}\[\\\|H\_\{t\}\-\\bar\{H\}\_\{t\}\\\|^\{2\}\]\}\{\\mu\_\{t\}^\{2\}/4\}\\leq\\frac\{16\\ell\_\{F\}^\{2\}M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{2\}\}\.\(54\)By Assumption[3](https://arxiv.org/html/2607.15412#Thmassumption3), for anyλ∈ΔM\\lambda\\in\\Delta^\{M\}, the smoothness of the scalarized empirical objective gives

λ⊤​FS​\(xt\+1\)−λ⊤​FS​\(xt\)\\displaystyle\\lambda^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\-\\lambda^\{\\top\}F\_\{S\}\(x\_\{t\}\)≤⟨∇FS​\(xt\)​λ,xt\+1−xt⟩\+ℓf,12​‖xt\+1−xt‖2\\displaystyle\\leq\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,x\_\{t\+1\}\-x\_\{t\}\\rangle\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\\|x\_\{t\+1\}\-x\_\{t\}\\\|^\{2\}=−αt​⟨∇FS​\(xt\)​λ,Qt​λt⟩\+ℓf,12​αt2​‖Qt​λt‖2\.\\displaystyle=\-\\alpha\_\{t\}\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,Q\_\{t\}\\lambda\_\{t\}\\rangle\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\\|Q\_\{t\}\\lambda\_\{t\}\\\|^\{2\}\.\(55\)We next bound the inner product term\. Write

−⟨∇FS​\(xt\)​λ,Qt​λt⟩\\displaystyle\-\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,Q\_\{t\}\\lambda\_\{t\}\\rangle=⟨∇FS​\(xt\)​λ,∇FS​\(xt\)​λ∗​\(xt\)−Qt​λt⟩−⟨∇FS​\(xt\)​λ,∇FS​\(xt\)​λ∗​\(xt\)⟩\.\\displaystyle=\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\-Q\_\{t\}\\lambda\_\{t\}\\rangle\-\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\rangle\.\(56\)Sinceλ∗​\(xt\)\\lambda^\{\*\}\(x\_\{t\}\)minimizes‖∇FS​\(xt\)​λ‖2\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|^\{2\}overΔM\\Delta^\{M\}, the first\-order optimality condition gives

⟨∇FS​\(xt\)​λ∗​\(xt\),∇FS​\(xt\)​\(λ−λ∗​\(xt\)\)⟩\\displaystyle\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\),\\nabla F\_\{S\}\(x\_\{t\}\)\(\\lambda\-\\lambda^\{\*\}\(x\_\{t\}\)\)\\rangle≥0,\\displaystyle\\geq 0,\(57\)⟨∇FS​\(xt\)​λ,∇FS​\(xt\)​λ∗​\(xt\)⟩\\displaystyle\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\rangle≥‖∇FS​\(xt\)​λ∗​\(xt\)‖2,∀λ∈ΔM\.\\displaystyle\\geq\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\},\\qquad\\forall\\lambda\\in\\Delta^\{M\}\.\(58\)Moreover, by Assumption[4](https://arxiv.org/html/2607.15412#Thmassumption4),‖∇FS​\(xt\)​λ‖≤ℓf\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|\\leq\\ell\_\{f\}, for allλ∈ΔM\\lambda\\in\\Delta^\{M\}\. Combining this with \([56](https://arxiv.org/html/2607.15412#A2.E56)\) and \([58](https://arxiv.org/html/2607.15412#A2.E58)\) gives

−⟨∇FS​\(xt\)​λ,Qt​λt⟩≤−‖∇FS​\(xt\)​λ∗​\(xt\)‖2\+ℓf​‖∇FS​\(xt\)​λ∗​\(xt\)−Qt​λt‖\.\-\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda,Q\_\{t\}\\lambda\_\{t\}\\rangle\\leq\-\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\+\\ell\_\{f\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\-Q\_\{t\}\\lambda\_\{t\}\\\|\.\(59\)Since‖∇FS​\(xt\)​λ∗​\(xt\)−Qt​λt‖=‖d∇FS​\(xt\)−dQt‖,\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\-Q\_\{t\}\\lambda\_\{t\}\\\|=\\\|d\_\{\\nabla F\_\{S\}\(x\_\{t\}\)\}\-d\_\{Q\_\{t\}\}\\\|,we now bound the direction difference separately on𝒢t\\mathcal\{G\}\_\{t\}and𝒢tc\\mathcal\{G\}\_\{t\}^\{c\}\. On𝒢t\\mathcal\{G\}\_\{t\}, by \([49](https://arxiv.org/html/2607.15412#A2.E49)\), Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)applies toQtQ\_\{t\}and∇FS​\(xt\)\\nabla F\_\{S\}\(x\_\{t\}\)\. Hence,

‖dQt−d∇FS​\(xt\)‖≤ℓd,t​‖Qt−∇FS​\(xt\)‖F,ℓd,t=1\+4​ℓF2μt\.\\\|d\_\{Q\_\{t\}\}\-d\_\{\\nabla F\_\{S\}\(x\_\{t\}\)\}\\\|\\leq\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\},\\qquad\\ell\_\{d,t\}=1\+\\frac\{4\\ell\_\{F\}^\{2\}\}\{\\mu\_\{t\}\}\.\(60\)Here Lemma[1](https://arxiv.org/html/2607.15412#Thmlemma1)is applied with nondegeneracy constantμt/2\\mu\_\{t\}/2, and the Frobenius norm is used through‖A‖≤‖A‖F\\\|A\\\|\\leq\\\|A\\\|\_\{F\}\. On𝒢tc\\mathcal\{G\}\_\{t\}^\{c\}, we use the1/21/2\-Hölder continuity from Lemma[2](https://arxiv.org/html/2607.15412#Thmlemma2)\. Since Assumption[4](https://arxiv.org/html/2607.15412#Thmassumption4)gives‖Qt‖F≤ℓF\\\|Q\_\{t\}\\\|\_\{F\}\\leq\\ell\_\{F\}and‖∇FS​\(xt\)‖F≤ℓF\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\leq\\ell\_\{F\}, bothQtQ\_\{t\}and∇FS​\(xt\)\\nabla F\_\{S\}\(x\_\{t\}\)are bounded byℓF\\ell\_\{F\}\. Thus,

‖dQt−d∇FS​\(xt\)‖≤2​ℓF​‖Qt−∇FS​\(xt\)‖F1/2\.\\\|d\_\{Q\_\{t\}\}\-d\_\{\\nabla F\_\{S\}\(x\_\{t\}\)\}\\\|\\leq 2\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\.\(61\)Combining \([60](https://arxiv.org/html/2607.15412#A2.E60)\) and \([61](https://arxiv.org/html/2607.15412#A2.E61)\), on the regular branch we first obtain the pathwise case\-by\-case bound

‖dQt−d∇FS​\(xt\)‖≤ℓd,t​‖Qt−∇FS​\(xt\)‖F​1𝒢t\+2​ℓF​‖Qt−∇FS​\(xt\)‖F1/2​1𝒢tc,\\\|d\_\{Q\_\{t\}\}\-d\_\{\\nabla F\_\{S\}\(x\_\{t\}\)\}\\\|\\leq\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\,\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}\}\+2\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\,\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\},\(62\)where the first term follows from \([60](https://arxiv.org/html/2607.15412#A2.E60)\) on𝒢t\\mathcal\{G\}\_\{t\}and the second from \([61](https://arxiv.org/html/2607.15412#A2.E61)\) on𝒢tc\\mathcal\{G\}\_\{t\}^\{c\}\. Since both terms are nonnegative, dropping𝟏𝒢t\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}\}only weakens the bound and yields

‖dQt−d∇FS​\(xt\)‖≤ℓd,t​‖Qt−∇FS​\(xt\)‖F\+2​ℓF​‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\.\\\|d\_\{Q\_\{t\}\}\-d\_\{\\nabla F\_\{S\}\(x\_\{t\}\)\}\\\|\\leq\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\+2\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\.\(63\)Substituting \([63](https://arxiv.org/html/2607.15412#A2.E63)\) into \([59](https://arxiv.org/html/2607.15412#A2.E59)\), and then into \([55](https://arxiv.org/html/2607.15412#A2.E55)\), gives

αt​‖∇FS​\(xt\)​λ∗​\(xt\)‖2\\displaystyle\\alpha\_\{t\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}≤λ⊤​FS​\(xt\)−λ⊤​FS​\(xt\+1\)\+αt​ℓf​ℓd,t​‖Qt−∇FS​\(xt\)‖F\\displaystyle\\leq\\lambda^\{\\top\}F\_\{S\}\(x\_\{t\}\)\-\\lambda^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\+\\alpha\_\{t\}\\ell\_\{f\}\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\+2​αt​ℓf​ℓF​‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\+ℓf,12​αt2​‖Qt​λt‖2\.\\displaystyle\\quad\+2\\alpha\_\{t\}\\ell\_\{f\}\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\\|Q\_\{t\}\\lambda\_\{t\}\\\|^\{2\}\.\(64\)Using Assumption[4](https://arxiv.org/html/2607.15412#Thmassumption4)andλt∈ΔM\\lambda\_\{t\}\\in\\Delta^\{M\}, we have‖Qt​λt‖≤ℓf≤ℓF\\\|Q\_\{t\}\\lambda\_\{t\}\\\|\\leq\\ell\_\{f\}\\leq\\ell\_\{F\}\. Thus, takingλ=λ0\\lambda=\\lambda\_\{0\}, we obtain

αt​‖∇FS​\(xt\)​λ∗​\(xt\)‖2\\displaystyle\\alpha\_\{t\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}≤λ0⊤​FS​\(xt\)−λ0⊤​FS​\(xt\+1\)\+αt​ℓf​ℓd,t​‖Qt−∇FS​\(xt\)‖F\\displaystyle\\leq\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\+\\alpha\_\{t\}\\ell\_\{f\}\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\+2​αt​ℓf​ℓF​‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\+ℓf,12​αt2​ℓF2\.\\displaystyle\\quad\+2\\alpha\_\{t\}\\ell\_\{f\}\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\ell\_\{F\}^\{2\}\.\(65\)Case 2:μmin​\(U⊤​Qt⊤​Qt​U\)<μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)<\\mu\_\{t\}\.In this case, the algorithm setsλt=λ0\\lambda\_\{t\}=\\lambda\_\{0\}, whereλ0∈ΔM\\lambda\_\{0\}\\in\\Delta^\{M\}is fixed\. Pluggingxt\+1=xt−αt​Qt​λ0x\_\{t\+1\}=x\_\{t\}\-\\alpha\_\{t\}Q\_\{t\}\\lambda\_\{0\}into Assumption[3](https://arxiv.org/html/2607.15412#Thmassumption3)withλ=λ0\\lambda=\\lambda\_\{0\}, we obtain

λ0⊤​FS​\(xt\+1\)−λ0⊤​FS​\(xt\)\\displaystyle\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\}\)≤−αt​⟨∇FS​\(xt\)​λ0,Qt​λ0⟩\+ℓf,12​αt2​‖Qt​λ0‖2\\displaystyle\\leq\-\\alpha\_\{t\}\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\},Q\_\{t\}\\lambda\_\{0\}\\rangle\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\\|Q\_\{t\}\\lambda\_\{0\}\\\|^\{2\}≤−αt​⟨∇FS​\(xt\)​λ0,Qt​λ0⟩\+ℓf,12​αt2​ℓF2\.\\displaystyle\\leq\-\\alpha\_\{t\}\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\},Q\_\{t\}\\lambda\_\{0\}\\rangle\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\ell\_\{F\}^\{2\}\.\(66\)We use the pathwise decomposition

⟨∇FS​\(xt\)​λ0,Qt​λ0⟩=‖∇FS​\(xt\)​λ0‖2\+⟨∇FS​\(xt\)​λ0,\(Qt−∇FS​\(xt\)\)​λ0⟩\.\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\},Q\_\{t\}\\lambda\_\{0\}\\rangle=\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\}\\\|^\{2\}\+\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\},\(Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\)\\lambda\_\{0\}\\rangle\.\(67\)Applying the Cauchy–Schwarz inequality to the second term of \([67](https://arxiv.org/html/2607.15412#A2.E67)\), together with‖∇FS​\(xt\)​λ0‖≤ℓf\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\}\\\|\\leq\\ell\_\{f\}and‖\(Qt−∇FS​\(xt\)\)​λ0‖≤‖Qt−∇FS​\(xt\)‖F\\\|\(Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\)\\lambda\_\{0\}\\\|\\leq\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}, we obtain

⟨∇FS​\(xt\)​λ0,Qt​λ0⟩\\displaystyle\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\},Q\_\{t\}\\lambda\_\{0\}\\rangle≥‖∇FS​\(xt\)​λ0‖2−‖∇FS​\(xt\)​λ0‖​‖\(Qt−∇FS​\(xt\)\)​λ0‖\\displaystyle\\geq\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\}\\\|^\{2\}\-\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\}\\\|\\,\\\|\(Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\)\\lambda\_\{0\}\\\|≥‖∇FS​\(xt\)​λ0‖2−ℓf​‖Qt−∇FS​\(xt\)‖F\.\\displaystyle\\geq\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\}\\\|^\{2\}\-\\ell\_\{f\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\.\(68\)Sinceλ∗​\(xt\)\\lambda^\{\*\}\(x\_\{t\}\)minimizes‖∇FS​\(xt\)​λ‖2\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|^\{2\}overΔM\\Delta^\{M\},‖∇FS​\(xt\)​λ∗​\(xt\)‖2≤‖∇FS​\(xt\)​λ0‖2\.\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\\leq\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\}\\\|^\{2\}\.Therefore,

⟨∇FS​\(xt\)​λ0,Qt​λ0⟩≥‖∇FS​\(xt\)​λ∗​\(xt\)‖2−ℓf​‖Qt−∇FS​\(xt\)‖F\.\\langle\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\_\{0\},Q\_\{t\}\\lambda\_\{0\}\\rangle\\geq\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\-\\ell\_\{f\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\.\(69\)Substituting this into \([66](https://arxiv.org/html/2607.15412#A2.E66)\) and rearranging gives

αt​‖∇FS​\(xt\)​λ∗​\(xt\)‖2≤λ0⊤​FS​\(xt\)−λ0⊤​FS​\(xt\+1\)\+αt​ℓf​‖Qt−∇FS​\(xt\)‖F\+ℓf,12​αt2​ℓF2\.\\alpha\_\{t\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\\leq\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\+\\alpha\_\{t\}\\ell\_\{f\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\ell\_\{F\}^\{2\}\.\(70\)Unified bound for both cases\.Sinceℓd,t≥1\\ell\_\{d,t\}\\geq 1, both \([65](https://arxiv.org/html/2607.15412#A2.E65)\) and \([70](https://arxiv.org/html/2607.15412#A2.E70)\) imply the following pathwise bound:

αt​‖∇FS​\(xt\)​λ∗​\(xt\)‖2\\displaystyle\\alpha\_\{t\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}≤λ0⊤​FS​\(xt\)−λ0⊤​FS​\(xt\+1\)\+αt​ℓf​ℓd,t​‖Qt−∇FS​\(xt\)‖F\\displaystyle\\leq\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\+\\alpha\_\{t\}\\ell\_\{f\}\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\+2​αt​ℓf​ℓF​‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\+ℓf,12​αt2​ℓF2\.\\displaystyle\\quad\+2\\alpha\_\{t\}\\ell\_\{f\}\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\ell\_\{F\}^\{2\}\.\(71\)Taking expectation in \([71](https://arxiv.org/html/2607.15412#A2.E71)\), we get

αt​𝔼​\[‖∇FS​\(xt\)​λ∗​\(xt\)‖2\]\\displaystyle\\alpha\_\{t\}\\mathbb\{E\}\[\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\]≤𝔼​\[λ0⊤​FS​\(xt\)−λ0⊤​FS​\(xt\+1\)\]\+αt​ℓf​ℓd,t​𝔼​\[‖Qt−∇FS​\(xt\)‖F\]\\displaystyle\\leq\\mathbb\{E\}\\\!\\left\[\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\\right\]\+\\alpha\_\{t\}\\ell\_\{f\}\\ell\_\{d,t\}\\mathbb\{E\}\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\]\+2​αt​ℓf​ℓF​𝔼​\[‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\]\+ℓf,12​αt2​ℓF2\.\\displaystyle\\quad\+2\\alpha\_\{t\}\\ell\_\{f\}\\sqrt\{\\ell\_\{F\}\}\\,\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\\right\]\+\\frac\{\\ell\_\{f,1\}\}\{2\}\\alpha\_\{t\}^\{2\}\\ell\_\{F\}^\{2\}\.\(72\)Conditioning onℱt\\mathcal\{F\}\_\{t\}, Assumption[2](https://arxiv.org/html/2607.15412#Thmassumption2)gives

𝔼​\[‖Qt−∇FS​\(xt\)‖F2∣ℱt\]=∑m=1M𝔼​\[‖qZt,m​\(xt\)−∇fS,m​\(xt\)‖2∣ℱt\]≤M​σ2\|Zt\|\.\{\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\\mid\\mathcal\{F\}\_\{t\}\\right\]=\\sum\_\{m=1\}^\{M\}\\mathbb\{E\}\\\!\\left\[\\\|q\_\{Z\_\{t\},m\}\(x\_\{t\}\)\-\\nabla f\_\{S,m\}\(x\_\{t\}\)\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\}\\right\]\\leq\\frac\{M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\.\}\(73\)Therefore, by Jensen’s inequality,

𝔼​\[‖Qt−∇FS​\(xt\)‖F∣ℱt\]≤M​σ\|Zt\|\.\{\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\mid\\mathcal\{F\}\_\{t\}\\right\]\\leq\\frac\{\\sqrt\{M\}\\sigma\}\{\\sqrt\{\|Z\_\{t\}\|\}\}\.\}\(74\)Taking total expectations and using the tower property yield

𝔼​\[‖Qt−∇FS​\(xt\)‖F2\]≤M​σ2\|Zt\|,\\displaystyle\{\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\\right\]\\leq\\frac\{M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\},\}\(75\)𝔼​\[‖Qt−∇FS​\(xt\)‖F\]≤M​σ\|Zt\|\.\\displaystyle\{\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\right\]\\leq\\frac\{\\sqrt\{M\}\\sigma\}\{\\sqrt\{\|Z\_\{t\}\|\}\}\.\}\(76\)It remains to bound the bad\-event term\. By Hölder’s inequality with conjugate exponents44and4/34/3, we have

𝔼​\[‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\\right\]≤\(𝔼​\[‖Qt−∇FS​\(xt\)‖F2\]\)1/4​\(ℙ​\(𝒢tc\)\)3/4\.\\displaystyle\\leq\\left\(\\mathbb\{E\}\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\]\\right\)^\{1/4\}\\left\(\\mathbb\{P\}\(\\mathcal\{G\}\_\{t\}^\{c\}\)\\right\)^\{3/4\}\.\(77\)Using \([75](https://arxiv.org/html/2607.15412#A2.E75)\) and \([54](https://arxiv.org/html/2607.15412#A2.E54)\), we obtain

𝔼​\[‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc\]≤\(M​σ2\|Zt\|\)1/4​\(16​ℓF2​M​σ2\|Zt\|​μt2\)3/4=𝒪​\(1\|Zt\|​μt3/2\)\.\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\\right\]\\leq\\left\(\\frac\{M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\\right\)^\{1/4\}\\left\(\\frac\{16\\ell\_\{F\}^\{2\}M\\sigma^\{2\}\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{2\}\}\\right\)^\{3/4\}=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\}\\right\)\.\(78\)Substituting \([76](https://arxiv.org/html/2607.15412#A2.E76)\) and \([78](https://arxiv.org/html/2607.15412#A2.E78)\) into \([72](https://arxiv.org/html/2607.15412#A2.E72)\), and using thatℓd,t=1\+4​ℓF2/μt\\ell\_\{d,t\}=1\+4\\ell\_\{F\}^\{2\}/\\mu\_\{t\}with0<μt≤μ¯0<\\mu\_\{t\}\\leq\\bar\{\\mu\}, we obtain

αt​𝔼​\[‖∇FS​\(xt\)​λ∗​\(xt\)‖2\]≤𝔼​\[λ0⊤​FS​\(xt\)−λ0⊤​FS​\(xt\+1\)\]\+αt​𝒪​\(1\|Zt\|\+1μt​\|Zt\|\+1\|Zt\|​μt3/2\)\+𝒪​\(αt2\)\.\\displaystyle\\alpha\_\{t\}\\mathbb\{E\}\[\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\]\\leq\\mathbb\{E\}\\\!\\left\[\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{t\+1\}\)\\right\]\\quad\+\\alpha\_\{t\}\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{\\mu\_\{t\}\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\}\\right\)\+\\mathcal\{O\}\(\\alpha\_\{t\}^\{2\}\)\.\(79\)Summing \([79](https://arxiv.org/html/2607.15412#A2.E79)\) overt=0,…,T−1t=0,\\ldots,T\-1, dividing both sides byα​T\\alpha T, and settingαt=α\\alpha\_\{t\}=\\alphafor alltt, we obtain

1T​∑t=0T−1𝔼​\[‖∇FS​\(xt\)​λ∗​\(xt\)‖2\]\\displaystyle\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\[\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\]≤𝔼​\[λ0⊤​FS​\(x0\)−λ0⊤​FS​\(xT\)\]α​T\\displaystyle\\leq\\frac\{\\mathbb\{E\}\\\!\\left\[\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{0\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{T\}\)\\right\]\}\{\\alpha T\}\+𝒪​\(1T​∑t=0T−11\|Zt\|\+1T​∑t=0T−11μt​\|Zt\|\+1T​∑t=0T−11\|Zt\|​μt3/2\)\+𝒪​\(α\)\.\\displaystyle\\quad\+\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\mu\_\{t\}\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\}\\right\)\+\\mathcal\{O\}\(\\alpha\)\.\(80\)By the definition ofλ∗​\(xt\)\\lambda^\{\*\}\(x\_\{t\}\),

𝔼​\[min0≤t≤T−1⁡RS​\(xt\)\]=𝔼​\[min0≤t≤T−1⁡‖∇FS​\(xt\)​λ∗​\(xt\)‖2\]≤1T​∑t=0T−1𝔼​\[‖∇FS​\(xt\)​λ∗​\(xt\)‖2\]\.\\displaystyle\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}R\_\{S\}\(x\_\{t\}\)\\right\]=\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\\right\]\\leq\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\\\!\\left\[\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\)\\\|^\{2\}\\right\]\.\(81\)By Assumption[1](https://arxiv.org/html/2607.15412#Thmassumption1)andλ0∈ΔM\\lambda\_\{0\}\\in\\Delta^\{M\}, the scalarized objectiveλ0⊤​FS​\(⋅\)\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(\\cdot\)is bounded below\. Hence, there exists a finite constantΔF\\Delta\_\{F\}such that𝔼​\[λ0⊤​FS​\(x0\)−λ0⊤​FS​\(xT\)\]≤ΔF<∞\\mathbb\{E\}\\\!\\left\[\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{0\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{T\}\)\\right\]\\leq\\Delta\_\{F\}<\\infty\. Therefore,𝔼​\[λ0⊤​FS​\(x0\)−λ0⊤​FS​\(xT\)\]α​T≤𝒪​\(1α​T\)\\frac\{\\mathbb\{E\}\\\!\\left\[\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{0\}\)\-\\lambda\_\{0\}^\{\\top\}F\_\{S\}\(x\_\{T\}\)\\right\]\}\{\\alpha T\}\\leq\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\\alpha T\}\\right\)\. Thus, combining \([81](https://arxiv.org/html/2607.15412#A2.E81)\) with \([80](https://arxiv.org/html/2607.15412#A2.E80)\) proves the desired averaged stationarity bound:

𝔼​\[min0≤t≤T−1⁡RS​\(xt\)\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}R\_\{S\}\(x\_\{t\}\)\\right\]≤𝒪​\(1α​T\+α\+1T​∑t=0T−11\|Zt\|\+1T​∑t=0T−11μt​\|Zt\|\+1T​∑t=0T−11\|Zt\|​μt3/2\)\.\\displaystyle\\leq\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\\alpha T\}\+\\alpha\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\mu\_\{t\}\\sqrt\{\|Z\_\{t\}\|\}\}\+\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\}\\right\)\.\(82\)Ifμt=Θ​\(1\)\\mu\_\{t\}=\\Theta\(1\), then there exists a constantμ¯\>0\\underline\{\\mu\}\>0such thatμt≥μ¯\\mu\_\{t\}\\geq\\underline\{\\mu\}for alltt\. Hence,1T​∑t=0T−11μt​\|Zt\|≤1μ¯​T​∑t=0T−11\|Zt\|,\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\mu\_\{t\}\\sqrt\{\|Z\_\{t\}\|\}\}\\leq\\frac\{1\}\{\\underline\{\\mu\}T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\\sqrt\{\|Z\_\{t\}\|\}\},and1T​∑t=0T−11\|Zt\|​μt3/2≤1μ¯3/2​T​∑t=0T−11\|Zt\|\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{3/2\}\}\\leq\\frac\{1\}\{\\underline\{\\mu\}^\{3/2\}T\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{1\}\{\|Z\_\{t\}\|\}\.Since\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\), we haveT−1​∑t=0T−1\|Zt\|−1/2=𝒪​\(T−1/2\)T^\{\-1\}\\sum\_\{t=0\}^\{T\-1\}\|Z\_\{t\}\|^\{\-1/2\}=\\mathcal\{O\}\(T^\{\-1/2\}\)andT−1​∑t=0T−1\|Zt\|−1=𝒪​\(log⁡T/T\)=𝒪​\(T−1/2\)T^\{\-1\}\\sum\_\{t=0\}^\{T\-1\}\|Z\_\{t\}\|^\{\-1\}=\\mathcal\{O\}\(\\log T/T\)=\\mathcal\{O\}\(T^\{\-1/2\}\)\. Choosingα=Θ​\(T−1/2\)\\alpha=\\Theta\(T^\{\-1/2\}\)and\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\)gives𝔼​\[min0≤t≤T−1⁡RS​\(xt\)\]=𝒪​\(T−1/2\)\.\\mathbb\{E\}\\\!\\left\[\{\\min\_\{0\\leq t\\leq T\-1\}\}R\_\{S\}\(x\_\{t\}\)\\right\]=\\mathcal\{O\}\(T^\{\-1/2\}\)\.Moreover, when the threshold decays logarithmically asμt=Θ​\(1log⁡\(e\+t\)\),\\mu\_\{t\}=\\Theta\\\!\\left\(\\frac\{1\}\{\\log\(e\+t\)\}\\right\),under\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\)andα=Θ​\(T−1/2\)\\alpha=\\Theta\(T^\{\-1/2\}\), the rate is𝒪~​\(T−1/2\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)\.

∎

### B\-DProof of Theorem[2](https://arxiv.org/html/2607.15412#Thmtheorem2)

###### Proof\.

SinceM=2M=2, write∇FS​\(xt\)=\[∇fS,1​\(xt\),∇fS,2​\(xt\)\]\\nabla F\_\{S\}\(x\_\{t\}\)=\[\\nabla f\_\{S,1\}\(x\_\{t\}\),\\nabla f\_\{S,2\}\(x\_\{t\}\)\]andQt=\[qZt,1​\(xt\),qZt,2​\(xt\)\]Q\_\{t\}=\[q\_\{Z\_\{t\},1\}\(x\_\{t\}\),q\_\{Z\_\{t\},2\}\(x\_\{t\}\)\]\. For brevity in this proof, writeqZt,m=qZt,m​\(xt\)q\_\{Z\_\{t\},m\}=q\_\{Z\_\{t\},m\}\(x\_\{t\}\)form=1,2m=1,2\. Letd​\(xt\)=−∇FS​\(xt\)​λ∗​\(xt\)d\(x\_\{t\}\)=\-\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda^\{\*\}\(x\_\{t\}\), whereλ∗​\(xt\)∈arg⁡minλ∈Δ2‖∇FS​\(xt\)​λ‖2\\lambda^\{\*\}\(x\_\{t\}\)\\in\\mathop\{\\arg\\min\}\_\{\\lambda\\in\{\\Delta^\{2\}\}\}\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\lambda\\\|^\{2\}, and letdt=−Qt​λtd\_\{t\}=\-Q\_\{t\}\\lambda\_\{t\}\. By Assumption[4](https://arxiv.org/html/2607.15412#Thmassumption4)and \([18](https://arxiv.org/html/2607.15412#S3.E18)\),‖Qt‖F≤ℓF\\\|Q\_\{t\}\\\|\_\{F\}\\leq\\ell\_\{F\}and‖∇FS​\(xt\)‖F≤ℓF\\\|\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\leq\\ell\_\{F\}, so the bad\-event estimate \([54](https://arxiv.org/html/2607.15412#A2.E54)\) applies directly withℓF\\ell\_\{F\}\. Define the regular branch eventℛt≔\{μmin​\(U⊤​Qt⊤​Qt​U\)≥μt\}\\mathcal\{R\}\_\{t\}\\coloneqq\\left\\\{\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)\\geq\\mu\_\{t\}\\right\\\}\. Thenℛtc=\{μmin​\(U⊤​Qt⊤​Qt​U\)<μt\}\\mathcal\{R\}\_\{t\}^\{c\}=\\left\\\{\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)<\\mu\_\{t\}\\right\\\}\. By the definition ofℰca​\(t\)\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)and Jensen’s inequality,

ℰca\(t\)=∥𝔼\[dt−d\(xt\)\]∥2=∥𝔼\[𝔼\[dt−d\(xt\)∣ℱt\]\]∥2≤𝔼\[∥𝔼\[dt−d\(xt\)∣ℱt\]∥2\]≤𝔼\[∥dt−d\(xt\)∥2\]\.\\displaystyle\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)=\\left\\\|\\mathbb\{E\}\[d\_\{t\}\-d\(x\_\{t\}\)\]\\right\\\|^\{2\}=\\left\\\|\\mathbb\{E\}\\\!\\left\[\\mathbb\{E\}\[d\_\{t\}\-d\(x\_\{t\}\)\\mid\\mathcal\{F\}\_\{t\}\]\\right\]\\right\\\|^\{2\}\\leq\\mathbb\{E\}\\\!\\left\[\\left\\\|\\mathbb\{E\}\[d\_\{t\}\-d\(x\_\{t\}\)\\mid\\mathcal\{F\}\_\{t\}\]\\right\\\|^\{2\}\\right\]\\leq\\mathbb\{E\}\\\!\\left\[\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]\.\(83\)We split the right\-hand side according to the two branches of Algorithm[1](https://arxiv.org/html/2607.15412#alg1):

𝔼​\[‖dt−d​\(xt\)‖2\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]=𝔼​\[𝟏ℛt​‖dt−d​\(xt\)‖2\]\+𝔼​\[𝟏ℛtc​‖dt−d​\(xt\)‖2\]\.\\displaystyle=\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}\}\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]\+\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}^\{c\}\}\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]\.\(84\)The two terms are controlled by different mechanisms\. On the regular branchℛt\\mathcal\{R\}\_\{t\}, the stochastic MGDA subproblem is sufficiently nondegenerate, so the direction perturbation can be bounded by the Lipschitz continuity of the CA direction, up to the bad\-event correction already used in the proof of Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1)\. On the degenerate branchℛtc\\mathcal\{R\}\_\{t\}^\{c\}, we do not rely on Lipschitz continuity\. Instead, whenM=2M=2, small tangent curvature directly implies‖qZt,1−qZt,2‖2=O​\(μt\)\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|^\{2\}=O\(\\mu\_\{t\}\), which controls the discrepancy between the fallback direction and the full\-batch CA direction\. We next bound the regular and degenerate branch terms separately\. Case 1:Ifμmin​\(U⊤​Qt⊤​Qt​U\)≥μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)\\geq\\mu\_\{t\}, using the regular\-branch direction perturbation bound \([63](https://arxiv.org/html/2607.15412#A2.E63)\) from the proof of Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1), we have

‖dt−d​\(xt\)‖≤ℓd,t​‖Qt−∇FS​\(xt\)‖F\+2​ℓF​‖Qt−∇FS​\(xt\)‖F1/2​𝟏𝒢tc,\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|\\leq\\ell\_\{d,t\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\+2\\sqrt\{\\ell\_\{F\}\}\\,\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{1/2\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\},\(85\)where𝒢tc=\{‖U⊤​Qt⊤​Qt​U−U⊤​∇FS​\(xt\)⊤​∇FS​\(xt\)​U‖2\>μt2\}\\mathcal\{G\}\_\{t\}^\{c\}=\\left\\\{\\\|U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\-U^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)^\{\\top\}\\nabla F\_\{S\}\(x\_\{t\}\)U\\\|\_\{2\}\>\\frac\{\\mu\_\{t\}\}\{2\}\\right\\\}\. Squaring \([85](https://arxiv.org/html/2607.15412#A2.E85)\) and using\(a\+b\)2≤2​a2\+2​b2\(a\+b\)^\{2\}\\leq 2a^\{2\}\+2b^\{2\}, we obtain

‖dt−d​\(xt\)‖2\\displaystyle\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}≤2​ℓd,t2​‖Qt−∇FS​\(xt\)‖F2\+8​ℓF​‖Qt−∇FS​\(xt\)‖F​𝟏𝒢tc\.\\displaystyle\\leq 2\\ell\_\{d,t\}^\{2\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\+8\\ell\_\{F\}\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\.\(86\)By conditioning onℱt\\mathcal\{F\}\_\{t\}, using Assumption[2](https://arxiv.org/html/2607.15412#Thmassumption2), and then taking total expectation, sinceM=2M=2,𝔼​\[‖Qt−∇FS​\(xt\)‖F2\]≤2​σ2\|Zt\|\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\\right\]\\leq\\frac\{2\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\. Moreover, by the Cauchy–Schwarz inequality and the bad\-event probability bound \([54](https://arxiv.org/html/2607.15412#A2.E54)\) from the proof of Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1),

𝔼​\[‖Qt−∇FS​\(xt\)‖F​𝟏𝒢tc\]≤\(𝔼​\[‖Qt−∇FS​\(xt\)‖F2\]\)1/2​\(ℙ​\(𝒢tc\)\)1/2≤\(2​σ2\|Zt\|\)1/2​\(32​ℓF2​σ2\|Zt\|​μt2\)1/2=𝒪​\(1\|Zt\|​μt\)\.\\displaystyle\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{t\}^\{c\}\}\\right\]\\leq\\left\(\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\\right\]\\right\)^\{1/2\}\\left\(\\mathbb\{P\}\(\\mathcal\{G\}\_\{t\}^\{c\}\)\\right\)^\{1/2\}\\leq\\left\(\\frac\{2\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\\right\)^\{1/2\}\\left\(\\frac\{32\\ell\_\{F\}^\{2\}\\sigma^\{2\}\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{2\}\}\\right\)^\{1/2\}=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}\}\\right\)\.\(87\)Usingℓd,t=1\+4​ℓF2/μt\\ell\_\{d,t\}=1\+4\\ell\_\{F\}^\{2\}/\\mu\_\{t\},𝔼​\[‖Qt−∇FS​\(xt\)‖F2\]≤2​σ2\|Zt\|\\mathbb\{E\}\\\!\\left\[\\\|Q\_\{t\}\-\\nabla F\_\{S\}\(x\_\{t\}\)\\\|\_\{F\}^\{2\}\\right\]\\leq\\frac\{2\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}, and \([87](https://arxiv.org/html/2607.15412#A2.E87)\) in \([86](https://arxiv.org/html/2607.15412#A2.E86)\), we obtain

𝔼​\[𝟏ℛt​‖dt−d​\(xt\)‖2\]=𝒪​\(1\|Zt\|​μt2\),\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}\}\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\|Z\_\{t\}\|\\mu\_\{t\}^\{2\}\}\\right\),\(88\)where the term𝒪​\(1/\(\|Zt\|​μt\)\)\\mathcal\{O\}\(1/\(\|Z\_\{t\}\|\\mu\_\{t\}\)\)is absorbed into𝒪​\(1/\(\|Zt\|​μt2\)\)\\mathcal\{O\}\(1/\(\|Z\_\{t\}\|\\mu\_\{t\}^\{2\}\)\)since0<μt≤μ¯0<\\mu\_\{t\}\\leq\\bar\{\\mu\}\. Case 2:Ifμmin​\(U⊤​Qt⊤​Qt​U\)<μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)<\\mu\_\{t\}, everyλ∈Δ2\\lambda\\in\{\\Delta^\{2\}\}can be written asλ=\(a,1−a\)\\lambda=\(a,1\-a\)for somea∈\[0,1\]a\\in\[0,1\]\. Write

λt=\(a^t,1−a^t\),λ∗​\(xt\)=\(at∗,1−at∗\),\\lambda\_\{t\}=\(\\hat\{a\}\_\{t\},1\-\\hat\{a\}\_\{t\}\),\\qquad\\lambda^\{\*\}\(x\_\{t\}\)=\(a\_\{t\}^\{\*\},1\-a\_\{t\}^\{\*\}\),\(89\)withat∗,a^t∈\[0,1\]a\_\{t\}^\{\*\},\\hat\{a\}\_\{t\}\\in\[0,1\]\. Then

dt=−\(a^t​qZt,1\+\(1−a^t\)​qZt,2\),d​\(xt\)=−\(at∗​∇fS,1​\(xt\)\+\(1−at∗\)​∇fS,2​\(xt\)\)\.d\_\{t\}=\-\(\\hat\{a\}\_\{t\}q\_\{Z\_\{t\},1\}\+\(1\-\\hat\{a\}\_\{t\}\)q\_\{Z\_\{t\},2\}\),\\qquad d\(x\_\{t\}\)=\-\(a\_\{t\}^\{\*\}\\nabla f\_\{S,1\}\(x\_\{t\}\)\+\(1\-a\_\{t\}^\{\*\}\)\\nabla f\_\{S,2\}\(x\_\{t\}\)\)\.\(90\)Adding and subtractingat∗​qZt,1\+\(1−at∗\)​qZt,2a\_\{t\}^\{\*\}q\_\{Z\_\{t\},1\}\+\(1\-a\_\{t\}^\{\*\}\)q\_\{Z\_\{t\},2\}, we obtain

dt−d​\(xt\)\\displaystyle d\_\{t\}\-d\(x\_\{t\}\)=\(at∗−a^t\)​\(qZt,1−qZt,2\)\+at∗​\(∇fS,1​\(xt\)−qZt,1\)\+\(1−at∗\)​\(∇fS,2​\(xt\)−qZt,2\)\.\\displaystyle=\(a\_\{t\}^\{\*\}\-\\hat\{a\}\_\{t\}\)\(q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\)\+a\_\{t\}^\{\*\}\(\\nabla f\_\{S,1\}\(x\_\{t\}\)\-q\_\{Z\_\{t\},1\}\)\+\(1\-a\_\{t\}^\{\*\}\)\(\\nabla f\_\{S,2\}\(x\_\{t\}\)\-q\_\{Z\_\{t\},2\}\)\.\(91\)Thus, usingat∗,a^t∈\[0,1\]a\_\{t\}^\{\*\},\\hat\{a\}\_\{t\}\\in\[0,1\],

‖dt−d​\(xt\)‖\\displaystyle\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|≤\|at∗−a^t\|​‖qZt,1−qZt,2‖\+at∗​‖∇fS,1​\(xt\)−qZt,1‖\+\(1−at∗\)​‖∇fS,2​\(xt\)−qZt,2‖\\displaystyle\\leq\|a\_\{t\}^\{\*\}\-\\hat\{a\}\_\{t\}\|\\,\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|\+a\_\{t\}^\{\*\}\\\|\\nabla f\_\{S,1\}\(x\_\{t\}\)\-q\_\{Z\_\{t\},1\}\\\|\+\(1\-a\_\{t\}^\{\*\}\)\\\|\\nabla f\_\{S,2\}\(x\_\{t\}\)\-q\_\{Z\_\{t\},2\}\\\|≤‖qZt,1−qZt,2‖\+‖∇fS,1​\(xt\)−qZt,1‖\+‖∇fS,2​\(xt\)−qZt,2‖\.\\displaystyle\\leq\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|\+\\\|\\nabla f\_\{S,1\}\(x\_\{t\}\)\-q\_\{Z\_\{t\},1\}\\\|\+\\\|\\nabla f\_\{S,2\}\(x\_\{t\}\)\-q\_\{Z\_\{t\},2\}\\\|\.\(92\)Squaring both sides and using‖u\+v\+w‖2≤3​‖u‖2\+3​‖v‖2\+3​‖w‖2\\\|u\+v\+w\\\|^\{2\}\\leq 3\\\|u\\\|^\{2\}\+3\\\|v\\\|^\{2\}\+3\\\|w\\\|^\{2\}, we get

‖dt−d​\(xt\)‖2≤3​‖qZt,1−∇fS,1​\(xt\)‖2\+3​‖qZt,2−∇fS,2​\(xt\)‖2\+3​‖qZt,1−qZt,2‖2\.\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\leq 3\\\|q\_\{Z\_\{t\},1\}\-\\nabla f\_\{S,1\}\(x\_\{t\}\)\\\|^\{2\}\+3\\\|q\_\{Z\_\{t\},2\}\-\\nabla f\_\{S,2\}\(x\_\{t\}\)\\\|^\{2\}\+3\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|^\{2\}\.\(93\)ForM=2M=2, the tangent space of the simplex isspan⁡\{\(1,−1\)⊤\}\\operatorname\{span\}\\\{\(1,\-1\)^\{\\top\}\\\}\. The reduced curvature matrixU⊤​Qt⊤​Qt​UU^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}Uis a scalar, and

μmin​\(U⊤​Qt⊤​Qt​U\)=12​\(qZt,1−qZt,2\)⊤​\(qZt,1−qZt,2\)=12​‖qZt,1−qZt,2‖2\.\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)=\\frac\{1\}\{2\}\(q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\)^\{\\top\}\(q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\)=\\frac\{1\}\{2\}\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|^\{2\}\.\(94\)Equivalently, forv=\(1,−1\)⊤v=\(1,\-1\)^\{\\top\}, we haveQt​v=qZt,1−qZt,2,Q\_\{t\}v=q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\},andU=v/2U=v/\\sqrt\{2\}\. Therefore, under the case conditionμmin​\(U⊤​Qt⊤​Qt​U\)<μt\\mu\_\{\\min\}\(U^\{\\top\}Q\_\{t\}^\{\\top\}Q\_\{t\}U\)<\\mu\_\{t\}, we have‖qZt,1−qZt,2‖2<2​μt\.\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|^\{2\}<2\\mu\_\{t\}\.Multiplying \([93](https://arxiv.org/html/2607.15412#A2.E93)\) by𝟏ℛtc\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}^\{c\}\}, bounding the last term via𝟏ℛtc​‖qZt,1−qZt,2‖2<2​μt\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}^\{c\}\}\\\|q\_\{Z\_\{t\},1\}\-q\_\{Z\_\{t\},2\}\\\|^\{2\}<2\\mu\_\{t\}, dropping the indicator on the two variance terms, and taking expectations yields

𝔼​\[𝟏ℛtc​‖dt−d​\(xt\)‖2\]≤3​𝔼​\[‖qZt,1−∇fS,1​\(xt\)‖2\]\+3​𝔼​\[‖qZt,2−∇fS,2​\(xt\)‖2\]\+6​μt\.\\displaystyle\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}^\{c\}\}\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]\\leq 3\\mathbb\{E\}\\\!\\left\[\\\|q\_\{Z\_\{t\},1\}\-\\nabla f\_\{S,1\}\(x\_\{t\}\)\\\|^\{2\}\\right\]\+3\\mathbb\{E\}\\\!\\left\[\\\|q\_\{Z\_\{t\},2\}\-\\nabla f\_\{S,2\}\(x\_\{t\}\)\\\|^\{2\}\\right\]\+6\\mu\_\{t\}\.\(95\)By Assumption[2](https://arxiv.org/html/2607.15412#Thmassumption2), form=1,2m=1,2,𝔼​\[‖qZt,m−∇fS,m​\(xt\)‖2\]≤σ2\|Zt\|\.\\mathbb\{E\}\\\!\\left\[\\\|q\_\{Z\_\{t\},m\}\-\\nabla f\_\{S,m\}\(x\_\{t\}\)\\\|^\{2\}\\right\]\\leq\\frac\{\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\.Combining this fact and \([95](https://arxiv.org/html/2607.15412#A2.E95)\), we obtain

𝔼​\[𝟏ℛtc​‖dt−d​\(xt\)‖2\]≤6​σ2\|Zt\|\+6​μt\.\\mathbb\{E\}\\\!\\left\[\\mathbf\{1\}\_\{\\mathcal\{R\}\_\{t\}^\{c\}\}\\\|d\_\{t\}\-d\(x\_\{t\}\)\\\|^\{2\}\\right\]\\leq\\frac\{6\\sigma^\{2\}\}\{\|Z\_\{t\}\|\}\+6\\mu\_\{t\}\.\(96\)Unified bound for both cases\.Combining these two cases, from \([88](https://arxiv.org/html/2607.15412#A2.E88)\) and \([96](https://arxiv.org/html/2607.15412#A2.E96)\), we conclude that

ℰca​\(t\)=𝒪​\(1\|Zt\|​μt2\+1\|Zt\|\+μt\)\.\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\|Z\_\{t\}\|\\,\\mu\_\{t\}^\{2\}\}\+\\frac\{1\}\{\|Z\_\{t\}\|\}\+\\mu\_\{t\}\\right\)\.\(97\)For the schedule used in Theorem[1](https://arxiv.org/html/2607.15412#Thmtheorem1), i\.e\.,\|Zt\|=Θ​\(t\+1\)\|Z\_\{t\}\|=\\Theta\(t\+1\)andμt=Θ​\(1log⁡\(e\+t\)\)\\mu\_\{t\}=\\Theta\\\!\\left\(\\frac\{1\}\{\\log\(e\+t\)\}\\right\), we obtain

ℰca​\(t\)=𝒪​\(1log⁡\(e\+t\)\)\.\\mathcal\{E\}\_\{\\mathrm\{ca\}\}\(t\)=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\\log\(e\+t\)\}\\right\)\.\(98\)This proves the theorem\. ∎