All issues

В работе предлагается новая версия метода Гаусса–Ньютона для решения системы нелинейных уравнений, основанная на идеях использования верхней оценки нормы невязки системы уравнений и квадратичной регуляризации. Предложенная версия метода Гаусса–Ньютона на практике фактически задает целое параметризованное семейство методов решения систем нелинейных уравнений и задач восстановления регрессионной зависимости. Разработанное семейство методов Гаусса–Ньютона состоит целиком из итеративных методов, включающих в себя также специальные формы алгоритмов Левенберга–Марквардта, с обобщением на случаи применения в неевклидовых нормированных пространствах. В разработанных методах используется локальная модель, осуществляющая параметризованное проксимальное отображение и допускающая на практике применение неточного оракула в формате «черного ящика» с ограничением на точность вычисления и на сложность вычисления. Для разработанного семейства методов приведен анализ эффективности в терминах количества итераций алгоритма, точности и сложности представления локальной модели и вычисления оракула, параметров размерности решаемой задачи с выводом локальной и глобальной сходимости при использовании произвольного оракула. В работе представлены условия глобальной сублинейной сходимости для предложенного семейства методов решения системы нелинейных уравнений, состоящих из гладких по Липшицу функций. В рамках дополнительных естественных предположений о невырожденности системы нелинейных функций установлена локальная суперлинейная сходимость для рассмотренного семейства методов. При выполнении условия Поляка–Лоясиевича для системы нелинейных уравнений доказана локальная и глобальная линейная сходимость рассмотренных методов Гаусса–Ньютона. Помимо теоретического обоснования методов, в работе рассматриваются вопросы их практической реализации. В частности, в проведенных экспериментах для точного оракула приводятся схемы эффективного вычисления в зависимости от параметров размерности решаемой задачи. Предложенное семейство методов объединяет в себе несколько существующих и часто используемых на практике модификаций метода Гаусса–Ньютона, позволяя получить гибкий и удобный в использовании метод, реализуемый на практике с помощью стандартных техник выпуклой оптимизации и вычислительной линейной алгебры.

In this paper, we introduce a new version of Gauss–Newton method for solving a system of nonlinear equations based on ideas of the residual upper bound for a system of nonlinear equations and a quadratic regularization term. The introduced Gauss–Newton method in practice virtually forms the whole parameterized family of the methods solving systems of nonlinear equations and regression problems. The developed family of Gauss–Newton methods completely consists of iterative methods with generalization for cases of non-euclidean normed spaces, including special forms of Levenberg–Marquardt algorithms. The developed methods use the local model based on a parameterized proximal mapping allowing us to use an inexact oracle of «black–box» form with restrictions for the computational precision and computational complexity. We perform an efficiency analysis including global and local convergence for the developed family of methods with an arbitrary oracle in terms of iteration complexity, precision and complexity of both local model and oracle, problem dimensionality. We present global sublinear convergence rates for methods of the proposed family for solving a system of nonlinear equations, consisting of Lipschitz smooth functions. We prove local superlinear convergence under extra natural non-degeneracy assumptions for system of nonlinear functions. We prove both local and global linear convergence for a system of nonlinear equations under Polyak–Lojasiewicz condition for proposed Gauss– Newton methods. Besides theoretical justifications of methods we also consider practical implementation issues. In particular, for conducted experiments we present effective computational schemes for the exact oracle regarding to the dimensionality of a problem. The proposed family of methods unites several existing and frequent in practice Gauss–Newton method modifications, allowing us to construct a flexible and convenient method implementable using standard convex optimization and computational linear algebra techniques.

