L-SVRG and L-Katyusha (Loopless Variance-Reduced Gradient Methods)

L-SVRG (Loopless Stochastic Variance-Reduced Gradient) and L-Katyusha (Loopless Katyusha) are single-loop stochastic variance-reduced optimization algorithms for finite-sum empirical risk minimization min_{x in R^d} f(x) = (1/n) sum_{i=1}^n f_i(x) that eliminate the deterministic outer epoch loop of SVRG and Katyusha and replace it with an independent biased coin flip performed at every iteration. At step k, both methods construct the unbiased variance-reduced estimator g^k = grad f_i(x^k) - grad f_i(w^k) + grad f(w^k) for i ~ Unif({1,...,n}) and update the reference point w^{k+1} to the current iterate (x^k in L-SVRG or y^k in L-Katyusha) with probability p in (0, 1] and keep w^{k+1} = w^k with probability 1 - p, achieving O((n + L/mu) log(1/epsilon)) and accelerated O((n + sqrt(nL/mu)) log(1/epsilon)) oracle complexities via a single-iteration Lyapunov contraction without requiring knowledge of the strong convexity constant mu to tune the epoch length in L-SVRG.