Tracking the Median of Gradients with a Stochastic Proximal Point Method
Authors: Fabian Schaipp
Guillaume Garrigos
Umut Simsekli
Robert M. Gower
Venue: Accepted by TMLR ()

Abstract: There are several applications of stochastic optimization where one can benefit from a robust estimate of the gradient. For example, domains such as distributed learning with corrupted nodes, the presence of large outliers in the training data, learning under privacy constraints, or even heavy-tailed noise due to the dynamics of the algorithm itself. Here we study SGD with robust gradient estimators based on estimating the median.
We first derive iterative methods based on the  stochastic proximal point method for computing the  median gradient and generalizations thereof.  Then we propose an algorithm estimating the median gradient across *iterations*, and find that several well known methods are particular cases of this framework.
For instance, we observe that different forms of clipping allow to compute online estimators of the *median* of gradients, in contrast to (heavy-ball) momentum, which corresponds to an online estimator of the *mean*.
Finally, we provide a theoretical framework for an algorithm computing the median gradient across *samples*, and show that the resulting method can converge even under heavy-tailed, state-dependent noise.

Published in Transactions on Machine Learning Research (10/2025)
Tracking the Median of Gradients with Stochastic Proxi- mal Point Method
Fabian Schaipp
fabian.schoipppHWnrr...
Technical University of Munich and Iraria Paris, ENS, PSL Research University
Guillaume Garrigos
perrigos@lpsm..n
Université Paris Cité and Sortonne Université, CNRS Laboraloire de Probabilités, Stalistique et Modélisation, F-75013 Paris, France
Umut Simşekli
wmwt.simsekki@hhri..ff
Inria, CNRS, ENS, PSL Research University Paris
Robert M. Gower
ngouerefaatroniissttute..rr
CCM, Flatiron Institule, Simons Poundation
New York City
Reviewed on OpenReview: https: // openrewiew. net/ forun? id= WMaLEg
Abstract
There several applications of stochastic optimization where benefit from robust estimate of the gradient. For example, domains such distributed learning with corrupted nodes, the presence of large outliers in the training data, learning under privacy constraints, or even heavy-tailed noise due to the dynamics of the algorithm itself. Here we study SCD with robust gradient estimators based on estimating the median.
We first derive itcrative methods based on the stochastic proximal point method for com- puting the median gradient and generalizations thereof. Then we propose an algorithm estimating the median gradient across iterations, and find that several well known meth- ods are particular cases of this framework. For instance, we observe that different forms of clipping allow to compute ouline estimators of the median of gradients, in contrast to (heavy- Finally, provide
ball) momentum, which corresponds theoretical framework for algorithm computing the median gradient across samples, and show that the resulting method can converge even under heavy-tailed, state-dependent noise.
online estimator of the
1 Introduction
Many problems in machine learning can be represented by an optimization problem
min l(w),
wERd
where is vector of parameters and l: Rd R is a loss function. To tackle this problem, gradient-based optimization algorithms have been the de-facto choice in many application domains (Nemirovsky & Yudin, 1983; Bottou, 2010; Bottou et al., 2018), where are only given access to noisy orucle of the gradient
g. V((un) + (w)))
(1)

---

Published in Transactions on Machine Learning Research (10/2025)
Here t denotes the iterations and (wr) Rd is noise vector that is sampled from distribution that depends on the parameter wt- With this noise oracle, stochastic gradient descent (SGD) with learning rate The is given by
W we 1/:tt
(SGD)
While SGD has proven useful in numerous applications, its performance heavily relies on the 'quality' of the noisy oracles gt, and can tragically degrade when the noise & has significant outliers, exhibits heavy tails (that is, ||Ell| is very large with non-negligible probability), or has been corrupted in an adversarial way. We provide two examples.
(i) Heavy-tailed gradients. Recent studies have provided theoretical and empirical evidence that heavy tails can naturally arise in stochastic optimization. From theoretical perspective Gurbuzbalaban et al. (2021); Hodgkinson & Mahoney (2021); Lehman et al. (2023) showed that the parameter-dependent nature of & can result in heavy tails, even in very basic settings such as linear regression with Gaussian data. On the other hand, it has been empirically observed that the gradients for training transformer architectures on language tasks are more heavy-tailed compared to, for example, convolutional models for image data (Zhang et al., 2020b; Kunstner et al., 2023). While the presence of heavy-tails in gradients might be beneficial in certain settings (Simsekli et al., 2020), from optimization perspective, it mostly introduces non-trivial challenges, which might even make the algorithm diverge unless additional care is taken (Zhang et al., 2020b; Gorbunov et al., 2020).
(ii) Corrupted nodes. A well-known problem in distributed learning is when some computation nodes are malicious and can communicate adversarial updates, which results in inaccurate gradient oracles that can significantly misguide the optimization procodure. Similar to the hcavy-tailed sctting, depending on how malicious the nodes are, SGD can be impractical unless certain modifications are made (Mhanıdi et al., 2018). We refer to Karimireddy et al. (2021) and references therein for an overview of more robust aggregation techniques.
In order to make the optimization algorithms more robust to such noisy oracles, many techniques have been developed for different domains under various conditions. In the context of heavy-tailed gradients, clipping is often employed (ZZang et al., 2020a; Puchkin et al., 2023; Koloskova et al., 2023). In distributed learning robust aggregation rules are needed to protect against corrupted or malicious nodes (Data et al., 2018; Karimireddy et al., 2021; Khirirat et al., 2023). This line of research is also closely related to error feedback in federated learning (Seide al., 2014; Karimireddy et al., 2019; Richtarik et al., 2021) and learning under differential privacy constraints (Khirirat et al., 2023).
Robustness of median. While attracting increasing attention in stochastic optimization thanks to mod- ern machine learning applications, laming the impact of strong noise has already been considered in various other domains. Indeed, estimation under heavy-tails and corruptions has been a long-standing topic in ro- bust statistics (Huber, 1981). Being a vast research field that has produced numerous algorithms designed for different tasks, one of the recurring themes in robust statistics is the use of the sample median and its variations as opposed to the sample mean (Minsker, 2015), whenever an aggregation of random variables is needed. For instance, in the presence of heavy tails, the sample median has been shown to be significantly more robust estimator of the true mean, whereas the sample mean can be vulnerable to strong noise (Lugosi & Mendelson, 2019).
Sample median SGD. Inspired by tools from robust statistics, some notions of median have been utilized in stochastic optimization as well (Yin al., 2018; Alistarh et al., 2018; Acharya et al., 2022). One such approach is to compute the median over finite sample of gradients. While this approach has paved the way for powerful optimization algorithms in terms of robustness, it often introduces significant computational burden, since a multivariate median needs to be computed at every iteration (Weiszfeld & Plastria, 2009; Vardi & Zhang, 2000).
Motivation. Clipping- and error feodback approaches on the one hand, and median- approaches the other hand are motivated through different. mathematical frameworks and appear to use different
2

---

Published in Transactions on Machine Learning Research (10/2025)
algorithmic tools. In this study, our main goal is to bridge the gap between these two seemingly different branches and to bring a unified theoretical perspective that can shed further light on both directions. The main tool to build this bridge between stochastic optimization and robust statistics will be the Stochastic Proximal Point method (SPP) (Asi & Duchi, 2019; Davis & Drusvyatskiy, 2019; Toulis et al., 2020) for solving a later-specified gradient estimation problem.
Contributions. We first show how heavy-ball momentum (Polyak, 1964) can be seen online estimator of the mean gradient using SPP. Here we use the term online in the sense that the method is given different loss function at cach step.
Encouraged by this result, we then focus on online estimation the median gradient, using the same tech- nique. Doing so, we recover several known clipping-basd based optimization algorithms from distributed learning special cases, such as Clip21 (Khirirat al., 2023), and variant of centered clipping (Karimireddy et al., 2021). We also shown connections to sign-based gradient methods (Riedmiller & Braun, 1993).
Our proposed framework allows to unify the different motivations for previously developed techniques, and illustrates that clipping- based optimization algorithms essentially run a loose estimation of the median across iterations. In particular, the observation that centered clipping and Clip21 are iterative estimators of geometric median appears be new, and might have consequences for its application in distributed learning.
We theoretically analyze these online gradient estimation methods in simplified setting: when allowing multiple gradient samples per iteration, we show that SCD with (approximately computed) median gradients indeed yields a very powerful algorithm, which converges with 1/vT rate (T being the number of iterations) even when the gradient oracles are hcavy-tailed with diverging socond-order moments. We further illustrato that, in addition to having infinite variance, the noise vectors (xw) can even have multiplicative dependence w, a scenario which is highly challenging and cannot be directly covered by existing theoretical results, see e.g., Wang et al. (2021); Zhang et al. (2020b); Puchkin et al. (2023).
We finally illustrate our theory on synthetic lcast-squares experiments where we compare the offectiveness of sample median, sample mean, and several online median estimators. Our results underline that for heavy- tailed noise, using the sample median is highly effective in contrast the sample mean which is unstable and often does not converge. Our experiments also show that our online median estimates require only single sample per iteration, making it less expensive alternative to the sample median. We further compare different clipping techniques for training transformer architectures on language modeling tasks, and show that they can improve upon the performance of SGD with momentum, however the gap is relatively small.
robust, and
Notation. Throughout the paper, | llp denotes the f--norm, given by ||=||p = (Ei 1=1))² when p e max |z|| when p When p we recover the usual Euclidean f--norm 11- which ==l....dd
[1, oc), and ||=||00
we will often simply denote by || I|- For matrix A, we denote its Frobenius norm by |AIlF = v Ees Al For N., we denote the set [n] = {I.....n]. n3.
2 Preliminaries
2.1 Heavy-tailed Random Variables
A random variable X is said to be heaoy-lailed if the tails of its distribution decay slower than the tails of an exponential distribution. One important example is the family of symmetric a-stable distributions Po. (Nolan, 2020, Def. 1.4), parameterized by a stability index a E (0. 2] and a scale a > When a = 1, this is the Cauchy distribution; when a = 2, it reduces to a Gaussian. The parameter a controls the spread of the distribution. When we call the distribution slandard and denote it by P., Pa.1- The parameter
3

---

Published in Transactions on Machine Learning Research (10/2025)
the other hand controls the heaviness of the tails: for < 2 the random variable X ~ Pa has infinite variance, whereas for S even the mean of X is infinite. However, for any a, the median is equal to O.
2.2 Mean Estimation and (Sample) Median
Estimating the mean of distribution, when given finite number of samples, is one of the core problems studied in statistics. If the distribution in question has heavy-tails, or has significant outliers, the sample mean turns out to be a poor estimator. Lugosi & Mendelson (2019) give a survey of alternative and more robust techniques: one such alternative the median, for which we will introduce basic definitions next.
Here, denote by 2 real-value random value, and the boldface denote the expectation with respect to the distribution of a (or respectively) by IE.
F random vector. We always
Multivariate median. The one-dimensional median is defined by
median(2) E argmmin E [Im =I]-
(2)
mER
In contrast to the mean, the median is always defined (though it may not be unique) (Cramér, 2016). Since are interested in approxinating the median gradient, we need notion of median that generalizes to random vectors E Rdd. For this, we can define the fp-median:
medians, (z) argmin E [[|m x =11p]
(3)
meRd
where || = ) is the lp norm. This recovers several existing notions of a multivariate median: for = we obtain a componentwise median (or (-median) and for p = 2 we obtain the geometric median (or f2-median) (Fréchet, 1948; Weiszfeld & Plastria, 2009; Minsker, 2015; Cohen et al., 2016). For d = 1 and every p E oo), the f-mmdian coincides with the one-dimensional median (2).
m²)²
Sample median. Given realizations z(1) (n) of z, the sample median is defined
median,
semm (z()) E argmin
Σ m 200
(4)
mERd
Clearly (4) is special case of (3), by setting the distribution of the empirical measure E 82.-
It is generally accepted that the sample median is a more robust estimator than the sample mean (Huber, 1981; Hampel et al., 2005). This nicely illustrated by the notion of a breakdown point (Donoho & Huber, 1983; Lopuhaa & Rousseeuw, 1991), which is the smallest fraction of a sample that, if arbitrarily corrupted, can arbitrarily change the value of the estimator. The breakdown point of the sample median is roughly 2: meaning that at least half of the samples need be outliers for the median diverge. The sample mean however be arbitrarily corrupted by single outlier, thus its breakdown point is 1 n'
If the samples 200 obtained by taking block-wise means over observations, (4) is called the median-of- means estimator (Nemirovsky & Yudin, 1983; Lugosi & Mendelson, 2019), which is known to be robust mcan estimator (Lugosi & Mendelson, 2019).
Relation to M-estimation. More generally, for function D: Rdd - IR we will consider the problem
argmin E (D(m x)]
(5)
meRd
We assume that is closed, proper, convex function and that (5) admits solution (see Appendix for a discussion). For D - the solution to (5) is the mean E [z] (if it exists), and for D ||. the solution
4

