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.

Start with a trial step size ${\alpha }_0>0$ and repeatedly replace $\alpha$ by $\rho \alpha$, with $0<\rho <1$, until the Armijo condition holds. For a differentiable function and a descent direction, the short-step argument in the Armijo condition proves finite termination. This alone does not enforce the curvature part of the Wolfe conditions.

Use the induced spectral norm for the symmetric matrix $H$ and interpret $\Vert g\Vert /\Vert H\Vert =+\infty$ when $H=0$. If $q=g^{T}Hg\le 0$, the Cauchy point gives a decrease at least $\Delta \Vert g\Vert$. If $q>0$, its step size satisfies $\tau q\le \Vert g{\Vert }^2$ and $q\le \Vert H\Vert \Vert g{\Vert }^2$, soThus the numerical constant $1/2$ is independent of the model data. The bound links a nonzero gradient to a definite predicted decrease, including for an indefinite matrix $H$.

For $g\ne 0$, the Cauchy point minimizes the quadratic model along the feasible part of the negative gradient ray. Writing $q=g^{T}Hg$, its step size isIndeed $m(-tg)=a-t\Vert g{\Vert }^2+\frac{1}{2}{t}^{2}q$ on $0\le t\le \Delta /\Vert g\Vert$. For $q\le 0$ it decreases throughout that interval; otherwise its unconstrained minimum occurs at $t=\Vert g{\Vert }^2/q$. The constant $a$ does not affect the minimizing step.

Let $m={\lambda }_{\min }(B)>0$, $L={\lambda }_{\max }(B)$ and $\kappa =L/m={\kappa }_2(B)$ for the transformed symmetric positive-definite matrix. Then preconditioned steepest descent satisfiesThis is a worst-case bound, not necessarily the actual rate. For our scaled example the bound is $(1/50{)}^2=0.0004$, slightly above its computed factor $q_M\approx 0.000384321291$. If the initial transformed error is an eigenvector, exact line search for a positive-definite quadratic removes it in one step, regardless of the full condition number.

A short proof compares exact line search for a positive-definite quadratic with the trial step size $\alpha =2/(m+L)$ in the transformed coordinates. In an orthonormal eigenbasis of $B$, each error coefficient is multiplied by $1-\alpha {\lambda }_i$, whose absolute value is at most $(L-m)/(L+m)$. Summing ${\lambda }_i$ times the squared coefficients bounds the trial energy by the square of this factor. The exact minimizing step size does at least as well. This also explains the terminating case $m=L$: the trial step removes the entire error in one iteration.

Suppose $f$ is a differentiable convex function with coordinate Lipschitz continuity constant $L_i>0$. Put $\varphi (u)=D_f(u,y)=f(u)-f(y)-\nabla f(y{)}^T(u-y)$, the Bregman divergence from the supporting affine function at $y$. The subgradient inequality gives $\varphi \ge 0$, and its coordinate Lipschitz constant is still $L_i$. The coordinate descent lemma with step size $1/L_i$ yieldsSince ${\partial }_i\varphi (x)={\partial }_{i}f(x)-{\partial }_{i}f(y)$, rearrangement proves the bound. Continuous differentiability suffices; a Hessian matrix is unnecessary.

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

The displayed estimate, for all $x$ and real $t$, defines a coordinate Lipschitz constant $L_i$ for the partial derivative in coordinate $i$. It implies the coordinate descent lemmaby the fundamental theorem of calculus and integration of the Lipschitz continuity estimate. Subtracting an affine function leaves these constants unchanged.

The apparently weaker estimate along the singleton negative gradient direction is equivalent when every real step size is allowed: if the initial partial derivative is nonzero, any displacement can be written $-\alpha {\partial }_{i}f(x)e_i$; if it is zero but the final partial derivative is nonzero, reverse the endpoints; if both vanish the estimate is trivial.

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

This initial value problem uses a square root and absolute value to define a continuous function on all of ${\mathbb{R}}^2$. For every finite waiting time $c\ge 0$, a forward solution of a differential equation on $t\ge 0$ isThe constant solution of a differential equation $y_{\infty }(t)=0$ is another choice. For example, at $t=3$, waits $c=0,1,2,3$ give values $9,4,1,0$. These are dimensionless mathematical trajectories; no measured physical waiting time is being supplied.

Verification uses the original ordinary differential equation, including the join. Before departure, both $y_c^{\prime }$ and $2\sqrt{|y_c|}$ vanish. For $t>c$, their common value is $2(t-c)$. For $c>0$, the difference quotient at the join isThus the derivative exists at $c$, equals the rate law there, and is continuous across the join. For $c=0$ the same computation gives the right derivative at the starting endpoint. For $c>0$, the left and right second derivatives at departure are $0$ and $2$: these forward solutions of a differential equation are continuously differentiable functions, without being twice differentiable at departure. The local two-sided statement of the Peano existence theorem is separate from this explicitly forward family.

