Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization
Authors: Sebastian Kassing
Simon Weissmann
Leif Döring
Venue: NeurIPS 2025 poster ()
Keywords: Stochastic gradient descent
Tikhonov regularization
convex optimization
minimum-norm solution
Primary area: optimization

Abstract: The present article studies the minimization of convex, $L$-smooth functions defined on a separable real Hilbert space. We analyze regularized stochastic gradient descent (reg-SGD), a variant of stochastic gradient descent that uses a Tikhonov regularization with time-dependent, vanishing regularization parameter. We prove strong convergence of reg-SGD to the minimum-norm solution of the original problem without additional boundedness assumptions. Moreover, we quantify the rate of convergence and optimize the interplay between step-sizes and regularization decay. Our analysis reveals how vanishing Tikhonov regularization controls the flow of SGD and yields stable learning dynamics, offering new insights into the design of iterative algorithms for convex problems, including those that arise in ill-posed inverse problems. We validate our theoretical findings through numerical experiments on image reconstruction and ODE-based inverse problems.

Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization
Sebastian Kassing* Institute of Mathematics
Simon Weissmann"
Institute of Mathematics
Technical University of Berlin 10623 Berlin, Germany kassingOmath. tu-berlin de
University of Mannheim
68159 Mannheim, Germany
simon. weis weissmann Ouni-uniinn mai-mmmnniimmmmmmm de
Leif Döring
Institute of Mathematics University of Mannheim
681 1,9 Mannheim, Germany
leif doeringeuni www.eeuiimmmmmmimmmmmmm de
Abstract
The present article studies the minimization of convex, L-smooth functions defined on separable real Hilbert space. We analyze regularized stochastic gradient descent (reg-SGD) a variant of stochastic gradient descent that uses a Tikhonov regularization with depedeenn,,nt, vanishing regularization parameter. We prove strong convergence of RGD to the minimum-none solution of the original problem without additional boundedness assumptions. Moreover, we quantify the rate of convergence and optimize the interplay between step- step-sizes and regularization decay. Our analysis reveals how vanishing Tikhonov regularization controls the flow of SGD and yields stable learning dynamics, offering new insights into the design of iterative algorithms for convex problems, including those that arise ill- ill-posed inverse problems. We validate our theoretical findings through numerical experiments on image reconstruction and aDsebased inverse problems.
1 Introduction
In this work we study the unconstrained optimization problem
min fxx),
#EX
where (X, xx) is a separable real Hilbert space with inner product (., x)xx and induced norm ||>|] x) The objective function f X' E will be assumed be differentiable,. convex, and L-smooth with arg minzex f(x) f 0. Moreover, we will always denote by r. E arg min f(x) the minimum-norm solution,
minimum with ||x. le S |[]|x x for all è arg mingex (x). A common strategy for finding a point close to the minimum- norm solution is to employ regular- ization techniques. One popular approach from the optimization literature is to include Tikhonov regularization into (I) in the form of
min fa(x),
fa(x) = f(x) || 12
(2)
These authors contributed equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where À 2 O is called the regularization parameter. Since the regularized objective function fa is A-strongly convex for any À > there exists unique minimum 2 arg m fx (x) and many first order methods, such as stochastic gradient descent (SGD), are able to efficiently find 22-
Tikhonov regularization is simple but effective method that appears in various contexts, such as statistics (e.g. ridge regression, (39] ) classical inverse problems [31], including parameter estimation
in partial differential equations 40 and image reconstruction 41 18 dating all the way back to Tikhonov [70]. In the context of training neural networks, Tikhonov regularization known under the name weight decay the method decreases the norm of the neural network weights. One early reference [50], for more recent work on the effect of weight decay on generalization we refer to [66], for LLM training to [22]. and for very recent experimental deep learning study to [29]. It is still a very much open problem to fully understand the different effects of weight decay, both from a practical but also the theoretical point of view in different optimization settings.
||=. for X < X, see for instance [5], there is trade-off between choosing large and small. Large À speeds up convergence with the price finding solutions that are too strongly regularized. On the other hand lim || x= lI. 0 suggests turn down the regularization over time in order to ensure convergence to the minimum-norm solution. The present article provides a rigorous theoretical analysis for Tikhonov regularized stochastic gradient descent (reg-SGD) with decreasing (non-constang regularization schedule AENN. We show how tune step-size and regularization schedules in order achieve strong convergence to T.. By strong convergence we refer to the convergence of the iterates X₁ in the sense lim3-soc || - Ix |Ix = O. For practical purposes, we derive how optimally tune the decay rates of polynomial schedules.
Recalling that ||æx|| S || <
1.1 Fixing the setup
Let us recall the classical Tikhonov regularized gradient descent scheme (reg-GD)
(3) which for constant À converges to IA under suitable conditions on the step-size sequence a. In many applications the gradient cannot be computed (or observed) exactly, instead only gradients with noisy perturbation are available. This leads to two equivalent formulations: one in which a noisy perturbation D3 is added the true gradient, and another in which the gradient is replaced by an estimated gradient V ( These formulations are equivalent if we define the noise as
X Xx-1 a& (XXxx1)) + Ax-Xa1),,
D2 = vX v (Xx=)) 1). We thus stick to the first setting but use the more accessible second notation for the pseudocode of Algorithm below.
In this article, we study the regularized stochastic gradient descent scheme (reg-SGD) with decreasing regularization parameter A. Let (Fx) KeEN be a filtration and (X*))EN, be an adapted sequence defined recursively by
= an (VS(Xx-1) + Ax + Da),
(4)
where x < oo, a and À are sequences of (deterministic or random) non-negative reals, and D = (D&)kES is adapted sequence of martingale differences, i.c. B[D₁ Fx-1] = 0 for all E N. More precisely, in Theorem 2.1 we assume the sequences a == (ax) (ex) and := (Ax ) to be predictable stochastic processes, L.e ag and A are -measuuurra for all & E N. The SGD formalism includes for instance stochastic gradients in finite-sum problems, where a random data point's gradient estimates the full gradient, see eeamlel below, and in expected risk minimization, where gradients are computed using samples from the data distribution.
Algorithm 1 Regularized Stochastic Gradient Descent (reg-SGD)
Require: Initial guess Xu, number of iterations N, step-size schedule a, regularization schedule À
1: for k == to N do
2: Compute unbiased gradient estimates: V v((x-1) & (f(x
3: Update parameters: X₁= X ank V (X + XpXX-11
4: end for
5:
return X
We will further impose a second moment condition on the stochastic error terms (De)kers, which allows the noise term to grow with the optimality gap and the gradient norm. We emphasize that

---

throughout this work we will not impose any additional boundedness assumptions on the iterates of the reg-SGD scheme. Therefore, a priori the noise term might be unbounded. However, in the proofs below we show that, under weak assumptions on the siep and regularization schedules, the additional regularization term implies almost sure boundedness of the iterates. This contrasts the dynamical behavior of standard SGD without regularization.
Assumption 1.1. The objective function f X + R is convex, continuously differentiable, and L-smooth. The latter means that ff X X globally L-Lipschitz continuous, i.e. there exists L > O such that V f(x)) V x x I L|| yllx for all x, y E X. Furthermore, we assume that arg min (z) + 0 and denote by x. E arg mix (a) the minimum norm solution.
For the noise sequence typical ABC-type assumption is posed. The assumption is an important relaxation bounded noise and can be verified many applications 44 36
Assumption 1.2. There exist constants A, C' 2 such that
E [1I [F-11]
-(a.))
E
In contrast to the classical ABC condition, only two constants A and C' appear. In Euclidean space when f is differentiable, L-smooth, and bounded below, one has
[ < 2L(((z) - f(z.)) for all E R.,
(5)
see e.g. Lemma C.1 in 73 The exact same argument (combining L-smoothness and the fundamental theorem of calculus) extends readily the Hilbert space setting. Therefore, AAssmmption 1.2] is equivalent to the classical ABC-condition
Px 1&
Fx-1] S A(((X=))) - ((x.)) BIIVS(X + C, KEN,
for some A, B, C
Example 1.3 (Mini-batch estimator for finite-sum problems). Consider the finite- finite-sum optimization problem
1 N min f(x) - N Σ M((),, DER
where, for all 1. can define mini-batch estimator with mini-batch size M E N via 9k = + LiEM V (XR-1), where (L,eN) is a family of iid. random variables that are uniformly distributed on (I...., N.. The corresponding gradient noise is defined as Dr 1 (V (Xn-1) (f(xk-))) and satisfies
Rd - is convex and Ly-smooth. At iteration k. E N, we
M
4T.
20
E
D |
S
M (f(X - -fx,) +
(6)
M
where L = E Li and of = EN f(xx))]11 We will prove (6) in Lemma C.I below.
1.2
Contribution
The present article continuous line of research on convergence properties for regularized differential equation based optimization flows (see e.g. 88 7 [56] and the references therein). We show that the discretization of the stochastic differential equation setting considered in [56] yields a simple iterative scheme with similar convergence guarantees. It is non-trivial to establish a discrete iterative scheme that convergences fast to the minimum-norm solution J.,, as the step-size schedules a and regularization schedules À need to be balanced very carefully. In fact, while the assumptions we pose on the step-size schedule a are similar the classical Robbins-Monne step-size conditions for convergence of SGD [63], the regularization schedule À has to satisfy two conflicting objectives. For a slowly decaying (almost constant) sequence X, one can use the strong convexity of the regularized objective function fx for all X > 0 to show that X is close to the minimum I'A, of fAy- However, this significantly slows down convergence to the minimum norm solution due the slow convergence of || x. llx. A crucial step in the analysis of reg-SGD will be to balance the two ervor terms
X x. 1|x & ||x - IA 11 1x + | - Iz I|x
3

---

appearing on the right- hand side. The main achievement of this article is carry out last-iterate estimates that yield 7,2 and almost sure convergence rates. In contrast to non- regularized SGD we obtain convergence to the minimum-nowe -nom solution (not just some solu- tion) of the optimization problem while obtain- ing comparable rates for the optimality gap. The simulation in Figure I on the right shows the ef- feet for f01 Ø2) = (I1 + Z2 1)² with noisy gradients perturbed by independent Gaussians. While vanilla SGD) converges to some minima (red dots), reg-SGD converges the minimum- norm solution. Another important theoretical property that reveal is that reg-SGD is more stable. It turns out that the iterative scheme is automatically bounded and cannot explode.
1:1: SGD
Figure A comparison of SGD and reg-SGD, reg-SGD converges to x. for all initializations.
Summary of main contributions:
T.2- and almost sure-convergence proof for last-iterates of reg-SGD to the minimum-nomm so- lution under the ABC-condition without additional boundedness assumption the stochastic iteration.
2 and almost sure-convergence rates for polynomial step-size and regularization schedules. Experiments that show the stability our polynomial step-size and regularization schedules.
1.3 Related work
To guide the reader we collect related articles and emphasize the line of research which we continue.
Deterministic Tikhonov regularization: The literature contains number of articles Tikhonov regularization with decreasing regularization parameter. For instance, in the context of deterministic optimization, this includes the analysis of first order ODEs 8 26 7 and second order ODEs 43 6 [2]. Extensions to stochastic optimization in continuous time, in particular an analysis of the stochastic differential inclusion process, have been considered in [56]. Many statements are based on results for the solution curve (z))A20 derived in [5] More generally, differential inclusions for constrained convex optimization problems have been intensively studied in ( [00 [1] 27 60). In Appendix D.2, we provide more details and illustrate the relation to Tikhonov regularization. Recently, the gradient flow for a fixed Tikhonov regularization has been analyzed in [21]. For small values of the regularization parameter X, the optimization dynamics can be decomposed into two distinct phases: an initial fast convergence toward the set of minima, followed by slow drift along this set that selects the minimizer with the smallest (2-norm.
In this article, we extend methodologies for steepest descent flows the stochastic discrete-time setting. Discrete time algorithms with decaying Tikhonov regularization have been analyzed in the context of iterative regularization schemes. For instance, Chapter of [4 iterative regularization is discussed to solve variational inequalities covering ( for convex f as a special case. Under certain conditions on the regularization decay and the step- step-sizes, strong convergence to the minimum norm solution can be guaranteed. A related analysis has been considered for non-linear inverse problems 15] In the specific application inverse problems, (3) is also known as the modified Landweher iteration, where convergence is mainly studied for nonlinear forward models using a-priori and a a-posteriori stopping rules [5 47 64). The thcoretical analysis is conducted in a non-convex setting and relies on the so-called tangential cone condition.
Stochastic gradient descent (with regularization): For recent results on convergence SGD
for possibly non-coovex optimization landscapes we refer the reader to [57 28 72 and references therein. Note that due to the non-convyxi,,, only convergence to a critical point can shown without guarantees of optimality. In the smooth and convex case, almost sure convergence rates for the last-iterates of SGD without Tikhonov regularization under the ABC-condition for the noise have been derived [5I]. Therein, it was proved that for step-sizes ai C., - with e E (0, } one has f(xx) f(x)) Okk- -ett almost surely. [59] gives rate of convergence for SGD with

---

polynomially decaying step-sizes in expectation. Their rate is optimal for the choice a = Cak 3 which yield the rate [[f(Xx) - f(x+)] E O(k-1/3). Assuming uniform boundedness of the gradients and iterates, [67] increased this rate of convergence to ( log(k)) for the step-sizes Og Cak- These additional assumptions have been lifted in [22. where only bounded variance of the noise assumed. Following [59] [52,, the Suppert-Polyan average also achieves the rate [[f(Xx) - f(x)) E
(k--1/2 log(k)) for og C. -- These results attain the lower bound for the optimization of L-smooth convex functions using first order algorithms that have access to unbiased gradient estimates with bounded variance derived in (2 up to a log factor. More recently, almost sure convergence rates under related setting have been derived in [65. However, without any additional regularization one can only guarantee convergence towards some global minimum. The present article targets specifically algorithms that find the minimum-norr solution. We show that, when using reg-SGD one gets comparable convergence rates in the optimality gap as the ones for vanilla SGI) cited above. Moreover, one weaken the bounded variance assumption noise, while also achieving strong convergence to the minimum-nore solution. We also point to (38, where the role of regularization for the convergence of SGD for a prescribed number of optimization steps is discussed. Using a fixed regularization parameter, the authors derive a complexity bound for averaged SGD. However, they do not discuss the role of Tikhonov regularization for convergence towards minimum-non norm solution. Finally, in the context of inverse problems the regularization properties of (vanilla) SGD have been analyzed for linear 42 44 46 and non-linear forward models
the
45 based on a- a-priori and a- a-posteriori stopping rules. Moreover, in RK SGD has been considered for inverse problems from statistical point of view.
Regularization effects in ML; An exciting line of research that we do not touch directly is the explicit and implicit regularization effect of SGD appearing in ML training. We refer the reader for instance to the recent articles [61 68 [6] and references therein. The relation to our work is that plain vanilla SGD tends to converge to minimum-norm solution in certain problems of practical relevance (in general it does not), while we prove that for convex problems Tikhonov regularized SGD with decaying regularization can always be made to converge to the minimum- normm solution.
2 Theoretical results
In this section, we present our main theoretical contributions concerning the convergence of stochastic gradient descent with decaying Tikhonov regularization. An abstract convergence result is presented, followed by quantitative rates of convergence for polynomial step-size and regularization schedules. For the ML practitioner, we derive optimal choices for the step-sizes and regularization parameters. All proofs are provided in Appendix D. where slightly more general statements are presented.
First, we carefully balance the step-size and the regularization parameters to ensure convergence of the energy function Eg- fAze. (Xx)- fra.a (Ixe..). ). In Lemma B.3 we then obtain the estimate ||Xx - Ixa l1x S E&/ /be, / which links the distance to the regulanzzdd munimizer with the energy function. Since X also influences the decay of F.,, we must jointly control both quantities to ensure that lim F&/ /A = O. Combined with the fact that limx-o I| 2=.lxx O, this yields strong convergence lim || x. lllxx = O (both in I and almost surely). Moreover, a convergence rate for || - x- lI is known, the analysis allows us to also quantify strong convergence rate for the iterates X₁ to x..
Approach:
2.1 General convergence results
First, we present a general convergence statement for reg-SGD to the minimum- solution, both in the almost sure sense as well as the L2-sense. The assumptions on the sequence of step-sizes a are similar to the Robbins- Monro step-size conditions. Regarding the sequence of regularization parameters X, the assumptions for deriving almost sure convergence to the momimum-norm solution reflect the competing goals of using the strong convexity of fx for À > 0 and having sufficiently fast convergence of æ - J.. Compared to the almost sure convergence statement in Theorem 2.1 the second result, Theorem 2.2] establishes convergence in L under arguably much weaker assumptions. allowed to decay at a very slow rate and no prior knowledge of the rate of convergence for zλ + I. is required.
In particular, the sequence
5

---

We stress that we do not impose any boundedness assumptions of the reg-SGD scheme. In particular, the fact that supkeN, X3 oo almost surely is consequence of Theorem 2.1 which is guaranteed by the retracting force of the Tikhonov regularization.
Theorem 2.1 (Almost sure convergence). Suppose that Assumption 1.7 and Assumption 1.2 are fulfilled and let (N&) be generated by 4 with predictable (random) step-sizes and regularization parameters that are uniformly bounded from above. Moreover, we assume that almost surely the sequence À is decreasing to and that
Σ Coad= KEN
Σ KEN
<0, and Σ CasdeeIl= 1x 113x) < xC. KEN
Then limg->o X x. almost surely.
One can question how to verify the third assumption in for practical applications. In Appendix E quantify the distance between z and x. in linear inverse problems satisfying source condition, as well as in the situation, where f satisfies a Łojasiewicz inequality. In general, one has no control for ||..- 11 ||arx1:2 see [7I. We thus present second result on I.*-convergence that holds also under simpler condition. Here we require deterministic step-sizes and regularization parameters. Our requirements in (8) are very similar the ones needed in the deterministic setting [14] Theorem 5.1 and Theorem 5.2] and are motivated by the corresponding deterministic result in continuous time 26 Theorem 2.2].
Theorem 2.2 conveernre.)) Suppose that Assumption 1./ Assumption 1.2
1.2 are fulfilled and ler kE&) be generated by 4) with deterministic step-sizes and deterministic and decreasing regularization parameters ()k) Moreover, assume that > and 7 or, alternatively, that
Σ KEN
xx 00, ag =oAa), and dE- - - o(axAu).
(8)
Then lim Xx Z. 11 =
In the next section, the theorems made more explicit by choosing polynomial step-size and regularization schedules that allow us to derive convergence rates.
2.2 Convergence rates
We now go step further and derive - and almost sure-convergence rates for the particular choices of polynomial schedules
ax C. and À CAk P.q (0,
Note that, due to Theorem 2.2, one has X - x. 1x21 - 0f and p + < 1. However, we further derive the following convergence rates.
Theorem 2.3 (L2-rates for reg-SGD with polynomial schedules). Suppose that Assumption 1.1 and p E (0, and q (p. p). Let (Xx)keN, be generated by 4 with ag Cak- and d C2k If 1- p we additionally assume that 2C2Ca > 1 - q. Then it holds that lim X|||Xx x= 11 and
Assumption 1.2 are satisfied. Let Ca, C2
(i) (X)) - [(xx)] O(k: (immmmim(.-pp)).
(ii) X -AL-i 11 O(k min(1 min(1 -- 2p) for p (0. and q E (2p, 1 p).
For a sequence of step-sizes 0% = Cak- with E (0, one can set d = C2k-1/2 order to get E(f(X;) - f(x)) O(
For q E (3, 1) one can set d -.k- 1+4 in order obtain
(X - [(x.)] -kk-1
Therefore, we exactly recover the rates of convergence to some minimum for SGD without regularization derived in [59]. Recently, (52) improved the convergence rate for g to

---

- E ((k-1//lo(((k) It is an interesting open question, whether the convergence rate reg-SGD can be improved this situation.
Finally, we derive almost sure convergence rates for regularized SGD. We highlight that Theorem 2.4 additionally gives almost sure convergence of reg-SGD to the minimum-nome solution for specitic choice of schedules without additional assumptions on the rate of convergence for ||+,|| ||
Theorem 2.4 (Almost sure-rates for reg-SGI with polynomial schedules). Suppose that Assump tion 1.1 and Assumption 1.2 are satisfied. Let Cos Cx 0, p E (0, ( and q (2t ( p). Let (Xx) keN, be generated by A with ag Cak and 2ạ Cxk P. Then, it holds that lim [X I= 11x = 0 almost surely and for any B E (0, 2g - 1)
(i) [(Xx) - f(x.)= E O m))(k)))().)))) almost surely,
(ii) | 1 1Ix O(k min( p.l g-))) almost surely.
C.k with ($,1) 1) one can set d Cyk- with 0 <E c <1 to get almost surely
For sequence of step-sizes ag
f(Xx) - f(x.) O(k-1+ots),
which the vanilla SGD rate convergence to some minimum that has been recently derived in 51.
Remark 2.5. In Theorem of the appendix we also provide a theorem on convergence rates for deterministic reg-GD (3) with polynomial step-size and regularization schedules.
Summary: Incorporating carefully chosen vanishing Tikhonov regularization helps mitigate an exploding optimization sequence (the process (X&)keN, is always bounded without further assump- tions), ensures convergence to the minimum-norm solution, and achieves convergence rates in the optimality gap comparable to those of plain vanilla SGD.
2.3 Refinements under Lojasiewicz condition
In this final result section, we refine the above results under stronger assumptions on We use ideas that were recently used for continuous-time optimization schemes, see (56). Let assume f satisfies Eojasiewicz condition
(f(x) f(x,))) & C for all x E f (If(x)), + r)).
(9)
for some C.r r > 0 and F e [0, ; then follows (and this is what we actually need) that there exist Crog > 0 such that
| xx S Ar
(0, 1].
(10)
with { - 1-T see [56 guarantee (10). however, in the subsequent convergence rates we rely only on (O). Now we use that
We provide further discussion in Appendix E Note that is sufficient to
X - 11x s X - FA l1 + A 1x.1.
that bound the distance the minimum-norm solution by (10) and the statements derived in Theorem 2.3 and Theorem 2.4]
Regarding the convergence in L Theorem 2.3 together with 10 implies the following strong convergence rates L²:
Corollary 2.6 (Strong T,2 convergence rates). Suppose that the conditions of Theorem 2.3 are satisfied and assume that (10) in place for some & > O. Then it holds that
X| x, 11 = O(k min(1 --0------------ 2p.222))))))...
Thus, we get the optimal rate of convergence for 15+3
and g = Lip which gives
X|||X; - x. 11 = O कす
For almost sure convergence,
Theorem 2.4 together with 10 implies strong convergence rates:
7

---

Corollary 2.7 (Strong a.s. convergence rates), Suppose that the conditions of Theorem 2.4 are satisfied and assume that (10) is in place for some Then for all B E (0, 2q 1) it holds that
| xx11xx = O(k min(1 q- p..81) almost surely.
Let >> 0 and choose 3 2g 1 E. Then, for the optimal values p 65+3
and q = get
| x. 1.11 O DE E), almost surely.
In Figure we illustrate the convergence rate of ||X; I. 1 depending the decay-rates p. of schedules a and À in the situation where f satisfies a Polyak-Lojjsiewing inequality, i.e. (9) is satisfied with r and, thus, (TO) is satisfied with 3- In Appendix A.2 we provide numerical experiment studying the behavior of convergence when implementing reg-SGD for different choices of a and X.
we
20lnr1 0 P.O
Sp, DEv) wish C 1/4
mlna 4 p.8 ww,8-pp.eeee M0p) with 1/4, 8 2g
(p
0.222
61
07
0.
0.36
0.44
0.4
0.56
0.1
0.2
0.4
2.5
0.5
02
0.4 04
5.8
Figure 2: Optimal choices of p and Left: convergence rate for E E[[|X F., 12112/ in the situation of Corollary 2.6 Right: almost sure convergence rate for ||X r. 12 in the situation of Corollary 2.7 under the Polyak- Sojaak--ojssieiizz inequality.
3 Practical implications
In this section, we discuss the relevance and application of reg-SGD with fine-tuned step-size and regularization schedules in the particular setting of linear inverse problems. We perform a concrete experiment confirm image reconstruction of tomography images the strength of our theoretically derived step-size and regularization schedules.
3.1 Why is reg-SGD important?
As motivation, consider classical linear inverse problem posed in Hilbert space [17 31 Let X' and y be two (separable) Hilbert spaces, and let A : - ) be a bounded linear operator. X' such that
Given the observation y E the task of the inverse problem to reconstruct Ax =x=y) y. The reconstruction problem in general ill-posed, since the solution Ar = is typically non-unique. In particular, when has non-trivial null space, there exist infinitely many solutions. Moreover, when A is compact operator the generalized Moore-Penroe inverse At is unbounded. As consequence small perturbations in the data can lead to large variations in the reconstruction. One popular approach to solving the inverse problem is to select stable reconstruction based on the minimum- solution
2x = arg min ||ellae i
arg min ||Ax 1aax--ylpn xlly } #EX
Finding minimum-nome solutions is, as we also show in the present article, closely related to reg- SGD. When the observation y in the range of A, then the unique minimum-norm solution given by A y. In practice, the data space y is often described SE C 1dd to R (e.g., in integral equations or tomography), where s may model a sensor location or angle. Hence, the inversion can be formulated risk minimization problem involving data samples
function space of variables
y/ (s:) + OE, R, i= 1, 1.....

---

generated by observations of some forward-mapped ground truth x² E A' perturbed by noise 6₁. The empirical objective can be formulated as
min f(x), f(x) = Σ A[x](())) - ZEA'
In our analysis we assume access unbiased gradient estimators for noise-free data yi in the finite data regime, or for noisy data in the infinite data regime (n x)). When analyzing finite noisy data, it is typically necessary to incorporate additional regularization, such early stopping based on Morozov's 's discrepancy principle 4 20 58 In practical applications, first-order optimization methods, and in particular the use of reg-SGD, is gaining popularity an efficient approach for solving large-scale inverse problems [30 24 It would be interesting to explore whether our analysis can be extended to more advanced variational regularization schemes on constrained or non-smooth optimization problems 25
In what follows, present results from experiment task of image reconstruction based on the Radon transformation. This experiment demonstrates the relevance of carefully tuning decreasing step-size and regularization schedules. Two additional experiments are provided in Appendix Ahthat highlight the performance of our theoretically derived optimal schedules.
3.2 Fine-tuned reg-SGD for X-ray tomography
In the context of X-ray tomography, the Radon transform models how two-dimensional image r(21, x2) is mapped its projection data Rg[z](-) via line integrals along rays oriented at various angles 8 E [0. T), see e.g. [37] for details. These projections are obtained by integrating the image along parallel lines, simulating the physical process of X-ray attenuation. Formally, the forward Radon transform at angle 0 is defined as
/ x(1 cos(()) sin(0), / (in + cos(()) ds
Rs [1)
where 2122, 22) is the image to be reconstructed, t E R denotes the location along the detector array orthogonal to the projection direction direction 8. For numerical implementation, is discretized over a grid of pixels and a finite set of lines and projection angles. The inverse problem then consists of the reconstruction of an unknown image x from its noisy or incomplete measured projection data Ro (zr]. For instance, the Radon transform may model X-rays passing through an object, and the reconstruction corresponds to inferring the internal structure of this object from these measurements, similar to assembling complete image from multiple shadow-like projections. We formulate the reconstruction as the optimization problem
Radon transform
min
Ro, [x] ge, 12.
We carried out an experiment, reconstructing an image from it's Radon transform (see Figure 3) solving the ill-posed optimization problem using SGD and reg-SGD with our optimal step-size schedule and a more aggressive regularization schedule. All details of the implementation are provided in Appendix A. The experiment demonstrates the strength of our fine-tuned step-size and regularization schedules. While our optimal schedules (p 3. q 3) yield fast convergence suboptimal level. More critically, vanilla SGD with theoretically optimal step-sizes even fails to produce feasible reconstructions. To illustrate this, in Figure we compare the reconstructed images from reg- SGD with the optimal rates from our analysis, reg-SGD with more aggressive rates, vanilla SGD, and the minimum-norm solution F., which is computed via the Moore-Penross pseudoinverse x. Alg. Additionally, we plot both the expected and a.s. optimality gap in Figure 5 ass well as the T,2_ and pathwise-error to the minimum norm solution Figure 5] In this experiment, SGD shows faster convergence in terms of the optimality gap, but ultimately fails to converge to the minimum-nome solution.
to the minimum-norm solution, more aggressive schedule (p q 2) stagnates
4 Conclusion and future work
We analyzed convergence properties of SGD with decreasing Tikhonov regularization. For convex optimization problems that may have infinitely many solutions, showed that the regularization

---

ground puth
observation (noiselree)
min-nomm sciutin
Figure 3: Left: base image. Middle: Radon transform, Right: minimum-norm solution I...
recondiuction reg-SGD (purs)
reg-SGD beggreetiee)
Figure 4: Left: reconstruction using reg-SGD with our optimal schedules. Middle: reconstruction using reg-SGD with more aggressive schedules. Right: reconstruction using vanilla SGD.
((X,) - ((x.)
IX
12"
SCD
SCID
121
reg SGD (aggressive
SGD
Lisoretiiaal A
SGD
mig- SGD Tugg reggresive)
194
107
10
10
10"
f(x,). Right: pathwise squared error to the minimum-norm solution |X x., 12 Each curve represents one of 10 independent runs, each of length N = 5 10 The red shaded lines depict individual runs of SGD, while the green dash-dotted and blue dashed shaded lines correspond to reg-SGD. The red solid line shows the average error across runs for SGD, the green bold dash-dotted and blue dashed line shows the average for reg-SGD, and the black dashed line indicates the theoretical convergence rate.
Figure 5: Left: pathwise optimality gap f(X;)
always be chosen to guarantee convergence (almost surely and in L²) to the minimum-non norm solution. fact, we provided guidance on explicit choices for polynomial step-size and regularization schedules that ensure best (in the sense of upper bounds) convergence rates. On the way revealed interesting mathematical insight into the effect regularization. In contrast to plain vanilla SGD, boundedness of the approximation sequence is always ensured. A number of concrete applications was provided to show that our theoretical best schedules indeed are consistent with experimental observations, specifically in the experiments offAppendix A.2) Since analysis is limited to the smooth convex setting without constraints, for future work could be interesting to
extend results beyond the convexity assumption on f. e.g. using gradient domination properties [32] or the tangential cone condition which is commonly employed in iterative regularization methods for non-linear inverse problems (47).
experiment with suggested decreasing regularization in deep learning problems,
decreasing regularization schedules better understand the relation of implicit and explicit regularization present in SGD, and
study other regularization variants in situations in which minimum-nome solutions are not desirable (c.g. linear inverse problems with noisy data).
10

---

Acknowledgments
We thank the reviewers and the area chair for their valuable feedback. Our sincere thanks to Adrian Riekert, whose discussions and feedback were instrumental in shaping the project from its outset. SK acknowledges funding by the Deutsche Forschugssemmiinscatt (DFG, German Research Foundation) CRC/TRR 388 "Rough Analysis, Stochastic Dynamics and Related Fields" Project ID 516748464.
References
[1] Pierre-Antoine Absil, Robert Mahony, and Ben Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, ((2)):31-545) 2005.
[2] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information- theoretic lower bounds on the oracle complexity of convex optimization. Advances Neural Information Processing Systems, 22, 2009.
[3] Cristian Daniel Alecsa and Szilárd Csaba László. Tikhonov regularization of perturbed heavy ball system with vanishing damping. SIAM Journal on Optimization, 31(4):2921 2021.
[4] Stephan W. Anzengruber and Ronny Ramlau. Morozov's discrepancy principle for Tikhonov- type functionals with nonlinear operators. Inverse Problems, 26(2):22501,, 2009.
[5] Hedy Attouch. Viscosity solutions of minimization problems. SIAM Journal on Optimization, 6(3):799-806, 1996.
[6] Hedy Attouch, Zaki Chbani, and Hassan Riahi. Combining fast inertial dynamics for convex optimization with Tikhonov regularization. Journal of Mathematical Analysis and Applications, 457(2):1065-1094 2018.
[7] Hedy Attouch, Zaki Chbani, and Hassan Riahi. Accelerated gradient methods with strong convergence to the minimum norm minimizer: dynamic approach combining time scaling, averaging, and Tikhonov regularization. arXiv preprint, arxiv:2211 11..1.1.111.. 1.11044, 2022.
[8] Hedy Attouch and Roberto Cominetti. A dynamical approach to convex minimization coupling approximation with the steepest descent method. Journal of Differential Equations, 128(2):519- 540, 1996.
[9] Hedy Attouch and Marc-Olivier Czamecki. Asymptotic behavior of coupled dynamical systems with multiscale aspects. Journal of Differential Equations, 13155)1115-11344, 2010.
[10] Hédy Attouch, Alic--lliver Czarnecki, and Juan Peypouquet. Coupling forward forward-bace backward with penalty schemes and parallel splitting for constrained variational inequalities. SIAM J. on Optimization, 2 21(4): 1 November 2011.
[11] Hédy Attouch, Marc-Olivier Czarnecki, and Juan Peypouquet. Prox-penalization and splitting methods for constrained variational problems. SIAM Journal on Optimization, 2191):149-173, 2011.
[12] Hedy Attouch and Szilárd Csaba László. Convex optimization via inertial algorithms with van- ishing Tikhonov regularization: fast convergence to the minimum norm solution. Mathematical Methods of Operations Research, 99(3):307 2024.
[13] J.-B. Baillon and H. Brezis. Une remarque le comportement asymptotique des semigroupes non linéaires. Houston J. Math., 2:5-7, 1976.
[14] A. Bakushinsky and A. Goncharsky. IlI- Ill-Posed Problems: Theory and Applications. Mathematics and Its Applications. Springer Dordrecht, edition, 1994. Reprinted in softcover 2012. eBook ISBN: 978-94--01--00266
[15] A. B. Bakushinsky and M. Yu. Kokurin. Iterative Methods for Approximate Solution of Inverse Problems. Mathematics and Its Applications. Springer Dordrecht, edition, 2004. eBook ISBN: 978-1-4020-31222 Softcover reprint published in 2010.
11

