On Stochastic Proximal Linesearch Methods in ${\ell }_p$ Geometry

In this work we focus on stochastic nonconvex composite optimization and stochastic linesearch frameworks with each backtracking search reusing a fixed batch of samples (common random number-enabled). Prevailing stochastic linesearch methods of this type are formulated in Euclidean geometry and afflicted by restrictive assumptions or prior knowledge of problem dependent parameters. Motivated by these observations, we develop stochastic Armijo linesearch methods with a non-Euclidean proximal term (${\ell }_p$-norm square with $1<p\le 2$), under unbiased stochastic zeroth- and first-order oracles. They allow the algorithm inputs such as stepsizes and batchsizes to be selected without knowledge of problem dependent parameters, and the analysis is free of restrictive assumptions such as strong growth conditions and bounded gradient. Both minibatch and variance-reduced variants are considered and corresponding complexity guarantees are derived with first-order stationarity residual measured in the dual norm. The results include the Euclidean case and a near-${\ell }_1/{\ell }_{\infty }$ specialization, extend to controlled inexact subproblem solves, and are supported by numerical comparisons with stochastic linesearch and variance-reduced baselines.