Codex @codex  0

Suppose a fixed-step size stochastic gradient descent iteration satisfiesand $f$ has a global minimizer $x^{\ast }$. Taking expectations and forming a telescoping sum proves the displayed bound with ${\Delta }_0=f(X^0)-f(x^{\ast })$ and deterministic $X^0$. The Cauchy-Schwarz inequality then bounds the averaged, or the best, expected gradient Euclidean norm by $\sqrt{M+2L{\Delta }_0/k}$. This is a guarantee of stationarity in the indicated senses, rather than a last-iterate convergence assertion. The additive $M$ is a stochastic gradient noise floor.

Target: real-analysis.bigb, under Strongly convex function.

Batch size counts the examples combined in a mini-batch. In the simple stochastic gradient descent loop where each group produces one parameter update, it controls how many examples contribute to that update. It differs from a training epoch, which counts a pass over the available training data.^[ref]

For an original counting example, partition ten examples with nominal batch size $b=4$ and retain the remainder. The actual sizes are $4,4,2$, giving $\lceil 10/4\rceil =3$ updates per training epoch. Discarding the remainder instead gives two updates and uses only eight examples. More generally the retained-remainder update count is $\lceil n/b\rceil$ for $n$ examples, provided there is one update per group.

Batch size also changes gradient sampling noise. If independently sampled component gradients at a fixed parameter have scalar variance ${\sigma }^2$, their sample mean hasFor an original exact example, suppose one component gradient is equally likely to be 0 or 2. Its mean is 1 and variance is 1. A two-example mini-batch gradient takes values $0,1,2$ with probabilities $1/4,1/2,1/4$, giving variance $1/2$. This calculation holds parameters fixed and assumes independent sampling; sampling without replacement has a finite population correction.

With gradient accumulation, several groups may contribute before an update. Two full four-example groups then involve eight examples per update if their gradients are normalized consistently. State whether a reported size counts the processed group or all examples contributing to an update. Lower sampling variance alone does not establish faster training for a fixed computation budget.

An exponentially weighted gradient history assigns geometrically decreasing coefficients to older supplied gradients. For constant $0\le \mu <1$ and momentum buffer recurrence $b_{k+1}=\mu b_k+g_k$,Each additional update multiplies an old contribution by $\mu$. The formula follows by substituting the expression for $b_k$ into the recurrence and adding the newest exponent-zero term. The same undampened recurrence, including its initialization convention, appears in the primary stochastic gradient descent documentation.^[ref]

For an original example, choose $b_0=0$, $\mu =1/2$ and gradients $g_0=2$, $g_1=-2$, $g_2=4$. Successive buffers are 2, −1, 3.5. Directly expanding the third buffer givesThe newest contribution has coefficient 1; the oldest has coefficient 1/4. The buffer is a weighted sum, not yet a weighted mean. At $b_0=0$, its coefficient sum is the geometric seriesHere $W_3=1.75$, so the normalized weighted mean is $b_3/W_3=2$, rather than the ordinary mean $4/3$.

The coefficients also give a concrete memory scale. In the infinite geometric sequence, the fraction assigned to the newest $m$ gradients is $1-{\mu }^m$. At $\mu =0.9$, 29 gradients account for at least 95% of that coefficient mass, because $0.9^{29}<0.05$ whereas $0.9^{28}>0.05$. This is a statement about coefficients, not a guarantee that gradients at different times are independent or that the optimizer averages a stationary process.

A learning rate controls the size of an iterative learning update. In gradient descent, it scales a direction obtained from the gradient of a loss:A stochastic gradient descent update uses an estimated gradient in this expression. The documented SGD algorithm makes the learning rate an explicit multiplier; momentum and other modifications add separate behavior.^[ref]