Статья посвящена выпукло-вогнутым седловым задачам, в которых целевая функция является суммой большого числа слагаемых. Такие задачи привлекают значительное внимание математического сообщества в связи с множеством приложений в машинном обучении, включая adversarial learning, adversarial attacks и robust reinforcement learning, и это лишь некоторые из них. Отдельные функции в сумме обычно представляют собой ошибку, связанную с объектом из выборки. Кроме того, формулировка допускает (возможно, негладкий) композитный член. Такие слагаемые часто отражают регуляризацию в задачах машинного обучения. Предполагается, что размерность одной из групп переменных относительно мала (около сотни или меньше), а другой — велика. Такой случай возникает, например, при рассмотрении двойственной формулировки задачи минимизации с умеренным числом ограничений. Предлагаемый подход основан на использовании метода секущей плоскости Вайды для минимизации относительно внешнего блока переменных. Этот алгоритм оптимизации особенно эффективен, когда размерность задачи не очень велика. Неточный оракул для метода Вайды вычисляется через приближенное решение внутренней задачи максимизации, которая решается ускоренным алгоритмом с редукцией дисперсии Katyusha. Таким образом, мы используем структуру задачи для достижения быстрой сходимости. В исследовании получены отдельные оценки сложности для градиентов различных компонент относительно различных переменных. Предложенный подход накладывает слабые предположения о целевой функции. В частности, не требуется ни сильной выпуклости, ни гладкости относительно низкоразмерной группы переменных. Количество шагов предложенного алгоритма, а также арифметическая сложность каждого шага явно зависят от размерности внешней переменной, отсюда предположение, что она относительно мала.

The paper is devoted to convex-concave saddle point problems where the objective is a sum of a large number of functions. Such problems attract considerable attention of the mathematical community due to the variety of applications in machine learning, including adversarial learning, adversarial attacks and robust reinforcement learning, to name a few. The individual functions in the sum usually represent losses related to examples from a data set. Additionally, the formulation admits a possibly nonsmooth composite term. Such terms often reflect regularization in machine learning problems. We assume that the dimension of one of the variable groups is relatively small (about a hundred or less), and the other one is large. This case arises, for example, when one considers the dual formulation for a minimization problem with a moderate number of constraints. The proposed approach is based on using Vaidya’s cutting plane method to minimize with respect to the outer block of variables. This optimization algorithm is especially effective when the dimension of the problem is not very large. An inexact oracle for Vaidya’s method is calculated via an approximate solution of the inner maximization problem, which is solved by the accelerated variance reduced algorithm Katyusha. Thus, we leverage the structure of the problem to achieve fast convergence. Separate complexity bounds for gradients of different components with respect to different variables are obtained in the study. The proposed approach is imposing very mild assumptions about the objective. In particular, neither strong convexity nor smoothness is required with respect to the low-dimensional variable group. The number of steps of the proposed algorithm as well as the arithmetic complexity of each step explicitly depend on the dimensionality of the outer variable, hence the assumption that it is relatively small.

В работе описывается двухстадийная модель равновесного распределения транспортных потоков. Модель состоит из двух блоков, где первый блок — модель расчета матрицы корреспонденций, а второй блок — модель равновесного распределения транспортных потоков по путям. Первая модель, используя матрицу транспортных затрат (затраты на перемещение из одного района в другой, в данном случае — время), рассчитывает матрицу корреспонденций, описывающую потребности в объемах передвижения из одного района в другой район. Для решения этой задачи предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийную модель. Вторая модель на базе равновесного принципа Нэша–Вардропа (каждый водитель выбирает кратчайший для себя путь) описывает, как именно потребности в перемещениях, задаваемые матрицей корреспонденций, распределяются по возможным путям. Таким образом, зная способы распределения потоков по путям, можно рассчитать матрицу затрат. Равновесием в двухстадийной модели транспортных потоков называют неподвижную точку цепочки из этих двух моделей. Практически ранее отмеченную задачу поиска неподвижной точки решали методом простых итераций. К сожалению, на данный момент вопрос сходимости и оценки скорости сходимости для этого метода не изучен. Кроме того, при численной реализации алгоритма возникает множество проблем. В частности, при неудачном выборе точки старта возникают ситуации, в которых алгоритм требует вычисления экстремально больших чисел и превышает размер доступной памяти даже в самых современных вычислительных машинах. Поэтому в статье предложены способ сведения задачи поиска описанного равновесия к задаче выпуклой негладкой оптимизации и численный способ решения полученной задачи оптимизации. Для обоих методов решения задачи были проведены численные эксперименты. Авторами использовались данные для Владивостока (для этого была обработана информация из различных источников и собрана в новый пакет) и двух небольших городов США. Методом простой прогонки двух блоков сходимости добиться не удалось, тогда как вторая модель для того же набора данных продемонстрировала скорость сходимости $k^{−1.67}$.

