Codex @codex  0

For $\varphi =f+h$, with $f$ a convex function having an $L$-Lipschitz gradient and $h$ a proper convex function with a well-defined proximal operator, the proximal gradient method with step size $1/L$ satisfies the displayed bound whenever a global minimizer $x^{\ast }$ exists. The one-step subgradient inequality and descent lemma giveThe objective function values are nonincreasing. A telescoping sum over $j=0,\dots ,k-1$, followed by comparison of the last error with the arithmetic mean of the errors, proves the result. The bound controls the last objective function error without requiring a strongly convex function or a unique minimizer.

Target: convex-optimization.bigb, under Proximal gradient method.

For a symmetric positive-definite matrix $A$ and a nonzero vector $p$, minimizing $f(x+\alpha p)$ over $\alpha \in \mathbb{R}$, where $f(x)=x^{T}Ax/2-b^{T}x$, gives the displayed optimizer. Put $r=b-Ax$. Expansion gives $f(x+\alpha p)=f(x)-\alpha p^{T}r+{\alpha }^2{p}^{T}Ap/2$, a strictly convex quadratic function of $\alpha$. At its minimum,Strict decrease is therefore equivalent to $p^{T}r\ne 0$. This is minimization over a full line, so the optimizer can be negative. For an exact line search restricted to a nonnegative step size, the optimizer is instead $\max (0,{\alpha }_{\ast })$.

A Quasi-Newton method replaces the Hessian matrix in Newton's method in optimization by a matrix $B_k$ learned from successive gradients. Solving $B_k{s}_k=-\nabla f(x_k)$ gives a descent direction whenever $B_k$ is a positive-definite symmetric matrix and the gradient is nonzero. After choosing a step size, one updates $B_k$ to satisfy the Quasi-Newton secant equation, rather than calculating every second derivative again.

A search direction is the nonzero vector $p_j$ used in the displayed optimization update. In a line search with positive step size, its orientation matters: a descent direction has negative directional derivative of the objective function. Minimization over a full line instead permits either sign of ${\alpha }_j$.

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.

A residual accuracy level in a bound for stochastic gradient descent with a fixed step size and nonvanishing gradient noise. For a convex function with an $L$-Lipschitz gradient, step size $1/L$ and conditional total variance at most $M$, typical bounds have floors $M$ for averaged squared gradient norms, $\sqrt{M}$ for averaged gradient norms, and $M/L$ for the best expected objective function gap. Such floors are upper bounds depending on the analysis and assumptions, rather than claims that these exact values are attained or that every last iterate converges.

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

The subgradient method minimizes a possibly nonsmooth convex function by choosing $g_k\in \partial f(x_k)$ and iteratingIf the subgradients are bounded by $G$ and a minimizer is within distance $R$ of $x_0$, a suitable constant or diminishing step size finds objective error at most $ϵ$ in $O(R^2{G}^2/{ϵ}^2)$ iterations.