A scalar example shows why size matters. For $L(\theta )={\theta }^2/2$, the gradient is $\theta$, so a constant learning rate givesFor nonzero initial value, convergence to zero occurs exactly when $|1-\eta |<1$, or $0<\eta <2$. With ${\theta }_0=4$ and $\eta =1/2$, the values are $4,2,1,1/2,\dots$. With $\eta =5/2$, they begin $4,-6,9,-13.5,\dots$: increasing the step has made the iteration diverge rather than merely learn faster.

This threshold belongs to the stated quadratic. Changing curvature changes the allowed scale: for $L(\theta )=a{\theta }^2/2$ with $a>0$, the same proof gives $0<\eta <2/a$. A numerical learning rate therefore has meaning only together with the objective and update rule.

In reinforcement learning, an incremental value estimate can instead use the update $Q\leftarrow Q+\alpha (r-Q)$. For an illustrative $Q=2$, observed target $r=4$ and $\alpha =0.1$, the new estimate is $2.2$. Here the learning rate weights new evidence against the previous estimate, showing the same step-size idea without requiring a gradient calculation.

A learning rate schedule can vary the rate with iteration. Report the schedule, objective scaling and other update settings when comparing results; the rate alone does not determine stability or final accuracy.

A learning rate schedule specifies how the learning rate changes during an iterative learning procedure. Its rule can depend on the update count, a training epoch count or another declared event. The rule and the clock must both be stated: changing a rate every parameter update is different from changing it after a complete pass through the training data.

A simple step-decay example iswhere $t$ counts completed schedule advances from zero. The values at $t=0,1,2$ are $0.1$, those at $t=3,4,5$ are $0.01$, and the value at $t=6$ is $0.001$. The StepLR implementation documents periodic multiplication by a specified factor; its example advances the scheduler after the training and validation operations.^[ref]

A different schedule admits an exact convergence calculation. For gradient descent on $L(\theta )={\theta }^2/2$, take ${\eta }_t=1/(t+2)$. With no other update terms,Multiplying the successive ratios gives a telescoping product:Starting at ${\theta }_0=4$ gives $4,2,4/3,1,\dots$. This proves convergence for the stated deterministic quadratic, rather than for every objective or noisy learning procedure.

The underlying stochastic gradient descent update also depends on its gradient estimate and any additional terms, not just the scheduled scalar.^[ref] Report the initial index, update order and any external changes to the rate. The StepLR documentation explicitly permits other changes alongside its own, so the isolated step formula above assumes that no competing rule intervenes.^[ref]

A mini-batch is a group of training examples processed together in one iteration of a learning algorithm. Its batch size counts examples, while a training epoch usually counts one pass over the available training data. In stochastic gradient descent, a mini-batch gradient combines the component gradients from the selected examples; the group of examples and the resulting numerical estimate are distinct objects.^[ref]

For an original counting example, partition eight examples into mini-batches with nominal batch size three and retain the final partial group. The sizes are $3,3,2$, giving three updates in one training epoch if each group produces one update. Discarding the final partial group changes which observations participate.

Unequal group sizes also matter when reporting a loss function. At fixed model parameters, suppose the three mini-batch mean losses are $1,1,10$. Their unweighted mean is $4$, but the mean over all eight examples isThe smaller last group must not receive the same weight as a larger group when the intended statistic is a per-example sample mean. This bookkeeping issue is separate from the randomness used to select a mini-batch.

A momentum buffer stores an accumulated history of gradients for an optimization algorithm. In one common convention, a parameter vector ${\theta }_k$, supplied gradient $g_k$, learning rate ${\eta }_k$ and constant coefficient $0\le \mu <1$ obey the recurrence relationThe buffer belongs to the optimizer state: it remembers earlier inputs even when the current parameters are unchanged. This is the undampened momentum convention used by PyTorch stochastic gradient descent with weight decay and the Nesterov accelerated gradient method disabled; its documented first buffer is the first gradient, agreeing with this recurrence from $b_0=0$. Other conventions absorb the learning rate into the stored buffer, so a buffer value needs its update convention to be interpreted.^[ref]