Authors describe a two-stage traffic assignment model. It contains of two blocks. The first block consists of a model for calculating a correspondence (demand) matrix, whereas the second block is a traffic assignment model. The first model calculates a matrix of correspondences using a matrix of transport costs (it characterizes the required volumes of movement from one area to another, it is time in this case). To solve this problem, authors propose to use one of the most popular methods of calculating the correspondence matrix in urban studies — the entropy model. The second model describes exactly how the needs for displacement specified by the correspondence matrix are distributed along the possible paths. Knowing the ways of the flows distribution along the paths, it is possible to calculate the cost matrix. Equilibrium in a two-stage model is a fixed point in the sequence of these two models. In practice the problem of finding a fixed point can be solved by the fixed-point iteration method. Unfortunately, at the moment the issue of convergence and estimations of the convergence rate for this method has not been studied quite thoroughly. In addition, the numerical implementation of the algorithm results in many problems. In particular, if the starting point is incorrect, situations may arise where the algorithm requires extremely large numbers to be computed and exceeds the available memory even on the most modern computers. Therefore the article proposes a method for reducing the problem of finding the equilibrium to the problem of the convex non-smooth optimization. Also a numerical method for solving the obtained optimization problem is proposed. Numerical experiments were carried out for both methods of solving the problem. The authors used data for Vladivostok (for this city information from various sources was processed and collected in a new dataset) and two smaller cities in the USA. It was not possible to achieve convergence by the method of fixed-point iteration, whereas the second model for the same dataset demonstrated convergence rate $k^{-1.67}$.

Работа посвящена построению эффективных и применимых к реальным задачам методов выпуклой оптимизации первого порядка, то есть использующих только значения целевой функции и ее производных. При построении используется быстрый градиентный метод OGM-G, который является оптимальным по оракульной сложности (числу вычислений градиента целевой функции), но при запуске требует знания констант сильной выпуклости и Липшица градиента для вычисления количества шагов и длины шага, требуемых для достижения заданной точности. Данное требование усложняет практическое использование метода. Предлагаются адаптивный по константе сильной выпуклости алгоритм ACGM, основанный на рестартах OGM-G с обновлениемо ценки константы сильной выпуклости, и адаптивный по константе Липшица градиента метод ALGM, в котором применение рестартов OGM-G дополнено подбором константы Липшица с проверкой условий гладкости, используемых в методе универсального градиентного спуска. При этом устраняются недостатки исходного метода, связанные с необходимостью знания данных констант, что делает возможным практическое использование. Доказывается, что оценки сложности построенных алгоритмов являются оптимальными с точностью до числового множителя. Для проверки полученных результатов проводятся эксперименты на модельных функциях и реальных задачах машинного обучения.

The work is devoted to the construction of efficient and applicable to real tasks first-order methods of convex optimization, that is, using only values of the target function and its derivatives. Construction uses OGMG, fast gradient method which is optimal by complexity, but requires to know the Lipschitz constant for gradient and the strong convexity constant to determine the number of steps and step length. This requirement makes practical usage very hard. An adaptive on the constant for strong convexity algorithm ACGM is proposed, based on restarts of the OGM-G with update of the strong convexity constant estimate, and an adaptive on the Lipschitz constant for gradient ALGM, in which the use of OGM-G restarts is supplemented by the selection of the Lipschitz constant with verification of the smoothness conditions used in the universal gradient descent method. This eliminates the disadvantages of the original method associated with the need to know these constants, which makes practical usage possible. Optimality of estimates for the complexity of the constructed algorithms is proved. To verify the results obtained, experiments on model functions and real tasks from machine learning are carried out.

