  Majorization-minimization algorithms consist of successively minimizing a
sequence of upper bounds of the objective function so that along the iterations
the objective function decreases. Such a simple principle allows to solve a
large class of optimization problems, even nonconvex, nonsmooth and stochastic.
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
present convergence guarantees for nonconvex and convex optimization when the
higher-order upper bounds approximate the objective function up to an error
that is p times differentiable and has a Lipschitz continuous p derivative.
More precisely, we derive asymptotic stationary point guarantees for nonconvex
problems, and for convex ones we establish local linear convergence results,
provided that the objective function is uniformly convex. Unlike other
higher-order methods, ours work with any batch size. Moreover, in contrast to
most existing stochastic Newton and third-order methods, our approach
guarantees local convergence faster than with first-order oracle and adapts to
the problem's curvature. Numerical simulations also confirm the efficiency of
our algorithmic framework.
