Motivation
A basic stochastic gradient can remain noisy at the solution. Individual records may prefer different parameter values even though their average gradient is zero. Reducing the step size eventually suppresses that noise, but also slows movement. Variance reduction takes another route: occasionally compute a full reference gradient and use it to correct cheap sampled directions. The correction should preserve the desired mean while canceling noise that the reference already explains.
This unit develops a complete snapshot method and its convergence proof under convexity assumptions. The method is commonly called stochastic variance-reduced gradient, or SVRG. Its name is less important than the estimator: evaluate the same sampled component at the current parameter and at a fixed snapshot, subtract the two, then add the full snapshot gradient. Using the same index in both places is essential. Two independently chosen indices define a different estimator and can destroy the cancellation.
We also examine a fixed preconditioner. It changes which directions count as long and which gradients count as large. A good choice can turn a badly stretched quadratic into a well-scaled problem; a poor or unjustified choice can invalidate a step-size argument. The proofs below therefore specify both the component smoothness and the geometry.
Definitions
Definition 7.1.1
(Finite-sum objective with strongly convex average)
Let on . Every component is differentiable, convex and globally -smooth, with the same valid constant . Assume is -strongly convex, , and has minimizer . Strong convexity means
In particular and the minimizer is unique. Component convexity is an extra assumption; it does not follow just because their average is strongly convex.
Definition 7.1.2
(Snapshot epoch)
An epoch fixes a snapshot , computes , and starts . At inner step , draw a fresh uniform independent index , form
After steps, the next snapshot is the average .
This precise output rule matters in the proof. Returning the last inner iterate instead requires another argument. All expectations below are conditional on the snapshot and past inner draws when appropriate; the new index remains uniform after those quantities are fixed.
Theorem/proposition
Theorem 7.1.3
(The corrected direction is unbiased and loses its noise)
For fixed current point and snapshot , let with uniform index . Then and
At the direction is exactly the full gradient, independent of the index. At it vanishes even when individual component gradients at the minimizer are nonzero.
Theorem 7.1.4
(A complete epoch contraction)
Under the stated convexity assumptions, choose . If the new snapshot is the inner-iterate average, then
In particular and give . Repeating epochs yields expected objective gap at most times its initial value after epochs. This is an expectation guarantee, not monotone improvement of every realized inner step.
The displayed epoch inequality itself is valid for . Contraction requires . The stricter choice makes , so that choosing a sufficiently large epoch length makes contraction attainable.
Proof sketch or proof idea
Proof
(Tangent subtraction and centering)
For one component, subtract its tangent plane at and call the resulting function . Convexity makes a minimizer of , and its gradient remains -Lipschitz. Applying the smooth upper model to a step of length in the negative gradient direction gives . Average over and use to obtain
Write as the difference between the current component gradient relative to its value at and the centered version of the snapshot's corresponding difference. The squared norm of a difference is at most twice each squared norm, and centering cannot increase a second moment. Applying the preceding inequality at and gives the first theorem. Taking expectations directly proves unbiasedness. The bound controls a second moment; it should not be described as the exact noise variance.
Proof X-ray
Why the tangent plane is subtracted first
The inequality measures the gap to the minimum of the function itself, and a component is usually not minimized at . Subtracting the tangent plane leaves the gradient differences unchanged, and component convexity is used exactly here, to make the minimizer of . Because , the average of the is , so the bound returns to the objective gap. The second idea is the splitting of into a part at and a centered part at : the elementary inequality and centering then give the constant .
Proof
(Telescoping the distance over an epoch)
For contraction, expand the squared distance after an update:
Conditional unbiasedness replaces by in the middle term, convexity gives , and the second-moment bound controls the last term. Together they give
Sum over the epoch and discard the nonnegative final distance. The initial distance is at most twice the snapshot gap divided by . Convexity bounds the objective at the average by the average of objectives. Divide by to obtain . Substitution of the specified step and epoch length makes its two terms at most one quarter each. Conditioning on each random snapshot before repeating this argument proves the multi-epoch statement.
Proof X-ray
One use of each hypothesis in the epoch proof
Each hypothesis enters at one identifiable point. A fresh uniform index given the past turns the cross term into in expectation, and convexity of bounds this by . Component convexity and smoothness enter only through the second-moment bound, which produces both the factor and the snapshot term . Strong convexity is used exactly once, to bound by ; that is the origin of the first term of . The telescoping sum closes because the final distance is nonnegative and can be discarded, and convexity of turns the average of the inner gaps into the gap at the averaged point. The last inner iterate has no such inequality, which is why the output rule belongs to the theorem.
Component convexity may look like a technicality, since the code runs unchanged without it. The following example shows that the second-moment bound itself fails.
Counterexample mode
A concave component breaks the second-moment bound
Claim: if the average is strongly convex and every component is -smooth, the bound of the first theorem holds without component convexity. Take , , and . Both components are -smooth, so , and is -strongly convex with ; but is concave. At and , the direction is , which equals or , so . The claimed bound is , which is smaller. The failing step is : here , so at the left side is and the right side is . Smoothness alone gives only , which needs a separate analysis; component convexity is the hypothesis that restores the stated bound.
Worked examples
Worked example 7.1.5
(A complete executable finite-sum method)
The following program minimizes three diagonal quadratics. Component has diagonal entries and center , with loss . The average Hessian is , so is valid, while bounds every component Hessian. The exact minimizer is . The average is accumulated before each update, matching the theorem's output rule.
import math
import random
data = [([1.0, 4.0], [1.0, 0.0]),
([2.0, 8.0], [0.0, 1.0]),
([3.0, 12.0], [-1.0, -1.0])]
def gradient(i, x):
h, center = data[i]
return [hj * (xj - aj) for hj, xj, aj in zip(h, x, center)]
def objective(x):
return math.fsum(0.5 * math.fsum(hj * (xj - aj)**2
for hj, xj, aj in zip(h, x, center))
for h, center in data) / len(data)
def svrg(start, epochs=5, seed=5):
n, d = len(data), len(start)
L, mu = 12.0, 2.0
eta, steps = 1 / (10 * L), math.ceil(50 * L / mu)
rng = random.Random(seed)
snapshot = list(start)
history = [objective(snapshot)]
for _ in range(epochs):
full = [0.0] * d
for i in range(n):
gi = gradient(i, snapshot)
full = [a + b / n for a, b in zip(full, gi)]
x = list(snapshot)
average = [0.0] * d
for _ in range(steps):
average = [a + b / steps for a, b in zip(average, x)]
i = rng.randrange(n)
now, old = gradient(i, x), gradient(i, snapshot)
direction = [a - b + c for a, b, c in zip(now, old, full)]
x = [a - eta * b for a, b in zip(x, direction)]
snapshot = average
history.append(objective(snapshot))
return snapshot, history
answer, history = svrg([3.0, 3.0])
optimum = [-1/3, -1/6]
assert objective(answer) >= objective(optimum) - 1e-12
print([round(x, 6) for x in answer])
print([round(value - objective(optimum), 6) for value in history])
The assertion checks only a mathematical lower bound, not convergence on all possible seeds. The code's trajectory illustrates the specified finite algorithm. Its random generator is reproducible; the proof idealizes fresh independent uniform indices. It never uses an observed decrease as a replacement for checking convexity and smoothness.
For the displayed run, the final point rounded to six places is [-0.332576, -0.166667]. Rounded objective gaps, including the starting point, are approximately 51.222222, 0.552737, 0.020938, 0.000538, 0.000022, 0.000001. These numbers check a particular implementation and seed. They are not substituted into the proof to estimate a universal contraction rate.
Worked example 7.1.6
(Cancellation of noise that survives at the solution)
Take and . Their average is , minimized at zero, yet individual gradients there are minus one and plus one. A basic sampled gradient remains noisy. The corrected direction is for either component, so in this particular problem it equals the full gradient at every point. The component offsets cancel because the same index is used twice. Independently sampling the two offsets would reintroduce noise.
Worked example 7.1.7
(Preconditioning removes a known quadratic stretch)
Let . Ordinary gradient descent with step one half multiplies the second coordinate by minus forty-nine and is unstable. Choose and update . With , both coordinates are halved, so the objective becomes one quarter of its previous value. The preconditioner encodes curvature information; it is not a universally safe operation for an arbitrary objective.
Example three suggests a general description of what a fixed preconditioner does.
Concept lensGeometric
Preconditioning as a change of coordinates
A fixed symmetric positive definite has a precise interpretation. Set and . The chain rule gives transformed gradients . Applying the same algorithm in coordinates is exactly the preconditioned update in . For twice differentiable losses, transformed Hessians are . Bounds on these matrices provide transformed smoothness and strong-convexity constants. The component upper bound must cover every component; conditioning only the average Hessian does not automatically bound the sampled gradients.
The distance in the proof changes with the coordinates too. In coordinates the squared distance is , the -quadratic form of the original difference rather than the Euclidean distance. One therefore cannot keep the old constants while replacing the update matrix arbitrarily. Objective values still refer to the same points, and inner-iterate averages are compatible because the change of coordinates is linear, but distances and step sizes must be read in one geometry.
For the stretched quadratic, that transformed Hessian is the identity. In a general large problem, constructing or applying may itself be expensive. A diagonal approximation has low storage and cheap application, while a dense exact inverse needs substantially more work. Compare total costs, including preprocessing and repeated applications, before declaring a smaller iteration count a computational gain. A changing preconditioner also leaves the fixed-coordinate transformation used in this proof.
Planning accuracy and checking a stopping point
The expected-gap theorem gives a concrete sufficient budget. If the initial gap is at most and the desired expected gap is , at least epochs suffice with the specified parameters. Combining this with the epoch cost gives order component-gradient evaluations, with the explicit constants supplied above. The initial bound and curvature constants must be justified; choosing optimistic values after inspecting a short run is not a proof of that budget.
There is also a pointwise certificate when the true full gradient is available.
Proposition 7.1.8
(Gradient certificate under strong convexity)
If is -strongly convex with minimizer , then for every point ,
Proof
(Minimizing the quadratic lower model)
Strong convexity at gives for every . The right side is a quadratic in , minimized at with value . Hence for every , in particular for , which is the claim.
The snapshot full-gradient calculation can therefore certify a sufficiently small gap without knowing the minimum objective value explicitly. This is a deterministic inequality under the strong-convexity hypothesis, so it applies to a randomly produced point as well. Replacing the full gradient by one noisy sampled direction would remove the certificate. In floating point, an unusually small computed gradient also requires attention to cancellation and numerical precision before it is interpreted at an arbitrarily fine tolerance.
Common mistakes
Common mistake
(Replacing or moving the snapshot gradient)
The full snapshot gradient is part of the estimator. Replacing it by an arbitrary noisy minibatch average does not preserve the exact conditional formula used above. There are useful methods with approximate snapshots, but they require another analysis. Likewise, a snapshot must remain fixed within the epoch; changing it after every sampled update changes both the estimator and the proof.
Common mistake
(Counting inner steps but not full passes)
One uncached epoch evaluates component gradients and uses working vectors in addition to stored or accessible data. Caching all component snapshot gradients can reduce repeated evaluations but adds storage. The benefit of variance reduction depends on the balance between full passes, inner steps, memory and the target accuracy. The contraction theorem gives a transparent sufficient budget, with conservative constants, rather than a universal fastest parameter choice.
Common mistake
(Quoting the linear rate outside strong convexity)
Strong convexity describes a particular objective and parameterization. Overparameterized models may have nonunique minimizers, and many neural-network objectives are nonconvex. The executable loop can still run there, but this global linear-convergence proof no longer certifies it. Reporting the distinction is part of using the theorem correctly.
Summary
Snapshot correction preserves the full gradient in expectation and cancels component noise near a solution. Component convexity and smoothness control its second moment, while strong convexity yields an explicit epoch contraction for the averaged output. Fixed preconditioning is a change of coordinates whose transformed constants must be checked. Algorithm, output rule, assumptions and resource budget belong in the same explanation.
Exercises
Quick check
(For the two offset quadratics in the second example, take and . Compute the corrected direction for each index and the next point when .)
Solution · Answer
The snapshot full gradient is . For the first component, the correction is . For the second it is . Both give the next point . The cancellation is exact because the component offset appears with opposite signs for the same index.
Quick check
(Take , , and . Evaluate the contraction factor in the theorem. How many epochs suffice to reduce its expected gap bound by a factor of at least thirty-two?)
Solution · Answer
Here and . The first term is , and the second is . Thus . Five epochs give the factor in expectation. This does not promise that each individual run improves by exactly that factor.
Quick check
(For and , find the transformed Hessian. Compare ordinary and preconditioned gradient descent at step from .)
Solution · Answer
The transformed Hessian is . Ordinary descent gives , whereas preconditioned descent gives . The latter halves both coordinates and quarters the quadratic objective. The former grows the second coordinate dramatically because its step is too large for the original curvature.
Quick check
(Explain why using a last inner iterate, independently chosen indices in the two component gradients, or a changing preconditioner cannot be justified merely by quoting this epoch proof. Identify the specific step affected in each case.)
Solution · Answer
The proof uses convexity to bound the objective at the average by the average of inner objectives; it gives no such conclusion for the last iterate alone. Same-index subtraction supplies the component-gradient cancellation behind the second-moment bound; independent indices change that noise calculation. A fixed preconditioner supplies one global coordinate transformation and one set of constants; changing it requires controlling a varying geometry. Each modification needs its own theorem, even if its code looks similar.