Методы оптимизации первого порядка являются важным рабочим инструментов для широкого спектра современных приложений в разных областях, среди которых можно выделить экономику, физику, биологию, машинное обучение и управление. Среди методов первого порядка особого внимания заслуживают ускоренные (моментные) методы в силу их практической эффективности. Метод тяжелого шарика (heavy-ball method — HB) — один из первых ускоренных методов. Данный метод был разработан в 1964 г., и для него был проведен анализ сходимости для квадратичных сильно выпуклых функций. С тех пор были предложены и проанализированы разные варианты HB. В частности, HB известен своей простотой реализации и эффективностью при решении невыпуклых задач. Однако, как и другие моментные методы, он имеет немонотонное поведение; более того, при сходимости HB с оптимальными параметрами наблюдается нежелательное явление, называемое пик-эффектом. Чтобы решить эту проблему, в этой статье мы рассматриваем усредненную версию метода тяжелого шарика (averaged heavy-ball method — AHB). Мы показываем, что для квадратичных задач AHB имеет меньшее максимальное отклонение от решения, чем HB. Кроме того, для общих выпуклых и сильно выпуклых функций доказаны неускоренные скорости глобальной сходимости AHB, его версии WAHB cо взвешенным усреднением, а также для AHB с рестартами R-AHB. Насколько нам известно, такие гарантии для HB с усреднением не были явно доказаны для сильно выпуклых задач в существующих работах. Наконец, мы проводим несколько численных экспериментов для минимизации квадратичных и неквадратичных функций, чтобы продемонстрировать преимущества использования усреднения для HB. Кроме того, мы также протестировали еще одну модификацию AHB, называемую методом tail-averaged heavy-ball (TAHB). В экспериментах мы наблюдали, что HB с правильно настроенной схемой усреднения сходится быстрее, чем HB без усреднения, и имеет меньшие осцилляции.

First-order optimization methods are workhorses in a wide range of modern applications in economics, physics, biology, machine learning, control, and other fields. Among other first-order methods accelerated and momentum ones obtain special attention because of their practical efficiency. The heavy-ball method (HB) is one of the first momentum methods. The method was proposed in 1964 and the first analysis was conducted for quadratic strongly convex functions. Since then a number of variations of HB have been proposed and analyzed. In particular, HB is known for its simplicity in implementation and its performance on nonconvex problems. However, as other momentum methods, it has nonmonotone behavior, and for optimal parameters, the method suffers from the so-called peak effect. To address this issue, in this paper, we consider an averaged version of the heavy-ball method (AHB). We show that for quadratic problems AHB has a smaller maximal deviation from the solution than HB. Moreover, for general convex and strongly convex functions, we prove non-accelerated rates of global convergence of AHB, its weighted version WAHB, and for AHB with restarts R-AHB. To the best of our knowledge, such guarantees for HB with averaging were not explicitly proven for strongly convex problems in the existing works. Finally, we conduct several numerical experiments on minimizing quadratic and nonquadratic functions to demonstrate the advantages of using averaging for HB. Moreover, we also tested one more modification of AHB called the tail-averaged heavy-ball method (TAHB). In the experiments, we observed that HB with a properly adjusted averaging scheme converges faster than HB without averaging and has smaller oscillations.

Статья посвящена решению некорректно поставленных задач математической физики для эллиптических и параболических уравнений, а именно задачи Коши для уравнения Гельмгольца и ретроспективной задачи Коши для уравнения теплопроводности с постоянными коэффициентами. Эти задачи сводятся к задачам выпуклой оптимизации в гильбертовом пространстве. Градиенты соответствующих функционалов вычисляются приближенно с помощью решения двух корректных задач. Предлагается метод решения исследуемых задач оптимизации — покомпонентный спуск в базисе из собственных функций связанного с задачей самосопряженного оператора. Если бы было возможно точное вычисление градиента, то этот метод давал бы сколь угодно точное решение задачи в зависимости от количества рассматриваемых элементов базиса. В реальных случаях возникновение погрешностей при вычислениях приводит к нарушению монотонности, что требует применения рестартов и ограничивает достижимое качество. В работе приводятся результаты экспериментов, подтверждающие эффективность построенного метода. Определяется, что новый подход превосходит подходы, основанные на использовании градиентных методов оптимизации: он позволяет достичь лучшего качества решения при значительно меньшем расходе вычислительных ресурсов. Предполагается, что построенный метод может быть обобщен и на другие задачи.

The article is devoted to solving ill-posed problems of mathematical physics for elliptic and parabolic equations, such as the Cauchy problem for the Helmholtz equation and the retrospective Cauchy problem for the heat equation with constant coefficients. These problems are reduced to problems of convex optimization in Hilbert space. The gradients of the corresponding functionals are calculated approximately by solving two well-posed problems. A new method is proposed for solving the optimization problems under study, it is component-by-component descent in the basis of eigenfunctions of a self-adjoint operator associated with the problem. If it was possible to calculate the gradient exactly, this method would give an arbitrarily exact solution of the problem, depending on the number of considered elements of the basis. In real cases, the inaccuracy of calculations leads to a violation of monotonicity, which requires the use of restarts and limits the achievable quality. The paper presents the results of experiments confirming the effectiveness of the constructed method. It is determined that the new approach is superior to approaches based on the use of gradient optimization methods: it allows to achieve better quality of solution with significantly less computational resources. It is assumed that the constructed method can be generalized to other problems.