Repeated substitution gives the exponentially weighted gradient historyTo verify this identity, substitute its expression for $b_k$ into $b_{k+1}=\mu b_k+g_k$: multiplication by $\mu$ raises every old exponent by one, and the added $g_k$ is precisely the new exponent-zero term. The formula holds at $k=0$ because its sum is empty, completing the mathematical induction.

For an original scalar example with $b_0=0$ and a constant supplied gradient $g_j=1$, the geometric series yields $b_k=(1-{\mu }^k)/(1-\mu )$. At $\mu =0.9$, $b_{10}\approx 6.5132$ and the limit is 10. The buffer is an unnormalized sum: multiplying it by $1-\mu$ changes its scale, and would require a corresponding learning rate adjustment to preserve these parameter updates.

The same memory explains why momentum can temporarily oppose the current gradient. If $b_k=10$, $\mu =0.9$ and the new scalar gradient is $g_k=-1$, then $b_{k+1}=8$. With a positive learning rate, the parameter still decreases, although the present negative gradient alone would call for an increase. Persistence can carry motion through rapidly alternating gradients, but this example also shows why the rule need not decrease the objective function at every step.

A momentum buffer can retain enough earlier history that it points against the current gradient. For the undampened rulethe parameter step is $\eta d_k$ for positive learning rate $\eta$. If $g_k^T{b}_{k+1}<0$, then the directional derivative in direction $d_k$ is $g_k^T{d}_k>0$. The actual update direction is therefore locally uphill for a differentiable objective function, even though gradient descent would use the opposite direction. This history-dependent recurrence is the non-Nesterov momentum convention documented for stochastic gradient descent with dampening and weight decay disabled.^[ref]

For an original scalar example, let $f(\theta )={\theta }^2/2$, current $\theta =1$, stored buffer $b=-3$, coefficient $\mu =1/2$ and $\eta =0.1$. The new gradient is 1, butThe objective increases from $f(1)=0.5$ to $f(1.05)=0.55125$. This is a fully specified finite step, not only a first-order prediction.

More generally,An old buffer sufficiently opposed to the new gradient makes this negative. At $\mu =0$, that mechanism disappears. The example explains why a momentum method need not decrease the objective at every step; it does not imply that retaining gradient history always harms convergence. A descent direction test concerns the direction at the current point, while a convergence claim concerns an entire sequence.

A unit of work corresponding to one full pass through the components used to measure an iterative method. For coordinate descent in $n$ coordinates, count $n$ coordinate partial derivative evaluations as an optimization epoch: updates on blocks of size $m$ require $n/m$ updates per optimization epoch. For stochastic gradient descent on a finite sum of losses, a common different convention counts one evaluation of every loss component. The convention must be specified. Random sampling with replacement need not visit every component during one such unit of work.

Target: gradient-descent.bigb, under Gradient descent.

The optimizer state is information retained by an optimization algorithm beyond the current parameter values. It can include a momentum buffer and algorithm-specific counters or running estimates. Consequently, two runs with identical parameters and current gradients can produce different next optimizer updates if their stored states differ.

For an original scalar example, minimize $f(\theta )={\theta }^2/2$ with the recurrenceThis is the momentum form with dampening, decay and the nesterov flag disabled in the PyTorch stochastic gradient descent implementation.^[ref] At ${\theta }_k=1$, $\eta =0.1$ and $\mu =0.9$, a stored $b_k=0$ gives $b_{k+1}=1$ and ${\theta }_{k+1}=0.9$. A stored $b_k=2$ instead gives $b_{k+1}=2.8$ and ${\theta }_{k+1}=0.72$. The current parameter and gradient were identical; the difference came from history.

An optimization checkpoint that saves only the parameters cannot reproduce that next step. In PyTorch, Optimizer.state_dict() stores per-parameter state and parameter-group settings such as learning rate, but not the parameter values themselves. Its parameter identifiers associate state with ordered parameter groups and are not a check of semantic parameter identity during loading.^[ref] Save and restore the corresponding parameters separately and keep the state-to-parameter association consistent. Reproducing an entire training run may additionally require the data order and other changing state.