---

[16] David Barrett and Benoit Dherin. Implicit gradient regularization. In International Conference on Learning Representations, 2021.
[17] Martin Benning and Martin Burger. Modern regularization methods for inverse problems. Acta Numerica, 27: 1- 2018.
[18] Mario Bertero, Patrizia Boccacci, and Christine De Mol. Introduction to inverse problems in imaging. CRC press, 2021.
[19] Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165:471-507, 2017.
[20] Thomas Bonesky. Morozov's 's discrepancy principle and Tikhonov-type functionals. Inverse Problems, 2551):55501,, 2008.
[21] Etienne Boursier, Scott Pesme, and Radu Andu-Alexandru Dragomir, A theoretical framework for grokking: Interpolation followed by riemannian norm minimisation, 2025.
[22] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[23] Ronald E Bruck. Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. Journal of Functional Analysis, 18(1):15-25 1975.
[24] M. Burger, A. Sawatzky, and G. Steidl. First Order Algorithms in Variational Image Processing. pages 345-407. Springer International Publishing, Cham, 2016.
[25]
Antonin Chambolle and Thomas Pock. An introduction to continuous optimization for imaging. Acta Numerica, 25:161-3199 2016.
[26) Roberto Cominetti, Juan Peypouquet, and Sylvain Sorin. Strong asymptotic convergence of evolution equations governed by maximal monotone operators with Tikhonov regularization. Journal of Differential Equations, 245(12)
2008.
[27] Marc-Olivier Czarnecki, Nahla Noun, and Juan Peypouquet. Splitting forward-backwee penalty scheme for constrained variational problems. Journal of Convex Analysis, 23(2):531-565, 2016.
[28] Steffen Dereich and Sebastian Kassing, Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapss. Journal of Machine Learning, 3(3):245-281, 2024.
[29] Francesco D' Angelo, Maksym Andriushchenko, Aditya Varre, and Nicolas Flammarion. Why do we need weight decay in modern deep learning? In Advances in Neural Information Processing Systems, volume 37, pages 23191-2933 23223. Curran Associates, Inc., 2024.
[30] Matthias Ehrhardt, Željko Kereta, Jingwei Liang, and Junqi Tang. A guide to stochastic optimisation for large-scale inverse problems. Inverse Problems, 41(5):05301,, may 2025.
[31] H.W. Engl, M. Hanke, and G. Neubauer. Regularization of Inverse Problems. Mathematics and Its Applications. Springer Netherlands, 1996.
[32] llyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimization under global Murdyka--ojjsieewe inequality. In Advances in Neural Information Processing Systems, volume 35, pages 158661 Curran Associates, Inc., 2022.
[33] Yuri Fonseca and Yuri Saporito. Statistical learning and inverse problems: A stochastic gradient approach. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 9591-9602. Curran Associates, Inc., 2022.
12

