New Bounds for the Last Iterate of the Stochastic subGradient Method Guglielmo Beretta1 , Tommaso Cesari2 , Roberto Colomboni3 , and Andrea Paudice1 1
Department of Computer Science, Aarhus University, Aarhus, Denmark School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada 3 School of Mathematics, University of Bristol, Bristol, United Kingdom [email protected], [email protected], [email protected], [email protected]
arXiv:2606.24879v1 [math.OC] 23 Jun 2026
2
Abstract We study the last iterate of the stochastic subgradient method for one-dimensional convex √ Lipschitz objectives. For a fixed horizon n, we consider the standard fixed stepsizes η = Θ(1/ n). We prove that, for such stepsize policies, under additive i.i.d. subgradient√noise with uniformly bounded variance, the last iterate features an optimization error of order 1/ n, thereby removing the extra (log n) factor present in existing generic bounds. On the other hand, √ we show that without the i.i.d. assumption, the optimization error can be of order (log n)/ n. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in [9].
1
Introduction
The (projected) Stochastic subGradient Method (SsGM) [4] is arguably one of the most popular algorithms in constrained stochastic optimization. Its success is largely due to its efficiency and provable performance. Classical analyses for convex Lipschitz objectives, which are also the focus of this work, typically control the expected optimization error of the average iterate [16, 15, 12, 2]. In the finite-horizon setting, where the number of iterations n is known in advance, one may use a √ standard fixed stepsize (ηi )1≤i≤n ≡ η with η = Θ(1/ n), and return the average iterate1 . Assuming uniformly bounded variance of the stochastic subgradients and finite diameter of the feasible set, √ averaging yields optimization error of order 1/ n, which is optimal for this class of problems [16, 1]. More recently, attention has shifted to the last iterate of the stochastic subgradient method [18, 6, 7, 13, 3]. This is the iterate naturally returned in practice, due to its simplicity and often superior empirical performance. However, last-iterate guarantees are substantially more delicate. The best √ √ known upper bound for the standard fixed-stepsize choice η = Θ(1/ n) is of order (log n)/ n, leaving an extra logarithmic factor compared with the optimal rate achieved by averaging [18]. This logarithmic loss is known to be unavoidable even in deterministic setting if the dimension is allowed to scale with the horizon, for instance when d ≈ n [20]. However, that does not settle the problem in fixed dimension. In fact, this is precisely the question asked in Open Problem 1 of [9]. 1
Throughout the paper, this notation has its usual finite-horizon meaning: there are constants 0 < c ≤ c < ∞ and √ n0 ∈ N such that, for every n ≥ n0 , all iterations use the same stepsize η = cn / n with cn ∈ [c, c]. Constants hidden in asymptotic notation may depend on c and c, but not on n.
1
Contributions. In this work, we answer this question negatively. More precisely, for every choice of constants 0 < c ≤ c < ∞, for every sufficiently large horizon n, and for every fixed stepsize √ η = cn / n with cn ∈ [c, c], we construct a one-dimensional stochastic convex optimization instance √ on which the last iterate suffers expected optimization error of order (log n)/ n (Theorem 3). Thus, averaging is not just a proof device: without additional structure, the last iterate is genuinely suboptimal even in dimension one. On the positive side, still for d = 1, we show that if the additive subgradient noise is both state-independent and time-homogeneous, then every standard √ √ fixed-stepsize family η = Θ(1/ n) yields the optimal last-iterate order 1/ n, with an explicit constant depending only on the problem parameters and on the hidden constants in the Θ notation (Theorem 2).
2
Related work
Existing last-iterate bounds. Besides the standard constant stepsize used in the finite-horizon setting, several alternative stepsize policies have been proposed to improve the behavior of the last iterate [7, 13]. [7] were the first to introduce a non-standard finite-horizon policy under which the √ last iterate recovers the optimal 1/ n rate. [13] later proposed a different finite-horizon policy with the same optimal guarantee. In the anytime setting, where the horizon is not √ fixed in advance, the standard choice is a decreasing stepsize. [18] showed that, for ηi = η/ i, the last iterate √ has optimization error of order at most (log n)/ n, and [6, 5] showed that this logarithmic factor is unavoidable even in the deterministic setting. Improved anytime guarantees can be obtained with more refined stepsize policies (e.g., see [17]), but an extra polylog(n) factor is necessary in infinite-dimensional, or sufficiently high-dimensional, settings [10]. Fixed-dimensional setting. The fixed-dimensional case is much less understood. [9] supported the possibility of removing the logarithmic factor by showing that, in dimension d = 1, for the absolute-value objective and a specific stochastic oracle model, the algorithm dynamics reduce to a √ biased one-sided random walk and the optimal 1/ n rate is attained. [11] extended this positive result to a class of one-dimensional piecewise-linear convex functions under sub-Gaussian noise. They √ also complemented their upper bounds with a lower bound of order (log d)/ n, which, however, does not rule out the optimal rate when d is fixed. In comparison, our positive result applies to arbitrary one-dimensional convex Lipschitz objectives, under a state-independent time-homogeneous additive √ noise model with finite second moment, and it is uniform over the stepsize family η = Θ(1/ n). On the other hand, our lower bound shows that, under the sole uniformly bounded variance assumption, the logarithmic factor is unavoidable even in d = 1 for the same stepsize family.
3
Problem Setting
Notation. Throughout, k and n will always denote natural numbers. For a fixed fuction f and x ∈ X , let us define ∆(x) := f (x) − f⋆ and dist(x, X⋆ ) := inf z∈X⋆ |x − z|. Given a closed convex set S ⊆ R, we write ΠS (x) := argminz∈S |x − z| for the orthogonal projection of x ∈ R onto S. We introduce an abuse of notation for closed intervals: given −∞ ≤ a ≤ b ≤ +∞ such that (a, b) ∈ / {(−∞, −∞), (+∞, +∞)}, we write [a, b] := {x ∈ R : a ≤ x ≤ b}, which is a subset of R even if a and/or b are infinite. With this notation, if S := [a, b] then ΠS (x) = max{a, min{x, b}} for every x ∈ R. Given a convex S ⊆ R, a point x ∈ S and a convex 2
function h : S → R, we call g ∈ R a relative subgradient of h at x with respect to S and write g ∈ ∂S h(x) if h(y) ≥ h(x) + g · (y − x) for every y ∈ S. For a convex function h on an interval, we write D− h and D+ h for its left and right derivatives, whenever they are defined. We use the standard fact that, if g ∈ ∂S h(x), then D− h(x) ≤ g whenever D− h(x) exists, and g ≤ D+ h(x) whenever D+ h(x) exists. For all x ∈ R, we denote by δx the Dirac probability measure at x. Problem Formulation. We consider the following optimization problem: minimize f (x) x∈X
under the following assumptions. Assumption 1 (Feasibility Domain). X ⊆ R is closed and convex, and X⋆ := arg minx∈X f (x) ̸= ∅. Moreover, f⋆ := minx∈X f (x) ∈ R. Assumption 2 (Convexity and Lipschitzness). f : X → R is convex and L-Lipschitz continuous on X. Assumption 2 implies that all secant slopes of f over X belong to [−L, L], and consequently,2 that ∂X f (x) ∩ [−L, L] ̸= ∅ for every x ∈ X . Under Assumptions 1–2, we will consider the following formulation of SsGM. For every trajectory, define the history Fk := σ(X1 , W1 , . . . , Wk−1 ),
k ≥ 1,
with the convention that F1 := σ(X1 ). Definition 1 (Projected Stochastic (sub)Gradient Method). Given an X -valued random variable X1 , a sequence of random variables (Wk )k∈N , a sequence of random variables (Gk )k∈N , where Gk ∈ ∂X f (Xk ) ∩ [−L, L] is Fk -measurable, and given η > 0, the stochastic (sub)gradient descent defines the iterates ∀k ≥ 1, Xk+1 := ΠX (Xk − η · (Gk + Wk )), (1) with ΠX (x) := argminz∈X |x − z| being the orthogonal projection of x ∈ R onto X . The term Wk can be regarded as an additive noise term that alters the value of Gk when updating Xk . The following condition is the additive-noise analogue of the conditional-unbiasedness and conditional-second-moment oracle condition described in [9]. The positive result strengthens this moment condition to a kernel-oracle specification and imposes both structural symmetries below. The lower bounds show that, even within this structured kernel class, imposing only one of the two symmetries is not enough to remove the logarithm. Assumption 3 (Variance Condition). There exists σ > 0 such that ∀k ≥ 1,
E[Wk | Fk ] = 0,
E[Wk2 | Fk ] ≤ σ 2 .
To separate the two structural properties that appear in our positive result, we strengthen the above into the following kernel-oracle formulation. 2
We observe that ∂X f (x) is an unbounded interval at every x that is a boundary point of X , and this motivates the explicit restriction |Gk | ≤ L given in Definition 1.
3
Assumption 4 (Centered additive kernel oracle). There exists σ > 0 and a specified family of probability kernels Qk : X × B(R) → [0, 1], k ≥ 1, such that, for every k ≥ 1, every x ∈ X , and every A ∈ B(R), Z Z w Qk (x, dw) = 0, w2 Qk (x, dw) ≤ σ 2 , R
R
and P(Wk ∈ A | Fk ) = Qk (Xk , A)
a.s.
The family of kernels is part of the oracle specification, not just an a posteriori representation along the realized trajectory: Qk (x, ·) is the noise law that the oracle would use at time k if the queried state were x. We can show that Assumption 4 implies Assumption 3: indeed, since Xk is Fk -measurable, Z E[Wk | Fk ] =
w Qk (Xk , dw) = 0, R
and E[Wk2 | Fk ] =
Z
w2 Qk (Xk , dw) ≤ σ 2 .
R
Thus Assumption 4 is not a weaker moment condition, but a more structured oracle specification: it describes the conditional law that would be used at every time and every queried state. Assumption 5 (Time-homogeneous additive kernel). The kernels in Assumption 4 do not depend on time: there exists a probability kernel Q : X × B(R) → [0, 1] such that Qk (x, ·) = Q(x, ·)
∀k ≥ 1, ∀x ∈ X .
Assumption 6 (State-independent additive kernel). The kernels in Assumption 4 do not depend on the queried state: for every k ≥ 1 there exists a probability measure µk on R such that Qk (x, ·) = µk (·)
∀x ∈ X .
If Assumptions 4, 5, and 6 all hold, then there exists a single centered law µ with second moment at most σ 2 such that Qk (x, ·) = µ(·) ∀k ≥ 1, ∀x ∈ X . Consequently, for every predictable SsGM trajectory, the realized noise sequence (Wk )k∈N is i.i.d. with law µ. Indeed, P(Wk ∈ A | Fk ) = µ(A) for every k and every Borel set A, and iterating this identity factorizes all finite-dimensional distributions. This constant-kernel case is the setting of the positive theorem. The lower bounds below show that neither symmetry is dispensable within the kernel-oracle class: there are logarithmic counterexamples satisfying Assumption 4 together with Assumption 5, and also logarithmic counterexamples satisfying Assumption 4 together with Assumption 6. Since Assumption 4 implies Assumption 3, both counterexample classes also satisfy the base second-moment condition. Random-field interpretation. Equivalently, one may imagine that at each round k the oracle samples a fresh random field (Wx,k )x∈X and returns WXk ,k . Time-homogeneity corresponds to these fresh fields being sampled from the same law at every time, while state-independence corresponds to all states having the same marginal noise law. The kernel formulation above is used to avoid measurability issues with random fields indexed by a continuum. 4
4
Results
The following theorem gives the positive side of the picture. We state both the pointwise fixed-stepsize √ estimate and its uniform consequence for standard fixed-stepsize families η = Θ(1/ n). Theorem 2. Suppose Assumptions 1, 2, 4, 5, and 6 hold, and let X1 ≡ x1 for some x1 ∈ X . For every n ≥ 2 and every fixed stepsize η > 0, the iterates generated by (1) satisfy dist(x1 , X⋆ )2 L2 + σ 2 2 E[∆(Xn )] ≤ η. (2) + (L + σ) + 2ηn 2 √ In particular, if η = cn / n, with 0 < c ≤ cn ≤ c < ∞, then dist(x1 , X⋆ )2 L2 + σ 2 1 E[∆(Xn )] ≤ + (L + σ)2 + c ·√ . (3) 2c 2 n We make first the following comments and defer the proof to Section 5. First, (3) is the precise √ upper-bound statement for the standard fixed-stepsize regime η = Θ(1/ n): the hidden constant √ may depend on c and c, but not on n. The 1/ n dependence in (3) is worst-case optimal up to universal constants. Second, the pointwise estimate (2) is slightly more informative: if one sets √ η = c/ n and optimizes over c > 0, then, when dist(x1 , X⋆ ) > 0, the optimizer is √ dist(x1 , X⋆ ) dist(x1 , X⋆ ) 3L2 + 4Lσ + 3σ 2 √ c⋆ = √ =⇒ E[∆(Xn )] ≤ n 3L2 + 4Lσ + 3σ 2 To prove Theorem 2, the first observation is that for every fixed stepsize η > 0 there is at least one index k⋆ with 1 ≤ k⋆ ≤ n such that E[∆(Xk⋆ )] ≤
dist(x1 , X⋆ )2 L2 + σ 2 + η. 2ηn 2
√ For η = c/ n, this becomes dist(x1 , X⋆ )2 L2 + σ 2 1 + ·c · √ . E[∆(Xk⋆ )] ≤ 2c 2 n
This bound is shown via a technique that is standard in the study of the average iterate of SsGM. We remark that k⋆ can be defined as the smallest k in argmin1≤k≤n E[∆(Xk )], and this makes k⋆ a deterministic constant once X , f , x1 , η, n, the noise law, and the predictable subgradient-selection rule are fixed. The first contribution of this paper is showing that, in our setting, E[(∆(Xk ) − ∆(Xk⋆ ))+ ] = E[(f (Xk ) − f (Xk⋆ ))+ ] ≤ (L + σ)2 η
for k⋆ ≤ k ≤ n,
(4)
which provides a bound of order η on how the expected suboptimality can degrade for the iterates √ following the k⋆ -th. In the standard fixed-stepsize regime η = Θ(1/ n), this is precisely of order √ 1/ n. In particular, taking k = n proves the desired inequality for the last iterate. The proof of (4) requires several new ideas. One key step is to argue conditionally on Fk⋆ , so that we may treat the value of f (Xk⋆ ) as a known constant, and we may reduce to a simpler problem where we want to deduce (4) knowing that for some q ≥ f⋆ we have f (Xk⋆ ) ≤ q. This is accomplished thanks to Lemma 10, where this additional information is leveraged to study E[(f (Xk ) − q)+ ] via the construction of one-sided random sequences that dominate the distance of Xk from a suitable enlargement of the sublevel {f ≤ q}. If a side of the domain is absent or infinite, the corresponding 5
one-sided sequence is either void or lives on [0, +∞); the latter case is handled by truncation and Fatou’s lemma in Corollary 9. We make use of the theory of general state-space Markov chains, and in particular of a Foster–Lyapunov-type argument [14], to show that the expected excess generated by these excursions remains of order η, uniformly over the remaining time. √ Under the hypotheses of Theorem 2, (3) states that every standard fixed-stepsize family η = Θ(1/ n) √ has last-iterate error controlled by C/ n, where C = C(c, c, dist(x1 , X⋆ ), L, σ) is independent of n. √ Thus this result uses the same interpretation of the Θ(1/ n) notation as the lower bound below. Our second contribution shows that the two kernel symmetries in Theorem 2 are both necessary in a minimax sense, and therefore Assumption 3 alone, is not enough to rule out the logarithm. In particular, the following shows that the log n factor is present even if this base condition is strengthened by imposing time-homogeneity alone, or by imposing state-independence alone. Theorem 3. Let X := [−2, 1], let f (x) := max{x, 0}, so that Assumption 1 holds with X⋆ := [−2, 0] and Assumption 2 holds with L = 1. Let g : X → [−1, 1] be the relative-subgradient selection associated with f defined by ( 0, x ≤ 0, g(x) := 1, x > 0. Fix constants 0 < c ≤ c < ∞. Then there exists n0 = n0 (c, c) ∈ N such that the following holds. For √ every n ≥ n0 and every cn ∈ [c, c], setting η := cn / n, the following hold: 1. There exists a noise process (Wk )k∈N satisfying Assumptions 4 and 5, but not Assumption 6, with σ 2 = 3 such that the iterates generated by (1) with some deterministic initialization X1 ∈ X⋆ and Gk := g(Xk ) satisfy E[f (Xn ) − f⋆ ] ≥
1 1 c log n η log ≥ 11 √ . 512 η 2 n
(5)
2. There exists a noise process (Wk )k∈N satisfying Assumptions 4 and 6, but not Assumption 5, with σ 2 = 1/2 such that the iterates generated by (1) with X1 ≡ 0 and Gk := g(Xk ) satisfy E[f (Xn ) − f⋆ ] ≥
1 1 c log n η log ≥ 11 √ . 128 η 2 n
(6)
We defer the proof to Section 6 and here we make some comments on the lower bound strategy. The two lower bounds given in Theorem 3 implement in different ways a common mechanism to displace the iterates far from the flat optimal set. For labels j = 1, 2, . . . , M , with a suitable M of order 1/η √ and hence of order n for standard fixed stepsizes, the mechanism specifies one rare large noise outcome for each label that is associated with the noise variables. The labels determine for which noise variables this outcome can occur: in the time-inhomogeneous construction, it can be sampled from the noise law at the time when j steps remain, while in the state-dependent construction it can be sampled from the noise law at a special state inside the flat optimal set. The noise outcome associated with label j has magnitude proportional to j, and the noise law at the corresponding time or state assigns this outcome probability mass of order 1/j 2 . Thus, when this outcome is sampled, the SsGM update displaces the iterate by order ηj. In the state-dependent construction, the non-rare noise outcomes move the iterate from one labeled state to the next, and, along the path where the earlier noise samples take these non-rare values, the state labeled by j is reached when about j steps remain. In both constructions, sampling the rare large outcome associated with label j produces terminal error of order ηj, so its expected contribution is of order η/j. Summing over √ j = 1, 2, . . . , M gives η log(1/η), which is of order (log n)/ n uniformly over all cn ∈ [c, c]. 6
5
Proof of Theorem 2
The proof is based on a monotone quantitative estimate on how the contribution of the term −η · Gk in (1) can move Xk toward or beyond a certain threshold separating Xk from X⋆ . This will involve the object introduced in the following definition: Definition 4. Let D ∈ R≥0 ∪ {+∞}, let I := [0, D], let m : I → R≥0 be non-decreasing and let η > 0. We define TI,m,η (z) := sup (s − η · m(s))+ , z ∈ I, 0≤s≤z
where (u)+ := max{u, 0}. We study some crucial properties of the object defined in Definition 4 Proposition 5. In the setting of Definition 4: 1. TI,m,η is non-decreasing; 2. The inequalities 0 ≤ TI,m,η (z) ≤ z hold for every z ∈ I; 3. TI,m,η is 1-Lipschitz on I; 4. For every z ∈ I,
Z z η·
m(s)ds ≤ z − TI,m,η (z) (z + η · m(z)) .
(7)
0
Proof. For brevity, set T := TI,m,η . 1. Follows directly by the definition. 2. For every 0 ≤ s ≤ z, we have 0 ≤ (s − ηm(s))+ ≤ s ≤ z. Taking the supremum over 0 ≤ s ≤ z gives 0 ≤ T (z) ≤ z. 3. Since T is non-decreasing, it is enough to prove that for every x, y ∈ I, with x ≤ y, T (y) − T (x) ≤ y − x. If x = y, this is trivial. If x < y, note that (
(8)
)
T (y) = max T (x), sup (s − ηm(s))+
.
(9)
x<s≤y
For every x < s ≤ y, monotonicity of m and the definition of T (x) yield s − ηm(s) ≤ y − ηm(x) ≤ y − x + x − ηm(x) ≤ y − x + T (x). Thus (s − ηm(s))+ ≤ y − x + T (x), Rand (9) gives (8). z 4. If T (z) = 0, then (7) follows by 0 m(s)ds ≤ z · m(z). If T (z) > 0, then for every 0 ≤ s∗ ≤ z, monotonicity of m gives Z s∗
Z z m(s)ds = 0
Z z m(s)ds +
0
m(s)ds ≤ m(s∗ ) · s∗ + m(z) · (z − s∗ ).
s∗
7
Multiplying by η and using that m(s∗ ) ≥ 0 and z ≥ s∗ , we get Z z m(s)ds ≤ η · m(s∗ ) · s∗ + η · m(z) · (z − s∗ ) η· 0
= (s∗ − s∗ + η · m(s∗ )) · s∗ + (z − s∗ + η · m(s∗ ) − η · m(s∗ )) · η · m(z) ≤ (z − s∗ + η · m(s∗ )) · z + (z − s∗ + η · m(s∗ )) · η · m(z) = z − s∗ − η · m(s∗ ) · (z + η · m(z)) . Then, Z z η·
z − s∗ − η · m(s∗ ) · (z + η · m(z)) 0≤s ≤z ∗ ∗ = z − sup (s − η · m(s )) · (z + η · m(z))
m(s)ds ≤ 0
inf ∗
0≤s∗ ≤z
= (z − T (z)) · (z + η · m(z)) , where the last step uses T (z) > 0. The next proposition provides the essential technical result to prove the key subsequent Lemma 10. Proposition 6. Let I = [0, D] be a closed bounded interval, let m : I → [0, L] be non-decreasing, and let η > 0. Let R ,R1 , R2 , . . . be an i.i.d. sequence of random variables such that E[R] = 0 and E[R2 ] ≤ σ 2 . Define the sequence (Zk )k∈N by ( Z1 ≡ 0, (10) Zk+1 = ΠI (TI,m,η (Zk ) − η · Rk ) k ≥ 1. Then:
Z Zk ∀k ≥ 1,
E 0
2 σ m(s)ds ≤ + Lσ · η. 2
Proof. Once again, set T := TI,m,η . We now discuss (10) in the framework of general state space Markov chains. The reader may find in Section C some basic notions and standard notation related to this topic and transition probability kernels. Consider the map Φ : I × R → I given by Φ(z, r) := ΠI (T (z) − η · r), which is continuous by continuity of T and of the projection ΠI . Let µ := Law(R) be the law of R, write B(I) for the Borel σ-field of I, and note that the map P : I × B(I) → [0, 1] defined by Z P (z, A) := I {Φ(z, r) ∈ A} dµ(r) = E[I{Φ(z, R) ∈ A}] R
is a transition probability kernel. Moreover, Zk+1 = Φ(Zk , Rk ), and the i.i.d. hypothesis on (Rk )k∈N shows that (Zk )k∈N is a time-homogeneous Markov chain on the compact state space I with transition probability kernel P and initial distribution δ0 . We assume the two following claims: Claim 7. There exists a probability measure π over (I, B(I)) that is invariant for the chain, i.e., πP = π. 8
(11)
Claim 8. There exists a bounded non-negative measurable function B : I → R and C ∈ R that satisfy the inequality Z z P B(z) − B(z) ≤ − m(s)ds + C · η, z ∈ I. (12) 0
More specifically, a solution is given by B(z) :=
z2 + 2Lz 2η
C :=
σ2 + Lσ. 2
(13)
Let B and C be as in (13), and let π be the invariant measure satisfying (11). Then, Z Z π(dz)B(z). π(dz)P B(z) = I
I
Therefore, integrating (12) with respect to π gives Z z 2 Z σ + Lσ · η. π(dz) m(s)ds ≤ 2 I 0
(14)
To conclude the proof, define (Yk )k∈N by taking Y1 ∼ π independent of (Rk )k∈N and setting ∀k ≥ 1,
Yk+1 = Φ(Yk , Rk ).
Then Yk ∼ π for every k by definition of π. Note that Z1 = 0 ≤ Y1 ∈ I, and we can show by induction that Zk ≤ Yk for every k ≥ 1, since for every fixed r the map s 7→ Φ(s, r) is non-decreasing, hence ∀k ≥ 1, Zk ≤ Yk =⇒ Zk+1 = Φ(Zk , Rk ) ≤ Φ(Yk , Rk ) = Yk+1 . Rz Using that z 7→ 0 m(s)ds is also non-decreasing, it follows that Z Zk E 0
Z Yk Z Z z 2 σ m(s)ds ≤ E m(s)ds = π(dz) m(s)ds ≤ + Lσ η, 2 0 I 0
where the last inequality is (14). We can extend Proposition 6 to the case D = +∞. Corollary 9. Let I := [0, +∞], let m : I → [0, L] be non-decreasing, and let η > 0. Let R, R1 , R2 , . . . be an i.i.d. sequence of random variables such that E[R] = 0 and E[R2 ] ≤ σ 2 . Define (Zk )k∈N by ( Z1 ≡ 0, Zk+1 = ΠI (TI,m,η (Zk ) − ηRk ) k ≥ 1, Then
Z Zk ∀k ≥ 1,
E 0
2 σ m(s)ds ≤ + Lσ η. 2
9
Proof. Fix an integer N ≥ 1. For M > 0, let IM = [0, M ], let TM := TIM ,m|I ,η , and define the M truncated chain ( (M ) Z1 ≡ 0, (M ) (M ) Zk+1 = ΠIM TM (Zk ) − ηRk k ≥ 1. By Proposition 6, "Z E
(M )
ZN
#
m(s)ds ≤
0
σ2 + Lσ η 2
for all M > 0.
(15)
On the event {max1≤k≤N Zk < M }, the truncated and untruncated chains coincide up to time N . (M ) Indeed, by induction, whenever Zk = Zk < M , we have TM (Zk ) = TI,m,η (Zk ); moreover, since the untruncated next state is still below M , the projections onto [0, M ] and [0, +∞) agree at the Rz (M ) next step. Hence ZN → ZN almost surely as M → +∞. Since z 7→ 0 m(s)ds is non-negative, Fatou’s lemma and (15) yield Z ZN E 0
"Z (M ) # ZN σ2 + Lσ η. m(s)ds ≤ lim inf E m(s)ds ≤ M →+∞ 2 0
Since N was arbitrary, the proof is complete. We can now prove a key lemma used to prove our positive result. Lemma 10. Suppose Assumptions 1, 2, 4, 5, and 6 hold, and let (Xk )k≥1 be generated by (1). Assume the existence of a positive integer k⋆ and some q ∈ R such that f (Xk⋆ ) ≤ q, deterministically. Then, for every k ≥ k⋆ , E[(f (Xk ) − q)+ ] ≤ (L + σ)2 · η. Proof. Let Sq := {x ∈ X : f (x) ≤ q}. The set Sq is non-empty because f (Xk⋆ ) ≤ q, and it is a closed convex subset of X . Set a := inf X ,
b := sup X ,
where the endpoints are allowed to be infinite, and (possibly) enlarge Sq to Eq := {x ∈ X : dist(x, Sq ) ≤ ηL} . This is a non-empty closed interval in X , possibly unbounded on either side. Let α := inf Eq ,
β := sup Eq ,
so that Eq = [α, β] ∩ X , using our extended-endpoint convention for intervals. We say that the left branch is present if α > a, and that the right branch is present if β < b. If a branch is not present, its contribution below is understood to be identically zero. Suppose first that the left branch is present. Then α is finite, and we define D(1) := α − a, 10
we note that 0 < D(1) ≤ +∞, with D(1) = +∞ when a = −∞, and we define I (1) := [0, D(1) ]. Let z (1) : X → I (1) ,
z (1) (x) := (α − x)+ ,
and h(1) : I (1) → R≥0 ,
h(1) (z) := f (α − z) − f (α).
The function h(1) is convex and L-Lipschitz by composition with the affine map z 7→ α − z. It is non-negative and non-decreasing because, on the left of the sublevel set Sq , convexity implies that all relative subgradients of f are non-positive; after the change of variables x = α − z, these slopes become non-negative slopes for h(1) . Define m(1) (0) = 0 and, for z > 0, let m(1) (z) be the left derivative of h(1) at z. Then m(1) : I (1) → [0, L] is non-decreasing and Z z h(1) (z) = m(1) (s)ds, z ∈ I (1) . 0
Similarly, if the right branch is present, then β is finite, and we define D(2) := b − β, where 0 < D(2) ≤ +∞, with D(2) = +∞ when b = +∞, and we define I (2) := [0, D(2) ], together with z (2) : X → I (2) ,
z (2) (x) := (x − β)+ ,
and h(2) : I (2) → R≥0 ,
h(2) (z) := f (β + z) − f (β).
Again, h(2) is convex and L-Lipschitz. It is non-negative and non-decreasing because, on the right of Sq , all relative subgradients of f are non-negative. Define m(2) (0) = 0 and, for z > 0, let m(2) (z) be the left derivative of h(2) at z. Then m(2) : I (2) → [0, L] is non-decreasing and Z z (2) h (z) = m(2) (s)ds, z ∈ I (2) . 0 (i)
For each present branch i ∈ {1, 2}, write T (i) = TI (i) ,m(i) ,η and define (Zk )k∈N by ( (i) Zk = 0 (i) Zk+1 = ΠI (i)
(i) T (i) (Zk ) − (−1)i ηWk
1 ≤ k ≤ k⋆ , k ≥ k⋆ .
Claim 11. For every present branch i ∈ {1, 2}, a.s., (i)
z (i) (Xk ) ≤ Zk
for all k ≥ k⋆ .
11
(16)
Claim 11 is proved in Section A. We now prove the deterministic decomposition X h(i) z (i) (x) , x ∈ X. (f (x) − q)+ ≤ ηL2 +
(17)
i∈{1,2}: branch i present
If x ∈ Eq , then dist(x, Sq ) ≤ ηL, hence by Lipschitzness (f (x) − q)+ ≤ ηL2 . If x < α, then the left branch is present. Since α ∈ Eq , there exists y ∈ Sq such that |y − α| ≤ ηL, and therefore (f (x) − q)+ ≤ f (x) − f (y) ≤ f (x) − f (α) + L|y − α| ≤ h(1) (z (1) (x)) + ηL2 . The case x > β is symmetric and gives (f (x) − q)+ ≤ h(2) (z (2) (x)) + ηL2 . Since every x ∈ X belongs to exactly one of these three regions, (17) follows. Let k ≥ k⋆ . By (17), Claim 11, and monotonicity of the functions h(i) , h i X (i) E[(f (Xk ) − q)+ ] ≤ ηL2 + E h(i) (Zk ) . i∈{1,2}: branch i present i eh := Z (i) For a present branch i, set Z k⋆ +h−1 and Rh := (−1) Wk⋆ +h−1 . Then (Rh )h≥1 is i.i.d., centered, eh )h≥1 . If D(i) = +∞, Corollary 9 and satisfies E[Rh2 ] ≤ σ 2 . If D(i) < +∞, Proposition 6 applies to (Z applies instead. Therefore, in either case, "Z (i) # h i Zk σ2 (i) (i) (i) m (s)ds ≤ E h (Zk ) = E + Lσ η. 2 0
There are at most two present branches, and therefore 2 σ 2 E[(f (Xk ) − q)+ ] ≤ ηL + 2 + Lσ η = (L + σ)2 η. 2 Now we have all the ingredients to complete the proof of Theorem 2. Let x⋆ ∈ X⋆ be such that |x1 − x⋆ | = dist(x1 , X⋆ ). For every k ≥ 1, by non-expansiveness of the projection onto X , (Xk+1 − x⋆ )2 = (ΠX (Xk − η · (Wk + Gk )) − ΠX (x⋆ ))2 ≤ (Xk − η · (Wk + Gk ) − x⋆ )2 . By Assumptions 4, 5, and 6, there exists a centered law µ with second moment at most σ 2 such that P(Wk ∈ A | Fk ) = µ(A) for every k and every Borel set A. Since Gk and Xk are Fk -measurable, it follows that E[(Xk+1 − x⋆ )2 ] ≤ E[(Xk − η · (Wk + Gk ) − x⋆ )2 ] ≤ E[(Xk − η · Gk − x⋆ )2 ] + σ 2 η 2 = E[(Xk − x⋆ )2 ] − 2E[Gk (Xk − x⋆ )] · η + E[G2k ] + σ 2 · η 2 ≤ E[(Xk − x⋆ )2 ] − 2E[Gk (Xk − x⋆ )] · η + (L2 + σ 2 ) · η 2 . The convexity of f entails that Gk (Xk − x⋆ ) ≥ f (Xk ) − f (x⋆ ) = ∆(Xk ). Hence 2η · E[∆(Xk )] ≤ E[(Xk − x⋆ )2 ] − E[(Xk+1 − x⋆ )2 ] + (L2 + σ 2 ) · η 2 . 12
(18)
We sum (18) for k = 1, 2, . . . , n to get3 2η ·
n X
E[∆(Xk )] ≤ |x1 − x⋆ |2 − E[(Xn+1 − x⋆ )2 ] + n · (L2 + σ 2 ) · η 2
k=1
≤ dist(x1 , X⋆ )2 + n · (L2 + σ 2 ) · η 2 . Therefore, there exists an index k⋆ ∈ {1, . . . , n} such that E[∆(Xk⋆ )] ≤
dist(x1 , X⋆ )2 L2 + σ 2 + η. 2ηn 2
(19)
By (19), for every k⋆ ≤ k ≤ n, E[∆(Xk )] = E[∆(Xk⋆ )] + E[∆(Xk ) − ∆(Xk⋆ )] ≤ E[∆(Xk⋆ )] + E[(∆(Xk ) − ∆(Xk⋆ ))+ ] dist(x1 , X⋆ )2 L2 + σ 2 + η + E[(∆(Xk ) − ∆(Xk⋆ ))+ ] 2ηn 2 dist(x1 , X⋆ )2 L2 + σ 2 = + η + E[(f (Xk ) − f (Xk⋆ ))+ ] =: (⋆) 2ηn 2
≤
What is left is bounding E[(f (Xk ) − f (Xk⋆ ))+ ]. To this end, we make the following claim. Claim 12. For every k⋆ ≤ k ≤ n, E [(f (Xk ) − f (Xk⋆ ))+ | Fk⋆ ] ≤ (L + σ)2 η
a.s.
(20)
The insight into Claim 12 is that Xk⋆ is Fk⋆ -measurable and that there is independence between the σ-fields Fk⋆ and σ(Wk⋆ , Wk⋆ +1 , . . . , Wk−1 ), hence Xk⋆ can be treated as a constant when taking the conditional expectation of (f (Xk ) − f (Xk⋆ ))+ , with respect to Fk⋆ . This justifies a conditional application of Lemma 10 with q = f (Xk⋆ ), which gives (20). The interested reader can find a complete proof of this claim in Section A. An application of Claim 12 and the tower property of expectation yields dist(x1 , X⋆ )2 L2 + σ 2 + η + E[E[(f (Xk ) − f (Xk⋆ ))+ |Fk⋆ ]] 2ηn 2 dist(x1 , X⋆ )2 L2 + σ 2 ≤ + η + (L + σ)2 η. 2ηn 2 √ Taking k = n gives (2). Substituting η = cn / n, with cn ∈ [c, c], then (3) follows immediately from (2). This completes the proof. (⋆) =
6
Proof of Theorem 3
Fix constants 0 < c ≤ c < ∞, a horizon n, and a coefficient cn ∈ [c, c]. Set cn 1 1 η := √ , M := , λ := min η, . 16η nη n 3
Note that here we assume the existence of Xn+1 , despite Xn being called the last iterate. The underlying tacit assumption, that was evident also in (1), is that the last iterate is called last in the sense that it is the last that we want to compute in implementations, but we assume that the recurrence defines the iterates for every k ≥ 1.
13
In the proof we take n0 = n0 (c, c) large enough so that, for all n ≥ n0 and all cn ∈ [c, c], √ 1 n 1 −8 η≤2 , η≥ , log ≥ log n. n c 4
(21)
For example, it is enough to take n0 larger than a numerical constant times max{c2 , c−2 , c4 , 1}. Then M ≥ 16 and M ≤ n − 1. Moreover, λ2 ≤
λ ≤ η,
1 , n
ηλ ≤ η,
nηλ ≤ 1.
(22)
√ Indeed, λ ≤ η by definition, while λ ≤ 1/ n follows from λ = min{η, 1/(nη)}. Also, if λ = η, then nηλ = nη 2 ≤ 1, whereas if λ = 1/(nη), then nηλ = 1. Recall from the statement of Theorem 3 that: X = [−2, 1],
f (x) = x+ = max{x, 0},
and
f⋆ = 0,
X⋆ = [−2, 0],
( 0, x ≤ 0, g(x) = 1, x > 0.
(23)
(24)
Then f is convex and 1-Lipschitz on X , and g(x) ∈ ∂X f (x) ∩ [−1, 1] for every x ∈ X . The next lemma reveals the harmonic structure emerging from our lower bound instance which leads to the logarithm term appearing in the lower bound. Lemma 13. Let Y be a non-negative random variable. Let η ∈ (0, 2−8 ] and let M := ⌊1/(16η)⌋. Suppose that there exist pairwise disjoint events E1 , . . . , EM and constants p, ℓ > 0 such that, for every j = 1, . . . , M , p P(Ej ) ≥ 2 , Y ≥ ℓηj on Ej . j Then 1 pℓ η log . E[Y ] ≥ 2 η Proof. By disjointness and non-negativity, E[Y ] ≥
M X
ℓηj P(Ej ) ≥ pℓη
j=1
Since
PM
j=1 j
M X 1 j=1
j
.
−1 ≥ log(M + 1) and M + 1 > 1/(16η), M X 1 j=1
j
≥ log
1 1 = log − log 16. 16η η
For η ≤ 2−8 , the last display is at least 12 log(1/η), and the claim follows. The following lemma explains why a rare large outcome of magnitude proportional to j, sampled when j steps remain, leaves terminal error of order ηj. Lemma 14. Fix j ∈ {1, . . . , M } and put kj := n − j. Suppose that, on some realization, −(j + 1)ηλ ≤ Xkj ≤ 0,
Wkj = −4j,
Wk = 0
Then, on the same realization, f (Xn ) − f⋆ ≥ 2ηj. 14
for every k = kj + 1, . . . , n − 1.
Proof. Since Xkj ≤ 0, we have g(Xkj ) = 0. Hence Wkj = −4j gives Xkj +1 = ΠX Xkj − ηWkj = ΠX Xkj + 4ηj . Because Xkj ∈ [−(j + 1)ηλ, 0], ηλ ≤ η, and j ≤ M ≤ 1/(16η), 1 0 < 4ηj − (j + 1)ηλ ≤ Xkj + 4ηj ≤ 4ηj ≤ . 4 Thus the projection does not act and Xkj +1 ≥ 4ηj − (j + 1)ηλ > 0. By hypothesis, for the remaining j − 1 updates the noises vanish. At each such update, the deterministic term can decrease the iterate by at most η, because g(x) ∈ [0, 1]. Since Xkj +1 ≤ 1/4 and the subsequent noiseless update x 7→ x − ηg(x) never increases the pre-projection point, all subsequent pre-projection points are at most 1. Hence the projection onto [−2, 1] cannot decrease them. Therefore Xn ≥ 4ηj − (j + 1)ηλ − (j − 1)η ≥ 4ηj − (j + 1)η − (j − 1)η = 2ηj. In particular Xn > 0, and so f (Xn ) = Xn .
6.1
A time-homogeneous state-dependent implementation
This subsection proves item 1 of Theorem 3. For j = 0, 1, . . . , n − 1, define the labeled states sj := −(j + 1)ηλ. Set X1 ≡ sn−1 = −nηλ. By (22), X1 ∈ [−1, 0] ⊆ X⋆ . Thus s0 = −ηλ. We define the noise law at state sj depending on whether sj is near or far from 0. Far labeled states. For j = M + 1, . . . , n − 1, define Q(sj , ·) = (1 − λ2 )δ−λ + λ2 δ 1−λ2 . λ
The noise realization −λ moves the point from sj to sj−1 , because sj − η(−λ) = −(j + 1)ηλ + ηλ = −jηλ = sj−1 . Near labeled states. For j = 1, . . . , M , set aj =
1 , 64j 2
bj = λ2 +
1 . 64j 2
1 Since aj + bj ≤ λ2 + 32 < 1, define
Q(sj , ·) = (1 − aj − bj )δ−λ + aj δ−4j + bj δRj , where Rj > 0 is chosen to make the noise centered: 1
Rj =
(1 − aj − bj )λ + 16j (1 − aj − bj )λ + 4jaj = . 1 bj λ2 + 64j 2 15
(25)
The rare large outcome associated with label j is −4j. It is assigned probability mass 1/(64j 2 ) by the state-dependent law at sj , and it moves the iterate to the right by 4ηj. At all other points x ∈ X \ {s1 , . . . , sn−1 }, set Q(x, ·) = δ0 . We construct the process recursively as follows. Given Fk , sample Wk from Q(Xk , ·) independently of the past, set Gk := g(Xk ), and update Xk+1 by (1). Lemma 15. The kernel Q is centered and has uniformly bounded second moment: Z Z w Q(x, dw) = 0, w2 Q(x, dw) ≤ 3, x ∈ X. R
(26)
R
Consequently, the oracle satisfies Assumptions 4 and 5 with σ 2 = 3, and hence also Assumption 3. Furthermore, it is not state-independent. Proof. At all points where Q(x, ·) = δ0 , the claims are immediate. For a far labeled state sj , j > M , the mean is 1 − λ2 = 0, (1 − λ2 )(−λ) + λ2 λ and the second moment is 2 1 − λ2 (1 − λ2 )λ2 + λ2 = (1 − λ2 )λ2 + (1 − λ2 )2 λ = 1 − λ2 ≤ 1. For a near labeled state sj , j ≤ M , the definition of Rj gives (1 − aj − bj )(−λ) + aj (−4j) + bj Rj = 0, so the noise is centered. For the second moment, using (25), Z w2 Q(sj , dw) = (1 − aj − bj )λ2 + aj (4j)2 + bj Rj2 R 1 2 (1 − a − b )λ + j j 1 16j ≤ λ2 + + 1 4 λ2 + 64j 2 2 1 2 16j 1 λ 2 ≤λ + +2 2 1 +2 2 1 4 λ + 64j λ + 64j 2 2 ≤ λ2 +
1 1 11 + 2 + = λ2 + . 4 2 4
Since λ ≤ η ≤ 2−8 , this is smaller than 3. Finally, because Xk is Fk -measurable and Wk is sampled from Q(Xk , ·) conditionally independently of the past, (26) gives E[Wk2 | Fk ] ≤ 3.
E[Wk | Fk ] = 0,
Finally, this verifies Assumptions 4 and 5 with σ 2 = 3, and hence also Assumption 3. The kernel is not state-independent: for example, Q(0, ·) = δ0 , whereas Q(sn−1 , ·) assigns positive mass to nonzero noise values.
16
If the process is at a labeled state sj with j ≥ 1 and the sampled noise is Wk = −λ, then Xk+1 = sj−1 . Therefore, along the path where these values are sampled before the rare large outcome, Xk = sn−k = −(n − k + 1)ηλ,
k = 1, 2, . . . , n.
In particular, sj is visited at time kj = n − j. For j = 1, . . . , M , define n−1 \ {Wn−r = −λ} ∩ {Wn−j = −4j}. Ej := r=j+1
On this event, a deterministic induction gives Xn−r = sr for every r = j + 1, . . . , n − 1, and hence the event indeed corresponds to following the labeled path down to sj and then taking the rare large outcome at sj . Lemma 16. For every j = 1, . . . , M , P(Ej ) ≥
1 . 512j 2
Moreover, the events E1 , . . . , EM are pairwise disjoint. Proof. By construction and conditional independence, M Y
P(Ej ) = aj
n−1 Y
(1 − ar − br )
r=j+1
(1 − λ2 ),
(27)
r=M +1
with empty products interpreted as one. Since λ2 ≤ 1/n, n−1 Y
1 (1 − λ2 ) ≥ (1 − 1/n)n ≥ . 4
r=M +1
Q P For the near-labeled product, applying (1 − u ) ≥ 1 − i i i ui , valid for ur ∈ [0, 1], to ur := ar + br = P∞ −2 1 2 2 λ + 32r2 ∈ [0, 1] and recalling that r=1 r = π /6 we have M Y
M X (1 − ar − br ) ≥ 1 − λ2 +
r=j+1
r=j+1
1 32r2
∞
1 X 1 ≥ 1 − Mλ − 32 r2 2
r=1
π2 ≥ 1 − M η2 − 192 η π2 1 − ≥ . ≥1− 16 192 2 Plugging these bounds and aj = 1/(64j 2 ) into (27) gives P(Ej ) ≥
1 1 1 · = . 2 8 64j 512j 2
We observe that, for every 1 ≤ j < ℓ ≤ M , the event Ej requires the noise realization Wk = −λ at sℓ , while Eℓ requires the rare large outcome Wkℓ = −4ℓ at sℓ . Hence the events are pairwise disjoint. 17
Now we show that for the events Ej the hypotheses of Lemma 14 hold. On Ej , the process reaches sj = −(j + 1)ηλ at time kj = n − j, and Wkj = −4j. The rare large outcome sends the iterate to a point at least 4ηj − (j + 1)ηλ > 0. From then on, as long as the iterate is positive, the kernel is δ0 ; with zero noise, each deterministic update decreases the iterate by at most η. Hence, after any h ≤ j − 1 subsequent updates, the iterate is at least 4ηj − (j + 1)ηλ − hη, which is positive. Therefore all subsequent noises up to time n − 1 are zero, and the hypotheses of Lemma 14 hold. Now we have all the ingredients to complete the proof of the time-homogeneous state-dependent case (Item 1 of Theorem 3). Lemma 16 and Lemma 14 verify the assumptions of Lemma 13 with Y = f (Xn ) − f⋆ , p = 1/512, and ℓ = 2. Hence 1 1 E[f (Xn ) − f⋆ ] ≥ η log . 512 η √ Since η = cn / n, and using that c ≤ cn ≤ c and (21), √ √ 1 cn n c n c log n √ √ η log = ≥ ≥ √ . log log η cn c 4 n n n This proves (5). Finally, the support of Q(sM , ·) contains the value −4M . Since 1/(16η) ≥ 16, we have M ≥ 1/(32η), and therefore √ 1 n ≥ . 4M ≥ 8η 8c √ Thus, for x = sM , the support of Q(x, ·) contains a value of magnitude at least n/(8c).
6.2
A state-independent time-inhomogeneous implementation
This subsection proves item 2 of Theorem 3. The objective and subgradient selection are the same as in (23)–(24), but the process starts from the optimal point X1 ≡ 0. Here the labels j are attached directly to some time indices of the iterates, thereby determining when the noise can produce a rare large outcome. For j = 1, . . . , M , define the special time kj = n − j. Let the random variables (Wk )k∈N be independent. At a special time kj , set 2 −4j, with probability 1/(64j ), Wkj = +4j, with probability 1/(64j 2 ), 0, otherwise, and at every non-special time set Wk = 0. This sequence is state-independent because the law of Wk depends only on k; in kernel notation, set Qk (x, ·) = Law(Wk ) for every x ∈ X . The rare large outcome associated with label j is again −4j, but now it can be sampled from the law of the time-indexed noise variable Wkj . Lemma 17. The associated kernels Qk (x, ·) = Law(Wk ) are centered and state-independent. Moreover, the variables (Wk )k∈N are independent across time and satisfy 1 E[Wk2 ] ≤ , 2
k ≥ 1.
In particular, the oracle satisfies Assumptions 4 and 6 with σ 2 = 1/2, and hence also Assumption 3. Finally, it is not time-homogeneous. 18
Proof. At non-special times the claim is immediate. At time kj , symmetry gives E[Wkj ] = 0, and E[Wk2j ] = 2
1 1 (4j)2 = . 2 64j 2
Since the variables are independent and their laws are fixed in advance, for every k the conditional law given Fk is Qk (Xk , ·) = Law(Wk ), and the conditional mean and second moment are the corresponding unconditional quantities. This verifies Assumptions 4 and 6 with σ 2 = 1/2, and hence also Assumption 3. The oracle is not time-homogeneous: non-special times have kernel δ0 , whereas each special time kj has a kernel assigning positive mass to ±4j. For j = 1, . . . , M , let Fj be the event that Wkj = −4j and Wkℓ = 0 for every ℓ = ̸ j with 1 ≤ ℓ ≤ M . Lemma 18. For every j = 1, . . . , M , P(Fj ) ≥
1 . 128j 2
Moreover, the events F1 , . . . , FM are pairwise disjoint. On Fj , the hypotheses of Lemma 14 hold. Proof. By independence, 1 1 Y P(Fj ) = 1− , 64j 2 32ℓ2 ℓ̸=j
P Q 1 P −2 < 1/2 and where the product is over ℓ ∈ {1, . . . , M } \ {j}. Since 32 ℓ≥1 ℓ i (1 − ui ) ≥ 1 − i ui for ui ∈ [0, 1], ∞ Y 1 1 X 1 1 1− ≥1− ≥ . 2 2 32ℓ 32 ℓ 2 ℓ̸=j
ℓ=1
Therefore P(Fj ) ≥ 1/(128j 2 ). Pairwise disjointness follows because, if j ̸= ℓ, then Fj requires Wkℓ = 0, whereas Fℓ requires Wkℓ = −4ℓ. On Fj , all special noises before time kj are zero, and all non-special noises are zero by construction. Since X1 = 0 and g(0) = 0, the process stays at 0 until time kj . At time kj , Wkj = −4j, and all later special noises are zero on Fj , while all later non-special noises are zero by construction. Thus the hypotheses of Lemma 14 hold with Xkj = 0 ∈ [−(j + 1)ηλ, 0]. Now we have all the ingredients to complete the proof of the state-independent time-inhomogeneous case (Item 2 of Theorem 3). Lemma 18 and Lemma 14 verify the assumptions of Lemma 13 with Y = f (Xn ) − f⋆ , p = 1/128, and ℓ = 2. Hence 1 1 E[f (Xn ) − f⋆ ] ≥ η log . 128 η √ Using the same conversion from η log(1/η) to (log n)/ n as in the state-dependent case, we get E[f (Xn ) − f⋆ ] ≥
c log n c log n √ ≥ 11 √ . 512 n 2 n
This proves (6). Moreover, the support of WkM contains the values ±4M , and therefore contains √ values of magnitude at least 1/(8η) ≥ n/(8c) by the same estimate as in the state-dependent construction.
19
7
Final remarks
The proof of Lemma 10 uses the combination of Assumptions 5 and 6 in a very concrete way. After conditioning on the good iterate Xk⋆ , the future noises are still independent copies of the same law, regardless of where the process moves. This lets us define the two one-sided dominating chains in (16) and apply Proposition 6 or Corollary 9, depending on whether the corresponding side of the domain is finite or infinite. All the argument is made possible by the Foster–Lyapunov-type inequality (12) that is derived from the fundamental inequality (7), which enables the construction of a suitable potential B as described in Claim 8. Theorem 3 shows that both kernel symmetries matter under conditional second-moment control only. If state-independence is dropped, the current state can determine the availability of a rare large noise outcome. The kernel is still fixed in time and centered at every state, but different states can expose different rare large outcomes. If time-homogeneity is dropped, the time index can play the same role: the state-independent laws associated with specific time indices can sample the corresponding rare large outcome. In both cases, the logarithm term cannot be ruled out. √ The examples use noise realizations of order 1/η, and hence of order n for every standard √ fixed-stepsize family η = Θ(1/ n). Thus they do not settle the corresponding models with uniformly almost-surely bounded stochastic gradients. What they do settle is that the plain variance condition, Assumption 3, is not sufficient to remove the logarithm. Even strengthening it by requiring only time-homogeneity, or only state-independence, is still insufficient. The logarithm disappears in our proof only when both structural symmetries are imposed simultaneously. Finally, an interesting open problem, is to establish if in the deterministic multivariate setting (for each fixed dimension d > 1), the last iterate is optimal.
Acknowledgments TC gratefully acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) through grant RGPIN-2023-03688 (Discovery Grants Program).
References [1] Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Informationtheoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5):3235–3249, 2012. [2] Francis Bach. Learning theory from first principles. MIT press, 2024. [3] Khaled Eldowa and Andrea Paudice. General tail bounds for non-smooth stochastic mirror descent. In Proceedings of the 27-th International Conference on Artificial Intelligence and Statistics, pages 3205–3213, 2024. [4] Yu. M. Ermol’ev. On the method of generalized stochastic gradients and quasi-Féjer sequences. Cybernetics, 5:208–220, 1969. [5] Nicholas J. A. Harvey, Chris Liaw, and Sikander Randhawa. Tight analyses for subgradient descent I: lower bounds. Open J. Math. Optim., 5:1–17, 2024. [6] Nicholas J.A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Proceedinds of the 32nd International Conference on Computational Learning Theory, pages 1579–1613, 2019. 20
[7] Prateek Jain, Dheeraj M. Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. SIAM Journal on Optimization, 31(2):1108–1130, 2021. [8] Olav Kallenberg. Foundations of Modern Probability, volume 99 of Probability Theory and Stochastic Modelling. Springer, 3 edition, 2021. [9] Tomer Koren and Shahar Segal. Open problem: Tight convergence of SGD in constant dimension. In COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 3847–3851, 2020. [10] Guy Kornowski and Ohad Shamir. Gradient descent’s last iterate is often (slightly) suboptimal. Preprint at arXiv:2604.13870, April 2026. [11] Daogao Liu and Zhou Lu. The convergence rate of SGD’s final iterate: Analysis on dimension dependence, 2021. Preprint arXiv:2106.14588. [12] Zijian Liu and Zhengyuan Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises: High-probability bound, in-expectation rate and initial distance adaptation. arXiv preprint arXiv:2303.12277, 2023. [13] Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In Proceedings of the 12-th International Conference on Learning Representations (to appear), 2024. [14] Sean P. Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Cambridge University Press, 2 edition, 2009. [15] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009. [16] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983. [17] Daniela Angela Parletta, Andrea Paudice, and Saverio Salzo. An improved analysis of the clipped stochastic subgradient method under heavy-tailed noise, 2025. [18] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Proceedings of the 30th International Conference on Machine Learning, 2013. [19] Serdar Yüksel and Sean P. Meyn. Random-time, state-dependent stochastic drift for Markov chains and application to stochastic stabilization over erasure channels, 2012. Preprint at arXiv:1010.4820. [20] Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 35(3):2182–2201, 2025.
21
A
Proofs of the Deferred Claims
A.1
Proof of Claim 7
Proof. We first prove that P satisfies the Feller property. Recall that a transition probability kernel P on the compact metric space I is Feller if φ ∈ C(I)
P φ ∈ C(I).
=⇒
Let φ ∈ C(I), and let zℓ → z in I. Since T is continuous and the projection ΠI is continuous, for every fixed r ∈ R, Φ(zℓ , r) = ΠI (T (zℓ ) − ηr) −→ ΠI (T (z) − ηr) = Φ(z, r). By continuity of φ, φ (Φ(zℓ , r)) −→ φ (Φ(z, r)) . Moreover, |φ (Φ(zℓ , r))| ≤ ∥φ∥∞ , and ∥φ∥∞ < ∞ because I is compact. The dominated convergence theorem gives Z Z P φ(zℓ ) = φ (Φ(zℓ , r)) µ(dr) −→ φ (Φ(z, r)) µ(dr) = P φ(z). R
R
Thus P φ ∈ C(I), and P is Feller. Consequently, the chain admits an invariant probability measure by the Krylov–Bogoliubov averaging argument. For the sake of completeness, we provide the details below. Fix z0 ∈ I and define N −1 1 X νN := δz0 P t , N t=0 t where δz0 P denotes the law at time t of the chain started from z0 .
Since I is a compact metric space, the set of probability measures on I is sequentially compact for weak convergence, i.e., every sequence of probability measures on I has a weakly convergent subsequence. Hence there exist a subsequence (νNj )j≥1 and a probability measure π on I such that w
νNj − → π, R
(28)
R
meaning that I φdνNj → I φdπ for every φ ∈ C(I). Fix φ ∈ C(I). We know that P is Feller, thus P φ ∈ C(I), and by (28) we get Z Z φdνNj −→ φdπ, I
and
Z I
I
Z φd(νNj P ) =
Z
I
P φdνNj −→
Z P φdπ =
I
φd(πP ). I
To show that these two limits coincide, note that Z Z N −1 P N φ(z0 ) − φ(z0 ) 1 X φd(νN P ) − φdνN = P t+1 φ(z0 ) − P t φ(z0 ) = , N N I I t=0
hence, Z
Z φd(νN P ) −
It follows that
I
I
Z
Z
φdνN ≤
2∥φ∥∞ −→ 0. N
φdπ,
φ ∈ C(I).
φd(πP ) = I
I
Continuous functions separate probability measures on compact metric spaces, thus πP = π. 22
A.2
Proof of Claim 8
Proof. Recall that T (z) = TI,m,η (z) = sup0≤s≤z (s − η · m(s))+ for every z ∈ I = [0, D], where m : I → [0, L] is a non-decreasing function. For every z ∈ I we set B(z) :=
z2 + 2Lz 2η
and we want to show that Z z E[B (ΠI (T (z) − η · R))] − B(z) ≤ −
m(s)ds +
0
σ2 + Lσ · η, 2
z ∈ I,
(29)
where the random variable R satisfies E[R] = 0 and E[R2 ] ≤ σ 2 . Our proof of (29) will require the two following inequalities: Z z B(T (z)) − B(z) ≤ − m(s)ds for every z ∈ I (30) 0
E[B(ΠI (s − η · R)) − B(s)] ≤ η ·
σ2 + Lσ 2
for every s ∈ I.
(31)
Assuming (30) and (31), (29) readily follows by plugging s = T (z) into (31) and adding the resulting inequality to (30). It remains to prove (30) and (31). To show (31), let s ∈ I. By definition of B, we may rewrite the left-hand side of (31) as: 1 2 2 E · (ΠI (s − η · R)) − s + 2L(ΠI (s − η · R) − s) (32) 2η Note that the projection onto [0, D] cannot increase the distance from 0. In particular: (ΠI (s − η · R))2 − s2 ≤ (s − η · R)2 − s2 = η 2 R2 − 2sRη.
(33)
Also, note that ΠI (s − δ) ≤ s if δ is positive, whereas ΠI (s − δ) ≤ s − δ if δ is non-positive, hence setting R− := max{−R, 0} yields ΠI (s − η · R) − s ≤ η · R− .
(34)
Combining (33) and (34) with (32) gives:
1 2 2 (η R − 2sRη) + 2Lη · R− E[B(ΠI (s − η · R)) − B(s)] ≤ E 2η 1 2 = E R + 2LR− · η, 2
where we used E[R] = 0. Moreover, E[R] = 0 entails that E[R− ] = E[R+ ] = 12 E[|R|]. This gives 1 2 σ + LE[|R|] · η, E[B(ΠI (s − η · R)) − B(s)] ≤ 2 p and Jensen’s inequality E[|R|] ≤ E[R2 ] ≤ σ yields (31). To show (30), let z ∈ I. By (7), we have Z z η m(s)ds ≤ (z − T (z)) (z + ηL) , 0
23
On the other hand, the identity (z 2 − T (z)2 ) = (z − T (z)) · (z + T (z)) gives z + T (z) . η B(z) − B(T (z)) = (z − T (z)) 2Lη + 2 Therefore, η B(z) − B(T (z)) − η
Z z
z + T (z) m(s)ds ≥ (z − T (z)) 2Lη + − (z + ηL) 2 0 z − T (z) . = (z − T (z)) Lη − 2
(35)
Recalling that T (z) ≤ z and noting that z − T (z) = z − sup (s − η · m(s))+ ≤ z − sup (s − η · m(s)) ≤ z − sup (s − η · L) = η · L, 0≤s≤z
0≤s≤z
0≤s≤z
it follows that the right-hand side of (35) is non-negative, which is equivalent to (30).
A.3
Proof of Claim 11
To prove Claim 11, we will use the following technical lemma. Lemma 19. Let X ⊆ R be a closed interval, let f : X → R be convex, and let S = {x ∈ X : f (x) ≤ q} be non-empty and closed. Fix ρ ≥ 0, and define E = {x ∈ X : dist(x, S) ≤ ρ},
α = inf E,
β = sup E,
with a = inf X and b = sup X . Then the following hold. 1. If α > a, then every x ∈ [α, α +ρ)∩ X lies strictly to the left of S, and every relative subgradient g ∈ ∂X f (x) satisfies g ≤ 0. 2. If β < b, then every x ∈ (β − ρ, β] ∩ X lies strictly to the right of S, and every relative subgradient g ∈ ∂X f (x) satisfies g ≥ 0. Proof. Since S is a non-empty closed convex subset of the interval X , it is a closed interval in X . Write u = inf S, v = sup S. If α > a, then the left endpoint of the enlarged set is not created by the boundary of X , hence α = u − ρ. Therefore every x ∈ [α, α + ρ) ∩ X satisfies x < u, and so x ∈ / S. Pick any y ∈ S. Then y > x and f (y) ≤ q < f (x). For any g ∈ ∂X f (x), the relative subgradient inequality gives f (y) ≥ f (x) + g(y − x). Since y − x > 0, this implies g≤
f (y) − f (x) < 0. y−x
In particular g ≤ 0. 24
The right side is symmetric. If β < b, then β = v + ρ. Hence every x ∈ (β − ρ, β] ∩ X satisfies x > v, and so x ∈ / S. Pick any y ∈ S. Then y < x and f (y) ≤ q < f (x). For g ∈ ∂X f (x), f (y) ≥ f (x) + g(y − x). Since y − x < 0, we obtain g≥
f (y) − f (x) > 0. y−x
In particular g ≥ 0. Proof of Claim 11. We prove the claim for each present branch separately. Consider first the left branch. The base step k = k⋆ holds because Xk⋆ ∈ Sq ⊆ Eq , hence Xk⋆ ≥ α (1) (1) and z (1) (Xk⋆ ) = 0 = Zk⋆ . Assume now that z (1) (Xk ) ≤ Zk for some k ≥ k⋆ . We first show that (1)
Xk − ηGk ≥ α − T (1) (Zk ).
(36)
If z (1) (Xk ) > 0, then Xk < α. Since Gk ≤ D+ f (Xk ) and D+ f (α − z) = −D− h(1) (z), we get Xk − ηGk ≥ Xk − ηD+ f (Xk ) = α − z (1) (Xk ) + ηm(1) (z (1) (Xk )) = α − z (1) (Xk ) − ηm(1) (z (1) (Xk )) (1)
≥ α − T (1) (z (1) (Xk )) ≥ α − T (1) (Zk ), where the last step uses the monotonicity of T (1) and the induction hypothesis. If instead z (1) (Xk ) = 0, then Xk ≥ α. If Gk ≤ 0, then Xk − ηGk ≥ Xk ≥ α. If Gk > 0, then Xk cannot belong to [α, α + ηL) ∩ X : by Lemma 19, applied with S = Sq and ρ = ηL, every relative subgradient of f at any point of this interval is non-positive, contradicting Gk ∈ ∂X f (Xk ) and Gk > 0. Hence Xk ≥ α + ηL, and therefore Xk − ηGk ≥ α + η(L − Gk ) ≥ α. Since T (1) ≥ 0, (36) follows. Using (36), (1) Xk − η(Gk + Wk ) ≥ α − T (1) (Zk ) + ηWk . Let a = inf X and recall that D(1) = α − a ∈ (0, +∞]. By monotonicity of one-dimensional projections, Xk+1 = ΠX (Xk − η(Gk + Wk )) ≥ Π[a,α] (Xk − η(Gk + Wk )) (1) ≥ Π[a,α] α − T (1) (Zk ) + ηWk (1) = α − Π[0,D(1) ] T (1) (Zk ) + ηWk (1)
= α − Zk+1 . (1)
This is exactly z (1) (Xk+1 ) ≤ Zk+1 . (2)
The right branch is symmetric. The base step follows from Xk⋆ ∈ Eq , so z (2) (Xk⋆ ) = 0 = Zk⋆ . (2)
Assume z (2) (Xk ) ≤ Zk . We first prove (2)
Xk − ηGk ≤ β + T (2) (Zk ). 25
(37)
If z (2) (Xk ) > 0, then Xk > β. Since Gk ≥ D− f (Xk ) and D− f (β + z) = D− h(2) (z), we have Xk − ηGk ≤ Xk − ηD− f (Xk ) = β + z (2) (Xk ) − ηm(2) (z (2) (Xk )) (2)
≤ β + T (2) (z (2) (Xk )) ≤ β + T (2) (Zk ). If z (2) (Xk ) = 0, then Xk ≤ β. If Gk ≥ 0, then Xk − ηGk ≤ Xk ≤ β. If Gk < 0, then Xk cannot belong to (β − ηL, β] ∩ X : by Lemma 19, applied with S = Sq and ρ = ηL, every relative subgradient of f at any point of this interval is non-negative, contradicting Gk ∈ ∂X f (Xk ) and Gk < 0. Hence Xk ≤ β − ηL, and therefore Xk − ηGk ≤ β − ηL + ηL = β. Since T (2) ≥ 0, (37) follows. Using (37), Xk+1 = ΠX (Xk − η(Gk + Wk )) ≤ Π[β,b] (Xk − η(Gk + Wk )) (2) ≤ Π[β,b] β + T (2) (Zk ) − ηWk (2) = β + Π[0,D(2) ] T (2) (Zk ) − ηWk (2)
= β + Zk+1 , (2)
where b = sup X and D(2) = b − β ∈ (0, +∞]. This proves z (2) (Xk+1 ) ≤ Zk+1 and completes the induction.
B
Proof of Claim 12
Proof. For k = k⋆ the claim is immediate. Hence fix k > k⋆ and set h := k − k⋆ . By Assumptions 4, 5, and 6, there exists a centered probability law µ on R with second moment at most σ 2 such that P(Wm ∈ A | Fm ) = µ(A)
∀m ≥ 1, ∀A ∈ B(R).
A standard induction using the tower property shows that, for every r ≥ 1, the block (Wk⋆ , Wk⋆ +1 , . . . , Wk⋆ +r−1 ) is independent of Fk⋆ and has law µ⊗r . Equivalently, the infinite future-noise sequence U∞ := (Wk⋆ , Wk⋆ +1 , . . .) is independent of Fk⋆ and has law µ⊗N . In particular, Uh := (Wk⋆ , Wk⋆ +1 , . . . , Wk−1 ) is independent of Fk⋆ and has law µ⊗h . Let V := (X1 , W1 , . . . , Wk⋆ −1 ), with the obvious convention when k⋆ = 1. Since Fk⋆ = σ(X1 , W1 , . . . , Wk⋆ −1 ), 26
we have σ(V ) = Fk⋆ . For every m ≥ 1, set Ym := (X1 , W1 , . . . , Wm−1 ),
Em := X × Rm−1 ,
with the convention E1 = X and Y1 = X1 . By Definition 1, Gm is Fm -measurable, and by the definition of the filtration, Fm = σ(Ym ). Hence σ(Gm ) ⊆ σ(Ym ), that is, Gm is Ym -measurable. Since R is a Borel space, the functional representation lemma of Doob [8, Lemma 1.14], applied with f = Gm and g = Ym , gives a B(Em )/B(R)-measurable map γ em : Em → R such that Gm = γ em (Ym ) Replacing γ em by
a.s.
γm := Π[−L,L] ◦ γ em ,
and using Gm ∈ [−L, L] a.s., we may assume that γm : Em → [−L, L] and Gm = γm (X1 , W1 , . . . , Wm−1 )
a.s.
Taking a countable intersection over m ≥ 1, these identities hold simultaneously on an event of probability one. On the same event, the validity assumption in Definition 1 gives γm (X1 , W1 , . . . , Wm−1 ) ∈ ∂X f (Xm ) ∩ [−L, L]
for every m ≥ 1.
We now define the frozen recursion. Fix v = (x1 , w1 , . . . , wk⋆ −1 ) ∈ Ek⋆ and an infinite future-noise sequence u = (u1 , u2 , . . .) ∈ RN . Define
( wm , 1 ≤ m ≤ k⋆ − 1, ωm (v, u) := um−k⋆ +1 , m ≥ k⋆ .
Set x1 (v, u) := x1 and, recursively for m ≥ 1, ym (v, u) := x1 , ω1 (v, u), . . . , ωm−1 (v, u) ∈ Em , gm (v, u) := γm ym (v, u) , and
xm+1 (v, u) := ΠX xm (v, u) − η gm (v, u) + ωm (v, u) .
The map (v, u) 7→ xm (v, u) is Borel for every m. Moreover, xk⋆ (v, u) depends only on v, so we write it as xk⋆ (v). Define the non-negative Borel map Ψh : Ek⋆ × Rh → R+ by Ψh (v, u1 , . . . , uh ) := f (xk (v, u)) − f (xk⋆ (v)) + , 27
where the right-hand side uses only the first h future-noise coordinates. By construction and by the simultaneous almost-sure identities above, Ψh (V, Uh ) = f (Xk ) − f (Xk⋆ ) + a.s. Since Uh is independent of Fk⋆ , has law µ⊗h , and V is Fk⋆ -measurable, the standard conditionalindependence identity gives h i Z ⊗h E f (Xk ) − f (Xk⋆ ) + | Fk⋆ = Ψh (v, u) µ (du) a.s. Rh
v=V
It remains to bound the frozen integral for Law(V )-a.e. frozen past v. For each m ≥ k⋆ , let Am ⊆ Ek⋆ × RN be the measurable set of pairs (v, u) such that gj (v, u) ∈ ∂X f (xj (v, u)) ∩ [−L, L]
for every 1 ≤ j ≤ m.
Under the original law, (V, U∞ ) ∈ Am almost surely. Since U∞ is independent of V and has law µ⊗N , this means Law(V ) ⊗ µ⊗N (Am ) = 1. By Fubini’s theorem, there exists a set Nm ⊆ Ek⋆ with Law(V )(Nm ) = 0 such that µ⊗N Am (v, ·) = 1 for every v ∈ / Nm . Set N :=
[
Nm .
m≥k⋆
Then Law(V )(N ) = 0, and for every v ∈ / N the frozen recursion has valid subgradient selections at all times, µ⊗N -almost surely. Fix such a v ∈ / N . Let U = (U1 , U2 , . . .) have law µ⊗N , and define the shifted post-k⋆ process X̄i := xk⋆ +i (v, U ),
Ḡi := gk⋆ +i (v, U ),
W̄i := Ui+1 ,
i ≥ 0.
Then X̄0 = xk⋆ (v) is deterministic, the noises (W̄i )i≥0 are i.i.d. with law µ, are centered, and have second moment at most σ 2 . Moreover, by the choice of v ∈ / N, Ḡi ∈ ∂X f (X̄i ) ∩ [−L, L]
for every i ≥ 0
almost surely. Thus the shifted frozen process satisfies the assumptions of Lemma 10. Applying that lemma with deterministic level q(v) := f (xk⋆ (v)) = f (X̄0 ) gives Z Rh
Ψh (v, u) µ⊗h (du) = E (f (X̄h ) − q(v))+ ≤ (L + σ)2 η.
Since this holds for every v ∈ / N and Law(V )(N ) = 0, substituting v = V in the conditionalexpectation identity yields h i E f (Xk ) − f (Xk⋆ ) + | Fk⋆ ≤ (L + σ)2 η a.s. This is exactly (20). 28
C
On General State Space Markov Chains
This section recalls some standard notation and known facts pertaining to general state space Markov-chains. See, e.g., [14] for a systematic treatment. Let S be a metric space with Borel σ-field B(S). A transition probability kernel is a map P : S ×B(S) → [0, 1] such that P (z, ·) is a probability measure for every z ∈ S, and P (·, A) is measurable for every A ∈ B(S). If (Zk )k∈N is a time-homogeneous Markov chain with kernel P , then P(Zk+1 ∈ A | Z1 , . . . , Zk ) = P (Zk , A). For every bounded measurable function φ : S → R and every probability measure λ on S, it is customary to write Z Z P φ(z) = φ(y)P (z, dy), (λP )(A) = P (z, A)λ(dz). S
S
Thus λP is the distribution after one step when the initial distribution is λ, and (λP )(φ) = λ(P φ). In this way, the notation extends in a natural way the usual notation for countable state-space Markov chains, so that the role of the transition matrix is replaced by P . A standard source of transition kernels on general state spaces is a stochastic recursion driven by fresh random inputs that are independent of the current state and of the past. For example, suppose that (Rk )k≥1 is an i.i.d. sequence with common law µ on a measurable space R, and that Φ : S × R → S is measurable. The recursion Zk+1 = Φ(Zk , Rk ),
k ≥ 1,
defines a time-homogeneous Markov chain, with transition kernel P (z, A) = P(Φ(z, R) ∈ A) where R ∼ µ. This construction is the general-state-space analogue of specifying the one-step transition probabilities of a countable-state chain. Of main importance in the study of Markov chains are the invariant probability measures. A probability measure π on S is invariant for P if πP = π. Equivalently, for every bounded measurable φ : S → R, Z Z P φ(z)π(dz) = φ(z)π(dz). S
S
Thus, if Z1 ∼ π, then Zk ∼ π for every k ≥ 1. Invariant probability measures are the general-statespace version of stationary distributions. One common route to the existence of invariant measures uses compactness and continuity. A kernel P on a compact metric space S is called Feller if φ ∈ C(S)
=⇒
P φ ∈ C(S).
This is often proved via the Krylov–Bogoliubov averaging argument, which guarantees that every Feller kernel on a compact metric space admits at least one invariant probability measure. Indeed, starting from a point z0 ∈ S, one considers the empirical averages of the laws N −1
νN :=
1 X δ z0 P k . N k=0
29
and shows that a subsequence converges weakly to an invariant probability measure. This compact Feller argument is only one way to prove existence of invariant measures; the broader theory also provides recurrence and tightness criteria for noncompact spaces. A central tool in general-state-space Markov-chain theory is the Foster–Lyapunov drift inequality. For a non-negative measurable function V : S → [0, ∞], define the one-step drift by P V (z) − V (z) whenever the terms are well defined. A typical Foster–Lyapunov inequality has the form P V (z) − V (z) ≤ −f (z) + b1C (z),
z ∈ S,
(38)
where f : S → [0, ∞) is a measurable function, C ∈ B(S), and b < ∞. Here the function V is called the Lyapunov function, and it is chosen so that its expected one-step variation is negative away from a controlled region, whereas the function f is the quantity controlled by the drift, the set C is the exceptional region where the negative drift may fail, and the constant b measures the size of this local compensation. Inequalities of the form (38) play a role in the proof of several useful properties of a chain, such as recurrence, positive recurrence, existence of invariant measures, integrability of invariant measures, moment bounds, tail bounds, and convergence in weighted norms. The common mechanism is that a negative expected drift of V prevents the chain from spending too much time in regions where f is large. The simplest consequence appears after integrating a drift inequality against an invariant probability measure (see, e.g., [19, Theorem 2.2]). If πP = π and the integrals are justified, then (38) gives Z f (z)π(dz) ≤ b π(C) ≤ b. S
Indeed, invariance cancels the two Lyapunov terms: Z Z P V (z)π(dz) = V (z)π(dz). S
S
When V is bounded, as happens automatically on a compact state space if V is continuous, this cancellation is immediate. In more general settings, one often obtains the same conclusion through standard truncation or comparison arguments. This stationary expectation bound can be used as a form of moment and tail control. Indeed, if f grows at infinity, then π(f ) < ∞ says that the invariant distribution has limited mass in the tails. For example, choosing f (z) comparable to |z|p gives a p-th moment bound, while choosing f (z) comparable to exp(θ|z|) gives exponential integrability. Such integrability estimates can then be converted into tail estimates by elementary inequalities.
30