Mini-batch gradient 2026-11-05
A mini-batch gradient averages gradients of several sampled components of a finite-sum objective. For and batch indices ,With independent uniform draws at fixed , it is an unbiased stochastic gradient: . Its covariance matrix is , where is the covariance of one sampled gradient. The factor follows because centered independent cross terms have expectation zero.
If the indices are sampled uniformly without replacement, the covariance is instead for , when uses the uniform-population normalization. At this gives the exact full gradient. Larger batches reduce sampling variance but require more component evaluations per update; biased sampling or data dependence requires its own analysis.
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 4 30J ii Solution Created 2026-09-24 Updated 2026-10-14
Choose independently and uniformly from . Starting from any , the projected stochastic gradient descent iteration isConditional on , , so is an unbiased stochastic gradient. The metric projection onto a closed convex set keeps every iterate in . For a fixed step size, return the Cesàro average .
The discrete base factors in the displayed construction inherit their variational parameters. Accordingly write , not a parameter-independent , for the joint base probability mass function or probability density function. The continuous noise factors can be parameter independent while the discrete factors are dependent. Calling the entire base law parameterless while retaining its nonzero score function would be inconsistent.
Let push the base law forward to , and defineUse a fixed base measure , with counting measure for discrete coordinates and Lebesgue measure for continuous coordinates. Assume locally parameter-independent support, differentiability and an integrable domination permitting differentiation under the integral sign. A valid reparameterization gradient givesApply the product rule before simplifying:This is the required combined score and pathwise gradient estimator. A sample from and the integrand on the last line give an unbiased stochastic gradient under the stated regularity conditions. Its first term is a score-function gradient estimator contribution; the remaining terms differentiate the sampled objective along the continuous transformation. The same separation appears in the general stochastic computation graph construction.[ref]
All derivatives inside the expectation hold fixed. They still include both explicit parameter dependence and dependence through . For a continuous coordinate ,The model joint density is fixed as changes, but its composition with need not be constant. Discrete coordinates are not differentiated as real-valued paths; their changing probabilities enter through the score function. Moving supports or parameter-dependent branch boundaries require additional care and are not justified merely by formally interchanging a derivative and an integral.
Past exam of the optimisation for data science course of the University of Oxford 2023 2 e Solution 2026-10-25
Condition on , and set , and . Since the sampled index is independent of and has the discrete uniform distribution, is an unbiased stochastic gradient:Write . Expanding and using the zero conditional mean of proves the stochastic gradient second-moment identityThe stochastic gradient descent update is . Expanding the squared Euclidean distance and using the preceding identities givesThe subgradient inequality for the differentiable convex function gives . Combining this with (3),Removing the temporary notation for the conditioning point yieldsThe noise contributes twice in this argument: once in the supplied bound (3), and once in converting the expected squared step into the squared gradient. Each contribution is at most .
Stochastic gradient descent Created 2026-09-24 Updated 2026-11-05
Stochastic gradient descent updates an optimization parameter using a random estimate of the gradient:For a finite-sum objective , selecting an index uniformly and taking gives an unbiased stochastic gradient. Averaging several selected gradients gives a mini-batch gradient. The saving is fewer component evaluations per update, while the randomness adds variance. Unbiasedness or a controlled bias is an assumption, rather than an automatic property of any approximate gradient.[ref]
https://leon.bottou.org/publications/pdf/sirev-2018.pdf. Bottou, Curtis and Nocedal, Optimization Methods for Large-Scale Machine Learning, §4, stochastic-gradient formulation and noise/stepsize trade-offs
A simple noise example is and , where independent centered noises have variance . With a constant step size ,Its mean tends to zero, but its limiting variance is : solve . Thus constant steps can leave a stochastic gradient noise floor even for this strictly convex quadratic. Smaller or diminishing steps change the balance between progress and noise; a nonconvex stationarity estimate must not be read as guaranteed convergence to a global minimum.
Stochastic gradient second-moment identity 2026-10-25
For an unbiased stochastic gradient at with finite conditional second moment, expand in the squared Euclidean norm. The cross term has zero conditional expectation, which proves the displayed identity. It separates the squared true gradient from the total conditional variance of its random estimate.
Target: gradient-descent.bigb, under Stochastic gradient descent. Unbiased stochastic gradient Created 2026-09-29 Updated 2026-11-05
A random vector is an unbiased stochastic gradient at an iterate ifFor an adaptive iteration it is often useful to require the stronger historical condition , where contains all information available before drawing the new sample. This states explicitly which information is held fixed in the conditional expectation.
For , a conditionally uniform index gives . If index instead has positive sampling probability , then is the correctly weighted estimate. Omitting these factors generally changes its expectation.