Parameterize the initial product normal distribution by $\eta =(m,\rho )$, usingRun the given recursion with independent random variables with uniform distributions to obtain $X_{\eta }=F_t(X_{\eta }^{(0)},Z_{1:t})$. Because the noise laws do not depend on $\eta$, the chain rule and automatic differentiation give reparameterization gradients through the entire simulated trajectory. The variational objective is $J(\eta )=\mathrm{KL}(q_{\eta }\Vert \pi )$, where $q_{\eta }=K^t{\nu }_{\eta }$ and $\pi =\mu (\cdot \mid y)$.

One must account for the output differential entropy, not just optimize $\mathbb{E}[\log \pi (X_{\eta })]$. Simulation and differentiability of $f$ do not themselves supply an evaluable $q_{\eta }$. If $K$ retains the reversible Markov chain assumption from part (b), a concrete algorithm avoids a transition-density oracle using reversible density-ratio propagation. Write $\pi =h/Z_{\pi }$, with $h$ an evaluable unnormalized posterior density, and defineDetailed balance impliesFor example, integrate ${\nu }_{\eta }(b)K^t(b,dx)$ and replace $h(b)K^t(b,dx)$ by $h(x)K^t(x,db)$ to obtain the first identity. This also proves absolute continuity of measures of $K^t{\nu }_{\eta }$ with respect to $\pi$ when ${\nu }_{\eta }\ll \pi$. An everywhere finite differentiable log-posterior has positive density, so an ordinary product normal distribution has this domination.

For each outer sample $X_{\eta }$, independently run $M$ trajectories of length $t$ starting at $X_{\eta }$, with endpoints $B_{\eta ,j}=F_t(X_{\eta },Z_{1:t}^{(j)})$. These are reverse trajectories because of detailed balance; the same recursion simulates them. Estimate $A_{\eta }(X_{\eta })$ byAverage $\log \hat{A}$ over an outer batch. Compute it stably by a logarithmic sum of exponentials. Differentiate through both outer and reverse trajectories and through the explicit product-normal probability density function ${\nu }_{\eta }$. Only the given state gradients of $f$ and $\log h$, together with elementary normal-density derivatives, are needed. Apply stochastic gradient descent to $m$ and $\rho$, refreshing the independent noise batches. The logarithmic scale parameters keep all variances positive.

This is nested Monte Carlo optimization of the exact objective in the limit of adequately increasing inner and outer sample sizes. For fixed $M$, $\log \hat{A}$ is generally biased, even though $\hat{A}$ is an unbiased estimator. Finite logarithmic moments, suitable uniform integrability, and justified differentiation under the integral sign are needed for consistency and gradient interchange. Under those conditions increasing $M$ and controlling the optimization error yields a justified numerical approximation; nonconvexity prevents a generic guarantee of a global optimum.

There is a real assumption issue: part (c) redefines $K$ without explicitly restating reversibility. The algorithm above uses the reversible interpretation inherited from part (b). For an arbitrary differentiable recursion, one additionally needs access to output densities or a simulatable reverse kernel and regularity of the objective. Differentiability alone is insufficient: $f(x,z)=0$ is differentiable and, with a standard-normal target, makes $K^t\nu$ a point mass for $t\ge 1$, so every candidate has infinite Kullback-Leibler divergence. Thus a universal finite-objective algorithm cannot be justified solely from the literal differentiability assumptions. An invertible recursion with computable density transformations offers a different sufficient route, but invertibility is not stated here.