The rate law tends to zero as $y\to 0$, but its secant slopes from zero are unbounded:No finite local Lipschitz constant exists at zero. At $\epsilon =10^{-2},10^{-4},10^{-6}$ the quotient is $20,200,2000$, even though the rates are shrinking to zero. Continuity controls the rate itself; Lipschitz continuity would control its change relative to the state displacement.

There is also a numerical lesson. The forward Euler method starting exactly at zero gives $Y_{k+1}=Y_k+2\Delta t\sqrt{|Y_k|}=0$ at every step. It reproduces the constant solution of a differential equation for every positive step size, while the moving trajectories remain equally valid. A computation producing one trajectory cannot establish uniqueness. Likewise, the separable differential equation calculation that divides by $\sqrt{|y|}$ only describes the moving pieces: checking the original equation recovers the zero pieces and their joins.

Suppose $f$ is a differentiable function on an open convex set $D\subseteq {\mathbb{R}}^n$ and has an $L$-Lipschitz gradient there, in the Euclidean norm. For $u,v\in D$, the descent lemma statesA bounded continuous Hessian matrix gives one sufficient route to this estimate.^[ref]

For a short proof, put $d=v-u$. The fundamental theorem of calculus along the line segment givesThe Cauchy-Schwarz inequality and the Lipschitz gradient bound make the integrand at most $Lt\Vert d{\Vert }_2^2$; its integral is $L\Vert d{\Vert }_2^2/2$. This proof needs no assumption that $f$ is a convex function.

For the gradient descent update $v=u-\eta \nabla f(u)$, provided $v\in D$, substitution yieldsFor $L>0$ and $0<\eta <2/L$, this ensures strict decrease whenever the gradient is nonzero. At $\eta =2/L$ it guarantees only nonincrease; the quadratic example has a nonshrinking alternating component at this endpoint. At $\eta =1/L$ the guaranteed decrease is $\Vert \nabla f(u){\Vert }_2^2/(2L)$. A bound valid only on $D$ cannot justify a step leaving $D$.

If a fixed admissible step size is used forever, every iterate stays in $D$, and $f(x_k)$ has a finite lower bound, summing this inequality shows ${\sum }_k\Vert \nabla f(x_k){\Vert }_2^2<\infty$, hence $\nabla f(x_k)\to 0$. That conclusion alone gives neither convergence of the iterates nor a global minimum. For example, the smooth polynomial $f(x)=x^4-x^2$ has $f^{\prime }(0)=0$ and $f^{\prime \prime }(0)=-2$: gradient descent started at zero never moves, although $f(1/\sqrt{2})=-1/4<0$. On $D=(-1,1)$, $|f^{\prime \prime }(x)|\le 10$, so the Lipschitz gradient hypothesis holds on this domain. Convex functions and strongly convex functions provide additional structure; the exact quadratic convergence result above uses a positive-definite matrix.

A real vector field $f$ is dissipative in an inner product iffor all $x,y$. Two solutions of the ordinary differential equation $y^{\prime }=f(y)$ satisfyThus their distance never increases. The linear case $f(y)=Ay$ recovers the dissipative operator condition. B-stability asks whether a Runge-Kutta method preserves this contraction for every positive step size.

A line search that finds a global minimizer along the chosen ray, provided one exists. For a negative gradient direction, its decrease in the objective function is at least that of any admissible fixed step size. The cost of solving this one-dimensional minimization problem must be included when comparing computation time.

Target: vector-space.bigb, under Vector subspace.

Suppose $f$ is continuously differentiable, $s$ is a descent direction, and $f(x+\alpha s)$ is bounded below for $\alpha \ge 0$. A positive step size satisfying the weak Wolfe conditions exists. To prove this, put $\varphi (\alpha )=f(x+\alpha s)$, $d={\varphi }^{\prime }(0)<0$, and $h(\alpha )=\varphi (\alpha )-\varphi (0)-{\beta }_1\alpha d$. The Armijo condition proof shows $h<0$ just to the right of zero. Boundedness below gives $h(\alpha )\to +\infty$. Consequently there is a first positive zero $A$, with $h\le 0$ on $[0,A]$. By the mean value theorem, some $t\in (0,A)$ satisfiesAt $t$, $h(t)\le 0$ gives the Armijo condition, and the displayed derivative gives the weak Wolfe conditions.