---

Published in Transactions on Machine Learning Research (10/2025)
is the geometric median defined in (3). Problem (5) can be seen as special case of M-estimators (Huber, 1981, Sec. 3.2).
The choice of D determines properties of the associated estimator: if the function D heavily penalizes large values, like the quadratic D bll I12: then the solution (5) will be sensitive to outliers. In contrast D = || 2l2 and D -| || grow only linearly, and thus (5) will be less sensitive outliers. We return to problem (5) later in Section 3.2.
3 Robust Gradient Estimation with Stochastic Proximal Point
3.1 Warmup: Momentum as Online Mean Gradient Estimation
When dealing with noisy gradient oracles, a standard technique is to apply (heavy-ball) momentum (Polyak, 1964). For momentum coefficient [0, 1), it given by
m = 3m: + (1 -3gr,. W++1 wt
(SGD-M)
m-
Momentum has been empirically shown to improve the performance of SGD in machine learning (Sutskever et al., 2013), and can be seen a variance reduction technique (Gower et al., 2020).
It is easy to that momentum performs exponentially weighted average section, we will derive a new perspective on SGD-M, namely being an online estimator of the mean gradient at a given point. To see this, we recall that for a random variable 2 E Rd its mean (if it exists) is the solution to (5) with = |1l 112. The random variable of interest this context are the noisy gradients gr. We could in principle solve problem (5) with iterative stochastic methods. For this purpose, we consider the stochastic proximal point (SPP) method (Asi & Duchi, 2019; Davis & Drusvyatskiy, 2019). We give a detailed introduction to SPP in the next section.
past gradients. In this
For the purpose of this section, it is sufficient to know that the iterates (m,) of SPP with step-size > 0 applied to (5) are given by (details in Appendix B.2)
1
m++1
argmin D(m gr) + 2T |m mill gt prox, prox,p - 9t),
(6)
where we denote by proxp the proximal operator of D,
prox (x) == argmin D(y) bly 2212.
yERd
For D = =1 112, is easy compute prox,p(x) + x. Thus, one iteration of SPP (6) is equal
m4+1 = gr + prox, (m. -9:) = g: + + (m: - 9:)) =
m, + 1
This is exactly the momentum step in (SGD-M) with 1 -. However, in SGD-M the parameters wi are updated each step as well, and thereby the distribution of the gradients ge changes cach step. In conclusion, the momentum operation can be understood as an online estimation of the mean gradient.
We end this section by justifying our choice specifically consider SPP for solving (5), instcad of SGD other stochastic methods. we were to apply SGD with step size problem (5), we would obtain
m++1 = (1 - (11-7)m m) + Tg:-
This also resembles momentum, but note that the momentum coefficient t could be negative if T > For SPP on the other hand, the momentum coefficient correctly parametrized since 1 1+r is contained in (0, for every 0.
5

---

Published in Transactions on Machine Learning Research (10/2025)
In conclusion, can understand heavy-ball momentum (SGD-M) applying SPP to the mean estimation problem in an online fashion. This opens the question what is the SPP update for estimators that are more robust to heavy-tailed noise, such as the median (or more generally for other choices for D that are of interest). We answer this in the next section.
3.2 Clipping as Online Median Gradient Estimation
We now focus on the following gradient estimation problem: let 9 denote the (lixed) distribution over noisy gradients For D R Rzo being closed, proper, convex function, consider the problem of approximating
argmin Eg-s (D(m - g)]
(8)
mERd
We consider stochastic iterative methods for solving (8), with a special focus on the stochastic proximal point method (SPP). We recall the SPP update being
1 -m - m,ll
m = argmin D(m - gt) +
m
2T
(9)
= 9t + prox pro 9:)- 9t)-
The SPP update be where SPP has closed form update, it is often preferred to SGD since is easier to tune (Asi & Duchi, 2019; Milzarek et al., 2024). Fortunately, as we show next, the SPP method enjoys closed-form updates for all choices of which are of interest in our context, in particular for E (Il 11,,1 l12 1ll [12]. All the details are deferred to Appendix B.3.
implicit version of SGD, which is hard to compute in general. In cases
Vectorwise clipping. If we choose D = || ||2, the SPP update applies clipping to the difference between sampled gradient Jr and previous estimate m..
Corollary 3.1. For D || 1|2 update (9) is given by
m m, + 2 m:),
(10)
where clip,,2(0)= = [ax|[r]]l]a) u1.
We can rewrite update (10) as m4+1 = 3.m, + (1- B:)g. with B := max In other words, online estimation of the geometric median (D lll) with SPP equal cautious version of momentum, samples which are too far from m, will be down weighted. This allows the iterates to be more robust to outliers.
Componentwise clipping. If we choose D || ll,, SPP performs componentwise clipping instead. Here as well, clipping protects against large individual entries by shrinking them independently.
Corollary 3.2. For D = || update (9) is given by
m++1 m. + clip,. mm;),
(11)
where clip,, (v) = (min (max ( -
Huber function. For update (10), it is possible that m thus no momentum. To allow for a soft transition, we can choose to be the Huber function. For μ > 0, it is given by
||||| S p. else.
H, Rd + R. Hz(2)=
|1||=||
2 2

---

Published in Transactions on Machine Learning Research (10/2025)
The Huber function operates like the squared loss for arguments with small norm, and like the æ--norm for arguments with large norms (potentially outllers).
Corollary 3.3. For D Has update (9) is given by
M++1 = 9: + mm - gt) = B. + (1 Br)g:.
(12)
where B ; max
PT
ge1 1 [1++)]
In update (12) the coefficient 3r is always positive. Thus, D H2 is a tradcoff between momentum with fixed coefficient (D = 1 -1%- and clipping (D = (2])) However, it comes at the cost of choosing/ Lunnng an additional hyperparameter μ.. In Appendix B.4, we additionally compare the updates when using stochastic subgradient descent instcad of SPP for solving (8), showing that sign-SGD is related to mmmedian cstimation.
4 Gradient Estimator in the Wild
Our final objective is to use robust gradient estimators within SGD-type method. Because at each iteration the weights w, updated, the distribution of the gradients (denoted by G in the previous section) also changes at each iteration of SGD. Our strategy is to interweave updates in the weights w, with SPP updates in the gradient estimators m.- That is, we sample one stochastic gradient ge per iteration and set
m4+1 9: + prox-p(mm. -9:),
(13)
W++1 = wt m++++
With the results from Sections 3.1 and 3.2, immediately obtain the following special cases:
m (1 -4--1-):7
147 ( m + 1
Wh+11 w. m11 (i) D = 12:
m4+1 m. + clipp.- m.)
(ii) DDD=11-1 p [1,
Wh+1 = wt - 7-
Equation (i) is SGD with momentum where the SPP step size defines the momentum coefficient. On the other hand, (ii) corresponds to clipping, and here the SPP step size determines the clipping threshold. other words, SGD with momentum is online mean estimation what clipping is to online median estimation.
A slightly different approach would be to restart m, in every iteration (cold start). In this case, (i) reduces to SCD with no momentum, while in (ii) the clipping operator is applied to Ir, instead of gr m. which is also common technique in practice (Zhang et al., 2020a). We discuss this relation below in more detail.
Connection to Error Feedback. Methods such as (13) are also used in the distributed learning setting to improve communication and protect against corrupted nodes (Karimireddy et al., 2021). These methods are often called Error Feedback (EF) methods (Seide et al., 2014; Richtarik et al., 2021) and generally involve an update of the form m++1 = m: + C,(g, m.) where C, Rd + Rd a compression operator. Projections onto balls can be seen as compression, since one can encode the resulting vector in fewer bits (Safaryan et al., 2021). In particular, centered clipping by Karimireddy et al. (2021), and the Clip21 method (Khirirat al., 2023) are using variations of update (10) in the distributed setting, and thus 'secretly estimating" the geometric median of the gradients returned across all nodes.
SGD with standard clipping. Even in the non-distributed setting, a standard technique to avoid training instabilities is to directly clip the gradient g: (Zhang al., 2020a). For momentum coefficient. B E [0, and
7

---

Published in Transactions on Machine Learning Research (10/2025)
>> 0, let
m 3m; + (1 - 3) min(1, Tox J
(14)
Wt+1 = Wt - 71:71
We will refer to (14) as clipped-SOD. The method has been studied extensively, often for the case / = 0, see Zhang et al. (2020a); Gorbunov et al. (2020); Koloskova et al. (2023); Puchkin et al. (2023) and references therein.
As explained above, when 8 = 0, then (14) is the same (10) with cold start (resetting m. 0 in every iteration); but this does not allow for momentum, which is usually used in practice on top of clipping. However, we can derive clipped-SGD (14) also as online SPP for computing a specific robust mean estimator, known as the Caloni- Giulini mean estimator (Catoni & Giulini, 2018; Lugosi & Mendelson, 2019). For this, consider the problem
argmin Eg- [1lm min (1, |ao 391 mERd
(15)
The solution to (15) is Egg- min(1, TōT |g] step of SPP (9) applied to (15) gives (14) with B 1tr
which is exactly the Ratoni-Giulini mean estimator. Now, one
Outline of remaining paper. Before comparing these different online gradient estimation methods in experiments, we will discuss convergence guarantees: ideally, we would like to analyze the online method (13). However, when is not strongly convex this analysis turns out to be difficult, mainly due to the fact that the distribution of gr changes every step. Hence, the next section will analyze the online median estimator in simplified setting, where we have access multiple samples each iteration, and can (approximately) compute their sample median. We focus on settings where the noise in gt is heavy-tailed, and prove that in such scenarios the sample median can still guarantee convergence (while the sample mean fails).
Finally, our experiments in Scction 6 will show that the online versions of the sample modian method (VClip and CClip) show superior performance as well in the heavy-tailed scenario, justifying the online estimation.
5 Theory for the Sample Median Gradient Method
In this section, we showease that SGD with an (approximate) sample median is robust heavy-tailed noise, whereas SGD using the sample mean fail. Consider the following sctup: at every iteration 2 0, we have access to n noisy oracle gradients (g) ,..., ((()), where
(1)
( v((w.) + ! (w.) for i 1= g
Here (E!" (wx) E Rd) is set of i..dd noise vectors. Given these sampled gradients, the typical approach of SGD would be to use their sample mean (average) 9: = 1 =u E 9; as update direction. However, Zhang et al. (2020b, Remark 1) show that this fails to converge for any stop size under heavy-tailed noisc.
Alternatively, improve robustness, we analyze the update
W++1 w. - 7mmmmmmm-..- + ex),
(16)
where m, = median,,, and e E Rdd represents random error we may commit in computing the sample median. We refer method (16) as Sample Medion Gradient Descent (SMGD).
8

---

Published in Transactions on Machine Learning Research (10/2025)
Assumption 5.1. There exists 01, 61, 82 2 0 such that, for every Rd, the sample median
(e. (g) verifies
E [ - V 1 8f v2]
(17)
E m E ml] || - of + 02 V((
Assumption 5.2. There exists ε > such that, for every 2 0, the error computing the sample median has finite variance: E |Ieal|2 gi (1)
..... < (m)
Based on these two assumptions, we establish the following complexity results for (16).
Proposition 5.3. Let L R be L-smooth and let Assumption 5.1 hold with 62 S 1 Take v S
+1(1+22+2652 and consider wy a sequence generated by (16) where ex verifies Assumption 5.2. Then, for every T 2 1 it holds
min E [IV[((:))] o o + 09 +2
0S
Proposition 5.4. Let f: Rd > be convex and G-Lipschitz, with argmin l + 0. Let Assumptions 5.1 and 5.2 hold. Without loss of generality assume that 62 = 02 = Then, for 7j = (dite)T+VT and every T 1, the iterates we from (16) satisfy
E [((wT) inf 0 inf(]=0 (0 (1/ + 81 +E).
where Wy ETD 0'w, with 0 =
T T+2"
The proofs follow tochniques from the analysis of biased SCD (scc c.g. Demidovich et al. (2023)) and are provided in Appendix A. Let us now discuss our main Assumption 5.1. Assune for simplicity that 62 = = 0 (for instance if is Lipschitz), that e; = (the sample median computed exactly), and consider that g. v((we) (0) where <(() is noise term. Then, Assumption 5.1 becomes'
E [meddian im(m (E. (1 v² +00.
(18)
In other words, need the second moment of the sample median of E(0) to be uniformly bounded. We want to stress that our choice of using the modian is crucial when the c(0)) come from a heavy-tailed distribution, such as a (univariate) standard a-stable distribution, with a E (1,2), Indeed, in this case we know that the variance of the sample median finite for sufficiently large sample size (see Bickel (1967, Theorem 2.2) and Nolan (2020, Theorem 1.2)) On the contrary, taking m, as the usual sample mean causes trouble, the variance of the sample mean is infimite everywhere. See Fig. 2 for illustration of this phenomenon.
This simple discussion illustrates that Assumption 5.1 can be satisfied under mild conditions on the noise. We exploit this the next corollary, which shows that the sa-saplle median can even accommodate state- dependent noise. Lct us define first our model for such noisc.
See Lemma A.2 in the appendix for proof. 2e know more: The sample median of parent distribution with median ş is asymptotically normal with location (Chu & Hotelling, 1955). For Cauchy distributions (a the sample median has finite variance for (Chu & Hotelling, 1955, Remark 1), while first and second moment of the sample mean undefined. 3This due the fact that, by definition of a-stability, the sample mean of i.idd sample follows same o-stable distribution (up to affine translation).
9

---

Published in Transactions on Machine Learning Research (10/2025)
first moment
second moment
first moment
second moment
1.0
10
1.0
10a
10a
101
0.5
10a
0.5
101
10a
0.0
0.0
10a
10-1
10-1
-0.5
0.5
10-2
10-2
-1.0
10
median
-1.0
10
median
10
10a
10
101
10a
10
Sample size
mean
Sample size
mean
1.1
(b) 1.5
Figure 2: First and second moment of sample median /mean for standard o-stable distribution. We approx- imate E by running 10 000 trials. The sample median has much smaller variance (cf. (18)) compared to the sample mean.
Assumption 5.5. For every w E R we have that = V((w) + E(w)ç, where E(w) E Rd is a matrix and Ç is a random vector whose components are drawn i.i.d. from a standard symmetric a-stable distribution with a > 1. There exists constants cı, > 0 such that
[[w)] s c1 + c2 Vi(w))] for all w E Rd.
In the recent literature (see e.g. Zhang et al. (2020b); Puchkin al. (2023); Sadiev et al. (2023)), a commonly made assumption is that E [llgg V((w))l s o² for some p < 2 where o² 0 cannot depend on On the contrary, Assumption 5.5 can accommodate much stronger noise. To illustrate this, consider d d= and ((w) = w²/2. Assumption 5.5 allows the noise model [(w) with E(w) = va + cz which results in strong noise, since Ç has infinite variance if a < 2, and this is amplisied by E(w) when w is large. Such strong noise makes vanilla SGD diverge, as we will illustrate our experiments.
Corollary 5.6. Let n 2 3 be odd and 1. Consider the iterates from (16) with 0, and suppose (i) V((w;) E(w,
(i) verifies Assumption 5.5.
that gt
(i) If is L-smooth and O (+)), then we have that minogesr - -
(ii) If is convex and Lipschitz and = 1/VT then we have that E [((ww) inf OLIVTT), where ür defined as in Proposition 5.4.
This result illustrates how powerful the sample median can be when used in gradient-based optimization. However, SMGD (16) has clear drawbacks: (i) requires draw multiple samples per iteration (multiple calls of the oracle), and (ii) we need to compute the sample median up to some tolerance. For instance, the geometric median
not be computed in closed form and there exists vast body of literature how to approximate it (Cohen et al., 2016). Moreover, the noise still needs to be symmetric in order for the median to denoise correctly (cf. Assumption 5.5 and Fig. 8 (right))..
Nevertheless, our convergence guarantees for SMGD allow us to be optimistic that the strong performance in the heavy-tailed setting will also transfer the online drop-in replacements (of (16)), which had previously presented in Section 4. We investigate this in the following experiments section.
10

---

Published in Transactions on Machine Learning Research (10/2025)
6 Experiments
We compare the iterative gradient estimation techniques for two experimental setups, namely (1) estimating a vector/gradient from fixed distribution, and (ii) methods of the form (13), that is, iterative gradient estimation while simultaneously learning the weights.
We study both settings for synthetic data where we can control the level of heavy-tailedness, as well as for language modelling tasks with transformer models. We consider the same three language modeling tasks as studied in (Kunstner et al., 2023): an encoder-only transformer for the PTB dataset, a Transformer-XI model for the WikiText-2 dataset, and fine-tuning a DistillBERT model for question-answering on the SQuAD dataset. We refer to Appendix C for details.
In the following, we use VClip to refer to vectorwise clipping (10) and CClip for componentwise clipping (11).
6.1 Gradient Estimation with Fixed Weights
Synthetic data. In the first experiment, we verify the hypothesis that the choice of D matters for problem (8); in particular, we show that estimating the median is more stable when the noise distribution heavy- tailed.
Setup. We consider the problem of estimating fixed vector from the oracle g under varying degrec of heavy-tailedness of PP For this purpose, we choose the standard, unskewed a-stable distribution Pa. We generate 9 E with with d = 10 where each component is generated i.i.d standard Gaussian.
with & ~ P,
In each iteration, a sample is generated as follows: each coordinate of (gt); is (independently) sampled from Pa with location (g); and varying values for a S 2. Importantly, the median of Pa is equal to the location (i.c. 9) for all values of a. Recall that for a S 1 the mean of Pa not defined, and otherwise equal to the median.
We run the SPP method (9) for D E f/1l 12 122 11 11,, Hph. with a fixed step size = 0.01 and track the relative f2-error where set μ 1.345 according to Huber (1981). For each method and distribution, we run 1000 iterations and 50 different seeds.
Im, Alla Glle The corresponding methods are called momentum, VC1ip, CClip, and Huber,
Discussion. From Fig. 3 we find that as the noise becomes more heavy-tailed (as a decreases), momentum fails to produce accurate estimates of 9. On the other hand, both Vclip and CClip are robust to heavy tails, as expected, we showed that VClip and CClip are estimating the median. Notably CClip becomes more accurate (relatively) as decreases. The Huber function produces results very similar to VClip, but slightly inferior. We refer to Fig. 8 for additional ablations on the choice of and skewed noise.
Language modelling. We also run momentum, VClip and CClip in order to estimate the full gradient for the language modeling tasks, where the weights are fized at initialization. The setup identical to the one described by Kunstner et al. (2023), in particular Figure 1 therein. We present the results in Appendix C.1.
6.2 Training with Online Gradient Estimation
We now present comparisons of varions (online) gradient estimators when simultanconsly training the weights, that is the distribution of gradients changes in each iteration.
Least squares with heavy-tailed noise. We consider the noise-perturbed least-squares problem min 3 w| and use gradient oracle given by g w + Rd, where & is the noise term. We consider three setups:
(S1) The components of & are i..d. distributed according to a standard a-stable distribution with location zero and 1.1. Note that Eeu [$] 0.
11

---

Published in Transactions on Machine Learning Research (10/2025)
momentum
vclip
10
Iz-error
0.5
1.50.55
0.5
0.4
1.2
Final relative f2-error
10
0.2
0.1
10-1
1000
0
1000
cclip
huber 1.345)
0.5
Relative 1z-error
0.4
1/-11.5
Ve-1.
10-2
momentum
0.3
velip
cclip
huber
3
0.1
0.50
0.75
1.00
1.25
1.50
1000
1000
1/a
Iteration
Ieeraiio
Figure 3: 7 = 0.01 Left: Final error for varying values of (from left to right, distributions are more heavy- (ailed). Shaded area marks minimal and maximal value over the 50 independent runs. Right: Convergence plot for all methods for 1 e [0.5, (higher value of 1 corresponds heavier tails). a
a
sample-mes mean
huber clipped-sgd
velip
11 mediaalemeddan
cclip
12 sample-median median
105
104
104
10a
103
Objective
102
Objective
Objective
10"
10
10
10-2
10-2
10
4
10
1000
2000
0
1000
2000
1000
2000
Iteration
Iteration
Iteration
(a) Setting (S1)
(b) Setting (S2)
Setting (S3)
Figure 4: Least squares with heavy-tailed noise that independent components (left), slate-dependent (middle), and where components of noise dependent (right). All methods in gray 5 samples per iteration, all others only one. Note that for (S2), the sample mean immediately diverges, and hence does not appear in the plot. Shaded area depicts minimum and maximum value over 50 repetitions.
(S2) Same as (S1), but the noise state-dependent, given by & where o / w.
(S3) & follows an elliptically contoured a-stable distribution (Nolan, 2013) with location zero and a = 1.1. In particular, the components of & are not independent.
We run seven different methods: the one hand, the method depicted in Section 5, (16), where in each iteration we draw median well the sample mean for my The Ez-median is approximately computed using the method proposed in Vardi & Zhang (2000).
5 samples. We run three variations of (16), namely using the e1- and la-sample
On the other hand, we run our online modian estimator methods (13), with D E {ll- 11,, I1 H,). that is, VClip, cclip, and Huber. Importantly, these methods only receive one sample per iteration, and they do not involve any median computations (in contrast to 4 and la-sample median). We also run clipped-SGD
12

---

0.9 for Published in Transactions on Machine Learning Research (10/2025)
sgd
clipped-sgd
adam
velip sgd
cellp-sge sglp--sd
10
Train Loss
6
4
4-
2
0
0
100
200
20
40
0
2
4
Epoch
Epoch
Epoch
(a) PTB
(b) WikiText-2
(c) SQUAD
Figure 5: Training loss for each method, with tuned learning rate. Shaded area depicts minimum and maximum value over 5 seeds.
(cf. (14)) with 3 = 0.9 and = 50.4 We run all methods with a learning rate d = 0.01. For VClip, CClip, and Huber we set r = 1, and we set again = 1.345 for Huber. We always run 50 repetitions and report averaged metrics.
Discussion. Fig. shows that both 4 and fz-sample median attain the smallest objective, while the sample mcan does not converge predicted by our theory (sce discussion after Proposition 5.3). From the online methods, CClip performs best in the scenario where the noise is componentwise independent, while VClip and Huber are better in the other case. Overall, Huber and VClip behave again very similarly (a more detailed analysis Huber with different values of μr can be found in Fig. 9). We find that both VClip and CClip reach much smaller loss values than clipping the stochastic gradient directly, and thus clipping only the increment better suited here. We also find that the f1-sample median can deal with state-dependent noise (S2) as predicted by our theory.
Language modeling. We now consider the online methods (13), that is training while simultaneously estimating the gradient, for the three language modeling tasks. We compare SGD-M, VClip and Cclip, and cLipped-SCD." We also add Adam as bascline, but focus on the comparison among the SCD-type methods. For all methods, we tune the learning rate on a logno-scaled grid (tuned values reported in Table 1), displaying the one that attained smallest final training loss (averaged over 5 seeds).
We choose a standard comeetuum/lipppinnn parameters for all tasks (without tuning): we SGD-M, 0.1 for V/CClip, and 0.9, 1 for clipped-SCD.
Discussion. Fig. shows that VClip improves over SGD-M for PTB and WikiText-2 and is on par for SQUAD. cciip performs always worse, which might be duc to the noise being not componentwisc independent. How- ever, VClip does not close the gap Adam, and also performs worse than clipped-SGD for the WikiText-2 dataset.
7 Conclusion
We provide a new approach for robust gradient estimation using the stochastic proximal point method, with focus on (online) estimators of the median gradient. We observe that this general framework intersects with many existing works robust stochastic optimization, where the connection between clipping and not known previously.
median estimation
4This choice is tradeoff between convergence (large e) and high instability (small e).
We also tried Ruber (with / = 1.3) these problems, but did observe advantage over VCLip (plots shown).
13

---

Published in Transactions on Machine Learning Research (10/2025)
sgd
clipped -gd
adam
velip-sgd
cellp-sgd
10
80
10a
Valid PPL
Valid PPL
60
103
Valid
10a
10
102
102
20
200
40
0
Epoch
Epoch
Epoch
(a) PTB
(b) WikiText-2
(c) SQUAD
Figure 6: Validation score (measured as perplexity, or F1 score) for each method, with tuned learning rate.
Shaded area depicts minimum and maximum value over 5 seeds.
We provide an analysis of SGD using the median sampled gradients (called SMGD), and show convergence guarantces under potentially heavy-tailed and stato-dependent noise. In contrast, under the same assump- tion, SGD with the sample mean does not converge.
Finally, numerical experiments show that ouline versions of SMGD, even though not covered by this theory, perform equally well on problems with heavy-tailed noise, while methods based on mean estimation fail. However, when training transformer models on langnage tasks, this gap is far less pronounced; this could indicate that the level of heavy-tailedness these applications moderate.
Acknowledgments
We thank the Scientific Computing Core at the Flatiron Institute, a division of the Simons Foundation, for the compute facilitics and support. U.S. and F.S. are partially supported by the French government under the management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANTR-1--3IA-0001 (PRAIRIE 3TA Institute), and the European Research Council Starting Grant DYNASTY 101039676. G.G. gratefully acknowledges the Flatiron Institute for their hospitality and financial support during the visit when this work was written.
14

---

Published in Transactions on Machine Learning Research (10/2025)
References
Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S. Dhillon, and Ufuk Topeu. Robust training in high dimensions via block coordinate geometric median descent. In International Conference on Artificial Intelligence and Statistics, volume 151, pp. 11145-11168, 2022.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 31, 2018.
Hilal Asi and John C. Duchi. Stochastic (approximate) proximal point methods: convergence, optimality, and adaptivity. SIAM J. Oplim., 29(3):2257 2290, 2019.
Heinz H. Bauschke and Patrick L. Combettes. Conver Analysis and Monotone Operator Theory in Hilbert
Spaces. Springer, 2017.
Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applicd Mathematics, Philadel- phia, PA, 2017.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. Tn International Conference on Machine Learning, volume 80, pp. 560 569, 2018.
Peter Bickel. Some contributions to the theory of order statistics. In Proc. Fifth Berkeley Sympos. Math. Slatist. and Probabilily, Vol. I: Stalistics, pp. 575 591. Univ. California Press, Berkeley, CA, 1967.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMP- 2TAT pp. 177-186,
Heidelberg, 2010.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Rev., 60(2):223 311, 2018.
J. Burke and M. Ferris. Weak Sharp Minima in Mathematical Programming, SIAM J. Control Optim., 31 (5):1340-1333) 1359, 1993.
Olivier Catoni and Maria Giulini. Dimension-free PAC-bayesian bounds for the estimation of the mean of a random vector. arXiv:1802.04306 February 2018.
John T. Chu and Harold Hotelling. The moments the sample median. The Annals of Mathematical Statisties, 26(4):593 606, 1955.
Michael B. Cohen, Yin Tat. Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In ACM Symposium Theory of Computing, pp. 9 21, New York, NY, USA, 2016.
O. Cornejo, A. Jourani, and C. Zálinesou. Conditioning and Upper-Tipschitz Inverse Subdifferentials in Nonsmooth Optimization Problems. J. Optimiz. Theory App., 95(1):127 148, 1997.
Harald Cramér. Mathematical Methods of Statistics (PMS-9), Volume 9. Princeton University Press, 2016.
Deepesh Data, Linqi Song, and Suhas Diggavi. Data encoding for byzantine-resilient distributed gradient descent. In Annual Allerton Conference on Communication, Control, and Compuling, pp. 863 870, 2018.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based mininization of weakly convex functions. SIAM J. Optim., 2027)227223. 2019.
Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtarik. A guide through the zoo of biased SGD. Advances in Neural Information Processing Systems, volume 36, pp. 23158 23171, 2023.
David Donoho and Peter J. Huber. The notion of breakdown point. In A Festschrift for Erich Lehmann, Wadsworth Statist./Proball Ser., pp. 187-184. Wadsworth, Belmont, CA, 1983.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Michael C. Ferris. Finite termination of the proximal point algorithm. Math. Program., 50(1-3):359- -66 1991.
Maurice R. Fréchet. Les éléments aléatoires de nature quelconque dans un espace distancié. 1948.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems, volume 33, pp. 15042-15053, 2020.
Robert M. Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduceed methods for machine learning, Proc. IEEE, 108(11):1968 1983, 2020.
Mert Gurbuzbalaban, Umut Simsckli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD, In Interna- lional Conference on Machine Learning, volume 139, pp. 3964 3975, 2021.
Frank R. Hampel, Elvezio M. Ronchelti, Peter J. Rousseeuw, and Werner A. Stahel. Robust Stalislics: The Approach Based on Inftuence Functions. Wiley, March 2005.
Liam Hodgkinssn and Michael Mahoney. Multiplicative noise and heavy tails in stochastic optimization. International Conference on Machine Learning, pp. 4262-4274, 2021.
Peter J. Huber. Robust statistics. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1981.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference Machine Learning, volume 97, pp. 3252-3261, 2019.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimiza- tion. In International Conference on Machine Learning, volume 139, pp. 5311-5319, 2021.
Sarit. Khirirat, Eduard Gorbunov, Samuel Horváth, Rustem Islamov, Fakhri Karray, and Peter Richtárik. Clip21: Error feedback for gradient clipping. MxXiv:2305.18929 2023.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and light convergence guarantees. In International Conference on Machine Learning, volume 202, pp. 17343 11743, 2023.
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between SGD and Adam transformers, but sign descent. might be. In International Conference Learning Representations, 2023.
Kruno Lehman, Alain Durmus, and Umut Simsekli. Approximate heavy tails in offline (multi-pass) stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 36, pp. 1451, 2023.
Bernard Lemaire. About the Convergence of the Proximal Method. In Advances in Optimization, number 382 in Lecture Notes in Economics and Mathematical Systems, pp. 39-51. Springer Berlin Heidelberg, 1992.
Bernard Lemaire. Well-posedness, conditioning and regularization of minimization, inclusion and fixed-point problems. Pliska Studia Mathematica Bulgarica, 12(1):71p 84p, 1998.
Adrian S. Lewis and Jong-Shi Pang. Error bounds for convex inequality systems. Generalized converity, generalized monotonicity: recent results, pp. 75-110, 1998.
Hendrik P. Lopuhaa and Peter J. Rousscouw. Breakdown points of affine equivariant estimators of multi- variate location and covariance matrices. Ann. Statist., 19(1):229-22) 2422 1991.
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Lond. Math. S., 19(5):1145-11990 2019.
16

---

Published in Transactions on Machine Learning Research (10/2025)
JS Maritz and RG Jarrett. A note estimating the variance of the sample median. J. Amer. Statistical Assoc., 73(361):194-196, 1978.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The Hidden Vulnerability of Distributed Learning in Byzantium. In International Conference on Machine Learning, pp. 3518-3527, 2018.
Andre Milzarek, Fabian Schaipp, and Michael Ulbrich. A semismooth Newton stochastic proximal point algorithm with variance reduction. SIAM J. Optim., 34(1):1157 1185, 2024.
Stanislay Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, 21(4), 2015.
A. S. Nemirovsky and D. B. and Yudin. Problem complerity and method efficiency in optimization. John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by F. R. Dawson, Wiley-lnterscience Series in Discrete Mathematics.
John P. Nolan. Multivariate elliptically contoured stable distributions: theory and estimation. Stat. Comput. Ser., 28(5):2067 2089, 2013.
John P. Nolan. Univariate Stable Distributions. Springer International Publishing, 2020.
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Nikita Puchkin, Eduard Gorbunov, Nikolay Kutuzov, and Alexander Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. #rXiv:2311.04166 2023.
Peter Richtarik, Tgor Sokolov, and Tyas Fatkhullin. E121: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, volume 34, pp. 4384 4396, 2021.
M. Riedmiller and H. Braun. A direct adaptive method for faster backpropagation lcarning: the rprop algorithm. In IEEE International Conference on Neural Networks, pp. vol.1, 1993.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Sammel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochastic opti- mization and variational inequalities: the case unbounded variance. arXivv2302.00999, 2023.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: Journal of the IMA, 112)):557-580 04 2021.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application to data-parallel distributed training of speech duns. In Interspeech, 2014.
Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In Advances in Newrul Information Processing Systems, volume 33, pp.
2020.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International Conference on Machine Learning, volume 28, pp. 1139-1147, 2013.
Panos Toulis, Thibaut Horel, and Edoardo M. Airoldi. The proximal robbins- monro method. Journal of the Royal Statistical Society Series B: Statistical Methodology, 63(1):188 212, 2020.
Yehuda Vardi and Cun-Hui Zhang. The multivariate Li-median and associated data depth. Proc. Natl. Acad. Sci., 9443):143311426 2000.
Hongjian Wang, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Simsekli, and Murat A Erdogdu. Conver- gence rates of stochastic gradient descent under infinite noise variance. Advances in Neural Information Processing Systems, 18:18866-188777 2021.
17

---

Published in Transactions on Machine Learning Research (10/2025)
Endre Weiszfeld and Frank Plastria. On the point for which the sum of the distances to given points is minimum. Ann. Oper. Res., 167 2009.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, volume 80, pp. 5650-5659, 2018.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: thcoretical justification for adaptivity. In International Conference on Learning Representations, 2020a.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaplive methods good for attention models? In Advances in Neurol Information Processing Systems, volume 33, pp. 15383 15393, 2020b.
18

---

Published in Transactions on Machine Learning Research (10/2025)
Contents
1 Introduction
1
2 Preliminaries
3
2.1 Hcavy-tailed Random Variables
3
2.2 Mean Estimation and (Sample) Median
3 Robust Gradient Estimation with Stochastic Proximal Point
5
3.1 Warmup: Momentum as Online Mean Gradient Estimation
5
3.2 Clipping as Online Median Gradient Estimation
Gradient Estimator in the Wild
7
Theory for the Sample Median Gradient Method
8
Experiments
11
6.1 Gradient Estimation with Fixed Weights
11
6.2 Training with Online Gradient Estimation
11
7 Conclusion
13
A Missing Proofs for Section
20
A.1 On the Assumptions on the Sample Median
A.2 Rates for SMGD for Smooth Nonconvex Functions: Proof of Proposition 5.3
22
A.3 Rates for Biased SCD for Convex Lipschitz Functions
23
A.4 Rates for SMGD for Convex Lipschitz Functions: Proof of Proposition 5.4 ................................
26
A.5 Rates for SMGD with Stable Noise: Proof of Corollary 5.6
27
B Approximate Computation of Gradient Estimators
27
B.1 Gradient Estimation Problem: General Considerations
27
B.2 Approximations Based on the Stochastic Proximal Point: General
28
B.3 Approximations Based on the Stochastic Proximal Point: Particular Cases of D
29
B.4 Approximations Based on Subgradient Updates
31
B.5 Rates for SPP
31
C Supplementary Information Experiments
33
19

---

Published in Transactions on Machine Learning Research (10/2025)
C.1 Additional Plots
33
C.2 Learning Rate Values for Transformer Training
35
Appendix
A Missing Proofs for Section 5
A.1 On the Assumptions the Sample Median
We first state simple fact about Lipschitz functions:
Lemma A.1. If Assumption 5.1 holds, and if l Lipschitz continuous, then without loss of generality can assume that 82 = 02 = 0.
Proof. If l is G-Lipschitz, then for every subgradient al(w) we have ||| G, so one can replace of with 8f + 82G2 and of with of ozG².
In the following proof of Proposition 5.3 we will need an equivalent but more compact formulation of Assumption 5.1.
Lemma A.2. Let m be a random variable in Rd and consider the following property:
[llm ve(w))1 S rテ 1/2 v2[w)(
(19)
If (17) holds then (19) holds with 1 = of + of and = & + TI (19) holds, then (17) holds with
81 = and 82 02
Proof. Expanding the squares, we get
E [[]m V E [[|m E [m] [13] + || [m]] - v((w))?
where we used that E [(m E [m] E [m] v((w))]] = 0. Now, the first implication is trivial, and the second follows from the positivity of the involved terms.
We now verify that Assumption 5.1 holds true for the -ssample median, provided that the noise the subgradient is linearly depending on an a-stable distribution, and that the linear coefficients grow with the norm of the subgradient.
Lemma A.3. Let n E N odd and n 2 Suppose that the subgradient oracles g() verify Assumption 3.5, for all 1....,7 and set
m mediam (w))
Then, Assumption 5.1 holds with 6, = 82 0, and of = CnCI, 02 = Cn,2, for some constant C, ((/nn)
Proof. Let us denote the noise vector by g(() (0 By the stability property of a-stable distributions (Nolan, 2020, Proposition 1.3), we have that
5 = c (w)) =
E( (w)) _a |E(w)xlaa?,
(20)
j=1
20

---

Published in Transactions on Machine Learning Research (10/2025)
where = denotes equality in distribution, is standard symmetric a-stable random variable in I, and [(w); denotes the k-th row of Ewv). Observe that from Assumption 5.5 we can write that
d
((w); <
S PM
E (ww)ilé - <d + <llVe(w))) for all w E R
(21)
by setting 0j = pa and C2 Pa c2 and where Pa > 0 is the best constant such that || lla S Pall ll,, which 2-a is Pa 2a
is for S 2, and Pa otherwisc.
We start by computing the bias term that is required by Assumption 5.1.
ml V((w) 112 E median (Ve(w) (u))) Ve(w=)1
E median (z)) 1|
where we used the fact that
mediang, (Vé(w) + (w)) = V((w) + median,,.ehhi (50)
On the other hand, the m-median boils down computing component-wist modians, hence we have that
E median
(3)
(w))
E median (el(
median
(8)
where median (e) argmin Ei Im (0) is the one dimensional sample median estimator.
Now, let us compute E mediangein) using the probability density function of the sample median (ef. Maritz Jarrett (1978)), we have that:
ck for some k E {l....,,)) d). Denoting r = (n 1)/2 and by
(4x [s[))==
n! r!r! x (F (w)(( (z)dd,
E
median
where F and & (x)) are respectively the cumulative distribution function (cdf) and the probability density function (pdf) of (()) ~ Pa. (l that is a symmetric a-stable random variable with scale [ (w) As & is continuous and symmetric around zero, we have (w, = Pw, (-x)(= and (1 Fu.. (x)) ( for all x E R. This gives us:
(F. P (2)dx [ (F., p (r)dd
A
(F), Pw, (x)dr ( (F), (-)=)) Pw,k (x)
=0.
Hence, we obtain that
median sejj (z0) = 0.
This shows that the first line of Assumption 5.1 holds with &n 62 0.
21

---

Published in Transactions on Machine Learning Research (10/2025)
We now proceed to the estimation of the variance. By using similar arguments, we have that:
E Il
E m
||]
E
[|meiann,
(s<)
E
medianne(m)
(44')
Pan,s (46 (1- Fun ( ))}
m!!
(ck)
(22)
r!y!
where (22) follows from Maritz Jarrett (1978, Equation 2.1). By using (20) with (21) and denoting the odf of the standard symmetric o-stable distribution by Fz, we further compute that:
n! r!r!
E [|
E m
11
2 (=(:)(1- -1()))) F2(+))
Σ Σx (w))
]
n! r!r!
<
E
=?
(2(:)(1- 1 -2(+t)
+ (4+<VVV((w))
=: Cn (ci + v
This shows that the second line of Assumption 5.1 holds with of = C.Paa and 62 = C2
Finally we observe that, again by Maritz Jarrett (1978, Equation 2.1); Cn is the variance of the sample median of set of iid. standard symmetric o-stable variables (z1...., En): where 2; = 2, As n - so, it is well-known that the sample median is asymptotically normal with variance 2/4nf((0)) where denotes the pdf of (see Maritz & Jarrett (1978)). Hence conclude that C, (1/n) the proof.
co. This concludes
A.2 Rates for SMGD for Smooth Nonconvex Functions: Proof of Proposition 5.3
The following proposition is an application of biased SGD results to the SMGD algorithm with errors. It is possible to show that Assumptions 5.1 and 5.2 both imply Assumption 9 from Demidovich et al. (2023). So from a qualitative point of view the result below the same that what we would obtain by using Theorem from Demidovich et al. (2023). But doing so would produce a bound with worse constants, so we prefer to provide a proof exploiting directly our assumptions.
1 Take n S Proposition 5.3. Let f d + IR be L-smooth and let Assumption 5.1 hold with 82 < 8.
SL(1+20:+36J] and consider w, a sequence generated by (16) where e, verifies Assumption 5.2. Then, for every T 2 1 it holds
[[( = o ( + + + 57 + o
min 0S
Proof. In this proof we note E, for the expectation taken conditionally to the filtration generated by ......
w. w. In particular, will have from Assumption 5.2 the errors together with the tower rule
that E, 2 = E,E |lea|l2 ....,,! (n) E2
Smoothness of & implies
L | w ((w(+1) - ((w:) - (Ve(wi) W441 wi) S
2
If we note d; := m. + Es, thus w1+1 Wi = -nd. This implies
Ln < 2
((w+41) - {(wi) + ()Ve)())
||
22

---

Published in Transactions on Machine Learning Research (10/2025)
Let bound the two terms depending d.. First, take expectation conditioned to Fo (which we will denote E,) to write
E, (Ve((i)) d+) (Ve(w;), Eg [d)) [[V((w)))]
)1 + + [d, 112
1 JI [d.] [l(ww))|1
2 V((w;;)] _ E [d+] - v
Using (17) and | [eæ] 2|? - E, ||| e
Σ 2² due to Jensen's incquality, we can bound
2 [d.- - v m+ ) - v R [m:] v((w))]l + R [ex] |1 < 26 + 28 [V((m)))1 20
Second, we use Young's inequality and our assumptions to bound ||d]]?:
E2 de
<
2 [lle: + m, - V((w;)) + 2| V[(w:))
4E, [|], + 4E, [1 m, - Ve(w;) || + 2 V((w,))
45 + 4(0 of) + (2 + 452 + 40 (o)
where in the last inequality we used that (17) implies (19) (ef. Lemma A.2). Combine all the above inequalities to get
E2 [((we+1)] - {(w)) + v((mm)) (20 + 26 Ve(w:))] + +
$ Tnp (4(5² + 5 + ff) = (2 + 482 + 40 402) v((w:))1)
2
Rearranging yields
E, [[(w++1)] - f(ws)
+ S <-n| 1 82 Ln(1 + 20. + 2522 V[(w):)) + n(f + + + ( +
If 82 S }/8 and using 17 S SL(1+202+26a) after taking full expectation, we obtain
B [l((wr+1) )] 1 [[(w))] < [[V + n7(o² - of oot).
Sum over 1 == 0,... - 1, multiply by * and use finally obtain
min t....
E [[V S + - [ [[] to
min [[((w))1? S 4(E(w)) inf
nT + SLn(e2 + + + + +46 + +
A.3 Rates for Biased SGD for Convex Lipschitz Functions
In this scction we prove another result about the complexity of biased SGD, that is SGD with biased estimators of the subgradient. As far as we know, biased SGD was only studied in the case of strongly convex functions or smooth nonconvex functions (Demidovich et al., 2023), or in the particular case random projections. In that regard, the next result new contribution to the analysis of biased SGD.
Before stating our result, recall few standard definitions given that we are working with nonsmooth convex function. Given convex function f: Rd - R, say that u is subgradient of E al w if
(Vw' E Rd) E(w') ((w) (u, w' - 2.
We note df(w) the set of all subgradients of l at w, that is called the subdifferential of at w.
23

---

Published in Transactions on Machine Learning Research (10/2025)
Theorem A.4. Let 8 Rd + I be convex G-Lipschitz function such that argmin of 0. Let vj 0, and note D = Ww w.ll for some w, E argmin &. Consider the iterates generated by biased Stochastic Subgradient Descent method
Wi+1 ww 79tt.
and assume that the estimator 9t has a uniformly finite bias and variance (we denote by Fr the filtration induced by Wo...., Wy):
E [g uell S 8,
E 19: - Ig Fil 11 $ o²,
where un is any subgradient of l at wt- Then, for every
2 1
2D 2 +
+ G)2
8ºT
E [(((T)) - inf
+
+1 4
n/
2
where ur is average of the first T iterates defined by WT if we take constant step size equal to
Σt 0 0 T+2
T
In particular,
Σ.
2v2D
(resp. 17
22 + (6 2)2)T S2T2
8T + VT
then we can guarantoe that
02 + (6
G)2
82 + 2
2D
0² + 6² + G2
E [((WT)) inf e < 2DV
(resp.
+ (2D2 + 1)6
T
VT
Proof. Let w. argmin E and T 2 1 be fixed. Develop the squares and use the definition of the algorithm
to write
|10+11 - w..11 ||w, - w.112 2(we++ - Wt: Wt - w.) + || - wv|l
||w, w. 2| 27/gr: wt - w.) + 1/
Let Dr be the projection of E [gt]Fii] onto ol(w:), the subdifferential of l at wi, which is nonemply closed convex set. This means that from our assumption on the bias of g, we will have
E [g Fi] gell < |E [g uell S
Then, after taking conditional expectation (denoted by E, [-] instead of E [-]FF)) we can write
E, [1 w.1l3] l/w, w.112 - 2n, [gt]. w. -w.) + 1) R,, [||g<]] []]
Iwu, w.|l2 21/(gt, wi -w.) + 2n/ E. [gr] w. -w.) + 17 1T [l|g]] ||
s ww w. 112 2ny(E(ure) - inf E) + 27 E, [gi] ur -w.) + 17 2 [llg] 112]
where in the last inequality used the convexity of l together with the fact that g: E a.(w:)) The last term can be bounded by using our assumptions on the estimator 9t, and the fact that has bounded subgradients:
E2 [19.11 [2] = E, [llg. E, Igd [12] + E, [9. 12 0²
E, [gdl gell + ll < 0² + (8+
Injecting this in the previous incquality we obtain
E, -
1 < l|,,- w,1 -2n(((w.)) inf f) + 2n E, [g:] w. w. -w.) w 17 (7
Now we introduce a parameter > 0, and we use Young's inequality together with our assumption on the bias of g: to write
2(g. E, [g.] w; w.) < 9g E, 1gd 21 + El|wo - = + + - w. w.11
24

---

Published in Transactions on Machine Learning Research (10/2025)
Inject this bound in our main inequality
E [| w. 17] - (1 + ne)llw, - w.ll 2n((((x) - inf () + n/o²² + (6 + G)² + n
and after reorganizing the terms, dividing by 2n and taking expectation we finally obtain
1 + B E [[/w, w.1l"] -
-w------ll 1 E [[ - w.ll + o² + (6+ 20
82
[[((w,)) inf $ -
+
21)
2
2
We are now ready to use a weighted telescopic sum argument. First, define := Itoe and Pt := 0r. Second, multiply our incquality by pt+1 and then sum for t = .,..., T-1. Observe that the term (1+mE) p is cqual to A due to our definition, which means that we have a telescoping sum where the terms & E lw w. ||
1
24
will cancel each other. Third, divide by Eino P++1 so to obtain
Σ PetiE [((ws) inf in
Po
o² +2+0 E 20 w. +
+66 G)2
-
82
Etso Pe+1 tm0
2n
T-1
P++1
2
2
Now define Wr
Eimo Ex= P++1i E1 gr
2 O'w,, and use Jensen's inequality to get -
11100 w.
0² +
(6 G)2 +
82 2
E [((WT)) inf ( S
+1
2n E P++1
2
We will now simplify this upper bound, so we can later make an appropriate choice of leading to the desired complexity bound. We will now focus on the geometric sum appearing in the denominator, and lower bound it. Start by using the definition of Pe to write
T-1
Σ PH+1 = no
Σ
0
1
)²)
1
1=
t=
On the one hand, we see that from the definition of we have
0 17 1
17 n
=
1 1 1 1t nE 1 I-me
On the other hand, we can guarantce that (1 - 8T) 2 1/2 provided that 2 To see this, first observe
that (1- 2 1/2 is equivalent to T' 2 TJ Since we impose that ne then necessarily 7+2 which means that 0-1 = 1 1 4. So what we need to verify is T 2
ln(2)
In(2) m] Now, observe that In(2) S 1.
Moreover, it is an exercise (see Lemma A.5 which is deferred to the end of this proof) to verify that for all 2 0, In(=+1) S + 1. So for our condition to hold it is enough to ask that T 2 2/2 + 1 which is equivalent to T 2 I, which is true.
Combining all those bounds together with our new definition for e, we now have
E ((((T)) inf e) 2||wo
w. 1|2
x² + (6+G)
G)²
TOT
+ 17
2 +
n/T
4
To simplify the last stage of our analysis, let us note a = =2| - w. 11, b = o² + our bound writes as
and c= 1 so that
E [((wr) - inf 4 S n
+ np + T.
(23)
Minimizing the right- hand side with respect to rj is equivalent to solve a = n/ + cn/,, where
T/r
a
nb + C + n²
a
bT + eI n=
2 Ww w.l2
r/T
T(b cT)
2(0² + (6 G) + 8812
25

---

Published in Transactions on Machine Learning Research (10/2025)
With such choice of stepsize, our bound becomes
2a T/
2a
cT
b T
+ - 21/w0 w-lly 0² + (8 + G)2
8² 2
E [((()))) - inf 5
T
T
and this gives us our first bound. For the second bound, let us take simply n 8T+VT and inject it into (23) to obtain
aδT +
avyT
b
eT
E (((()))
inf
+
+
T
8T
+
TT
8T + VT
a
b
c
+ b
$ 0d +
+
+ aδ +
VT
VT
8
VT
2D
d²
8
G
+ (2D2
+ 118,
VT
where the last inequality we simplified some numerical constants.
Lemma A.5. For every z 2 0, In(1+>) S 2 1 x.
1
Proof. This inequality is equivalent to In(1+z)> 2 2m
2+3 or again (x+22 Im(1+x) 2 2r. Define Φ (-1, +00) 4
R as ((x) = (x + 2) In(1 + z) and compute its derivatives:
e' (z) 1n(1 +
1 and ("(x)
(1 + x²)²
We that d²(x) 2 for all 2 0, so is convex on [0, +00). So
the tangent inequality:
<(x) > (0) (0) 0) 0 2x 2x.
(24)
Therefore <(x) 2 2x for all x 2 0, which is what we wanted prove.
A.4 Rates for SMGD for Convex Lipschitz Functions: Proof of Proposition 5.4
Proposition 5.4. Let E Rd + R be convex and G-Lipschitz, with argmin l + 0. Let Assumptions 5.1 and 5.2 hold. Without loss of generality assume that 82 = 02 = Then, for n (dite)T+VT and every T 1, the itcrates w, from (16) satisfy
1 E [((wT) inf in (0) + 81 +e)
where wT = Ei- Ow. with T42
Proof. In this proof, we note F3 the filtration generated by wo. wi, and we will note E, to refer to the expectation conditioned on Ft.
We want to apply Theorem A.4. Let denote g: m. e., so that the iterates of SMGD verify W:+1 wi ng: We are now going to show that Jt has uniformly bounded bias and variance. For this we will make use of Assumptions 5.1 and 5.2. Remember that we assurned 82 = 02 = 0 without loss of generality (we can do this according to Lemma A.1), so we note d and o instead of 6, and 01. Also, Assumption 5.2 on the
errors together with the tower rule imply that E, [[le:]|]] = E, [ ||e. (1) " .....gt"" (n) S e2. Regarding the bias, can write
E [g: ve(w:))
[R [m. v((w))) |R [e:] || S +
26

---

Published in Transactions on Machine Learning Research (10/2025)
where in the last inequality we used Jensen's inequality to write | [e:] || S VE, e As for the variance, write
E. [1l. E S 2E, m. E, [m.] [|a] + 2E, [lle, Er [ex] [1]] s 20 SE, [|, [P]] - 20 + 8
Using Theorem A.4, we obtain
2 20/ w. 1
20 + 85 +
(6 + G)2
n n(0++)
E [((w))) inf E
+1
r/T
2
4
Setting the step size 17 = (6+e)2++ VT we conclude that
2D + 20 8E² + (6 (
G2
E [((wr)) inf 8
+2D2 +E).
VT
A.5 Rates for SMGD with Stable Noise: Proof Corollary 5.6
Corollary 5.6. Let n 2 be odd and p = 1. Consider the iterates from (16) with e 0, and suppose that V((w;) + (() verifies Assumption 5.5.
(i) If L-smooth and O (+))) then we have that minogesT-1 (IV = O(1/VT)
(ii) If is convex and Lipschitz and 17 1/vT then we have that E [((WT) inf E] O(L/VT), where ur is defined as in Proposition 5.4.
Proof. First of all, remember that the l-median can be computed exactly, by computing component-wise a one-dimensional median. This allows us have E Assumption 5.2. Further, due to Lemma A.3 we have ó1 0 in Assumption 5.1.
Proof of part (i). Choose 81(1+202+26)VVT where 82, 02 are from Lemma A.3. Hence, we can apply Proposition 5.3. As 17 S with C +2(14202+25. get the bound CVT VT O(1/VT).
C
Proof of part (ii). The result direct consequence of Lemma A.3 and Proposition 5.4. This completes the proof.
B Approximate Computation of Gradient Estimators
B.1 Gradient Estimation Problem: General Considerations
Given a function D Rd - we consider the problem (5); which writes
argmin E [D(m z)]
meRd
In what follows, we will mostly consider functions satisfying the following assumption.
Assumption B.1. The function D Rd - R is convex, argınin D(z) {0) and problem (5) admits solution.
Note that assuming D to be convex and finite implies that it is continuous, therefore measurable, which means that E 1D(m =]] is well defined. The assumption that argmin D(z) = {0} guarantees that in the trivial case when the distribution a Dirac 8may then the solution to (5) is exactly mp- The assumption that solution to (5) exists is casily verified in practice, under the assumption that D is cocreive:
27

---

Published in Transactions on Machine Learning Research (10/2025)
Lemma B.2. Let D IR IR be convex. Assume that [D( -E(=)) +00 If D is coercive, i.e.
lim D(m) +oc, then (5) admits solution.
Proof. Let ((m) := E [D(m- ([mm=)] 2)]. Since we assume that ((B[=]) E - E[ < +oo then ø is proper. Since is convex then ó is convex, as an expectation convex functions. Moreover D is convex and finite, which means that is continuous on Rd, see e.g- Corollary 8.39 Bauschke Combettes (2017). Therefore Φ is an expectation of lower semicontinuous functions, which implies that Φ is lower semicontinuous.
Since D is coercive, convex and continuous, we know that there exists E (0, +xx) and b R (see Proposition 14.16 in Bauschke & Combettes (2017)) such that D(-) 2 all ||++1 b. Therefore
((m)
E (D(m m =)] 2 aE m =|| +
a m E [ oI =|| - E [z] |I] +
a m E [>] - aE [D(= [x]]] ||
t00,
where the incqualitics we used the fact that || || is 1-Lipschitz, and that aE [| - [[]] || aE [D( - E [x])] < too. So is coercive on top of being proper convex and lower semicontinuous. We can then conclude that ø has a minimizer, with for instance Proposition 11.15 from Bauschke & Com- bettes (2017).
S
B.2 Approximations Based on the Stochastic Proximal Point: General
Given proper, closed convex function ó R IR U {+00} and 0, we recall the definition of the proximal operator
prox, (mo) argmin ((m) + 2T m moll
meRd
Applying the SPP algorithm to (8) gives the following ilerations
Sample gr i..d. from g
m argmin D(m 9:) + 2F 4/1 mmel3 meR
(25)
As we see next, those iterations can be reformulated to simply involve the proximal operator of D:
Proposition B.3. Let DD verify Assumption B.1. The SPP update (25) for solving (9) can be equivalently writlen as
m = 9: + prox (m, (m - g:)
(26)
= p- m (gt).
(27)
where (*(m) == supy ( (y. D(y)) is the Fenchel conjugate of D, and ge is sampled i..d. from at each iteration.
Proof. Here we make use of proximal calculus rules, which can found in most textbooks on convex analysis, for
example Chapter in Beck (2017). Starting from (25), and applying the variable transformation y y y gt.
we have
M = argmin D(y - g:)) + 27 ll - m&|l
yER4
gi + argmin D + (m, g
g: + prox (m: g:).
28

---

Published in Transactions on Machine Learning Research (10/2025)
This proves (26). As for (27), combine (rD)* +D*(//) (Beck, 2017, Thm. 4.14) and the Morean decompasition theorem (Beck, 2017, Thm. 6.44), to obtain
prox,p(m) = m prox, D=)
Plugging into (26) we have
M+++1 9t + DroX,D(11 9:)
9t + m, - 9t - -prxx, D=)) - g:)
m. D) - gr)
(28)
Finally, using that for any function J it holds argmin f(y) m + argmin [Ø + m) in (28) gives
m = m.
mi + prox prox-D' (itmm) y (-gr)
--prox ('ttmm (-gt) gt)
-prox T2' (mسس)) (g:)
where in the final equality we used that if f(x) = -g(=)) we have that
(m) -prox,(-
B.3 Approximations Based the Stochastic Proximal Point: Particular Cases of D
We first characterize the SPP update (9) for when D is the norm, and show it simply require to project the sampled gradient onto certain ball of radius T centered at m..
Proposition B.4. Let = || ll, be the fo-norm for [1, o.]. Let q E [1, oc] such that 1, and let (m,,T) = { ||m yllg ST.. The SPP update (9) is given by
m m, + Proje, (0.7) (gt m.)
(29)
(m) (gt). (g:).
(30)
Proof. The proximal operator of the fo-norm given by
prox+ (m) 7 (o)oj,,
see Example 6.47 Bock (2017). Using this in (26) gives
m441 9: prox (m: 9t)
m: 9:
m. PProj (0.1)
m, + TProjs (0.1) gt ml
-m + Proja, (0.r) (g: - m.)) (m).)) (g1) m.
m4 + (mroje,
Projs,(mer)) (g:)
where the third equality we used that
Proje, (r0)),
29

---

Published in Transactions on Machine Learning Research (10/2025)
1a++
Figure 7: One SPP update (30) for D = ||- (blue) or D = 11-112 (green) amounts to project onto a ball of the dual norm, centered at the current itcrate my and radius r > 0. The thick lines represent the projections of ge for all possible values of
followed by
Projs Projs,(m/nr) (m/T..1) (U/T) = -Pojje (ma (m,))(y)
in the fourth equality and in the fifth equality.
Projs, ProjB,(m..)) - m. m
Using Proposition B.4 we develop closed form updates of the SPP method for when D is the 41- the 4-normm with both methods being related to clipping.
Corollary 3.2. For D ||. update (9) is given by
m141 m, + clip,,1 m.),
(11)
where (l) == (min (max(:a - -))
Proof. Follows from (29) and that
min(max(v,- -7,, Proja (0.r) (v).
Corollary 3.1. For D || 122 update (9) is given by
m m; + clip, 2g: -m:),
(10)
where (l)p,,(())= = max r. w
Proof. Follows from (29), by using that
(roje,(o.)) = max T, |
"
We end this section with the closed form updates of the SPP method for when D the Huber function.
Corollary 3.3. For D Has update (9) is given by
m4+1 + 3m, gt) = B.m; + (1 Br)g:,
(12)
30

---

Published in Transactions on Machine Learning Research (10/2025)
where Br ;= max m. g.l. p(++T))
Proof. Follows from (9) and the fact that the proximal operator of the Huber function is given by prox+H, (z) (1 (|
z. For proof, Beck (2017, Example 6.66), and note that here we have the additional factor j in the definition of Hμ.
B.4 Approximations Based on Subgradient Updates
Instead of SPP, we could solve (8) by iteratively taking steps of stochastic subgradient descent. D is convex, then in each iteration we sample a gradient It, and update our current estimate m, by
m4+1 = m. Tue, u, E @ - -9:)-
(31)
Here, > O is the learning rate, and is subgradient (of the convex subdifferential), Since D could be non-differentiable function such as the fz- or (--orm,, we use subgradients instead of gradients.
Squared fo-norm. As first simple example of (31), let D = 11ll 112 In this case (31) becomes
m4+1 - T(m; gi) (1 m) + T9:-
(32)
This again (heavy-ball) momentum (cf. SGD-M), now with coefficient. to SPP, the coefficient 8 could be negative, and is only in [0, 1) (as typically is the case for momentum) if r E 1].
Note that in contrast
4-norm. If we choose D = -11- -11-11,
I1,, update (31) gives
m++1 m. + 7 sgn(g: m.),
where the sgn-operator can take any value in [-1, for coordinates [d] such that (g. m.); 0. This recovers a version of sign-SGD (Riedmiller & Braun, 1993; Bernstein et al., 2018), where the sign-operation is applied to the increment m. gt. For example, if we reset m, 0 in every iteration, we obtain exactly sign-SCD.
6--norm. If we choose D || l12, and if ge * m. update (31) gives
m m,
m. gr
(1 | gell
m. +
9t-
m, gell
m, gt
Otherwise, if g: = m., we can choose any u, with | s and set m,41 = m. - Jug; in particular we can set m4+1 m..
B.5 Rates for SPP
Now that we have presented how to compute the iterates (9) in practice, let us state its convergence properties. Since all these methods are instantiates of the SPP method, we can use standard results such as Davis & Drusvyatskiy (2019, Thm. 4.4).
Proposition B.5. Let D be a norm, let d(m) := Egng [D(m g)}, and let m. E argmin ((m). If m, is meRd
generated by (9) then for my = 7 I m, we have
E [(((m)) ((m.)) = 0 ||mm m.
12 TT + +T)
31

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. Since we assume that D is norm over R then it convex and continuous. Moreover, since all norms are equivalent in R4, we have that ((w) I C// for some constant G > 0. Thus DD is G-Lipschitz function. If now we write Og := D g), it is clear that it is convex and Lipschitz. Therefore, o = Bg [dg] is itself a convex G-Lipschitz function. The claim now follows from Davis & Drusvyatskly (2019, Theorem 4.4).
Here is corollary stating rates on the expected distance between the approximate sample median and the true sample median, when using the f--norm:
Corollary B.6. In the context of Proposition B.5, assume that -1-112 and that g sum of Dirac measures 1/ Ei= fg. Then have further
E || - m.ll = O mo - m. 112
(Imo-- TT + +
Proof. In this proof, we use the notation (z)))=11...dd to specify the indivdual components of a vector R For æ IRd, we define the sign operator as follows: let sgn(#)) (sgn(a;)))==L...d where xy is the j-th coordinate of æ E Rd, and where we define for a scalar t E E the set-valued operator sgn(t) {+1} if 0,
sgn(l) = (-1) i < O, and sgn(() = [-1, if ( = O. Further, given a set A C Rd we define ||||| == inf |||]]
aaA
To obtain the desired bound, and given that we already have the conclusion of Proposition B.5, it is enough for us to show that there exists p > 0 such that
(vm E Rd) a ddiis(mm (m, argmin Φ) S 6(m) - inf Φb
It is standard result from variational analysis that this property is true if and only if the following inequality is satisfied (see Theorem 5.1 in Cornejo et al. (1997) or Proposition 3.1 in Lemaire (1998))
(vm E dom dom@d) [(@((m)]l= J..
Our goal now to prove the above inequality, from which the conclusion will follow. Let us consider m o argmin o and use standard calculus to write
1 n Σ sgn(m (m 9:)
1 sm, (9.)))) j=l.....d j(i))))=i.....
d6(m) (m)
n Σ sgn (m, sgn(m;
(9:1,) j=1....d
Our goal is to show that [00(m)]]- 2 1. which is equivalent to show that || | sgn(m - gi)ll 2 1. Because m & argmin o, we know that & d0(m) so there must exist a coordinate j such that the j-th coordinate of d0(m) does not contain zero, in other words such that 0 & Σi sgu(m, - (g:))). Using the fact that || 112 2 || bloo, we can therefore lower bound Ei= sgn (m -g:)ll Ei= sgn(m, (g,)))
Let us denote 8; sgn(m, (gi);), so that want to prove that /E= 8:|- 2 1. Let now consider few cases.
If = or {-1} for every i, then Ens 8; is a singleton. Furthermore is a sum of relative numbers, so D -== 8; Z. But we also know that 0 & E Si, so we conclude that E 8 Z*, and so that Σ D 8/
If s, = [-1,++ for every then we immediately see that 0 E 8 which is contradiction.
Otherwise, the are combinations of singletons and intervals. Let us note I - (i 8; (-1,++) and 1' = {i :i:30 s; {+1}), which are not empty by assumption. Let us also note k > 1 the cardinality
Tt. sometimes referred (weak) sharp minima (Ferris, 1991; Burke Ferris, 1993), (superlinear)(lnna)) conditioning (Lemaire, 1992; Cornejo al., 1997; Lemaire, 1998), or error bound (Lewis Pang, 1998).
32

---

Published in Transactions on Machine Learning Research (10/2025)
of I, so that Σier 8, [-kk,+ +k]. We also introduce = Eier' 8, E Now can write
n
84
inf 1-1
[t| = inf 4, rEl tE|-k,th]
It t+ = d(s; 1-k, +k]),
where the latter is the distance from the number 8 the interval [-k, +k]. Now remember that 0 & Σi= 86, this distance cannot be zero, which means that |s] >> k. Moreover both and & are rational numbers, this distance must be greater equal to 1. This concludes the proof.
C Supplementary Information on Experiments
This section provides additional information for the experimental setup.
For the language modeling experiments, all details are identical Kunstner et al. (2023), Section A.1. They also provide implementations for all tasks https: http:://gtthbb com com/fKunstner hainer//oiie-gged sadiss--dddd----aaae adam-sign which use. For the training runs for language modeling, use batch size 256 for PTB, 320 for WikiText and 32 for SQuAD.
C.1 Additional Plots
Ablations for Fig. We provide two ablation studies for the experiment on gradient estimation on heavy-tailed synthetic data. First, Fig. (left) shows that for Gaussian noise (a = 2), the performance of momentum can surpass v/Cclip depending on selection of the step size т. However, this does not fix the issue of a quickly degrading performance for momentum, when decreases.
Second, Fig. 8 (right) shows the performance under skewed heavy-tailed noise; for this, we set the skewness parameter of the a-stable distribution to one.
10
10
Final relative error
Final relative f--error
10
10
10-1
10-1
10-2
moment
10
momentum
velp
velip
oclp
cclip
huber
buber
10 3
3
0.50
0.75
1.00
1.25
1.50
0.50
0.75
1.00
1.25
1.50
1/a
1/a
Figure 8: (Left) Same as Fig. but with 0.001. Here, momentum performs best for Gaussian data, but still becomes instable when the noise is more heavy-tailed. (Right) Same Fig. 3 but with skewed noise. Here, the median of the noise is no longer zero, which explains the failure of v/CClip.
33

---

Published in Transactions on Machine Learning Research (10/2025)
-== 0.65
#= 1.3
4=2.6
11=5.2
10a
105
10
10a
Objective
10a
103
103
103
T= t=1 0.1
0.316
1.0
3.16
104
10
101
10
10.0
10-1
10-1
10-1
1000
2000
1000
2000
0
1000
2000
1000
2000
Iteration
Figure 9: Least-squares problem (same as (S1)) for Huber with different values of μ and т. Setting 7 = 1.0
performs relatively well across the selected range of values of μ.
Full gradient estimation with fixed weights. Here, we show the results for estimating the full gradient of transformer architecture, with weights fixed initialization. Fig. 10 shows the results for PTB where we tried three different batch sizes (64, 256, 1024). Fig. 11 shows the results for WikiText-2.
We remark that in this experiment only, we have used the first order approximation of (7), namely m4+1 (1 - r) m 7gt- That is, we replace T+F with its first-order Taylor approximation around zero, which is equal to T. As the value of r is small, this has negligible impact on the result: for example, if T 0.01, then 1+r 0.0099.
Discussion. From Fig. 10, observe two phenomena: in the long run, momentum attains the lowest error for estimating the full batch gradient. However, the initial decrease of the error is much faster for CClip, followed by VClip. This is important when using these estimates within a training setup such as (13), where we only do one iteration of gradient estimation, followed by an update of the weight (and honce a change the full-batch gradient). Secondly, we observe that the difference convergence speeds is most pronounced when the batch size increases. Hence, being robust outliers seems not to be solvable only by increasing the batch size and thus decreasing the noise of the mini-batch gradient. In fact, the contrary seems to be the case. This is similar to the observations made in Kunstner et al. (2023).
batch size 64
batch size 256
batch size 1024
momentum
10a
vclip
cclip
12-er 12-error
10-1
10-2
2
2
0
2
T=0.01
Epoch
r=0.1
Figure 10:
Encoder transformer PTB dataset, with weights fixed at initialization. clip,, and clip,,2 to estimate the full-batch gradient.
We momentum,
34

---

Published in Transactions on Machine Learning Research (10/2025)
batch size 80
batch size 320
momentum
100
vclip cclip
12-error
10
10
0
2
0
2
T=0.01
Epoch
T=0.1
Figure 11: Encoder transformer Wikitext-2 dataset, with weights fixed at initialization. We use mentum, clip,,1 and clip,,2 to estimate the full-batch gradient.
C.2 Learning Rate Values for Transformer Training
Here, we report for each of the language modelling tasks, the lcarning rate value that is displayed Fig. For each method, we tuned the learning rate over set of values 10 for a suitable interval of integer numbers J
Table 1: Tuned learning rate values used for each method. All methods use constant learning rates. For SGD-M, tuning information is also reported in Section C.1 in (Kunstner et al., 2023)).
Name
SGD-M
clipped-SOl
VClip
CClip
Adam
PTB
1.0
3.16
3.16
0.316
0.001
WikiText-2
0.316
3.16
1.0
0.316
0.001
SQUAD
0.316
1.0
0.316
0.1
0.000316
35


Reviews:
[{"review_id": "8SR96ZCwVq", "reviewer": "Reviewer_pgqA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The submission has a very interesting narrative and is carefully written. It tackles a fundamental topic. Surely many readers will find it interesting. \n\nI view this work as less focused on new methods and more about revealing a new perspective. This type of work could be very impactful. However, I am not an expert in this area and it is hard for me to evaluate this.\n\nAt times, I felt unsure of which results were new and how they compare to what is known. For example, in Section 3.1 it says \"we will derive a new perspective on SGD-M, namely being an *online estimator of the mean gradient*.\" (Emphasis theirs.) Now, this section is explicitly a warmup, but the perspective is not new: one can see from the description that $m_t$ is an exponentially weighted moving average of the past gradients. See [1,2] for explicit discussion of this. I believe the new connection is running the framework through SPP, but this could be more explicit.\n\nSimilarly, in Section 5 I was left wondering what the existing similar results are. I see that the methods converge under reasonable heavy-tailed noise assumptions. Do these results match rates from an easier setting? Are they the best results one could hope for? Do they give new guarantees for an existing algorithm?\n\n[1] https://optimization.cbe.cornell.edu/index.php?title=Momentum\n\n[2] https://stats.stackexchange.com/questions/353833/why-is-gradient-descent-with-momentum-considered-an-exponentially-weighted-avera", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission concerns clipping and robustness in optimization. Clipping gradients is commonly used in practice to make an optimization process less sensitive to noise. The main contribution of this paper is to show how clipping can be viewed as a robustified momentum procedure. The submission has some derivations (showing the equivalences), convergence statements, and experiments.\n\nIn more detail, we can view standard momentum as computing an exponentially weighted moving average of the gradients. As I understand it, this paper asks: what if we used some other notion of \"average gradient\" as our momentum term? They suggest using online, robust methods for a median (based on stochastic proximal point solving the associated M-estimation task). They then show how existing methods such as clipping can be viewed as instantiations of this approach. This provides some formal explanation for their success in many practical applications.\n\nThey provide theory showing how some of these approaches will converge in settings where the gradient noise is heavy-tailed. There are experiments on synthetic data and a language modeling task.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Modify the warmup in Section 3.1 to make it clear which parts of the presentation are new. \n- If you believe it is appropriate, please consider adding more context around the convergence results.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IpM5ZNL8SG", "reviewer": "Reviewer_5XN1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is well-written and easy to follow. It provides a set of nice preliminaries about $\\ell_p$-medians of random vectors and their online estimation problems. I find the relationship between gradient clipping and online median gradient estimation problems very interesting.\n2. This paper proposes an insightful general viewpoint for analyzing several existing clipping-based optimization algorithms under the framework of online median gradient estimation.\n3. The assumptions for the theoretical analysis in Section 5 and the discussions therein are clear and sound.\n4. This paper provides a set of systematic comparative analyses between several algorithms based on (or, at least, related to) mean/median gradient estimation, which clearly shows that median-based and clipping-based algorithms showcase a robust optimization dynamic in general.\n\n**Weaknesses**\n\n1. **The relationship between the online median gradient estimation and the robustness of several clipping-based algorithms (e.g., V/CClip-SGD) is not very convincing.**\n    1. Throughout the paper, the authors emphasize the benefits of clipping-based methods in terms of robust convergence, attributing it to the online median estimation of the stochastic gradients. As kindly explained in Section 3, the update rule of $\\boldsymbol{m}_t$ based on vector-/component-wise clipping leads to the estimated median gradient only when the distribution $\\mathcal{G}$ of the gradients is fixed. On the other hand, if the update rule is “interweaved” with the weight update rule, it will provide an estimate of the median gradient over the course of the training trajectory. This is not quite the same as the median of the stochastically sampled (possible) update directions at each time step. Also, we do not really want to estimate the median of all the stochastic gradients that (can) appear during training because (1) the distribution of stochastic gradients must change depending on the weight vector $\\boldsymbol{w}_t$; (2) we expect the gradients (or the amount/direction of the update) to be very small at near convergence, mostly at the end of the training. In this sense, I do not believe that the vector-/component-wise clipping (as in the paper) will provide robustness in the training trajectory due to estimating the median gradients (yet there might be some other reasons).\n2. **Section 5 does not provide genuine convergence guarantees for SMGD.**\n    1. As far as I understand, the proofs of Propositions 5.3 and 5.4 do not rely on the fact that $\\boldsymbol{m}_t$ is the sample $\\ell_p$-**median** of stochastic gradients. The proofs always hold when Assumptions 5.1 and 5.2 hold, where we can replace the term “sample median” with any kind of random vector or any estimator (in a statistical sense) of the loss gradient $\\nabla \\ell (\\boldsymbol{w})$. The paper lacks such an explanation that the propositions are generally true for any kind of stochastic gradient method with biased gradient estimators.\n    1. According to the discussion in the main text, the authors claim that it is important to use the estimator of median gradients because it generally has smaller (finite) variance given that the sample size $n$ is sufficiently large. This claim is intuitively correct, but the paper does not handle this topic rigorously. Several questions remain: Exactly when (e.g., for what class of distributions, or with how large a sample size) does the variance of the estimator become reasonably small in general? Do we have a theoretical/rigorous guarantee that the methods using the sample mean gradients always fail to converge under heavy-tailed (or state-dependent) gradient noise? Is it always true that SGD using the sample median gradients succeeds in converging when SGD using the sample mean gradients can succeed?\n    1. Propositions 5.3 and 5.4 have irreducible terms in $\\delta_1$ and $\\varepsilon$, each due to the bias of the gradient estimator and the error for estimating the sample median. These terms can be huge in general, meaning that the propositions do not really prove a meaningful convergence to a (local) optimum. Even though Corollary 5.6. seems to provide a couple of convergence results using a step size of scale $1/\\sqrt{T}$,  I strongly believe that this is possible because of Assumption 5.5, supposing an **unbiased** gradient oracle (although its distribution is heavy-tailed). In general, the mean and the median of a distribution do not match at all. I believe analyzing the behavior of the optimization algorithms must be significant, especially when the median is quite (or even largely) apart from the mean, and in this case, I think we need convergence metrics other than “mean” squared gradient norm or “mean” sub-optimality in function values.\n        - By the way, the step size conditions in Propositions 5.3 and 5.4 are not reflected in Corollary 5.6.\n    1. Lastly, the descriptions of Propositions 5.3 and 5.4 lack clear dependencies regarding the sample size $n$ (of course, the proofs of these propositions do not depend on the sample size $n$ in general) and a problem parameter $\\sigma_1$.\n3. **Algorithmic behaviors of V/CClip-SGD are not studied well.**\n    1. Although the relationship between vector-/component-wise clipping gradients under fixed gradient distribution and the online median gradient estimation is interesting, a more interesting topic would be the behavior of optimization algorithms when applying these clipping techniques. Unfortunately, this aspect is not well studied in this paper.\n    1. There can be several research questions. Is the median estimation really happening when we interweave the clipping-based SPP update and the weight update? How does the estimated ‘median’ ($\\boldsymbol{m}_t$) behave? How good/bad/similar are they compared to SGD using the sample mean/median gradients?\n    1. The only thing I can expect from Propositions 5.3 and 5.4 is that V/CClip-SGD are *strictly* worse than SGD with exact sample median gradients ($\\varepsilon = 0$) due to the estimation error for the sample median.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors of this paper study the optimization algorithms based on the estimated median of stochastic gradients, whose convergence is more robust to heavy-tailed gradient noises.\n\n1. They study the mean/median gradient estimation problems using stochastic proximal point (SPP) methods under a fixed gradient distribution. As a result, they figure out that some notions of gradient clipping are related to estimating the median of gradients online.\n2. Alternately applying a SPP update (of mean/median estimates) and a descent step (to update the learning parameters), they recover several existing clipping-based algorithms (especially for distributed learning scenarios) as special cases.\n3. Pivoting the interest to the sample median gradient descent (SMGD) algorithm, they show that the convergence of SMGD is guaranteed more robustly even under heavy-tailed, state-dependent gradient noise.\n\nLastly, they numerically compare the algorithms based on mean/median gradient estimations on toy examples and language modeling tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Required Changes**\n\n- Every point listed above under “weaknesses” should be resolved.\n\n**Recommended Changes & Some Questions expected to be answered**\n\n1. The paper is mainly comparing $\\mathcal{D}=\\lVert\\cdot\\rVert^2$ versus $\\mathcal{D}=\\lVert\\cdot\\rVert$. Can you provide some discussions about what happens if we let $\\mathcal{D}=\\lVert\\cdot\\rVert^\\gamma$ where $1<\\gamma<2$ or even $0 < \\gamma < 1$?\n2. Questions regarding Figure 3\n    1. Why does the “momentum” have a worse $\\ell_2$ error than the other clipping-based method even when $1/\\alpha=0.5$? As far as I know, the standard $\\alpha$-stable distribution reduces to a Gaussian distribution when $\\alpha=2$, which is light-tailed (having a finite variance). I do not see any reason for the mean-estimating method being worse than the median-estimating method(s), even under the light-tailed noise.\n    2. What will happen in the plots if we encounter a *skewed* (but heavy-tailed) noise distribution, having the median different from the mean?\n3. Questions regarding Figure 4\n    1. The method “huber” must trade off between mean-/median-estimating methods. Have you tried to draw the objective plots by manipulating the value of the parameter $\\mu$ for the Huber function?\n    2. Will a smaller learning rate or a learning rate scheduling alleviate the instability in SGD with sample mean gradients?\n4. Comments regarding Figures 5 and 6\n    1. Adam with a usual gradient clipping, VClip, or CClip can be put into the baselines. In particular, we often use Adam with gradient clipping in real-world LLM training.\n    2. Probably, $\\ell_1$-SMGD can also be tested for training language models. ($\\ell_2$-SMGD is not that necessary due to its computational burden.)\n5. Minor typo under Figure 6: “$\\texttt{V/CCLip}$” $\\rightarrow$ ”$\\texttt{V/CClip}$”.", "broader_impact_concerns": "Since this work mostly focuses on the theoretical aspects of optimization algorithms and their application in toy problems, the Broader Impact Statement section seems unnecessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0OqfXMvQNV", "reviewer": "Reviewer_oT8M", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. The writing is very clean and easy to follow.\n2. The framework based on the stochastic proximal point method for estimating gradients appears to be a novel contribution that unifies several existing approaches.\n3. The paper provides both theoretical analysis and empirical validation. The convergence guarantees under heavy-tailed and state-dependent noise are clearly stated and backed by synthetic and real-world experiments.\n\n**Weaknesses:**\n\n1. The technical depth does not appear to be very high; the convergence analysis seems fairly standard. That said, I am only marginally familiar with the relevant literature, so I have limited expertise to comment definitively on its originality or significance.\n2. The empirical gains on real tasks are modest. While the proposed methods outperform momentum in some settings, they do not surpass Adam, and the robustness benefits are mostly visible in synthetic or controlled setups.\n3. The paper could benefit from more discussion of practical guidelines—for example, how to choose appropriate proximity functions for different contexts, or when the proposed methods are likely to outperform existing optimizers in real-world applications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies convex optimization under noisy gradient feedback, focusing specifically on methods for *robustly estimating gradients* when the noise is unfavorable—such as when it contains significant outliers, exhibits heavy tails, or is adversarially corrupted. Motivated by the median trick in robust statistics, the authors propose a general framework based on the *stochastic proximal point (SPP)* method, using different proximity functions (e.g., $\\ell_1$, $\\ell_2$, or squared $\\ell_2$ norms). The paper shows that several classical methods—such as momentum, gradient clipping, and Huber-style updates—can all be recovered as special cases of this SPP framework by choosing appropriate prox operators.\n\nUnder certain assumptions, the authors prove that if an oracle can provide a few independent gradient samples per iteration, then the proposed method (using sample *median* estimate for gradients) achieves the standard $O(1/\\sqrt{T})$ convergence rate—even under $\\alpha$-stable or state-dependent noise, where variance may be infinite and standard SGD can diverge.\n\nSynthetic experiments are conducted to validate the robustness of these estimators under heavy-tailed noise. The results show that median-based updates are more stable and accurate than momentum or clipped-SGD in pathological regimes. Additional experiments on real NLP tasks (e.g., PTB, WikiText-2, and SQuAD) show modest improvements over momentum, although the method does not outperform Adam.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I outlined some minor comments in the weaknesses section, but they do not affect my overall recommendation. I believe this is a solid work that makes a clear conceptual and theoretical contribution. It is suitable for publication in TMLR.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)