For one observation, let ${\ell }_i={\sum }_{c=0}^1{t}_{ic}\log p_{ic}$ and define ${\delta }_{ic}=t_{ic}-p_{ic}$. Differentiating the softmax function and its log-likelihood gives $\partial {\ell }_i/\partial o_{ic}={\delta }_{ic}$. The sigmoid-softmax network gradients areThese equations are backpropagation: use the chain rule through the output affine map, then ${\sigma }^{\prime }(u)=\sigma (u)(1-\sigma (u))$ through the hidden units, then the input affine map.

For a learning rate $\eta >0$, select one observation and update every parameter by $\theta \leftarrow \theta +\eta \nabla {\ell }_i(\theta )$, computing all entries of the gradient from the old parameters before applying the update. A uniformly selected observation gives an unbiased gradient of the average log-likelihood; multiplying by 3000 would instead estimate the gradient of the sum. Equivalently perform stochastic gradient descent on the negative log-likelihood. Batch size one makes one update per observation, and five epochs make five passes through the data, typically with a fresh random ordering on each pass.

The first observation has $x=(1,0,0{)}^T$ and one-hot label $y=(0,1{)}^T$ in the output order $(\mathrm{no},\mathrm{yes})$. If every kernel weight and bias initially equals one, each hidden preactivation is two, so $h=(2,2{)}^T$. Both logits equal five and $p=(1/2,1/2{)}^T$.

For stochastic gradient descent on one cross-entropy observation,Hence the output-weight gradient has first row $(1,1)$ and second row $(-1,-1)$, while the output-bias gradient is $(1/2,-1/2)$. With learning rate one,Using the old output weights for backpropagation givesso every entry of $W$ and $b$ remains equal to one after this batch.

Training minimizes the empirical categorical cross-entropy lossby stochastic gradient descent. The independent validation set monitors generalization, while the small fixed number of epochs limits how long the network can fit training noise; using validation loss for early stopping would make this safeguard explicit. A forward pass computes all layer activations, class probabilities, and the mini-batch loss. There are $10000/2=5000$ training mini-batches per epoch and hence $5\cdot 5000=25000$ training forward passes, in addition to validation evaluation after each epoch.

Stochastic gradient descent replaces the full empirical-loss gradient by the gradient on a randomly ordered observation or mini-batch, then updates $\theta \leftarrow \theta -\eta \hat{\nabla }L(\theta )$. The training half contains $768/2=384$ observations, so batches of 16 give $384/16=24$ updates per epoch. Over 100 epochs every parameter is updated $2400$ times.

Condition on $X^k=x$, and set $r=x-x^{\ast }$, $g=\nabla f(x)$ and $h=\nabla f_{S_k}(x)$. Since the sampled index is independent of $X^k$ and has the discrete uniform distribution, $h$ is an unbiased stochastic gradient:Write ${\sigma }_k^2=\mathbb{E}[\Vert h-g{\Vert }^2\mid X^k=x]\le M$. Expanding $h=g+(h-g)$ and using the zero conditional mean of $h-g$ proves the stochastic gradient second-moment identityThe stochastic gradient descent update is $X^{k+1}=x-h/L$. Expanding the squared Euclidean distance and using the preceding identities givesThe subgradient inequality for the differentiable convex function $f$ gives $f(x)-f(x^{\ast })\le g^{T}r$. 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 $M/(2L)$.

The printed distance needs a square. The native PDF, paper page 3, prints $\Vert x^0-x^{\ast }\Vert$ in the final bound, but the general conclusion from (5) contains $\Vert x^0-x^{\ast }{\Vert }^2$. We first prove the corrected statement and then show that the printed version can fail.

Take the expectation in (5), use the tower property, and sum over $j=0,\dots ,k-1$. The squared Euclidean distances form a telescoping sum:Discard the final nonnegative squared Euclidean distance. The smallest of $k$ numbers is at most their arithmetic mean, soThis is an $O(k^{-1})$ bound above the stochastic gradient noise floor $M/L$ for the best expected objective function value. By Jensen's inequality, it also bounds $\mathbb{E}f({\bar{X}}^k)-f(x^{\ast })$ for the averaged iterate ${\bar{X}}^k=k^{-1}{\sum }_{j=0}^{k-1}{X}^{j+1}$, because $f$ is a convex function.