Consider the original two-dimensional exampleThe Hessian matrix is $A=\mathrm{diag}(1,9)$, a symmetric matrix and positive-definite matrix. Its eigenvectors are the coordinate directions, its eigenvalues are $1$ and $9$, and its Euclidean norm condition number is $9$. The unique global minimum is $x_{\ast }=0$, so the error $e_k=x_k-x_{\ast }$ equals $x_k$. The linear map $I-\eta A$, with $I$ the identity matrix, givesFor $\eta =1/5=0.2$, the two coordinate error multipliers are $0.8$ and $-0.8$. Consequently $x_1=(1.6,-0.8{)}^T$, $x_2=(1.28,0.64{)}^T$, and the second coordinate changes sign at every step while both shrink. The Euclidean norm of the error contracts by $0.8$ each step. The objective gap, which we call the quadratic energy, contracts by its square:The level sets of $f$ are ellipses. Oscillation across their narrow direction is compatible with strictly decreasing energy.

For $\eta =1/4=0.25$, the coordinate error multipliers become $0.75$ and $-1.25$, giving $x_1=(1.5,-1.25{)}^T$. The first coordinate still tends to zero, but the second alternates and grows. Direct substitution givesThus a larger positive step size can turn a strictly convex function into a divergent iteration. Energy and error are different quantities: coordinate errors carry signed multipliers, while each coordinate's contribution to energy carries the squared multiplier.

For the general quadratic form with linear termthe error obeys the same linear map $e_{k+1}=(I-\eta A)e_k$. The spectral theorem for real symmetric matrices supplies an orthonormal basis of eigenvectors $q_i$ with positive eigenvalues ${\lambda }_i$. Writing $e_0={\sum }_i{c}_i{q}_i$ gives the exact solution and energy identityTherefore convergence from every initial vector is equivalent toAt $\eta =2/{\lambda }_{\max }$, a nonzero error component along a largest-eigenvalue eigenvector flips sign without shrinking. Above that threshold it grows. A particular start can still converge if it has zero components in every unstable direction; the interval is the condition for all starts. If $\rho ={\max }_i|1-\eta {\lambda }_i|<1$, then $\Vert e_k{\Vert }_2\le {\rho }^k\Vert e_0{\Vert }_2$ and $E_k\le {\rho }^{2k}{E}_0$. These bounds follow by summing the squared components in the orthonormal basis.

Gradient accumulation combines gradient contributions from several processed mini-batches before one optimizer update. Parameters stay fixed while those contributions are evaluated. With consistent normalization, an additive per-example loss function can therefore use an effective batch size larger than the group processed at once.^[ref]

For an original example, let per-example scalar gradients be $1,3,8$ at the same parameter value. Process the first two together and the last separately. Their means are 2 and 8. The combined per-example mean isThe unweighted mean of group means is 5 and gives the smaller group too much weight. One implementation accumulates each group's summed loss divided by the total example count, then performs one update.

Accumulation is also different from consecutive updates. Let $f_i(\theta )=(\theta -a_i{)}^2/2$, with $a=(-1,-3,-8)$, starting at $\theta =0$ and using step size $0.1$. One accumulated mean-gradient step gives $\theta =-0.4$. Updating first on the two-example mean gives $\theta =-0.2$; the last example then has gradient $7.8$, and a second step gives $\theta =-0.98$.

The distinction is where the gradients are evaluated. Agreement with one larger group requires fixed parameters and compatible model state, additive losses and consistent weighting. A method whose calculations depend on the whole group can violate those assumptions. State whether batch size denotes a processed group or the complete set contributing to an update.

Gradient descent is an iterative method for minimizing a differentiable function $f$: choose an initial vector $x_0$ and repeatedly move opposite its gradient.^[ref]

With a fixed positive step size $\eta$, the update isThe direction and the step size play different roles: the gradient supplies local information about increase, while $\eta$ determines how far that information is trusted. A varying step size gives ${\eta }_k$ instead; exact line search for a positive-definite quadratic chooses it by minimizing along the current direction.

Why is this the steepest direction? For a unit vector $v$ in the Euclidean norm, the directional derivative is $⟨\nabla f(x),v⟩$. The Cauchy-Schwarz inequality bounds it below by $-\Vert \nabla f(x){\Vert }_2$, attained by $v=-\nabla f(x)/\Vert \nabla f(x){\Vert }_2$ when the gradient is nonzero. This is steepest descent relative to the Euclidean norm; changing the norm can change the steepest direction. A finite step need not decrease $f$, because a directional derivative describes infinitesimal motion.

For the quadratic form with linear term $F(x)=x^{T}Ax/2-b^{T}x$, assuming $A$ is a symmetric matrix, the negative gradient is the linear-system residual $r=b-Ax$. Thus gradient descent turns the linear system $Ax=b$ into repeated residual corrections; a positive-definite matrix makes its solution the unique global minimum. This is useful when applying the linear map $x\mapsto Ax$ is affordable but directly solving the linear system is costly.

