Gradient-type method for optimization problems with Polyak - Lojasiewicz condition: relative inexactness in gradient and adaptive parameters setting

In this paper we consider the class of minimization problems with Lipschitz-continuous gradient and the well-known Polyak - Lojasiewicz condition. Optimization problems with the Polyak - Lojasiewicz condition are relevant because they are found in a wide variety of important applications, including non-linear systems with parameterization in deep learning. The presence of an inexactness in information available to a method is naturally possible, and the question of investigating the influence of such an inexactness on the quality of the solution given by the method arises. In the paper we investigate a formulation for the assumption of availability at any current point of the gradient of the target function with a relative inexactness. We propose some adaptive (self-tuning) gradient-type methods. If in the first of them the adaptivity of step size selection is realized only by the smoothness parameter of the target function, in the second method it’s also realized by the value related to the relative inexactness in the gradient. For each method, a theoretical estimate of the quality of the output point is obtained. The adaptive approach makes it possible, in particular, to apply the obtained results to problems with target functions which do not satisfy the Lipschitz condition of the gradient over the whole space. This is illustrated by the results of computational experiments for Rosenbrock and Nesterov - Skokov functions.