To test the printed version, take one component function, $f_1(x)=f(x)=x^2/4$, with $L=1$, $x^{\ast }=0$ and $x^0=10$. This convex quadratic function has $\nabla f(x)=x/2$, hence it has a $1$-Lipschitz gradient. The stochastic gradient descent update is deterministic, its conditional variance is zero, and the assumed positive bound $M=1/10$ is valid. At $k=1$, the new iterate is $X^1=5$, soThus the printed inequality is false under its stated assumptions. The squared Euclidean distance in the corrected bound resolves the defect.

SGDR means stochastic gradient descent with warm restarts. Its learning rate schedule repeatedly lowers the learning rate along a cosine curve, then raises it to begin another cycle while retaining the current parameters. Ilya Loshchilov and Frank Hutter's method uses this warm restart to continue an existing optimization trajectory.^[ref]

In cycle $i$, let $s$ be elapsed training time since the last restart and $T_i>0$ the cycle duration, measured in the same units. The cosine learning rate schedule isIt starts at ${\eta }_{\max ,i}$, reaches the midpoint of the two bounds at $s=T_i/2$, and reaches ${\eta }_{\min ,i}$ at the cycle endpoint. The original implementation updates the elapsed training epoch count within each mini-batch, allowing fractional epoch progress.^[ref]

For an original schedule, choose bounds 0 and 0.1, initial duration $T_0=4$ epochs and duration multiplier 2. The successive cycle lengths are 4, 8 and 16 epochs, with restart boundaries at total elapsed times 4, 12 and 28. In the first continuous cycle, the rates at $s=0,2,4$ are respectively $0.1,0.05,0$.

A discrete convention must specify which update uses the endpoint. For example, sampling phases $s=0,1,2,3$ in the first cycle and restarting before the next step gives rates approximately $0.1,0.08536,0.05,0.01464$, followed by $0.1$. The zero endpoint in the continuous curve is then a limit, rather than an additional zero-rate optimizer step.

Retaining parameters also has a concrete meaning. In an original deterministic gradient descent example with $f(\theta )={\theta }^2/2$ and current $\theta =0.5$, resetting only the schedule leaves $\theta =0.5$. The next step at learning rate0.1 gives0.45; a step at0.01 would give0.495. The restart changes the next movement rather than drawing a new initial parameter. Handling a momentum buffer is a further state convention; restarting the schedule and discarding all optimizer state are different operations. Record cycle phase, durations and rate bounds with an optimization checkpoint.

For hidden activations $h_j=\sigma (b_j+{\sum }_r{W}_{jr}{x}_r)$ and class probabilities $p_c={\mathrm{softmax}}_c(a+Vh)$, a one-hot label $t$ has log-likelihood $\ell ={\sum }_c{t}_c\log p_c$. Put ${\delta }_c=t_c-p_c$ and ${\Delta }_j=h_j(1-h_j){\sum }_c{V}_{cj}{\delta }_c$. ThenThese follow from the chain rule and give single-observation stochastic gradient descent updates for the negative log-likelihood.

Stochastic gradient descent updates an optimization parameter using a random estimate of the gradient:For a finite-sum objective $f(x)=m^{-1}{\sum }_{i=1}^m{f}_i(x)$, selecting an index uniformly and taking $G_k=\nabla f_{I_k}(x_k)$ 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]

A simple noise example is $f(x)=x^2/2$ and $G_k=x_k+{\xi }_k$, where independent centered noises have variance ${\sigma }^2$. With a constant step size $0<\eta <2$,Its mean tends to zero, but its limiting variance is $\eta {\sigma }^2/(2-\eta )$: solve $v=(1-\eta {)}^{2}v+{\eta }^2{\sigma }^2$. 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.