A regularized logistic finite sum with an exact minimizer

Given: The finite data set and objective in the Statement.

Finite-sum SVRG: SVRG returns an independent uniform inner iterate and uses a full gradient plus two component gradients per inner update.

Expected linear contraction of an SVRG epoch: if all components are convex, continuously differentiable and $L$-smooth, the average is $\mu$-strongly convex with a stationary point $x^{\ast }$, $n\ge 10L\mathrm{/}\mu$, $\eta =1\mathrm{/}(10L)$, and $m=2n$, then from a deterministic snapshot with the theorem's independent uniform component draws and output index the expected gap relative to $x^{\ast }$ contracts by its stated $q$.

Gradient of a finite sum is the finite sum of gradients: the gradient of the finite average is the average of component gradients.

Strong convexity for an extended-real objective: $\mu$-strong convexity is the strong-Jensen inequality with decrement $(\mu \mathrm{/}2)\theta (1-\theta )\mathrm{\mid }x-y{\mathrm{\mid }}^2$.

Lipschitz map, $\alpha$-Hölder map for rational $0<\alpha \le 1$, and contraction: an $L$-Lipschitz gradient obeys $\mathrm{\mid }{f}_i^{\mathrm{\prime }}(u)-f_i^{\mathrm{\prime }}(v)\mathrm{\mid }\le L\mathrm{\mid }u-v\mathrm{\mid }$ in one dimension.

The exponential function is smooth and $(\exp {)}^{\mathrm{\prime }}=\exp$: $(e^w{)}^{\mathrm{\prime }}=e^w$.

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $(\log u{)}^{\mathrm{\prime }}=1\mathrm{/}u$ for $u>0$.

The chain rule for total derivatives: $D(g\circ f)(a)=Dg(f(a))\circ Df(a)$: the derivative of a composition is the derivative of the outer function applied to the derivative of the inner function.

Sums and scalar multiples of totally differentiable maps are totally differentiable with the expected derivatives: sums and scalar multiples differentiate termwise.

The mean value theorem, as the case $g(x)=x$ of Cauchy's: for $f$ continuous on $[a,b]$ with $a<b$ and differentiable on $(a,b)$ there is $c\in (a,b)$ with $f(b)-f(a)=f^{\mathrm{\prime }}(c)(b-a)$: a differentiable scalar function's difference over an interval equals its derivative at an intermediate point times the interval length.

Multivariable Taylor formula with a Lagrange remainder along a line segment: a $C^2$ scalar function on a segment has a second-order Taylor formula with Hessian remainder at an intermediate point.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: in one dimension the Euclidean norm is absolute value.

The real exponential function and the number $e$ by a power series: $\exp (w)$ is the real exponential and $e=\exp (1)$.

Finite sums and finite products, by recursion: $F$ is the finite average of its fourteen component losses.

The natural logarithm as the inverse of the exponential function: for $x>0$, $\log x$ is the unique real $y$ with $\exp (y)=x$.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log$ is strictly increasing on $(0,\mathrm{\infty })$ and $\log (ab)=\log a+\log b$ for $a,b>0$.

The exponential is positive and satisfies $\exp (-x)=1\mathrm{/}\exp (x)$: $\exp (w)>0$ and $\exp (-w)=1\mathrm{/}\exp (w)$.

Convex and strictly convex functions on Euclidean convex sets: convexity is the segment inequality for function values.

Sign rules for products and monotonicity of multiplication: multiplication by a positive denominator preserves order. Squares of nonzero elements are positive makes a nonzero real square positive, and Multiplication by zero: $0\cdot a=0$ gives square zero in the zero case; thus every real square is nonnegative.

Laws of finite sums and finite products: finite sums are additive and obey scaling.

The Axiom of Choice: assume AC for the conditional-expectation interfaces inherited from the SVRG theorem [F2].