  Majorization-minimization schemes are a broad class of iterative methods
targeting general optimization problems, including nonconvex, nonsmooth and
stochastic. These algorithms minimize successively a sequence of upper bounds
of the objective function so that along the iterations the objective value
decreases. We present a stochastic higher-order algorithmic framework for
minimizing the average of a very large number of sufficiently smooth functions.
Our stochastic framework is based on the notion of stochastic higher-order
upper bound approximations of the finite-sum objective function and
minibatching. We derive convergence results for nonconvex and convex
optimization problems when the higher-order approximation of the objective
function yields an error that is p times differentiable and has Lipschitz
continuous p derivative. More precisely, for general nonconvex problems we
present asymptotic stationary point guarantees and under Kurdyka-Lojasiewicz
property we derive local convergence rates ranging from sublinear to linear.
For convex problems with uniformly convex objective function we derive local
(super)linear convergence results for our algorithm. Compared to existing
stochastic (first-order) methods, our algorithm adapts to the problem's
curvature and allows using any batch size. Preliminary numerical tests support
the effectiveness of our algorithmic framework.