---

[34] Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv Preprint, arXiv:2301. 11235, 2024.
[35] Guillaume Garrigos, Lorenzo Rosasco, and Silvia Villa. Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry. Mathematical Programming. 198:937-996, 2023.
[36] Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference on Artificial Intelligence and Statistics, pages 1315-1323. PMLR, 2021.
[37] Per Christian Hansen, Jakob Jørgensen, and William R. B. Lionheart. Computed Tomography: Algorithms, Insight, and Just Enough Theory. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2021.
[38] Wenwu He and Yang Liu. To regularize not: Revisiting SGD with simple algorithms and experimental studies. Expert Systems with Applications, 112:1-14, 2018.
[39] A.E. Hoerl. Application of ridge analysis to regression problems. Chemical Engineering Progress, 58(3):54-555 59, 1962.
[40] Victor Isakov. Inverse problems for partial differential equations, volume 127, Springer, 2006.
[41] Kazufumi Ito and Bangti Jin. Inverse problems: Tikhonov theory and algorithms, volume 22. World Scientific, 2014.
[42] Tim Jahn and Bangti Jin. On the discrepancy principle for stochastic gradient descent. Inverse Problems, 36(9):995009, sep 2020.
[43] Mohamed Ali Jendoubi and Ramzi May. On an asymptotically autonomous system with Tikhonov type regularizing term. Archiv der Mathematik, 95(4):389-399, 2010.
[44] Bangti Jin and Xiliang Lu. On the regularizing property of stochastic gradient descent. Inverse Problems, 35(1)015504, nov 2018
[45] Bangti Jin, Zehui Zhou, and Jun Zou. On the convergence of stochastic gradient descent for nonlinear ill-posed problems. SIAM Journal on Optimization, 30(2): 1211-154,, 2020.
[46] Bangti Jin, Zehui Zhou, and Jun Zou. On the saturation phenomenon of stochastic gradi- ent descent for linear inverse problems. SIAM/ASA Journal on Uncertainty Quantification, 94)::1553-1588, 2021.
[47] Barbara Kaltenbacher, Andreas Neubauer, and Otmar Scherzer. Iterative Regularization Meth- ods for Nonlinear Ill-Posed Problems. De Gruyter, Berlin, New York, 2008
[48] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Lojssk--ooasiewiiz condition. In Machine Learning and Knowledge Discovery Databases, pages 795-811 111, Cham, 2016. Springer International Publishing.
[49] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2023.
[50] Anders Krogh and John Hertz. A simple weight decay can improve generalization. In J. Moody, S. Hanson, and R.P. Lippmann, editors, Advances in Neural Information Processing Systems, volume 4, 1991.
[51] Jun Liu and Ye Yuan. Almost sure convergence rates analysis and saddle avoidance of stochastic gradient methods. Journal of Machine Learning Research, 25(271): 400, 2024.
[52] Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024.
[53] S. Lojasiewicz. Ensembles semi-analytiques. Lectures Notes IHES (Bures-sur- Yvette), 1965.
13

---

[54] Stanislaw Lojasiewicz. Une propriété topologique des souseensembles analytiques réels. Les équations aux dérivées partielles, 117:87-89, 1963.
[55] Stanislaw Lojasiewicz. Sur les trajectoires du gradient d'une fonction analytique. Seminari di geometria, 1983(1984::115-117 1982.
[56] Rodrigo Maulen-Soto, Jalal Fadili, and Hedy Attouch. Tikhonov regularization for stochastic non-smooth convex optimization in Hilbert spaces. arXiv preprint, arXiv:2403.06700, 2024.
[57] Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. In Advances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2020.
[58] V.A. Morozov. Regularization of incorrectly posed problems and the choice of regularization parameter. USSR Computational Mathematics and Mathematical Physics, 6(1):242 251, 1966.
(59) Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems, 24, 2011.
[60] Juan Peypouquet.
Coupling the Gradient Method with a General Exterior Penalization Scheme for Convex Minimization. Journal of Optimization Theory and Applications, 153(1): April 2012.
[61] Anant Raj and Francis Bach. Explicit regularization of stochastic gradient methods through duality. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
[62] H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing Methods Statistics, pages 233-257. Academic Press, 1971.
[63] Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400-477, 1951.
[64] Otmar Scherzer. A modified Landweber iteration for solving parameter estimation problems. Applied Mathematics and Optimization, 38:45-68, 1998.
[65] Othmane Sebbouh, Robert Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Proceedings of Thirty Fourth Conference on Learning Theory. PMLR, 2021.
[66] Shai Shalev-Shwarte and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[67] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning. PMLR, 2013.
[68] Samuel L Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization in stochastic gradient descent. In International Conference on Learning Representations, 2021.
[69] Vladislav Tadić. Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema. Stochastic Processes and their Application,, 125(5):1715- 1755, 2015.
[70] Andrey Nikolayevich Tikhonov. On the stability of inverse problems. Dokl. akad. nauk SSSR, 3955):195-198, 1943.
[71] Denis Torralba. Convergence épigraphique et changements d' é'cceelle analyse variationnelle el optimisation: applications aux transitions de phases la méthode barrière logarithmique. PhD thesis, Montpellier 2, 1996.
14

---

[72] Simon Weissmann, Sara Klein, Waiss Azizian, and Leif Döring. Almost sure convergence of stochastic gradient methods under gradient domination. Transactions on Machine Learning Research, 2025.
[73] Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type part I: Discrete time analysis. Journal of Nonlinear Science, 33(3):45, 2023.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarizes the theoretical findings in this paper; all claims are proven.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations the work and possible future work are discussed in Section 4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
Full proofs of all results are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all information to reproduce the results the numerical experiment in Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [Yes]
Justification:
We provide the code as zip-file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https Cooeeeoodeesssseeeeee 7/nips.com / cassiicnncccyyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The problem setup is explained in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: The experimental results conducted multiple repetitions and the pathwise error is plotted.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
18

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The numerical experiments can be run without specific computer resources. The code was run on local machine (Macbook M3 Pro 2023). The runtime of execution for the experiments in Appendix A.2 were around 20 minutes, for the experiments in Section 3.2 around hours, and for the experiments in Appendixx A.3 around 20 minutes.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://wwrrppppoooooo.....ccaaaa
Answer: [Yes]
Justification: We agree with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
22

---

A Omitted details and additional numerical experiments
In the following section. we give a detailed description of the implementation for our numerical experiment conducted in Section Moreover, we provide two additional experiments.
A.1 Implementation details of the Radon transform
discretize the Radon transform using fixed set of 32 equally spaced projection angles 02 E [0, ".. i ,,...,32 and use 100 parallel rays per angle. The unknown image defined on a 128 128 pixel grid and represented as a vector æ E Hd |2 Given any image E Rd its discretized Radon transform is implemented as a matrix-vector product Ax, where A E K is the forward operator, and K = 32 x 100, corresponds to the total number of measurements (i.e., the number of angle-ray combinations). Each row of A represents discrete line integral along one ray at a given projection angle. The objective function is then defined as
In the example offSection 3.2
128
f(z) == _ |Arr- 2
- E ZER
where g = (go,.... 90..) E R collects all projection measurements.
We implemented both SGD and reg-SGD by partitioning the forward operator A E Kxd into blocks A, E 100xd each corresponding to a fixed projection angle 0,, i 11 ,,...,.... 32. each iteration, the angle 0, is sampled uniformly at random, and the gradient of f is approximated by Vf(()) = A! (A,r - ge.) ) E Idd and additionally perturbed by independent noise following multivariate normal distribution with zero mean and covariance 0.5² ld. For SGD we chose the step-size schedule ag 20k 11/2 For reg-SGD we chose aş = 20% 2/3 and regularization
A = 0.01 Moreover, we compare to reg-SGD with dg = 20k -0/3 and regularization A 0.01A 2/3, i.e., reg with a too fast decay of regularization. We initialize all algorithms
for each repetition at zero.
A.2 toy example
In this section we present didactic toy example from 77). where the regularization emror in terms of ||b x. can be calculated exactly. Consider the objective function
f 22) 2 (a) + 2 - 1)²
with unique minimum-norm solution x, (1/2, see the plot in Section 1.2, Note that there
exist infinitely many global minima of f. Incorporating Tikhonov regularization results in
1
(x f(z1
[a] 222) with xx
2
such that the residuals in the Euclidean distance of I2² are bounded by
| -x1-x11 12(2+ + A)
< 2
Therefore, equation [T)) is satisfied with = 1.
Implementation details: We have implemented both vanilla SGD and reg-SGD by hand and initialized both algorithms with same initial state Xo -N(0,) 1) and perturbed the exact gradient V in each iteration by independent noise following multivariate normal distribution with zero mean and covariance 0.12 2. Id. For SGD we chose the step-size schedule a₁ = 0.1k 1/2 & E N. For SGD chose ag 0.1k 7 and regularization A - where p 4E+3 (1 + p)/2 when considering the L convergence rates and = (6g + 31 = 2/3 when considering the almost sure convergence rates see Corollary 2.6 and Corollary 2.7
The plots of and illustrate that reg-SGD converges to the minimum-norm solution both in 1,2 (Figure 6) and almost surely (Figure 7). as indicated by the vanishing squared error. In contrast, SGD does not converge to the minimum- norm solution, although achieves convergence in the expected FFiuure 6) and pathwise optimality gap FFiuure 7). This highlights the regularization effect
23

---