В статье рассматривается одна из задач транспортного моделирования — поиск равновесного распределения транспортных потоков в сети. Для описания временных издержек и распределения потоков в сети, представляемой с помощью графа, используется классическая модель Бэкмана. При этом поведение агентов не является полностью рациональным, что описывается посредством введения марковской логит-динамики: в каждый момент времени водительвыбирает маршрут случайно согласно распределению Гиббса с учетом текущих временных затрат на ребрах графа. Таким образом, задача сводится к поиску стационарного распределения для данной динамики, которое является стохастическим равновесием Нэша – Вардропа в соответствующей популяционной игре загрузки транспортной сети. Так как данная игра является потенциальной, эта задача эквивалентна минимизации некоторого функционала от распределения потоков, причем стохастичностьпро является в появлении энтропийной регуляризации. Для полученной задачи оптимизации построена двойственная задача. Для ее решения применен универсальный прямо-двойственный градиентный метод. Его особенность заключается в адаптивной настройке на локальную гладкость задачи, что особенно важно при сложной структуре целевой функции и невозможности априорно оценитьг ладкость с приемлемой точностью. Такая ситуация имеет место в рассматриваемой задаче, так как свойства функции сильно зависят от транспортного графа, на который мы не накладываем сильных ограничений. В статье приводится описание алгоритма, в том числе подробно рассмотрено применение численного дифференцирования для вычисления значения и градиента целевой функции. В работе представлены теоретическая оценка времени работы алгоритма и результаты численных экспериментов на примере небольшого американского города.

We consider one of the problems of transport modelling — searching the equilibrium distribution of traffic flows in the network. We use the classic Beckman’s model to describe time costs and flow distribution in the network represented by directed graph. Meanwhile agents’ behavior is not completely rational, what is described by the introduction of Markov logit dynamics: any driver selects a route randomly according to the Gibbs’ distribution taking into account current time costs on the edges of the graph. Thus, the problem is reduced to searching of the stationary distribution for this dynamics which is a stochastic Nash – Wardrope equilibrium in the corresponding population congestion game in the transport network. Since the game is potential, this problem is equivalent to the problem of minimization of some functional over flows distribution. The stochasticity is reflected in the appearance of the entropy regularization, in contrast to non-stochastic case. The dual problem is constructed to obtain a solution of the optimization problem. The universal primal-dual gradient method is applied. A major specificity of this method lies in an adaptive adjustment to the local smoothness of the problem, what is most important in case of the complex structure of the objective function and an inability to obtain a prior smoothness bound with acceptable accuracy. Such a situation occurs in the considered problem since the properties of the function strongly depend on the transport graph, on which we do not impose strong restrictions. The article describes the algorithm including the numerical differentiation for calculation of the objective function value and gradient. In addition, the paper represents a theoretical estimate of time complexity of the algorithm and the results of numerical experiments conducted on a small American town.

В данной работе рассматриваются задачи выпуклой стохастической оптимизации, возникающие в анализе данных (минимизация функции риска), а также в математической статистике (минимизация функции правдоподобия). Такие задачи могут быть решены как онлайн-, так и офлайн-методами (метод Монте-Карло). При офлайн-подходе исходная задача заменяется эмпирической задачей — задачей минимизации эмпирического риска. В современном машинном обучении ключевым является следующий вопрос: какой размер выборки (количество слагаемых в функционале эмпирического риска) нужно взять, чтобы достаточно точное решение эмпирической задачи было решением исходной задачи с заданной точностью. Базируясь на недавних существенных продвижениях в машинном обучении и оптимизации для решения выпуклых стохастических задач на евклидовых шарах (или всем пространстве), мы рассматриваем случай произвольных шаров в $p$-нормах и исследуем, как влияет выбор параметра $p$ на оценки необходимого числа слагаемых в функции эмпирического риска.

