ADAPTIVE PRIMAL–DUAL METHODS WITH AN INEXACT ORACLE FOR RELATIVELY SMOOTH OPTIMIZATION PROBLEMS AND THEIR APPLICATIONS TO RECOVERING LOW-RANK MATRICES

The article is devoted to adaptive primal-dual first-order methods for relatively smooth optimization problems with constraint inequalities, as well as their applications to problems of reconstruction of low-rank matrices. It is shown that for a certain class of relatively smooth problems of reconstruction of low–rank matrices, a triangular scaled property with a scaling coefficient of γ = 2 can be applied, which opened up the possibility of applying accelerated methods and methods of the Frank-Wolfe type and the results on their computational guarantees for such problems. An adaptive version of the similar triangles method is proposed for smooth problems with respect to the Bregman divergence with a triangular scaled property with a scaling coefficient of γ = 2. Non-accelerated and accelerated primal-dual adaptive methods with an inaccurate oracle for relatively smooth problems are also proposed. The accelerated primal-dual method is also an analogue of the method of similar triangles and uses the triangular scaled property of the Bregman divergence with a scaling coefficient γ = 2. The key feature of the methods studied in the article is the possibility of using inaccurate information in iterations and taking into account the inaccuracy of solving auxiliary subtasks in iterations of methods. This is natural due to the complication of such subtasks due to the use of the Bregman divergence instead of the square of the Euclidean norm. In particular, this led to a variant of the Frank–Wolfe method for a distinguished class of relatively smooth problems. For all the proposed methods, theoretical results on the quality of the solution were obtained.

primal-dual method, method of similar triangles, Frank–Wolfe method, relative smoothness, inaccurate oracle, triangular scaled property, low-rank matrix