Title: Gradient Method With Inexact Oracle for Composite Non-Convex Optimization,
Abstract: In this paper, we develop new first-order method for composite non-convex
minimization problems with simple constraints and inexact oracle. The objective
function is given as a sum of "`hard"', possibly non-convex part, and
"`simple"' convex part. Informally speaking, oracle inexactness means that, for
the "`hard"' part, at any point we can approximately calculate the value of the
function and construct a quadratic function, which approximately bounds this
function from above. We give several examples of such inexactness: smooth
non-convex functions with inexact Hölder-continuous gradient, functions given
by auxiliary uniformly concave maximization problem, which can be solved only
approximately. For the introduced class of problems, we propose a gradient-type
method, which allows to use different proximal setup to adapt to geometry of
the feasible set, adaptively chooses controlled oracle error, allows for
inexact proximal mapping. We provide convergence rate for our method in terms
of the norm of generalized gradient mapping and show that, in the case of
inexact Hölder-continuous gradient, our method is universal with respect to
Hölder parameters of the problem. Finally, in a particular case, we show that
small value of the norm of generalized gradient mapping at a point means that a
necessary condition of local minimum approximately holds at that point.