В данной работе рассмотрены как выпуклые задачи оптимизации, так и седловые. Для сильно выпуклых задач были обобщены уже имеющиеся результаты об одинаковых размерах выборки в обоих подходах (онлайн и офлайн) на произвольные нормы. Более того, было показано, что условие сильной выпуклости может быть ослаблено: полученные результаты справедливы для функций, удовлетворяющих условию квадратичного роста. В случае когда данное условие не выполняется, предлагается использовать регуляризацию исходной задачи в произвольной норме. В отличие от выпуклых задач седловые задачи являются намного менее изученными. Для седловых задач размер выборки был получен при условии $\gamma$-роста седловой функции по разным группам переменных. Это условие при $\gamma = 1$ есть не что иное, как аналог условия острого минимума в выпуклых задач. В данной статье было показано, что размер выборки в случае острого минимума (седла) почти не зависит от желаемой точности решения исходной задачи.

In this paper, we consider convex stochastic optimization problems arising in machine learning applications (e. g., risk minimization) and mathematical statistics (e. g., maximum likelihood estimation). There are two main approaches to solve such kinds of problems, namely the Stochastic Approximation approach (online approach) and the Sample Average Approximation approach, also known as the Monte Carlo approach, (offline approach). In the offline approach, the problem is replaced by its empirical counterpart (the empirical risk minimization problem). The natural question is how to define the problem sample size, i. e., how many realizations should be sampled so that the quite accurate solution of the empirical problem be the solution of the original problem with the desired precision. This issue is one of the main issues in modern machine learning and optimization. In the last decade, a lot of significant advances were made in these areas to solve convex stochastic optimization problems on the Euclidean balls (or the whole space). In this work, we are based on these advances and study the case of arbitrary balls in the $p$-norms. We also explore the question of how the parameter $p$ affects the estimates of the required number of terms as a function of empirical risk.

In this paper, both convex and saddle point optimization problems are considered. For strongly convex problems, the existing results on the same sample sizes in both approaches (online and offline) were generalized to arbitrary norms. Moreover, it was shown that the strong convexity condition can be weakened: the obtained results are valid for functions satisfying the quadratic growth condition. In the case when this condition is not met, it is proposed to use the regularization of the original problem in an arbitrary norm. In contradistinction to convex problems, saddle point problems are much less studied. For saddle point problems, the sample size was obtained under the condition of $\gamma$-growth of the objective function. When $\gamma = 1$, this condition is the condition of sharp minimum in convex problems. In this article, it was shown that the sample size in the case of a sharp minimum is almost independent of the desired accuracy of the solution of the original problem.

В этой статье мы предлагаем новый метод первого порядка для композитных невыпуклых задач минимизации с простыми ограничениями и неточным оракулом. Целевая функция задается как сумма «сложной», возможно, невыпуклой части с неточным оракулом и «простой» выпуклой части. Мы обобщаем понятие неточного оракула для выпуклых функций на случай невыпуклых функций. Неформально говоря, неточность оракула означает, что для «сложной» части в любой точке можно приближенно вычислить значение функции и построить квадратичную функцию, которая приближенно ограничивает эту функцию сверху. Рассматривается два возможных типа ошибки: контролируемая, которая может быть сде- лана сколь угодно маленькой, например, за счет решения вспомогательной задачи, и неконтролируемая. Примерами такой неточности являются: гладкие невыпуклые функции с неточным и непрерывным по Гёльдеру градиентом, функции, заданные вспомогательной равномерно вогнутой задачей максимизации, которая может быть решена лишь приближенно. Для введенного класса задачм ы предлагаем метод типа проекции градиента / зеркального спуска, который позволяет использовать различные прокс-функции для задания неевклидовой проекции на допустимое множество и более гибкой адаптации к геометрии допустимого множества; адаптивно выбирает контролируемую ошибку оракула и ошибку неевклидового проектирования; допускает неточное проксимальное отображение с двумя типами ошибки: контролируемой и неконтролируемой. Мы доказываем скорость сходимости нашего метода в терминах нормы обобщенного градиентного отображения и показываем, что в случае неточного непрерывного по Гёльдеру градиента наш метод является универсальным по отношению к параметру и константе Гёльдера. Это означает, что методу не нужно знание этих параметров для работы. При этом полученная оценка сложности является равномерно наилучшей при всех параметрах Гёльдера. Наконец, в частном случае показано, что малое значение нормы обобщенного градиентного отображения в точке означает, что в этой точке приближенно выполняется необходимое условие локального минимума.