99
10"4
SGI: -
SGD: EANA
13
Eneuretiid
Dag SGD: BII -X
Easorefica
Chwovticnll 4
10"
13
107
10
Figure 6: Left: expected optimality gap (x)( - f(x )] Right: errrrr to the minimum-norm solution E[[] Xx x. =l. Each curve computed 100 independent of length N 10 The red line shows the average performance of SGD, the green line represents reg-SGD, and the black dotted lines indicate the corresponding theoretical convergence rates from our theorems.
10113
131
SCD: ((Ax)
10
Eisorctioal
rng. SGD: [Xg x.1
10
Ebroretical 2-122
theoretical g-29
Figure 7: Left: pathwise optimality gap f(Xx) f(z.). Right: pathwise squared eπrоr to the minimum-norm, solution [Xg 2, Each curve represents one 10 independent runs, each of length N 10 The red shaded lines depict individual runs of SGD, while the green dash-dotted shaded lines correspond to reg-SGI) The red solid line shows the average error across runs for SGD, the green bold dash-dotted line shows the average for reg-SGD, and the black dashed line indicates the theoretical convergence rate.
of reg-SGD in guiding the iterates toward the unique minimum-norm solution as also indicated in Figure
Next, we compare different choices of (p, q) for reg-SGD, In particular, we run reg-SGD with 0g 0.2gk and 0 -P for the choices
(p.g)= {001111, 0.667), (0, 0.667). (0.111
Moreover, we increase the noise covariance to (0, Id). The expected convergence behavior is shown in FFigure 8 while the resulting errors displayed in Figuree As expected, we do not observe convergence for the choices (0, 0.667) and (0.67, 0.5) as the regularization is not turned off, respectively turned off too fast. We observe convergence both a.s. and in L when choosing
[1
9.0
25p)
mira1 q p.0 p. p.265) g 1,
235
07
077
01t
0.12
0.4
(p-0.11. 11.0..11...0 q
0.671
0.4
(p-0.11, 0.11, 0.67
(p=iL.00 q-16667
(p=t.000) 0.0707)
[p=0.00 07, q=0
1999
(p=0 07, g 50)
0.110.11.0 0-0 0.201
(p- 0.11, Q-0.20)
0.2
52
0.4
8.6
06
0.2
0.4
06
0.8
Figure 8: Convergence rate for Xr x, 11 in the situation of Corollary 2.6 (left) and almost sure convergence for X 11 in the situation of Corollary 2.7 the consid- ered setting of AApenddx A.2 with & 1. Furthermore, we display the choices (p.q) E (0.111, 111, 0.667), (0, 0.666), (0.67, (0.67,0.5). (0.111,0.29)) which are simulated and displayed in Fig
uue g
24

---

5(x
x.1
107
10
10P
10"
12
16/13
(0.11..007
L..6.
1611
[p.0] (0.67.0.50)
1AAM0 (1-) (.0.29)
[v (0.11,0.20)
10
16
10
10
12"
Right: pathwise squared error to the minimum-norm solution ||X 11. Each curve represents one of 10 independent runs, each of length N 10 The shaded lines depict individual runs reg-SGD. The solid lines show the average errors for reg-SGD, The different colors correspond to various choices of (p. g) ((0.111,0.667) (0, 0.667), (0.67, 0.5), (0.111, 0.29)}.
Figure Left: pathwise optimality gap
(0.111, 0.667) as suggested by our theory. In contrast, when choosing (0.111, 0.29) our theoretical results suggest that the step-size decay is too slow, which we observe in high variance of the deviation the minimum value o1 in the step-size schedule. For SGD, fix 2 = --0.111 and use the step-size schedule (gg- = aj -0.667 We report both the pathwise optimality gap and the pathwise squared error the minimum-norm solution for SGD (Figure 10) and reg-SGD Figure 11) under varying initial step sizes a E {0.01, 0,1,
solution. In the final experiment, we examine the effect of the initial
og k-k-1/2 while for reg-SGD
1(x))
X 2.12
10
16
10"
10
10'2
0.01
10
-00L
10h90
10
10
10"
101
10" 10"
12" 10" 10"
12
10'
10" 10" 10" 10f 10²
Figure 10: Left: pathwise optimality gap f(Xx) - f(x.). Right: pathwise squared error to the minimum-norm solution |X x. Each curve represents one of 10 independent runs of SGD, each of length N 10?. The shaded lines depict individual runs of SGD. The solid lines show the average errors for SGD. The different colors correspond to various choices of a E (0.01, 0.1, 1,2
A.3 ODE based inverse problem.
In the following example, we consider linear inverse problem arising from the one-dimensional elliptic boundary value problem
(s)
+ p(s) = z(s), s (0,1),
ds²
(11)
p(s) = 0, sE (0,1).
It consists of recovering the unknown function E 0 (D) from discrete, noisefree observations d²
y Ax E K where A O G-1. Here, G d2s + Id denotes the differential operator on Ax
D(G) = 17 (00 1)) and O H)) - R denotes the discrete observation operator evaluating
function p E ([0, 1]) K = 64 equidistant observation points 5 k/K, k I,..., K, i.c.
25

---

((xx)
100
101
10
10"
10
0.01
10.00
10
10 10" 101 125 10. 107 10
10P
10
10' 10" 10" 10"
10"
Figure 11: Left: pathwise optimality gap f(Xx) f(x.). Right: pathwise squared error to the minimum-nore solution |X, x,, 1 Each curve represents one of 10 independent runs of reg- SGD, each of length N 107. The shaded lines depict individual runs of reg-SGD, The solid lines show the average errors for reg-SGD. The different colors correspond to various choices of 01 E {0.01, 0,1, 1,
Op(-) (p(s1),... ................................ p(sk)) The ground truth right-hand side æt used to generate the data is simulated as a random function
Σ v2 sin(iT))) & 5~~N0 ~((,0)
xt <T(s)
Implementation details; We numerically approximate the solution operator G on grid Ds C [0, with mesh size 5 = 2-8 and represent the unknown function as vector æ1 E BRd with d = 28, The resulting discretized forward model is then given by matrix E R-K xd and the inverse problem reduces to solving the least-squares problem:
min f(x), f(x) := 1 -11 -
where y = (p(s1),... ................................ p(sk)) K contains the discrete measurements associated with (II).
We implemented both SGD and reg-SGD by partitioning the forward operator A IR Kx into rows l....,,K Hence, A, corresponds the discretized ODE solution location A; R lxxd
At each iteration, batch of 16 locations (Sig...., .i1)) are sampled uniformly at random, and the gradient of is approximated by vf(x) & Σソ= A!, (A,, Viy) E Rd and additionally perturbed by independent noise following multivariate normal distribution with zero mean and
SCIE 7(Xa)
10-9
Dag DgD: S(NA))
SGD: 1xx - r// SCD: IX2
1-12
104
Figure 12: Left: pathwise optimality gap f(X)) fa.)). Right: pathwise squared error to the minimum-norm solution X 12 Each curve represents one of 10 independent runs, each of length N 107. The red shaded lines depict individual runs of SGD, while the green dash-dotted shaded lines correspond to reg-SGD. The red solid line shows the average error across runs for SGD, the green bold dash-dotted line shows the average for reg-SGD, and the black dashed line indicates the theoretical convergence rate.
26

---

covariance 0.001 Id. For SGD we chose the step-size schedule 100k 1/2, For reg- Peg-SGD we chose 100K and regularization A = 0.001k We initialize both algorithms for each repetition zero.
In Figure 12. we compare the expected and pathwise optimality gap (left) as well as the L and pathwise error the minimum-norm solution (right). While SGD shows fast convergence in terms of the optimality gap, it again fails to converge to the minimum-norm solution. In contrast, reg-SGD slows down the convergence in terms of the optimality gap, but safely reconstructs the minimum- norm solution. In Figure 13 (left), we plot the reconstruction of the unknown right-hand side xf resulting from the minimum-nore solution 2;, ATy. and from the last iterates of SGD and reg-SGD. Moreover, in Figure 13 (right) we plot the corresponding ODE solutions when solving (11) with the estimated right-hand side.
SGD
8.15
Eng SGD
0.05
Figure 13: Left: reconstruction of xt using the minimum-norm solution s, Aty, where At is the Moore-Penrose inverse of A, the last iterate of reg-SGD and of SGD. Right: corresponding ODE solutions of (II.
B Auxiliary results
In the following section, we provide a list of auxiliary results which are needed in the proofs of our main results.
Lemma B.1. Suppose that f satisfies
Assumption I.I then the following statements hold true:
(i) For all X, X it holds that
Sx
|| 11
2
(ii) For all 2 X 2 it holds that
0 3 fx(x)= fx(xx) < 1- X'
||
(iii) For all 2 it holds that
f(x) - ((x)-f(x)) fa(x) fa(2)) + -11111111 11
Proof. The first assertion is direct consequence of fx(x)) S fx(xx) f(xx) + | 122- since xA is the minimum of fx- The second assertion follows from fa(x) 2 fx( for all E X' and | l|x < ||x,Ixx. For the third assertion all x E X.
(ii) with X' 0 together with f(x) < fa()) for
Lemma B.2. Let f be L-smooth, then fx is T. + X-smooth for any X 2 0.
Proof. For arbitrary 2, E X apply triangle inequality to deduce
[+)xx>) xx | [V)() () X(x u)llx S L|Ix - u||x + A|Iı - vlix.
27

---

Note that by L-smoothness the descent condition holds, meaning that for any A' we have
L 2 1 yl1..
f()) s f(x) (v) x)x
(12)
The following lemma is similar to 7 Lemma 3]. For completeness we give proof.
Lemma B.3. Under UnderAssuumpn Assumption 1.1 the following estimates are satisfied for all x E X and X 2 0:
(i) f(x) - f(x,)= & fx(x) - fa(()) + 11
(ii) | xxll v (AA())-/A(AA)
Proof. (i): For arbitrary x X we have
f(x) f(x)) fx(z) - fx(x,) + 2 (112 - -
=>x [a(2))) + (a(12)) [a(r,) 2 (1x0011 -11:113))
S fx(2) fx(z)) + 11.
(ii: The second assertion follows from the X-strong convexity of fx and vxx())) =
Lemma B.4. Let p and 2 fv N. Then for all N one has
(k: + 1)0+1 S ax= Aut1 I kp-1
and
AR-1
+ (1)
Proof. We define spss) = E (0, oo). and note that ('(s) -ps theorem, for all & E N there exists a c E [k, k + 1] such that
-ps1(t (p+1), By the mean value
Au - Ac+1 ((k) - (k + =)==))(()(k=])) (1--)))k))))
cP+I
The first assertion follows by the monotonicity of + 1/80t1, For the second assertion, we use Taylor's approximation theorem at to get
d PP
k 1 = +0(1))+((1))( (1)))=11-) -1) to k- -1)
t
40
d
k
P k
1 K.
Lemma B.5 (Robbins-Siegmun) theorem, see Theorem in 622). Let (Fi)keN be a filtration and (Xx)ken) (YK))en, and (Zx keN be (FR)keN-aun aee-tddptedd sequences of non-negative random variables. Let (TK) be sequence of non-negative reals and assume that
(i) I1 (1 + Tw) 00,
(ii) Iee Z < oo, almost surely, and
(iii) E[E++1 F S (1 + 7
Xx + Zg. almost surely for all e N.
Then Exs X and (Yr )EE converges almost surely.
We will use the following two versions of the Robbins-Sicgmund theorem.
28

---

Corollary B.6. Let (FK)keN be a filtattonn. let (ZR)kEN be summable sequence of non-negative reals and let (Y KEN be an (F))eex-adapte sequence that uniformly bounded from below. Assume that for all le E N
E|E++1
FA S Yx + 2/.
(13)
Then (YK)NEN converges almost surely.
Proof. Let C 2 0 be a constant such that for all l E N one has Y 2 -C, almost surely. Set (YE)eeN = (Yx + Ce and note that (13) still holds when replacing (Ya)ke) by (Yz)keN. Thus,
the statement follows from Lemma B.5 for the choice V Xx = 0 and (ZR)NeN (Zk)kEN. O
Corollary B.7. Let (F&)keN be a filtration and (Ys)KEN. (An)kEN, (Bk)NeN and (CK)keN non- negative and adapted processes satisfying almost surely that
A
BB< k=1
<
and
Σ k=1
C₂ <0.
1=1
Moreover, suppose for all le E N one has almost surely that
[| Ful (1+ Cs - Ax)Ya + B2.
Then Y& + O holds almost surely as k xc.
Proof. The proof follows the same lines as the proof of Lemma A.2 in (72.. For completeness, we provide the full details. Compared to Lemma B.5] have Y2 Y2. Xx
7 Y Bg and Thk = CR. Using Lemma B.5 we obtain the existence of Y.. which is almost surely finite. integrable and satisfies Yn You almost surely. Additionally, we have that Σ
Σ Xx Σ A oo implying that lim inf Y2 O, where have used the assumption Lk A& almost surely. Since the limit inferior and limit coincide for converging sequences, the assertion follows by
Y0
lim Y2
lim inf Y2 = 0 almost surely.
k-000
k++00
C Finite-sum problems
In this section, we prove from Example 1.3 in the introduction. We consider the finite-sum optimization problem
N Σ M((),
min ((x) = =ER
where, for all i 1,...,,. N. Rdd R is convex and L,-smooth. The mini-batch estimator with mini-batch size M E N is defined via gk 37 EiEAs (X,-1), for all & E N, where (, is family of iid. random variables that are uniformly distributed on {I,..., NJ. The corresponding gradient noise is defined as D₃ = + E.eM (X v We show that in the finite-sum situation the ABC-condition, DSCCcconittoo./Assupptioo
|Asummptin 1.2 is satisfied. The following lemma
a version of (34 Lemma 4.20] with improved constants.
Lemma C.1. The sequence (Dx) satisfies for all E
4L
20
Dxll Fx-1] <
(f(X--1)-(22))
+ M
M
where L = 1 N EM L; and o3 = 1 N
EN (xx))11
Proof. Since, for all i (1...., N). f convex and -moothh we get for ar y E IRd that
L r v11
f((x) - f() s (Vf((v). 3)
29

---

For fixed y R let
- (:0) x- - v).
Due to convexity of fú, p, is non-negative. Moreover, Vip((a)= = v.((a)) - (f(x))-Vi(ly) is L, Lipsschhi
Thus, for = (()(a)
L,
0 pi(z) (p(() (Vpi(z), V Li
L; Vp((z) 1|2
+
2 Li
= f((x) - f(y) (VA()), x- 1\
Vf((z) vf(())1
2L,
which yields
Vf(22) - v((e)11 s 2L.(f(()) (f))))))))))--)- - (Vf(().== v\)
(14)
Thus.
N
E
| 2 Fk-1]
[V - -V
NM
[+((x-)) V.(x)- V/ita)1
NM
2
2
M
NM
Since + DE - = vS(Xx-1) we can use
14 with x = Xx-1 and y = x.
get
1
1 [ - Vf((=)) - VF(X
Σ
-
N
N
s (1-((xx1)-5000
X
D Proofs of the main results
As first step, we derive an iterative bound for the optimality gap of the regularized objective function
Ex == fxcm (X+) - fArts (#Ae4s); ), k E No-
(15)
Gemena B.3 this process (EE)keNo serves as Lyapunov function for computing the convergence rates stated in Section 2
Proposition D.1. Suppose that Assumpttttn 1.1 and Assumptiio 1.2 are fulfilled and and let
be generated by (4) with predictable (random) step-sizes and regularization parameters that are uniformly bounded from above and such that (>x) is almost surely decreasing. For l E N denote Lt>e F Then, for all le E E,,
by Ao {ar Σ
E 11 FA FR-1) S (1
(1
L + A
0kk
+
L+
dE
aZA
1/, FE-1
2
A
Ac+1
|x
112
L 2
A
A
| + c).
2
2
2
30

---

Proof. Using Assumption 1.2 the property f I fxL, and the descent condition applied to the (L Ax) >mmothh function fxu, yields, for ls E N.
BAlay/an Fx-1] S Th (Jaa (Xx-1) - -ox: (1 (1- L+ dE on (X
2
L d
+
aR 1Fx-1l)
2
(SAe (Xxx)) - -1
+ Ax
- Lse
V (X
2
+ L+ dR o
- -s(x))) + 0))
S Lsc (Exe (Xx=1) ass (1- L+ dx
|V (Xx- 111
akk
2
L + AB
ak (A(fa, (Xx-1) - (xe(e)))) + イ
2
1 || + +())
where in the last step we also used Lemma B. (iii). Since each Sxx is Ax-Strongly convex, it satisfies the Salyak-Lojasiwwic- inequality
(x) - (xx( S 2
(=)x(())) xe
(16)
Thus,
E(1,, fu, Fk-11 S la (fx, (Xx-1) -20d78 (1 (1- -+
2 as ( [fa, (Xx-1) (xxu))
L + AE
a (A(fA) (Xx-1) - (xxee)))) + >
2 1|2.113 2 +0)).
+
2
Next, we observe that
- (Xa fxets (Xkt) - SA (Ix+11) = (Xx( - (TxM) + (Xx)
+ (xNA) - Jruss (TAats)
S (Xk) - fxe + (1xx)) - -fren (IXe-))
since frct. (Xk) - (Xxx= & O. Combining the previous computations and using Lemma B. (ii) yields
E B[1 E& FR-11) S (1 22ROU
-1-
L A a1x) Ab
) 1ag FE-1 + Sxn (mxx)) - SAui (3A211))
2
L Au af
(xx.)) + A dk || 11 + C)
+
2
< 1 22pax
(1-11t
I.+ dx
2 ovk
li Es-1 +
da Ac+1
| 11
2
+ 2
L + Ax 0xk
[1,, AFx-1
A de
113x + +c).
2
With the help of the energy function (Ex) LEE), we can bound the optimality gap of the true objective function, as well as the distance to the unique minimizer of the regularized objective function. For this, we rephrase[Lemma Lemma B.3 in the notation used in this section.
Lemma D.2. Suppose that Asssmmptio I.1 is fulfilled and let (Xe)kEN, be generated by 4 Then the following estimates are satished for all k E N:
(i) [(Xx) -(xx)) < Ex. +
de+1 11...
2
(i) | - 112 S
2E.
31

---

D.1 General convergence result
First, we prove the general convergence results. We emphasize that no boundedness assumption is imposed on the reg-SGD scheme. In fact, in the proof Theorem 2.1 we will show that Assump- tions 1.1 1.2 together with (T7) imply that sup ||xx,:I3 < oc almost surely. The proof uses ideas from Theorem 4.1 in [56] and Lemma 3.1 in (28 Due to the discretization error, we introduce and analyze combined I. Lyapunov function (ypk: + FE)KEN, where (p: = || - 1.3 and Fyz is defined
in 115 in order to prove a descent step.
D.1.1 Proof of Theorem 2.1
Let us recall the statements. We note that using a stopping time argument one can lift the boundedness assumption on the step-sizes and regularization parameters. However, proving this generalization requires lot of heavy notation and technical arguments.
Theorem D.3 (Almost sure convergence), Suppose that Assumption 1.1 and Assumption 1.2 are fulfilled and let ( (Ne)ReN, be generated by 44 with predictable (random) step-sizes and regularization parameters that are uniformly bounded from above. Moreover, we assume that almost surely (>E))EN is decreasing to and
Eas C = 00
Σak< 00
and
Σ CasA -110x11122 <0.. KEN
(17)
KEN
KEN
Then limg- t00 X = T. almost surely.
Proof. For k E No let 9pu: ||x x- 11..- Then, for all & E E.N.
Elppk FE-1] S 9 20m (V Sx (X X bx + 2l (X
(18)
+ +ax A(s2, (Xx- - Sx, (xs.) )) + A
||= 113x + C)
2
where we used Assumption 1.2
and Lemma B.I (iii). Strong convexity of SAr yields
Ak
(xx 2 fA (X + [Vfx x), - Xx-1)x +
- 21
2
dt
2 (xxx + (V X 1), -xx-)xx +
||x=1 - 1x11-xx111 11.
2
Since, f(x.) S f this implies
d 2
A
-X d Xx-1 - xx.
||.-
122e
2
| 11 + (VSA, (X -
2
2
so that
A
d || -2.1
(V X4-1 xx,xx 2
(1=TA -1
+ 2
(19)
2
Combining
(18) and 19 gives
E lppk
Fa-1| 1]
$ (1 aAdx)5pk-1 04 (1
113 - || 11 + 2
f/x (X 1x
+ (A (X SN (x)a)) ) ds
|| + C)
2
$ (1 ondx + 04 x. 11xx - || l1ze
oz ((A + 2T. + 22x) (Xx-1) - (x),,) )) A 2
|| CC)
where in the last step we used that analogously to 5 one has
|V (x) < 2(L + (fr (x) - f(xxa))
for x E X.
Now, recall that Proposition D.I gives that for all k E
T3. 1 Fx FR-1] <
2 (1
L + A
0kk
+
L+
aAAAA 1 FE-1
2
+
d Ac+1
|x 11
L 2
A
A
| + c).
2
2
2
32

---

where E = fActI (Xx) - freti (oXL=T) ) Fix N E N and for ls 2 N denote Bx(N)- = fas S L+>i"
i = N....,k) kj. Then, for all k N
E| EI + Bx) Fk-1l S Th (V) (P + Ex-1)
(1 11 - ||
d dk+1
2 11 + at (A (A d
| + +C) 11+ I -=)
(20)
2
2
2
where
max (1 Ao 1 - 27 (1
L 1 a4k +
1 >
A+ + 2L 1 27t al
2
2
and we have used that PK-1 Ek-1 2 and 1 (B)) On the event 1 we have
L A
Tk S 1 11-0--1 +
A+ A
2L 2A o
(21)
2
=:Ax
where by assumption E Ck < oo and ΣnEN A do almost surely. Now, we can apply Corollary B.7 for the process (IB + ERl)ReN deduce that, on (N)) = Nea (N)) one has Pk almost surely + co. Since as 0 almost surely one has
IP {UB =
NEN
and, thus, the proof of the theorem is finished.
D.1.2 Proof Theorem 2.2
We again reformulate the statement and provide the full proof of the general L L'-convergence.
Theorem D.4 -Lo-eenverg....). Suppose that Assumption 1.1 Assumpioon 1.2 are fulfilled and let (X&),eN, be generated by (4) with deterministic step-sizes and deterministic and decreasing regularization parameters (eN) Moreover, assume that AR 0 and (17), alternatively.
Σ KEN
axAs=
ag o(>x) and d Ak-1 o(ax)a).
(22)
Then limg E X F. 113 O.
Proof. First, we prove the theorem assuming that (17) holds. By assumption, one has EXEN A oc. ΣKEN Ck < oc, ΣkEN az < 0o, EtEn Agg a|....1...... || l12)) < co and Σe \/-1) = d1 < 0c, where (Ag) and (C&) are defined in (T). Therefore, after taking expectations (20). can apply Corollary B.7 for the deterministic process (Yε)keN = (B(p, + Ex] Ex])KEN to deduce that Elpp| 0 and E[ 0.
Let us now prove the statement under (2 Combining
20 with the fact that dr - 0, there exist
G > 0 and N N such that for all k N one has
Elick + Ex Fk-1) < (1 (1 + E a axd (1 11....11.. ||,,,, 113c)
+ A
A6t1
1I.. ag ( d || 123e + +c)(1 (1 L + d
2
Moreover, using that af = olax )x ), dB - Aet1 = o(axds) and || 11x + 1| lell for all
there exists N N such that for all k N
Elpp + Ee Fe-1] < (1 CGande)( + FR-1) Ear
(23)
Rewriting 23 gives
B pk + Ex
E
5 G.
[ S -Caxdd) (p pp- + Ex
Cj
so that, taking expectation and using ΣLEN Ore DC, we get
8
< 0. lim sup Elypk + ER] C2 k0000
The statement now follows from - 0.
33

---

D.2 Deterministic case: Convergence rate for reg-GD
Before discussing the convergence rates for reg- GD, we want to relate our analysis to the literature in convex optimization. For this purpose we formulate our task of finding the minimum nomimum-norm solution as constrained optimization problem form of
min x
s.t. x E == arg min fwy |all
yE
This naturally relates to the task of solving general variational inclusions of form
E A(x) Nc(x)
where A denotes a (maximal) monotone operator and Nc(x) = fo X (w, <0 Ve E C} the normal cone a closed convex set C z. In our setting the operator A(x) V=bile1l3 ===== is strongly monotone. Another important class of problems studied in this context are hierarchical optimization problems of finding points the set
S = arg min (g(2) x arg min f(z)}
for convex functions g and f. This relates to our setting by choosing g(-) = || 11
To solve these types of problems, one popular approach includes penalty based methods which are described as differential inclusion
a(t) + A(x(t)) + ((t)af(z(t)) 30
(24)
where the penalty parameter ((t) tends to infinity. As demonstrated in (). when the monotone operator is sub-differential A = 0g. then we may equivalently consider the differential inclusion
+(t) + x(t)0g(z(()) + (f(((t)) 30
with vanishing parameter A(t). In summary, analyses of the above differential inclusion can be translated to the differential equation
#(t) + Vf(((t))) + A(t)=(t) =0
(25)
describing the regularized steepest descent in continuous time. Note that reg- reg-GD defined in (3) can be interpreted as explicit Euler discretization of (25).
D.2.1 Related work in the deterministic setting
The analysis of dynamical systems corresponding to 24 with 0f dates back to the 1970s. For instance, [3]. was shown that for A = ög. where is lower semicontinuous, proper, and convex, the trajectory converges weakly to minimizer of g. More generally, for maximal monotone operators A, the ergodic average of the trajectory converges weakly to point A 4(((O)) (3).
The penalty-based differential inclusion (24) was introduced in 99, where the authors established weak ergodic convergence (and even strong convergence for strongly monotone operators A) under the integrability condition
8(1)
V'
PA -10)
P ) dt oo for all range(Nc), 3(1)
where 4 denotes the Fenchel conjugate of V, and ac is the support function of the set C. This condition now commonly referred as the Sttouch-Czarncn
condition.
Note that a similar condition arises in our analysis as the final requirement in While our condition can be characterized via the Lojasiewicz inequality, the Attouch- -aanch-kCaeekiii condition can be characterized using quadratic error bound of the form
(x) 2 C' dist(x, C)²
which implies that
||r|2
V (p) - -c(p) < 2C'
see for instance I for more details. In this case, the Attouch-rammeci condition guaranteed under integrability conditions on the penalty function B(-).
34

---

In the discrete-time time setting, the Attouch-Czarnenn Czarnecki condition translates into a summability condition involving both the penalty sequence and the step-sizes. For instance, [60] introduces coupled gradient method with exterior penalization, leading to the condition
Σ an nEN
( ac pn
P Bn
< 00.
Here, the author considers the case where A Vg and both Vf and Vg are Lipschitz continuous, establishing weak convergence under convexity of and strong convergence when is strongly convex. Other results in the discrete-time setting include splitting-bar -based discretization schemes [10] [1 [7] whose convergence analysis rely on some similar variant of the Aitouch-Czarnees condition.
D.2.2 Convergence rate for reg-GD
In the following, we quantify the rate of convergence of reg-GD defined in (3). Our derived rates are consistent with known results for the ODE (25). In particular, for sufficiently small step-sizes, i.e 02 I E. our results match those derived in 7 Theorem 5] when defining the numerical time
L = Σt=1 Oi for & E N and noting that l C. 4l-4 and X Cx(2 - p/(1-9) for g < 1.
I-g
The proof follows the strategy of 7 Theorem 5].
Theorem D.5. Suppose that Assumption 1.1 is satisfied. Let Ca C2 > 0, p (0, and q 10.1-p), pl. Let (eN), be generated by (3) for all & E N. (A+)keN = (Cxk -or=P))es P)keN and (ax) (eN) (Cak ")EN such that the following conditions are satisfied:
Ca 7 2C > -
q
qq = - p and q # 0
2CAC.(1 LCa >1
and
Then holds that
(i) Es E O(k
(ii) f(Xx) - f(xx) =(K-P) P(K
(iii) [Xxx - -13-1ll3 E O0kk for E [0, - p), and
(iv) lim |X - x. 11xxxx = 0 0.for y E [0, -pp.. p).
Proof. (i): Proposition D.I with D3 = 0 guarantees that, for all h No with ag S 2 one has
L + dE as))
FR-1 d Ac+1
Fx < 2d
| 11
2
Set 3-11 q and for & N detind Fpu Exk2. By assumption on (ax) JAE one has an < for all but finitely many indices k. Therefore there exists an N E N such that for all k > N
Pk S (1
2Aa (1
L An an
Pk
+
Ax
A
I.
11
(26)
2
(k: - 1)
2k-
Using Lemma B.4 one has
A Akt1
Cxp
k 1-1
-
2
and there exist e, > 0 such that after possibly increasing N one has for all k 2 N
(1 (1- 2AAccs
L + d
4.8
S (1 22p (1 (1-
(1- 2 0 1) (1+
L d
(3 + 8)
2 (k
1)8
k
< e d'ARcss
(27)
In order to avoid confusion, we note that bu is defined differently as in the proofss of Theorem D.3 and Theorem D.4
35

---

where in the case q = and * 0 we have used that 20 > 1 1 and in the case 0 and p 1 have used that CC,C. (1 - 1. Inserting these inequalities (26).
CAP 2 1
SP s (1 - s' An p
CAP k- 11
(1-E'CACak 8 9)pkkkp-------
2
which is equivalent
Pk
P
| [ S 611='C.Cok (px-1
25 201211 |1:.lll
p
Ca'Ca
Therefore, by induction we get
(px
p
[10llx)) < (pN 20'Ca
|sal1x))
II (1 (1- (1-='Ccc((++1)2277
20'Ca
(=N+1
< (PN
PN
P
exp
Σ eCC.cali1) K:g 0.
2E'Ca
N=
where convergence holds since p S 1. This implies
sup sup Ppk lim sup Exk < k-00
|2,||x..
2c'Ca
k
(ii: Follows from (i) and Lemma D.2 using that p S
(iii): Follows from (i) and Lemma D.2
(iv): Follows from (iii) together with lim || I. x1,1x 0.
X-+0
we will derive optimal decay rates for the step-size and regularization decay for the convergence to the minimum-norm solution under the additional assumption that there exist Creg, with
In the spirit Section 2.3
|
I. l1x S Ar
A (0. 1]
see also Section
Using Theorem D.5 one has
[ 1 O(k min min(1-0-n:2Em),
(28)
Thus, we get the optimal rate of convergence for Co < 2. 9 00 and p = 28+1 which gives
X xx 1 E O म
In Figure 14 we illustrate the convergence rate on depending on the decay-rates g for & = 1
miaa2 with 1/4
(2=0 867, 00000
088
035
0.5
93
5.55
02
Figure 14: Convergence rate for X - 22112 112 in the situation of Theorem D.5 under the Polyak-
Eojasiewicz inequality, i.e. under (10p with 1
36

---

D.3 L covveeeeeee rate for reg-SGD: Proof of Theorem 2.3
In the following, we formulate Thhorrem 2.3 in more details and provide a full prove.
Theorem D.6. Suppose that Assumption 1.1 and Assumption 1.2 are satisfied. Let Ca. C2 > O. PE (0, { and E (p, 1 - pl. Let (ER) generated by (4) with (au))EN = (Cak ")EN and (AR)REN = (Cak KEN. q - -p we additionally assume that 2CxCa that lim x
q. Then, holds
11 0 and
(i) [F& E O(k min(1---- min(1-
(ii ( - f(x,)] O(k mimmmin((-)))) and
(i)) [II| Jxe+i 1ixll O(k min(1 --P- --p--22p)) 2p) for p (0, and E (2p, 1 p).
Proof. We will only prove the first claim (i). Due to Theorem 2.2 one has E X xz 1
> p and p + < 1. The statements (ii)- follow analogously to the proof of Theorem D.5 Let
3=min({ - q, q p) and ÿı: E Eig k. By assumption on (ax)ken one has ag < for all but
finitely many & E N so that, using Proposition D.1
9R < (1
L ++ d
L+ a3A
+
(K 1)3 Pk-
A Ak+1
+ d
Ak
|r. 12x
+
2 a (A
|.. 11x + CC).
-
2
Since q > p. p. 1, and 2C Ca > min(p, - 2p) in the case that q p one can show as in that there exist and N N such that for all N
Cxp k. Pl| 111 2
L L+ E' AE' 2
C A/- 11-11 + C) 20-8, (29)
Pkk S (1 E'Ap )p
By choice of B, one has p + max(1 +p- p- 3, 3,29 5). Therefore, show analogously to the proof of Theorem D3.5 that
lim sup :Pk limsup E[ < 0c.
4-000
D.4 Almost sure convergence rate for reg-SGD: Proof of Theorem 2.4
In the following, formulate Theorem 2.4 more details and provide full prove. The proof of the almost sure convergence rates requires a sophisticated application of the Robbins-Siegmund theorem, Corollary B.6. For this, use the variation of constants formula to separate the influence of the stochastic noise term (DR)ken and the deterministic change in the global minimum of the regularized objective function (I T'e41 )et..
Theorem D.7. Suppose that Asssuptiin I.I and Assumption 1.2 are satisfied. Let Ca, Cx > p (0, 1) and q E (2,1- pl. Let (Xk)keN, be generated by (4) with (au)KEN (Cak-T)ae and (AR)
(5)k-))ENT Let B (0, 2q 1) and, if p. assume that 2CxCa >
min - q). Then,
(i) Eg E O(k min(3,1-a)) almost surely,
(8) f(Xx) -s(x)) O(k min(8.))) almost surely,
(ii) [ - -'v-i 11x O(k min(88pp.1-g-p) p-1---))) almost surely, and
(iv) limg-ro 18a x. 2=I1xx 0 almost surely for (0, ( and g (2#1_1 p).
37

---

Proof. We will only prove property (i). Properties (ii)-ivv) follow analogously to the proof of
Theorem D.5 By Proposition D.1 for all k E N with aq S L+dx one has
E E FR-1) - (1 22R00E (1
L X 0kk
L+
2 Fa-1
+
2
A Ak+1
10,11xx
+
L + x
akk
2.
dk
| + +C).
2
2
2
For le E No we define
k
V
A6t1
F.
11x
II J=
(1-2)yag
(1- L 1 k,)
A1 ,
I
2
2
2
1=1
and
Ex = Ex- k. Since ag - 0, one has for all but finitely many k's that
EE Fk-1]] Es 1/ F1-1l
1 - 22x
L A
04k)
+
L
AE
a2,A)
A Ek-1
2
A Au+1
|,,,1132
+
L Ak
O
2
A
Ak
||:60 11 + +C) - V/
2
2
2
1 2220
(1
+ Ak
L+
L
An
2 A Ex-1
Ock
+
2
2
d
Au+1
11,,133
+
+
Av
0x
A
dE
||
11x +C)
2
2
2
L+
An
L Ak
Ax
Aut1
22x
+
||
11
2
2
2
+ Ak
L
Au
1
24pas
O4k
+
a
Ex-1
2
2
L + dK
Ak
11..1. + +C).
2
2
Let B E (0, 2q -
1), B = min( 1-1-1,1111 9) and Px Egk By assumption on (ax) one has
2 Oik < I for all but finitely many k E N so that
Elpak| FR-1] S (1 (1-22A (1
2N
L+ do okk)
+
L AR
(k- 1)8 Pk
2
2
L d ca A dx
||
11x + +C)+
-20+B
2
Since p. p.p 1, and 2C2Ca 3 in the case that q 1 p. one can show in
27 that
there exist 5' > and N E N such that for all k > N
Blppk Fa-1) S (1 e' (bRR) + L+
C
AE'
[|r.a12e + c) -20+
(30)
2
2
for all sufficiently large k. In order to apply the Robbins- Sabbins-ieegund theorem, Corollary B.6 we first prove that (Wx)Ren e (k--)). Note that (VR)keN is deterministic sequence that satisfies for all ks N
VA (1 (1-22 2dECr (1
L d2
L A 0 A Vn d Akt1
|| 11
2
2
Therefore, analogously to the proof in the deterministic setting, see Theorem D.5 and especially 27 we get v ", (Va from below. Now, since B < 2q we get Σ k22+9 xc. Hence, we can apply Corollary B.6 to get almost sure convergence of (1Pk JAEN and, thus, Eg E O(k almost surely. Together with Ex Ex Ux and V = (k- this implies that Es E Ok-B almost surely.
JREN bounded and, subsequently, (yp*) (ee))nn is uniformly bounded
38

---

E Properties of the Tikhonov regularization
In the following section, we want describe scenarios in which (10) is satisfied.
Linear inverse problems. Let A - y be a compact linear operator between two Hilbert spaces. For y R(A) @ R(A)+, the minimum-norm solution to the problem
min f(x), [(x) = 1 -111 - -113
#EX
can be written in the form of the singular value decomposition (SVD) of A:
1
xx Aty
(y, un)y
On
DEN
where (on, un UnlneN is the SVD of with singular values (on an orthonormal basis (un heN of R(A), and an orthonormal basis (Un)NeN of R(A*). Similarly, for any À > 0, the unique minimizer of
- 11 w113 + |1=1
min fx(x), fx(x)
2
also be written using the SVD) as:
FA =
Σ NEN
On
(y, Un y
o + X
To obtain a convergence rate for ||.. xxlxx as X + 0, we need to bound
1 On
0n + + 1) - 0hO
X
Fi (A)
on
+
( +
(n
+
However, when A is infinite- dimesioadi the singular values On are positive and satisfy oo on 0, meaning that (A) remains unbounded. Therefore, without additional assumptions, we can only deduce that
lim Ir. xxI1x 0,
x-0
but without a specific rate in To impose a convergence rate, one typically assumes so-called source condition (31 common in the inverse problem literature, which imposes a smoothness assumption on the sefinite-dimensionne
minimum-nowe solution T..
In terms of the SVD, the source condition with parameter v > can be described by the representation of the minimum-norm solution
A = x. Σ oh (w, un)x
nEN
for some bounded w E X. Using this representation together with the SVD expression for xx one can derive the following bound for the error ||Ir, =x
C,X2, v # 2, C.X², V < 2,
||.. - xx113 <
where Cp is a constant depending on > 0.
Lojasiewicz condition. Introduced in the 1960s by Lojasiewiez [54 [53] the Lojasiewicz inequality (11 has become one of the standard assumptions for convergence gradient based algorithms 28 72). It has the appeal that it is locally satisfied by every analytic objective function In the machine learning community, (31) with - = is especially popular, since it allows linear convergence of deterministic algorithms in non-convex situations [48] [3] We cite recent result in
15
54
[56] that derives and upper bound for the distance æ and x. under validity of the t.ojasiewicz
inequality. The result uses connection between the Lojasiewicz inequality and Hölderian error bound derived in [19].
Lemma F. (See Theorem 5 in [19 and 4.7 in 56 Let f X - be differentiable, convex
function with arg min f * 0.
39

---

(i) Assume that there exist C,r r > 0 and T E [0, 1) such that
-(x)))(()))) 2 V (x))lx for all x E (U)()), + r().
(31)
Then there exists a constant C' > 0 such that with = - holds that
f(x) f(x)) C"
inf &Earg minr f
|| 2112 for all (f.)) (32)
(ii) Assume that
32 holds. Then, there exist Crey & > such that
π - x+11x S A for all E [0,
Finally, note that in linear inverse problems a Lojasiewicz condition can be verified under the source condition discussed before, see [35] Theorem 5.10).
40


Reviews:
[{"review_id": "sY8rhVpwtp", "reviewer": "Reviewer_7hxJ", "summary": "This paper analyzes the Tikhonov regularized stochastic gradient descent (reg-SGD) algorithm for minimizing convex and $L$-smooth functions in separable real Hilbert spaces. \n\nAssuming a typical ABC-type condition on the noise sequence and without requiring any boundedness assumptions, the authors prove almost sure and $L^2$ convergence of the last iterates of reg-SGD to the minimum-norm solution. For polynomial stepsize and regularization schedules, they further establish sublinear convergence rates in both almost sure and $L^2$-convergence senses, with refined results under the \\L ojasiewicz condition. \n\nNumerical experiments are provided to support the theoretical results.", "questions": "Please see the weakness part and should address W2.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "S1. This paper establishes almost sure and $L^2$ convergence of reg-SGD to the minimum-norm solution without imposing additional boundedness assumptions. Moreover, the almost sure boundedness of the iterates is proved, highlighting the stability of reg-SGD to vanilla SGD. \n\nS2. This paper provides clear guidance on explicit choices of polynomial stepsize and regularization schedules that guarantee convergence of reg-SGD, enhancing the applicability of the analysis in pratical applications.\n\nW1. Typos. \n1) Line 228, 631, 742: It should be \"$\\Vert X_k - x_{\\lambda_{k+1}}\\Vert_{\\mathcal{X}}^2$\". \n2) Line 666-667: It should be \"$\\lambda_k - \\lambda_{k+1} = o(\\alpha_k \\lambda_k)$\". \n3) Line 701-702: It should be \"$\\cdots - \\frac{p}{2\\varepsilon^\\prime C_\\alpha}\\Vert x_{*}\\Vert_{\\mathcal{X}}^2$\". \n4) Line 726, 750: It should be \"$p+q\\leq 1$\". \n5) Line 728: It should be \"$p+q = \\min\\\\{1+p-\\beta,2q-\\beta\\\\}$\". \n6) Line 749: It should be \"$E[\\varphi_k\\ \\vert F_{k-1}] \\leq \\cdots \\varphi_{k-1} + \\cdots$\".\n\nW2. Gaps in the Assumptions of Theorem 2.1. The claim in Line 658-659 that $\\varphi_k\\to 0$ almost surely via Corollary B.8 lacks sufficient justification. To apply Corollary B.8, it is necessary to verify that  \n\n$\n1-\\tau_k = \\min\\\\{\\alpha_k\\lambda_k, 2\\alpha_k\\lambda_k(1-\\frac{L+\\lambda_k}{2}\\alpha_k)-(\\frac{L+\\lambda_k}{2}A+A+2L+2\\lambda_k)\\alpha_k^2\\\\} \\geq 0\n$\n\nholds on $B_\\infty(N)$ for sufficiently large $k$. However, under the assumptions of Theorem 2.1, this inequality may not be satisfied. As a counterexample, define $C_1 \\triangleq \\frac{LA}{4} + \\frac{A}{2} + L$, set $\\lambda_k = \\frac{1}{\\sqrt{k}}$ for $k\\in Z_{+}$, and let \n$$\n\\alpha_k = \\begin{cases}\n\\frac{2}{C_1}\\lambda_{k}\\quad &\\mbox{if}\\ k = 2^n\\ \\mbox{for some}\\ n\\in \\mathbb{N}\\\\\\\\\n\\frac{\\lambda_k}{\\log k}\\quad &\\mbox{otherwise}.\n\\end{cases}\n$$\nThen it follows from   \n$\n\\sum_{n\\geq 0} \\frac{1}{2^n} < \\infty,\\quad \\sum_{k\\geq 3}\\ \\frac{1}{k(\\log k)^2} < \\infty\\quad \\mbox{and}\\quad \\sum_{k\\geq 3}\\ \\frac{1}{k\\log k} = + \\infty,\n$\nthat $\\sum_k \\alpha_k^2 < \\infty$ and $\\sum_k \\alpha_k \\lambda_k = \\infty$, satisfying the requirements of Theorem 2.1. However, for any $k = 2^n$ with $n\\in \\mathbb{N}$, we have \n\n$\n1-\\tau_k \\leq 2\\alpha_k \\lambda_k - 2C_1 \\alpha_k^2 = 2\\alpha_k \\lambda_k (1-C_1\\frac{\\alpha_k}{\\lambda_k}) = \\alpha_k \\lambda_k (1-C_1 \\cdot \\frac{2}{C_1}) = -\\alpha_k \\lambda_k < 0,\n$\n\nwhich implies that $1-\\tau_k < 0$ occurs infinitely many times. Consequently, the key condition for applying Corollary B.8 is violated, and the almost sure convergence of $\\varphi_k$ cannot be guaranteed under the stated assumptions.\n\nW3. Assumptions in Theorem 2.2 and proof argument in Line 668. See W2.\n\nW4. Proof argument of Theorem 2.4. In Line 756, the derivation of $\\Psi_k\\in \\mathcal{O}(k^{-1+q})$ by an argument analogous to the proof of Theorem C.5 is potentially problematic. When $q>0$ and $q = 1-p$, the proof of Theorem C.5 requires the condition that $2C_\\lambda C_\\alpha > 1-q$ (see Line 698-699), which may not be satisfied under the assumptions of Theorem 2.4 when $\\beta < 1-q$.\n\nW5. Proof argument of Theorem 2.4. In Line 758-759, the application of Corollary B.7 to establish almost sure convergence of $\\{\\varphi_k\\}$ is not fully justified. The corollary requires a uniform lower bound on $\\{\\varphi_k\\}$, but the almost sure boundedness of $\\{\\tilde{E}_k\\}$ alone is insufficient, since $\\varphi_k = \\tilde{E}_k k^\\beta$ with $\\beta > 0$ by definition. This raises concerns about the applicability of the corollary in this context.", "was_revised": true, "final_justification": "I have raised my score as I believe the new arguments are correct and appreciate the efforts made by the authors. However, given that the paper is 33 pages long and the modifications involve multiple changes to various theorems and lemmas, I am unable to verify all the details without reviewing the complete revision. As reviewers, we are not in a position to check every detail within the very limited time available.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work, in particular the in-depth checking of the proofs. We very much hope you will be awarded a best reviewer award. Your careful review helped us to improve clarity of the proofs for the reader. Thanks! All your points can be fixed with minor modifications. In the following, we will provide point by point responses to your comments. If you agree with the corrections we would appreciate if you would raise the score.\n\nTo allow a full revision we give the full details how the corrected version will look like.\n\n## W1.\nThanks, we will correct the typos.\n\n## W2/W3. Gaps in the Assumptions of Theorem 2.1 and Theorem 2.2. \n\nThe problem you have identified here lies in our application of Corollary B.8 which in its current form does not allow a recursive inequality of form \n$$\\mathbb E[Y_{k+1} \\mid \\mathcal F_k] \\le (1+C_k - A_k) Y_k + B_k,$$\nwhere $\\sum C_k<\\infty, \\sum B_k <\\infty$ and $\\sum A_k=\\infty$ almost surely. However, such an extension is an immediate consequence of the Robbins-Siegmund theorem (see below). Having the corollary in this form, we can split $\\tau_k$ on $\\mathbb B_\\infty(N)$ into \n    $$ \\tau_k \\le 1- \\alpha_k\\lambda_k + \\Big(\\frac{L+\\lambda_{k}}{2} A +A+2L+2\\lambda_k\\Big) \\alpha_{k}^2 =: 1-A_k + C_k, $$\nsuch that we can apply the updated Corollary B.8. For W3 and the concerns in the proof of Theorem 2.2, we similarly split $\\tau_k$ into $1-A_k+C_k$, such that $\\sum A_k=\\infty$ and $\\sum C_k <\\infty$. Below are the full details and how the manuscript will be changed:\n\n### Action 1 (Updated Corollary B.8): \n\nWe will include the following extended Corollary 3.8:\n\n**Corollary:** Let $(\\mathcal F_k)$ be a filtration and $(Y_k)$, $(A_k)$, $(B_k)$ and $(C_k)$ be non-negative and adapted processes satisfying almost surely that \n$$ \n\\sum_{k = 1}^\\infty A_k = \\infty \\quad , \\quad \\sum_{k=1}^\\infty B_k <\\infty\\quad \\text{and}\\quad \\sum_{k=1}^\\infty C_k<\\infty. \n$$\n\nMoreover, suppose that for all $k \\in \\mathbb N$ one has almost surely that\n$$\n\\mathbb E[Y_{k+1} \\mid \\mathcal F_k] \\le (1+C_k-A_k)Y_k+B_k.\n$$\nThen $Y_k \\to 0$ holds almost surely as $k \\to \\infty$.\n\n*Proof:* The proof follows the same lines as the proof of Lemma A.2 in [54]. For completeness, we provide the details. Compared to Lemma B.6, we have $Y_k = Y_k$, $X_k = A_kY_k$, $Z_k = B_k$ and $\\gamma_k = C_k$. Using Lemma B.6 we obtain the existence of $Y_\\infty$ which is almost surely finite, integrable and satisfies $Y_n\\to Y_\\infty$ almost surely. Additionally, we have that $\\sum_{k=1}^\\infty X_k = \\sum A_k Y_k<\\infty$ implying that $\\liminf_{k\\to\\infty} Y_k = 0$, where we have used the assumption $\\sum_{k=1}^\\infty A_k = \\infty$ almost surely. Since the limit inferior and limit coincide for converging sequences, the assertion follows by\n$$ Y_\\infty = \\lim_{k\\to\\infty} Y_k = \\liminf_{k\\to\\infty} Y_k = 0\\quad \\text{almost surely}.$$\n\n### Action 2 (Changes in Thm 2.1):\n\nMoreover, we have updated the the proof of Theorem 2.1 from line 655 as follows:\n\nFix $N \\in \\mathbb N$ and for $k \\ge N$ denote $\\mathbb B_k(N)=  \\lbrace  \\alpha_i \\le \\frac{1}{L+\\lambda_i} : i = N, \\dots, k \\rbrace $.\nThen, for all $ k > N$\n$$\n\\mathbb E[1_{\\mathbb B_k(N)}(\\varphi_k + E_k) \\mid \\mathcal F_{k-1}] \\le \\tau_k 1_{\\mathbb B_{k-1}(N)}(\\varphi_{k-1}+E_{k-1}) + \\alpha_k \\lambda_k (\\|x_\\ast\\|^2-\\|x_{\\lambda_k}\\|^2) + \\frac{\\lambda_{k}-\\lambda_{k+1}}{2}\\|x_\\ast\\|^2  + \\alpha_k^2\\Bigl(A\\frac {\\lambda_{k}}2 \\|x_\\ast\\|^2 +C \\Bigr)\\Bigl( 1+ \\frac{L+\\lambda_k}{2} \\Bigr),\n$$\nwhere\n$$\n\\tau_k =  \\max\\Big( 1-\\alpha_k\\lambda_k, 1-2\\lambda_{k}\\alpha_{k}\\Big(1-\\frac{L+\\lambda_k}2\\alpha_{k}\\Big)+\\Bigl(\\frac{L+\\lambda_{k}}{2} A +A+2L+2\\lambda_k\\Bigr) \\alpha_{k}^2  \\Big)\n$$\nand we have used that $\\varphi_{k-1}+E_{k-1} \\ge 0$ and $B_{k-1}(N) \\supset B_k(N)$. On the event $B_{k-1}(N)$ we have\n$$ \n\\tau_k \\le 1-\\alpha_k\\lambda_k + \\Bigl(\\frac{L+\\lambda_{k}}{2} A +A+2L+2\\lambda_k\\Bigr) \\alpha_{k}^2 =: 1-A_k + C_k \\,,\n$$\nwhere by assumption $\\sum_{k\\in\\mathbb N} C_k <\\infty$ and $\\sum_{k\\in\\mathbb N} A_k = \\infty$ almost surely. Now, we can apply Corollary B.8 for the process $(1_{\\mathbb B_k(N)} (\\varphi_k+E_k), k\\ge N)$ \nto deduce that, on $B_\\infty(N) = \\bigcap_{k \\ge N} B_k(N)$, one has $\\varphi_k \\to 0$ almost surely as $k \\to \\infty$. Since $\\alpha_k \\to 0$ almost surely one has\n$$\n\\mathbb P \\Big( \\bigcup_{N \\in \\mathbb N} B_\\infty(N) \\Big)=1\n$$\nand, thus, the proof of the theorem is finished. \n\n### Action 3 (Changes in Thm 2.2):\n\nThe beginning of the proof of Theorem 2.2 now reads as follows:\n\nFirst, we prove the theorem assuming that (15) holds. By assumption, one has $\\sum_{k\\in\\mathbb N} A_k = \\infty$, $\\sum_{k\\in\\mathbb N} C_k <\\infty$, $\\sum_{k \\in \\mathbb N} \\alpha_k^2<\\infty$, $\\sum_{k \\in \\mathbb N} \\alpha_k\\lambda_k (\\|x_\\ast\\|^2-\\|x_{\\lambda_k}\\|^2)<\\infty$ and $\\sum_{k = 1 }^\\infty(\\lambda_k-\\lambda_{k+1}) = \\lambda_1 < \\infty$. Therefore, after taking expectations in (18), we can apply Lemma B.5 to deduce that $\\mathbb E[\\varphi_k]\\to 0$ and $\\mathbb E[E_k] \\to 0$.\n\n## W4. Proof argument of Theorem 2.4. (Line 756)\n\nThanks for noticing this issue. In view of inequality (22) in Theorem C.5, we need the constant $2C_\\lambda C_\\alpha$ to be strictly larger than the exponent in the convergence rate if $q=1-p$. For proving Theorem C.7 it is sufficient to show that $\\Psi_k \\in \\mathcal O(k^{-\\min(\\beta,1-q)})$. Thus, we only require $2C_\\lambda C_\\alpha > \\min(\\beta,1-q)$.\nIn Theorem 2.4 in the main text, we excluded the case $q=1-p$ to streamline presentation.\n\n### Action 4 (Assumptions in Theorem 2.4): \n\nIn Theorem C.7 we will assume that $2C_\\lambda C_\\alpha > \\min(\\beta,1-q)$. In the proof of Theorem C.7 we will write that $\\Psi_k \\in \\mathcal O(k^{-\\min(\\beta,1-q)})$.\n\n## W5. Proof argument of Theorem 2.4. (Line 758-759)\n\nThank you very much for noticing this. We can use the idea from our response to W4 to show that $\\tilde E_k k^{\\min(\\beta, 1-q)}$ is uniformly bounded from below. Then, we can apply Corollary B.7 to show that $\\tilde E_k \\in \\mathcal O(k^{-\\min(\\beta,1-q)})$ almost surely, which is sufficient for proving Theorem C.7.\n\n### Action 5 (Proof adaption of Theorem 2.4):\n\nWe define $\\beta \\in (0,2q-1)$, $\\tilde \\beta = \\min(\\beta, 1-q)$ and $\\varphi_k = \\tilde E_k k^{\\tilde \\beta}$. The end of the proof now reads: \n\nTherefore, analogously to the proof in the deterministic setting, we get $\\Psi_k \\in \\mathcal O(k^{-\\tilde \\beta})$, i.e. $(\\Psi_k k^{\\tilde \\beta}, k \\in \\mathbb N)$ is bounded and, subsequently, $(\\varphi_k, k \\in \\mathbb N)$ is uniformly bounded from below. \n        Now, since $\\beta < 2q-1$ we get $\\sum k^{-2q+\\beta} < \\infty$. Hence, we can apply Corollary~B.7 to get almost sure convergence of $(\\varphi_k)_{k \\in \\mathbb N}$ and, thus,\n\t\t$\n\t\t\t\\tilde E_k \\in \\mathcal O(k^{-\\tilde \\beta})\n\t\t$\n        almost surely.\n        Together with $\\tilde E_k = E_k -\\Psi_k$ and $\\Psi_k = \\mathcal O(k^{-\\tilde \\beta})$, this implies that\n\t\t$\n\t\t\tE_k \\in \\mathcal O( k^{-\\tilde \\beta})\n\t\t$\n        almost surely."}, {"review_id": "Tws3hSiAGU", "reviewer": "Reviewer_icyv", "summary": "# Summary\n\nThis paper focuses on an algorithm combining SGD with Tikhonov regularization for minimizing a convex and smooth function $f$. \nThe paper is mostly theoretical, and provides numerous results showing that the algorithm converges towards the minimal norm minimizer of $f$, thereafter noted $x_*$. \n\nMore precisely, the authors leverage the introduction of the regularization term to obtain\n\n- Almost-sure and $L^2$ convergence of the iterates $X_k$ towards $x_*$,\n- Convergence of the values $f(X_k)$ towards $\\inf f$,\n- Convergence rates for the above quantities,\n\nall this under more or less strict assumptions on the parameters of the method (namely: the learning rate and the regularization parameter).", "questions": "# Questions/comments\n\n1. I would like the authors to review properly the existing literature on deterministic Tikhonov-gradient algorithms. Then I would like to see some comparison between their results / hypotheses of Section 2.1 with what was done in the deterministic setting, both in the continuous and discrete regime. I believe this would allow the reader to better appreciate the results. \n\n   1. For instance the third assumption in (6) seems strongly connected to assumptions which already appeared (albeit under different forms) in the literature. See\n\n      - p.132 in \"Coupling the gradient method with a general exterior penalization scheme for convex minimization\"\n      - Hypothesis H4 in \"Prox-Penalization and Splitting Methods for Constrained Variational Problems\"\n\n      and in particular look at how those papers make a connection with  the Łojasiewicz inequality (or other equivalent error bounds such as $f(x) - f(x_*) \\geq C dist(x, argmin f)^\\tau$ ). \n\n   2. Are the assumptions (7) the same that what is known in the deterministic case? Is there any work able to obtain convergence without making an assumption like in (6)? \n\n   If the above is done properly **I will raise my score**.\n\n2. Appendix D:  It is known that source conditions imply that a Łojasiewicz inequality holds onto some set, see Theorem 5.10 in \"Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry\". Can it be proved that the regularization path $x_\\lambda$ belongs to such set? If yes, then a connection could be made between the \"linear inverse problem\" scenario and the \"Łojasiewicz\" scenario.\n\n3. Authors claim that Tikhonov regularization helps preventing the explosion of the trajectory of SGD. I wonder how true is this claim, given that it is not yet fully known what can or cannot do SGD (here by SGD I mean sampling a function f_i when minimizing an expectation of f_i). For instance recent results (see \"Stochastic Gradient Descent Revisited\") indicate that SGD does not need bounded trajectories to converge in function values. More precisely, convergence of the values always hold, so under a mere coercivity assumption we can recover the boundedness of the iterates. \n\n4. You certainly want to tell the reader that Assumption 1.2 is not an assumption when $f = \\mathbb{E}[f_i]$ and $\\hat \\nabla f(x) = \\nabla f_i(x)$ , and always holds true with $A=4L$ and $C = \\mathbb{E}[\\Vert \\nabla f_i(x_*) \\Vert^2]$ .", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strengths \n\nOverall I was very positively impressed by the paper.\n\n- It is very well written. While the topic is technical, the paper is quite easy to read\n- The contribution is very good. The results (see the summary) answer all the questions we could have for such stochastic method (well, one could always ask for high probability results...). The obtained rates are for most of them as good as what is currently known for vanilla SGD.\n- The assumptions are minimal, and match what are standard assumptions in the community: no bounded gradient assumption but a mere ABC-like condition (which is always verified for vanilla SGD), basic assumptions on the parameters\n\n# Weaknesses\n\n- The main complaint I have is the connection to the literature. The authors claim that there is one only work on gradient algorithms combining with a Tikhonov term. This is incorrect. The literature on the topic is quite consequent and goes back to the 70's, ranging from simple perturbations of the Landweber algorithm for inverse problems, to general methods for selecting a specific minimizer of a function f. Here are a few entries (there are many others, see the literature therein):\n  - \"Convergence of diagonally stationary sequences in convex\n    optimization\"\n  - \"Coupling forward-backward with penalty schemes and parallel splitting for constrained variational inequalities\"\n  - \"Splitting forward-backward penalty scheme for constrained variational problems\"\n  - for the applications in inverse problems (that the authors seem to favor):\n    - \"A modified Landweber iteration for solving parameter\n      estimation problems\"\n    - \"Iterative Regularization Methods for Nonlinear Ill-Posed Problems\"\n    - \"Iterative Methods for Approximate Solution of Inverse Problems\"\n- An other (minor) weakness is that I did not find the numerical experiments very compelling. I would have rather liked to see whether Reg-SGD can help find solutions which generalize better (or no numerics at all).", "was_revised": true, "final_justification": "This is a serious contribution and all the issues I raised have been addressed by the authors.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent in evaluating our work and your overall positive feedback. We agree that our connection to the literature of classical deterministic optimization came short and we will make sure to include much more details in our revised manuscript as described below. In the following, we provide point by point responses to your comments. To allow full revision, we give full details how our updated manuscript will look like.\n\n# W1/Q1: Related literature\nThank you very much for your careful assessment of our literature review and for pointing out important research areas that were previously omitted. We revised Section 1.3 to include additional related work in the areas of constrained optimization and iterative regularization methods. More importantly, we added a detailed discussion of the connection between Tikhonov regularization and constrained convex optimization. We hope these revisions significantly clarify our contributions and better situate our work within the relevant research landscape.\n\nRegarding assumption (7) we now remark that: Our requirements in (7) are very similar to the ones needed in the deterministic setting [Bakushinsky & Goncharsky (1994), Thm 5.1 and Thm 5.2] and are motivated by the corresponding deterministic result in continuous time [Cominetti et al. (2008), Thm 2.2].\n\n## Action 1 (Updated Sec. 1.3): \n\nWe include the following:\n\n**Deterministic Tikhonov regularization** ..... derived in [5]. More generally, differential inclusions for constrained convex optimization problems have been intensively studied in [9, 10, 11, 26, 57]. In App. C.2, we provide more details and illustrate the relation to Tikhonov regularization \n... Discrete time algorithms with decaying Tikhonov regularization have been analyzed in the context of iterative regularization schemes. For instance, in chapter 5 of [14] iterative regularization is discussed to solve variational inequalities covering (3) for convex $f$ as a special case. Under certain conditions on the regularization decay and the step sizes, strong convergence to the minimum-norm solution can be guaranteed. A related analysis has been considered for non-linear IPs [15]. In the specific application to IPs, (3) is also known as the modified Landweber iteration, where convergence is mainly studied for nonlinear forward models using a-priori and a-posteriori stopping rules  [15, 44, 61]. The theoretical analysis is conducted in a non-convex setting and relies on the so-called tangential cone condition.\n\n..... Finally, in the context of IPs the regularization properties of (vanilla) SGD have been analyzed for linear forward [39, 41, 43]  and non-linear models [42] based on a-priori and a-posteriori stopping rules.\n\n## Action 2 (Updated Sec C.2):\n\nWe begin Sec C.2 with:\n\nBefore discussing the convergence rates for reg-GD, we want to relate our analysis to the literature in convex optimization. For this purpose we formulate our task of finding the minimum-norm solution as constrained optimization problem in form of\n$$ \\min_{x\\in X} 1/2\\lVert x\\rVert_{X}^2 \\quad \\text{s.t.}\\quad x\\in C:=\\arg\\min_{y\\in X} f(y). $$\nThis naturally relates to the task of solving general variational inclusions of form\n$$ 0 \\in A(x) + N_C(x) $$\nwhere $A$ denotes a (maximal) monotone operator and $$N_C(x) = \\lbrace v\\in X: \\langle v,w-x\\rangle\\le 0\\quad \\forall w\\in C\\rbrace$$ is the normal cone of a closed convex set $C$ at $x$. In our setting the operator $A(x)=\\nabla_z 1/2\\lVert z\\rVert_{X}^2\\mid_{z=x} = x$ is strongly monotone. Another important class of problems studied in this context are hierarchical optimization problems of finding points in the set\n$$ S = \\arg\\min \\lbrace g(x)\\mid x\\in\\arg\\min f(x)\\rbrace $$\nfor two convex functions $g$ and $f$. This relates to our setting by choosing $g(\\cdot) = \\lVert \\cdot\\rVert_{X}^2$.\n\nTo solve these types of problems, one popular approach includes penalty based methods which are described as differential inclusion\n$$\n    \\dot x(t)+A(x(t))+\\beta(t)\\partial f(x(t))\\ni0 \\quad(21)\n$$\nwhere the penalty parameter $\\beta(t)$ tends to infinity. As demonstrated in [9], when the monotone operator is a sub-differential $A = \\partial g$, then we may equivalently consider the differential inclusion \n$$\n    \\dot x(t)+\\lambda(t)\\partial g(x(t))+\\partial f(x(t))\\ni0\n$$\nwith vanishing parameter $\\lambda(t)$. In summary, analyses of the above differential inclusion can be translated to the differential equation\n$$\n    \\dot x(t)+\\nabla f(x(t))+\\lambda(t)x(t) = 0 \\quad (22)\n$$\ndescribing the regularized steepest descent in continuous time. Note that reg-GD defined in (3) can be interpreted as explicit Euler discretization of (22).\n\n## Action 3 (additional discussion on related work):\nWe added Sec C.2.1:\n\n**C.2.1 Related work**\n\nThe analysis of dynamical systems corresponding to (21) with $\\partial f = 0$ dates back to the 1970s. For instance, in [13], it was shown that for $A = \\partial g$, where $g$ is l.s.c., proper, and convex, the trajectory converges weakly to a minimizer of $g$. More generally, for maximal monotone operators $A$, the ergodic average of the trajectory converges weakly to a point in $A^{-1}(\\{0\\})$ [22]. \n\nThe penalty-based differential inclusion (21) was introduced in [9], where the authors established weak ergodic convergence (and even strong convergence for strongly monotone operators $A$) under the integrability condition\n$$\n\\int_0^{\\infty} \\beta(t) \\Big[ \\Psi^* \\big(p/\\beta(t)\\big) -\\sigma_C\\big(p/\\beta(t)\\big) \\Big] dt < \\infty, \\forall p\\in range(N_C),\n$$\nwhere $\\Psi^*$ denotes the Fenchel conjugate of $\\Psi$, and $\\sigma_C$ is the support function of the set $C$. This condition is now commonly referred to as the *Attouch–Czarnecki condition*.\n\nNote that a similar condition arises in our analysis as the final requirement in (6). While our condition can be characterized via the Lojasiewicz inequality, the Attouch–Czarnecki condition can be characterized using a quadratic error bound of the form\n$$\n\\Psi(x) \\ge C dist(x, C)^2,\n$$\nimplying that\n$$\n\\Psi^*(p) - \\sigma_C(p) \\le \\|p\\|^2/(2C),\n$$\nsee for instance [9,11] for more details. In this case, the Attouch–Czarnecki condition is guaranteed under integrability conditions on the penalty function $\\beta$.\n\nIn the discrete-time setting, the Attouch–Czarnecki condition translates into a summability condition involving both the penalty sequence and the step sizes. For instance, [57] introduces a coupled gradient method with exterior penalization, leading to the condition\n$$\n\\sum_{n \\in \\mathbb{N}} \\alpha_n \\beta_n \\Big[ \\Psi^*(p/\\beta_n) - \\sigma_C(p/\\beta_n) \\Big] < \\infty\\,.\n$$\nHere, the author considers the case where $A = \\nabla g$ and both $\\nabla f$ and $\\nabla g$ are Lipschitz continuous, establishing weak convergence under convexity of $g$, and strong convergence when $g$ is strongly convex. Other results in the discrete-time setting include splitting-based discretization schemes [10, 11, 26]  whose convergence analysis rely on some similar variant of the Attouch–Czarnecki condition.\n\n## Important references\n- [9] Attouch & Czarnecki (2010)\n- [10] Attouch et al. (2012)\n- [11] Attouch et al. (2011)\n- [14] Bakushinsky & Goncharsky (1994)\n- [44] Kaltenbacher (2008)\n- [57] Peypouquet (2012)\n- [61] Scherzer (1998)\n\n# Q2: Relation of source condition and Lojasiewicz condition \nThank you very much for pointing us to this interesting connection. Assuming that $y\\in R(A)\\oplus R(A)^\\perp$, one can indeed verify that $x_\\lambda \\in X_{\\nu,\\delta} = \\lbrace (A^* A)^{\\nu/2} w\\in X\\mid w\\in X,\\lVert w\\rVert_{X}\\le \\delta\\rbrace$ due to the SVD representation of $x_\\lambda$. More precisely, let $x^\\dagger = \\sum_{n\\in\\mathbb N} \\sigma_n^\\nu \\langle w,v_n\\rangle_{X} \\,  v_n$, then we have\n$$\nx_\\lambda = \\sum_{n\\in\\mathbb N} \\sigma_n^\\nu\\sigma_n^2/(\\sigma_n^2 + \\lambda) \\langle w,v_n\\rangle_{X} v_n = \\sum_{n\\in\\mathbb N} \\sigma_n^\\nu \\langle  w_\\lambda,v_n\\rangle_{X} v_n\n$$\nwith $\\lVert w_\\lambda\\rVert_{X}^2 \\le \\sup_{n} \\sigma_n^2/(\\sigma_n^2+\\lambda) \\lVert w\\rVert_{X}^2 \\le \\lVert w\\rVert_{X}^2$. Hence, $x_\\lambda \\in X_{\\nu,\\delta}$ whenever we assume $x^\\dagger \\in X_{\\nu,\\delta}$. \n\n## Action: \nWe will cite the mentioned paper and discuss the relation of the Lojasiewicz condition to linear IP.\n\n# Q3: Preventing explosion of SGD\nThank you for your question. It is true that boundedness (bds) of the iterates of SGD, its necessity and its consequences is an active field of research. The recent work of Liu & Yuan (JMLR 2024) shows a.s. bds of vanilla SGD under convexity and the ABC-condition for step-sizes $\\alpha_k = C_\\alpha k^{-q}$ with $q \\in (2/3,1)$, see Thm 13 therein. Using vanishing Tikhonov regularization, we can go as low as $q \\in (1/2,1]$ for a.s. bds and $q \\in (0,1]$ for bds in $L^2$. In the case $q \\in (0,1/2)$ bds is especially difficult to achieve, since the corresponding martingale (the sum over all of the accumulated noise terms) does not converge. \n\nIt is true that for convergence of the function value (or convergence to the set of global minima), bds of the trajectory is not necessarily required (see e.g. Louzi (2024) or Garrigos et al. (2025)). Still, there are certain benefits from having bounded (or convergent) trajectories, such as benefiting from averaging over the iterates for objective functions satisfying the PL-inequality, see e.g. Dereich & Kassing (EJP 2023). Bds can easily be achieved for coercive functions without a Tikhonov regularization (see e.g. Thm 1 in Mertikopoulos et al. (NeurIPS 2020), Lem D.1 in Dereich & Kassing (EJP 2023), or Lem 1.6 in Louzi (2024)). However, in this work we show that for general (possibly non-coercive) convex functions a vanishing Tikhonov regularization is strong enough to imply bds of the paths if the decay of the regularization parameter is not too fast.\n\n## Action: \nWe will include a paragraph with the above discussion.\n\n# Q4: ERM\nThank you very much, we will add a comment."}, {"review_id": "018chiOz1O", "reviewer": "Reviewer_Ahp1", "summary": "This paper provide convergence analysis for reg-SGD in optimization problems under convexity and  Łojasiewicz conditions problems. It establishes the $L^2$ and almost-sure convergence of SGD under the ABC conditions of the stochastic noise.", "questions": "1. Could you please compare with the following recent work?\n\nBoursier, E., Pesme, S., & Dragomir, R. A. (2025). A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation. arXiv preprint arXiv:2505.20172.\n\n2. Are there any new insights that could potentially be useful be practice according to your theory?", "limitations": "See the weakness part.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strength** The paper is clear is easy to follow. I believe the result of this paper is correct.\n\n**Weakness** \n\n1. The result is expected and not surprising to me. I think it is well-known that with regularization the algorithm will converge to the min-norm solution, although the existing analysis may not be comprehensive as this paper. I do not think this paper bring new insights to the community. \n\n2. The paper only studies problems under convexity and  Łojasiewicz conditions problems, but it lacks analysis of for general nonconvex optimization problems, which are the most widespread applications of SGD (or reg-SGD). For instance, neural network training.", "was_revised": true, "final_justification": "I acknowledge the contribution on the \" convergence rates and as a consequence the tuning of step-size vs. decay of regularization\" and thus raise the score to 4.", "rebuttal": "Dear reviewer,\n\nWe thank you for the time spent in evaluating our work. In the following, we will clarify your concerns by providing point by point responses to your comments.\n\n## Weaknesses 1\nYou say \"The result is expected and not surprising to me. I think it is well-known that with regularization the algorithm will converge to the min-norm solution\". It seems like when looking at our article, you completely overlooked the main results - the delicate balance of decaying regularization parameter and step sizes. In particular, our derived convergence rates. We will sharpen the abstract in the final version to hightlight these contributions even more. When considering access to the minimizers $x_\\lambda$, convergence to the min-norm solution $x_\\ast$ in the sense that $\\lVert x_\\lambda-x_\\ast\\rVert \\to 0$ is not surprising. However, when considering an iterative regularized optimization scheme it is far from obvious how to schedule the interplay between the regularization parameter and the step-sizes in order to achieve fast convergence to $x_\\ast$. See for instance Chapter 5 in \"Ill-Posed Problems: Theory and Applications\", and in particular Theorem 5.1 and 5.2. In our stochastic setting this involves additional challenges to verify our Theorem 2.1 and 2.2.\n\nMoreover, we emphasize that the **main contribution of the article are the convergence rates** and as a consequence the tuning of step-size vs. decay of regularization. For graphical illustrations please consult our examples. Specifically in Figure 5, you can observe that a too fast decay of the regularization leads to non-convergence.\n\n## Weakness 2 \nFirst, it should be noted that our main statements only require convexity and not validity of a Lojasiewicz inequality. We use the Lojasiewicz inequality only as an example where $\\lVert x_\\lambda-x_\\ast\\rVert$ can be quantified and, thus, optimal hyperparameter schedules can be derived explicitly.\n\nMoreover, it is well-known that Lojasiewicz/gradient domination-assumptions are relevant for the training of neural networks. Gradient domination holds for instance locally for over-parameterized NNs, see for instance Liu et al. \"Loss landscapes and optimization in over-parameterized non-linear systems and neural networks\". We acknowledge that a comprehensive theoretical analysis in the general non‑convex setting would be highly relevant for understanding deep neural network training. However, before tackling non‑convex problems, it is essential to build a solid foundation by studying the convex case. Insights from convex analysis frequently yield valuable theoretical and practical tools that can be adapted to non‑convex scenarios, as also recently illustrated by the findings in \"The Surprising Agreement Between Convex Optimization Theory and Learning‑Rate Scheduling for Large Model Training\" (ICML 2025).\n\n## Question 1\nThe work \"A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation\" analyzes a gradient flow (GF) with constant Tikhonov regularization from a dynamical systems point of view. It considers a family of GF trajectories parametrized by the regularization parameter and shows that, after an appropriate time-speedup, the limiting dynamics as $\\lambda \\to 0$ is a GF on the manifold of minima that minimizes the $\\ell^2$-norm. This work is conceptually different from our analysis. We consider **a single** optimization trajectory with **time-vanishing** Tikhonov regularization. This allows us to prove convergence results, derive convergence rates and present optimal hyperparameter schedules. The work \"A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation\" considers a **family** of optimization trajectories with **fixed** Tikhonov regularization. Notably,  GF with fixed Tikhonov regularization only finds $x_\\lambda \\neq x_\\ast$. Not only the setting is fundamentally different, but also the statements and implications. While the work \"A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation\" presents a **qualitative** result, deriving a limiting ODE as $\\lambda \\to 0$ and $t\\to \\infty$, one of the main contributions of our work to present **quantitative results** deriving convergence rates and optimal hyperparameter schedules. \n\n### Action\nWe will add a paragraph mentioning  applications of Katzenbergers theorem for optimization schemes in machine learning.\n\n## Question 2\n It is non-trivial to choose the decreasing regularization (depending on the step-sizes) to achieve (fast) convergence to the min-norm solution. This has immediate practical relevance, as acknowledged also by other reviewers and demonstrated in our numerical experiments.\n\nIn Figure 2,9 and 12 we give a lower bound on the rate of convergence for (S)GD depending on the hyperparameter schedules. In Figure 5 and 8 we show the importance of balancing the regularization decay with the step-size decay.\n\nThe main contribution of this work is precisely to quantify the heuristic idea that, as long as the regularization parameter decays sufficiently slow, reg-SGD converges to the minimum-norm solution and to present optimal hyperparameter schedules that can be used in practice to achieve fast convergence to $x_\\ast$."}, {"review_id": "P5hYNmSCkb", "reviewer": "Reviewer_M92n", "summary": "This paper analyzes regularized SGD for the minimization of convex smooth function, with vanishing Tikhonov regularization parameter and proves convergence to the minimum norm solution. The analysis highlights properties about the the flow of SGD and stable learning, how to tune the step sizes and regularization parameters, and is supported by experiments.", "questions": "1) The authors might consider moving some of the experiments in Section A.2, which highlight the optimality of the theoretical schedules, to the main body of the paper, perhaps sacrificing one of the real examples of Section 3? I would understand the choice not to do this, but I do feel these appendix experiments are quite important for the point of the paper. \n2) Can the authors please do a thorough spelling/grammar check?\n3) Empirically, is the method sensitive to the tuned parameters? Can there be some computational savings by using approximations (throughout)?", "limitations": "Some limitations are discussed in the conclusion, mostly pointing out future directions.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well written, easy to follow, and motivates the problem well while highlighting the novelty. The related work is thorough and the theoretical results are clearly stated.\n\nQuick note to check spelling and grammar, I spotted a few errors (e.g. \"continuous a line\" on line 83). \n\nSection 3.1 felt oddly placed or oddly named. I understand wanting to work through an example later in the paper, but motivating its importance is usually done quite early (I don't have a strong preference just wanted to raise this point).\n\nThere are many experiments in the appendices, some of which feel crucial to the main results. It is likely due to space concerns, but perhaps the authors may wish to re-assess which experiments are included in the main body.", "was_revised": true, "final_justification": "I still believe this is a solid paper and contribution (especially after the modifications the authors will make), so my rating stays at an Accept.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work and for the positive feedback. \n\n## W1/Q2. Grammar corrections.\nThank you for bringing this to our attention. We will carefully proofread the manuscript to correct any grammatical or typographical errors and ensure that the revised version is polished.\n\n## W2/W3/Q1. Content of Section 3.\nWe appreciate your positive feedback on our additional experiments in the appendix. In case of acceptance, we will make use of the additional content page to integrate key experimental results into the main body of our paper. Moreover, we will explore the option of replacing parts of Section 3.1 with more numerical experiments. \n\n## Q3. Sensitivity to tuning parameters. \nThis is a very important question. The only hyperparameters to tune are the initial step size and the initial regularization parameter. We observed that reg-SGD exhibits significantly lower sensitivity to the initial step size compared to vanilla SGD. From our experiments, one can choose even larger initial step sizes for reg‑SGD without encountering the instability that plagues standard SGD. Regarding the regularization parameter, initializing with values that are too small can lead to transient instabilities. Choosing slightly too large initial values for the regularization will be corrected during the iterations by the scheduled decrease.\n\n### Action.\nWe will complement these findings with an additional numerical experiment that systematically compares the three methods from Section 3.2 over a range of initial step sizes and regularization parameters."}, {"review_id": "h8kiZcas1H", "reviewer": "Reviewer_25Se", "summary": "This paper studies the stochastic gradient descent algorithm with Tikhonov regularization (reg-SGD), applied to the minimization of a convex smooth function on a Hilbert space. Theoretical results show that the iterates of the reg-SGD algorithm converge in norm, almost surely, to the minimum-norm solution with a careful choice of the step size and regularization parameters and under a certain condition on the minimum norm solution itself. When the latter assumption cannot be verified based on problem-specific structures, such as the source condition or the Łojasiewicz inequality, a second result on convergence in norm in the mean squared sense may still hold with more lenient assumptions. The authors offer both a theoretical analysis and a practical guidance for the optimal scheduling of the decaying step size and regularization parameters. Practical importance and feasibility of the algorithm are demonstrated on a Radon transform inversion arising in X-ray tomography problems.", "questions": "1. As elaborated in the Weaknesses Section, I suggest drawing concrete connections to the effects of minibatch sampling throughout the work. Specifically, this may be done through suggesting how **Assumption 1.2** may be verifiable and including the minibatch size as a tuning parameter in **Section 3.2**. Space constraints may be overcome by relegating them to the Supplements.\n2. How pliable do you believe the analysis of the method is to the following two extensions: (i) problems with *noise*, where a minimum-norm solution may not be optimal, as acknowledged in Section 4; and, (ii) problems with a *nonlinear operator*, which naturally arise in PDE parameter identification problems? It is conceivable both that the noise is also present in (ii) and that the need for SGD arises from a large number of independent observations.\n3. Section 1.3 leaves somewhat open the connection between this work and the parallel line of investigation into the generalizability of \"flat minima\" (and whether SGD can reliably find it). Can the analysis given in this work shed a light on a better understanding of when the SGD-found optimal are generalizable? Is the suggested generalizability in machine learning community due to the SGD \"imitating\" the effects of Tikhonov regularization, and if so, should the introduction of reg-SGD imply that the engineers revise their existing scheduling of parameter decay and early stopping rules to prevent \"excessive\" regularization?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* Strengths\n  1. The problem is clearly motivated, both theoretically and in practical examples and the analysis of the regularized SGD algorithm is technically solid with no blatant flaws.\n  2. Extension of the by now various results on SGD algorithm to Hilbert spaces and beyond is an interesting problem in and of itself in applied mathematics. The authors have made a contribution towards connecting the existing machine learning point of view towards SGD algorithms and the existing, albeit somewhat detached, literature on the analysis of Tikhonov regularization. \n\n* Weaknesses\n  1. The current exposition seems to only analyze SGD \"at large\" without delving into the specific ways in which the existing SGD algorithms are implemented. More specifically: in many machine learning tasks, and also in the tomography problem investigated in Section 3.2, the need for SGD often arises from the large number of observations, presumably \"independent\" in a precisely probabilistic or looser sense, hence the replacement of the full-scan gradient evaluation with a minibatch gradient evaluation. There are at least two sections in this work that may benefit from a more concrete connection to the assumption of gradient noise arising from minibatch sampling: **Assumption 1.2**, which I believe will be verifiable in this case; and the empirical investigations in **Section 3.2**, where the trade-offs involved in minibatch size and the performance of the reg-SGD remain unexplored.", "was_revised": true, "final_justification": "Weakness and Questions raised by the current reviewer were satisfactorily addressed by the authors. I suggest the promised additions and commentaries regarding Weakness 1 and Question 2 to be incorporated in the revision.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work and your overall positive feedback. \n\n# W1/Q1. Incorporation of mini-batch gradient evaluation:\n\nThis is an important point that we would like to incorporate into the revised version of our manuscript. When introducing a mini-batch scheme, one can easily verify Assumption 1.2. Since the sample across the mini-batch is usually assumed to be i.i.d., we can simply apply Bienaymé's identity to show a variance reduction and, therefore, the verification of the ABC condition. Another interesting line of study would be the derivation of feasible step sizes and regularization parameters when the mini-batch size is increased dynamically. \n\n## Action:\nIn our revised manuscript, we will add a discussion about empirical risk minimization and the incorporation of a mini-batch sampling scheme. Moreover, we will discuss the verification of Assumption 1.2 within this setting.\n\n# Q2. Possible extensions\n## Q2.1. Noisy observations: \nThe extension of our analysis to the noisy observation setting is planned for future work. In particular, there are several papers on the application of SGD in the context of linear inverse problems, where the least square problem is viewed as finite sum loss. See for instance: \n- \"On the regularizing property of stochastic gradient descent\"\n- \"On the discrepancy principle for stochastic gradient descent\"\n- \"On the saturation phenomenon of stochastic gradient descent for linear inverse problems\"\n\nThe analysis for vanilla SGD is usually based on the fact that in the finite sum setting the iterates remain in the range of the adjoint of the forward operator. In a noisy operator evaluation setup this property might be violated. Using our reg-SGD analysis we will be able to derive a-priori and even a-posteriori stopping rules to ensure convergence as classical regularization method. \n\n## Q2.2. Nonlinear models: \n\nSimilarly as the extension to the noisy observation setting, we are planning to extend our analysis to the non-convex setting in the context of non-linear inverse problems. There has been much work on deterministic iterative regularization methods for non-linear inverse problems which are based on a so-called tangential cone condition, see for instance \"Iterative Regularization Methods for Nonlinear Ill-Posed Problems\". This condition allows to derive recursive inequalities and to construct suitable Lyapunov functions. More precisely, we anticipate that our analysis can be used to extend the modified Landweber iteration introduced by Scherzer (\"A modified Landweber iteration for solving parameter estimation problems\") to the stochastic setting. A similar line of work has already investigated the extension of the Landweber iteration to the stochastic setting (which corresponds to vanilla SGD), see \"On the convergence of stochastic gradient descent for nonlinear ill-posed problems\".\n\n## Action:\n\nWe will add references to the iterative regularization methods applied in linear and non-linear inverse problems. Moreover, we include additional comments on our planned application of reg-SGD in this context.\n\n# Q3. Relation to flat minima\nThank you for this interesting question. In fact, there seem to be many parallels between Tikhonov regularization, the minimum-norm solution and flat minima with their generalization properties. \nFirst, using Tikhonov regularization for convex learning problems is known to stabilize solutions, prevent overfitting and can be used to prove PAC learnability of  convex, smooth and bounded learning problems (see Theorem 13.1 and Corollary 13.11 in \"Understanding Machine Learning: From Theory to Algorithms\"). \n\nAnother similarity can be drawn by looking at works applying Katzenbergers theorem. In \"A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation\" the authors show that an appropriate time speedup of gradient flow trajectories leads to a gradient flow on the manifold minimizing the $\\ell^2$-norm as $\\lambda \\to 0$. A similar result for flat minima can be found in \"What Happens after SGD Reaches Zero Loss? –A Mathematical Framework\" and \"Singular-limit analysis of gradient descent with noise injection\" where it is shown that SGD (after an appropriate time change) leads to an SDE on the manifold of minima that aims to minimize the flatness of the minimum as the learning rate tends to zero. \nIt seems to us that the concept of \"flat minima\" is in some sense similar to the concept of the minimum-norm solution in the context of non-convex optimization.\n\nFinally, we want to point to the connection between introducing Tikhonov regularization and using Dropout (see e.g. \"Dropout Regularization Versus l2-Penalization in the Linear Model\") and recent findings in \"The Surprising Agreement Between Convex Optimization Theory and Learning‑Rate Scheduling for Large Model Training\" (ICML 2025)."}]

Author rebuttal:

Meta-review: **Summary:** 
This paper investigates the property of the Tikhonov regularized stochastic gradient descent (reg-SGD) algorithm for solving convex and $L$-smooth objectives in separable real Hilbert space. Under an ABC-type assumptions on the stochastic noise, convergence of the last iterates of reg-SGD is presented. For polynomial stepsize and regularization schedules, theoretical guarantees are also provided. The theoretical result is supported with numerical experiments. 


**Strength:**
 - A well presented paper in terms of written, clarity.
 - Important contributions to the understand of SGD algorithm.
 - Weak assumptions, only requires an ABC-type assumption and does not need bounded gradient assumption. 

**Weakness:**
 - The organization of the paper can be further improved. 
 - Missing discussion on connections with existing literature.
 - The first submission contains mathematical flaws.

**Discussion summary:** 
The paper provides a solid theoretical analysis of SGD with Tikhonov regularization, and the findings make an important contribution to understanding the method. During the rebuttal phase, the reviewers’ concerns were satisfactorily addressed. The authors are advised to revise the manuscript carefully, especially given that the initial submission contained mathematical errors.
Decision: Accept (poster)