The attraction is that a gradient evaluation gives an entire update without solving a new linear system. The difficulty is choosing a step size that progresses along gently curved directions without overshooting steep ones. Fixed-step gradient descent on a positive-definite quadratic makes this tension exact: every eigenvector direction has its own multiplier, determined by its eigenvalue. The resulting condition number dependence explains why a narrow valley can slow even an inexpensive iterative method.

The simplicity of the gradient update and its sensitivity to the condition number of the Hessian matrix are central practical features.^[ref]

Let $A$ be real symmetric, let $b$ be a unit eigenvector satisfying $Ab=\lambda b$, and use scalar step sizes ${\alpha }_n$. The gradient of the displayed cubic polynomial function isOn the eigenline, $\nabla h(tb)=3\lambda t^{2}b$, so a gradient descent update remains on that same line and obeys the scalar recurrence in the title. Induction proves invariance for every iterate starting on the line, including an iterate that reaches zero. This is a statement about the geometry of the updates, not a convergence theorem: when $\lambda \ne 0$, the restriction $h(tb)=\lambda t^3$ is unbounded below in one direction.

For a smooth real function $F$ on Euclidean space, its downward gradient flow is the ordinary differential equation $\dot{x}=-\nabla F(x)$. The chain rule givesThus $F$ is a Lyapunov function, and a nonstationary trajectory cannot return to its starting point. For $F(x)=x^2/2$, the solution is $x(t)=x(0)e^{-t}$. The explicit Euler method gives $x_{n+1}=x_n-h\nabla F(x_n)$, namely gradient descent. The continuous decrease does not guarantee decrease for every discrete step size; even this quadratic example requires $0<h<2$ for strict contraction.

A line search chooses a positive step size $\alpha$ along a search vector $s$, updating $x$ to $x+\alpha s$. For a differentiable function $f$, a descent direction makes sufficiently short steps decrease the objective function; an Armijo condition quantifies the decrease, while the Wolfe conditions also prevent accepting an unnecessarily short step.

For a fixed symmetric matrix and positive-definite matrix $A$, what positive step size minimizes the largest coordinate error multiplier over all eigenvector directions? Let $m={\lambda }_{\min }>0$ and $L={\lambda }_{\max }$. Since $|1-\eta \lambda |$ is a convex function of $\lambda$, its maximum over the eigenvalues occurs at an endpoint:Balance the two extremes by solving $1-\eta m=-(1-\eta L)$:Here $\kappa$ is the Euclidean norm condition number of $A$. This balance is optimal: for $\eta <{\eta }_{\ast }$ the endpoint $1-\eta m$ exceeds ${\rho }_{\ast }$, and for $\eta >{\eta }_{\ast }$ the endpoint $\eta L-1$ exceeds ${\rho }_{\ast }$. The optimal worst-case energy factor is ${\rho }_{\ast }^2$, rather than ${\rho }_{\ast }$. This optimizes a uniform one-step bound; a particular initial error supported on fewer eigenvectors can have a different best step size.

In the example $m=1$, $L=9$, so ${\eta }_{\ast }=0.2$ and ${\rho }_{\ast }^2=0.64$. Both eigenvalue directions attain that energy factor, making the displayed history exact. The smaller step size $0.1$ instead givesIts first step reaches $E_1=1.665$, below $4.16$ for $\eta =0.2$, but subsequent progress is limited by the first direction's energy factor $0.81$. By $k=5$, the energies are approximately $0.69736$ and $0.69793$, respectively; by $k=6$, the $0.2$ iteration is ahead. A better first step need not yield a faster long-run history.

As the condition number grows, ${\rho }_{\ast }$ approaches one: stability in the direction of the largest eigenvalue forces small movement along the smallest-eigenvalue direction. This is a precise reason to improve scaling or use a method such as the conjugate gradient method, rather than merely increasing the step size. When $m=L$, choosing $\eta =1/m$ eliminates every error component in one step.

Fix an iteration and abbreviate $x=x^k$, $s=s^k$, $d=\nabla f(x{)}^{T}s$. Since $s$ is a descent direction, $d<0$. The directional derivative givesChoose $\bar{\alpha }>0$ so that $|o(\alpha )|\le \frac{1}{2}(1-{\beta }_1)(-d)\alpha$ for $0<\alpha \le \bar{\alpha }$. ThenThis is the Armijo condition for every such positive step size, and $\alpha =0$ gives equality. In particular, a backtracking line search terminates after finitely many reductions.