In this paper, we develop a new first-order method for composite nonconvex minimization problems with simple constraints and inexact oracle. The objective function is given as a sum of «hard», possibly nonconvex 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 nonconvex functions with inexact H¨older-continuous gradient, functions given by the 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 one to use a different proximal setup to adapt to the geometry of the feasible set, adaptively chooses controlled oracle error, allows for inexact proximal mapping. We provide a convergence rate for our method in terms of the norm of generalized gradient mapping and show that, in the case of an 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 the 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.

В данной статье проведен обзор как исторических достижений, так и современных результатов в области марковских процессов принятия решений (Markov Decision Process, MDP) и выпуклой оптимизации. Данный обзор является первой попыткой освещения на русском языке области обучения с подкреплением в контексте выпуклой оптимизации. Рассматриваются фундаментальное уравнение Беллмана и построенные на его основе критерии оптимальности политики — стратегии, принимающие решение по известному состоянию среды на данный момент. Также рассмотрены основные итеративные алгоритмы оптимизации политики, построенные на решении уравнений Беллмана. Важным разделом данной статьи стало рассмотрение альтернативы к подходу $Q$-обучения — метода прямой максимизации средней награды агента для избранной стратегии от взаимодействия со средой. Таким образом, решение данной задачи выпуклой оптимизации представимо в виде задачи линейного программирования. В работе демонстрируется, как аппарат выпуклой оптимизации применяется для решения задачи обучения с подкреплением (Reinforcement Learning, RL). В частности, показано, как понятие сильной двойственности позволяет естественно модифицировать постановку задачи RL, показывая эквивалентность между максимизацией награды агента и поиском его оптимальной стратегии. В работе также рассматривается вопрос сложности оптимизации MDP относительно количества троек «состояние–действие–награда», получаемых в результате взаимодействия со средой. Представлены оптимальные границы сложности решения MDP в случае эргодического процесса с бесконечным горизонтом, а также в случае нестационарного процесса с конечным горизонтом, который можно перезапускать несколько раз подряд или сразу запускать параллельно в нескольких потоках. Также в обзоре рассмотрены последние результаты по уменьшению зазора нижней и верхней оценки сложности оптимизации MDP с усредненным вознаграждением (Averaged MDP, AMDP). В заключение рассматриваются вещественнозначная параметризация политики агента и класс градиентных методов оптимизации через максимизацию $Q$-функции ценности. В частности, представлен специальный класс MDP с ограничениями на ценность политики (Constrained Markov Decision Process, CMDP), для которых предложен общий прямодвойственный подход к оптимизации, обладающий сильной двойственностью.

This article reviews both historical achievements and modern results in the field of Markov Decision Process (MDP) and convex optimization. This review is the first attempt to cover the field of reinforcement learning in Russian in the context of convex optimization. The fundamental Bellman equation and the criteria of optimality of policy — strategies based on it, which make decisions based on the known state of the environment at the moment, are considered. The main iterative algorithms of policy optimization based on the solution of the Bellman equations are also considered. An important section of this article was the consideration of an alternative to the $Q$-learning approach — the method of direct maximization of the agent’s average reward for the chosen strategy from interaction with the environment. Thus, the solution of this convex optimization problem can be represented as a linear programming problem. The paper demonstrates how the convex optimization apparatus is used to solve the problem of Reinforcement Learning (RL). In particular, it is shown how the concept of strong duality allows us to naturally modify the formulation of the RL problem, showing the equivalence between maximizing the agent’s reward and finding his optimal strategy. The paper also discusses the complexity of MDP optimization with respect to the number of state–action–reward triples obtained as a result of interaction with the environment. The optimal limits of the MDP solution complexity are presented in the case of an ergodic process with an infinite horizon, as well as in the case of a non-stationary process with a finite horizon, which can be restarted several times in a row or immediately run in parallel in several threads. The review also reviews the latest results on reducing the gap between the lower and upper estimates of the complexity of MDP optimization with average remuneration (Averaged MDP, AMDP). In conclusion, the real-valued parametrization of agent policy and a class of gradient optimization methods through maximizing the $Q$-function of value are considered. In particular, a special class of MDPs with restrictions on the value of policy (Constrained Markov Decision Process, CMDP) is presented, for which a general direct-dual approach to optimization with strong duality is proposed.