Все выпуски

В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближенного решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро – Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счет замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю. Е. Нестерова (2018 г.), а также за счет специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю. Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка $p \geqslant 3$.

In this work we consider Monteiro – Svaiter accelerated hybrid proximal extragradient (A-HPE) framework and accelerated Newton proximal extragradient (A-NPE) framework. The last framework contains an optimal method for rather smooth convex optimization problems with second-order oracle. We generalize A-NPE framework for higher order derivative oracle (schemes). We replace Newton’s type step in A-NPE that was used for auxiliary problem by Newton’s regularized (tensor) type step (Yu. Nesterov, 2018). Moreover we generalize large step A-HPE/A-NPE framework by replacing Monteiro – Svaiter’s large step condition so that this framework could work for high-order schemes. The main contribution of the paper is as follows: we propose optimal highorder methods for convex optimization problems. As far as we know for that moment there exist only zero, first and second order optimal methods that work according to the lower bounds. For higher order schemes there exists a gap between the lower bounds (Arjevani, Shamir, Shiff, 2017) and existing high-order (tensor) methods (Nesterov – Polyak, 2006; Yu.Nesterov, 2008; M. Baes, 2009; Yu.Nesterov, 2018). Asymptotically the ratio of the rates of convergences for the best existing methods and lower bounds is about 1.5. In this work we eliminate this gap and show that lower bounds are tight. We also consider rather smooth strongly convex optimization problems and show how to generalize the proposed methods to this case. The basic idea is to use restart technique until iteration sequence reach the region of quadratic convergence of Newton method and then use Newton method. One can show that the considered method converges with optimal rates up to a logarithmic factor. Note, that proposed in this work technique can be generalized in the case when we can’t solve auxiliary problem exactly, moreover we can’t even calculate the derivatives of the functional exactly. Moreover, the proposed technique can be generalized to the composite optimization problems and in particular to the constraint convex optimization problems. We also formulate a list of open questions that arise around the main result of this paper (optimal universal method of high order e.t.c.).

В данной работе рассматривается возможность применения концепции $(\delta, L)$-модели функции для оптимизационных задач, в которых посредством решения прямой задачи имеется необходимость восстанавливать решение двойственной задачи. Концепция $(\delta, L)$-модели основана на концепции $(\delta, L)$-оракула, предложенной Деволдером–Глинером–Нестеровым, при этом данные авторы предложили фукнционалы в оптимизационных задачах аппроксимировать сверху выпуклой параболой с некоторым аддитивным шумом $\delta$; таким образом, им удалось получить квадратичные верхние оценки с шумом даже для негладких функционалов. Концепция $(\delta, L)$-модели продолжает эту идею за счет того, что аппроксимация сверху делается не выпуклой параболой, а некоторым более сложным выпуклым функционалом. Возможность восстанавливать решение двойственной задачи хорошо зарекомендовала себя, так как во многих случаях в прямой задаче можно значительно быстрее находить решение, чем в двойственной. Отметим, что прямо-двойственные методы хорошо изучены, но при этом, как правило, каждый метод предлагается под конкретный класс задач. Наша же цель — предложить метод, который бы включал в себя сразу различные методы. Это реализуется за счет использования концепции $(\delta, L)$-модели и адаптивной структуры наших методов. Таким образом, нам удалось получить прямо-двойственный адаптивный градиентный метод и быстрый градиентный метод с $(\delta, L)$-моделью и доказать оценки сходимости для них, причем для некоторых классов задач данные оценки являются оптимальными. Основная идея заключается в том, что нахождение двойственных решений происходит относительно оптимизационной задачи, которая аппроксимируют прямую с помощью концепции $(\delta, L)$-модели и имеет более простую структуру, поэтому находить двойственное решение у нее проще. Стоит отметить, что это происходит на каждом шаге работы оптимизационного метода; таким образом, реализуется принцип «разделяй и властвуй».

In this work we consider a possibility to use the conception of $(\delta, L)$-model of a function for optimization tasks, whereby solving a primal problem there is a necessity to recover a solution of a dual problem. The conception of $(\delta, L)$-model is based on the conception of $(\delta, L)$-oracle which was proposed by Devolder–Glineur–Nesterov, herewith the authors proposed approximate a function with an upper bound using a convex quadratic function with some additive noise $\delta$. They managed to get convex quadratic upper bounds with noise even for nonsmooth functions. The conception of $(\delta, L)$-model continues this idea by using instead of a convex quadratic function a more complex convex function in an upper bound. Possibility to recover the solution of a dual problem gives great benefits in different problems, for instance, in some cases, it is faster to find a solution in a primal problem than in a dual problem. Note that primal-dual methods are well studied, but usually each class of optimization problems has its own primal-dual method. Our goal is to develop a method which can find solutions in different classes of optimization problems. This is realized through the use of the conception of $(\delta, L)$-model and adaptive structure of our methods. Thereby, we developed primal-dual adaptive gradient method and fast gradient method with $(\delta, L)$-model and proved convergence rates of the methods, moreover, for some classes of optimization problems the rates are optimal. The main idea is the following: we find a dual solution to an approximation of a primal problem using the conception of $(\delta, L)$-model. It is much easier to find a solution to an approximated problem, however, we have to do it in each step of our method, thereby the principle of “divide and conquer” is realized.

В статье рассматривается задача минимизации математического ожидания выпуклой функции. Задачи такого вида повсеместны в машинном обучении, а также часто возникают в ряде других приложений. На практике для их решения обычно используются процедуры типа стохастического градиентного спуска (SGD). В нашей работе предлагается решать такие задачи с использованием метода эллипсоидов с мини-батчингом. Алгоритм имеет линейную скорость сходимости и может оказаться эффективнее SGD в ряде задач. Это подтверждается в наших экспериментах, исходный код которых находится в открытом доступе. Для получения линейной скорости сходимости метода не требуется ни гладкость, ни сильная выпуклость целевой функции. Таким образом, сложность алгоритма не зависит от обусловленности задачи. В работе доказывается, что метод эллипсоидов с наперед заданной вероятностью находит решение с желаемой точностью при использовании мини-батчей, размер которых пропорционален точности в степени -2. Это позволяет выполнять алгоритм параллельно на большом числе процессоров, тогда как возможности для батчараллелизации процедур типа стохастического градиентного спуска весьма ограничены. Несмотря на быструю сходимость, общее количество вычислений градиента для метода эллипсоидов может получиться больше, чем для SGD, который неплохо сходится и при маленьком размере батча. Количество итераций метода эллипсоидов квадратично зависит от размерности задачи, поэтому метод подойдет для относительно небольших размерностей.

The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a variety of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are usually used to solve such problems. We propose to use the ellipsoid method with mini-batching, which converges linearly and can be more efficient than SGD for a class of problems. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of the objective to achieve linear convergence. Thus, its complexity does not depend on the conditional number of the problem. We prove that the method arrives at an approximate solution with given probability when using mini-batches of size proportional to the desired accuracy to the power −2. This enables efficient parallel execution of the algorithm, whereas possibilities for batch parallelization of SGD are rather limited. Despite fast convergence, ellipsoid method can result in a greater total number of calls to oracle than SGD, which works decently with small batches. Complexity is quadratic in dimension of the problem, hence the method is suitable for relatively small dimensionalities.

Статья посвящена выпукло-вогнутым седловым задачам, в которых целевая функция является суммой большого числа слагаемых. Такие задачи привлекают значительное внимание математического сообщества в связи с множеством приложений в машинном обучении, включая 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.

В работе проведен краткий обзор имеющихся подходов к расчету разрушения твердых тел. Основное внимание уделено алгоритмам, использующим единый подход к расчету деформирования и для неразрушенного, и для разрушенного состояний материала. Представлен термодинамический вывод единых реологических соотношений, учитывающих упругие, вязкие и пластические свойства материалов и описывающих потерю способности сопротивления деформации по мере накопления микроповреждений. Показано, что рассматриваемая математическая модель обеспечивает непрерывную зависимость решения от входных параметров (параметров материальной среды, начальных и граничных условий, параметров дискретизации) при разупрочнении материала.

Представлены явные и неявные безматричные алгоритмы расчета эволюции деформирования. Неявные схемы реализованы с использованием итераций метода сопряженных градиентов, при этом расчет каждой итерации в точности совпадает с расчетом шага по времени для двухслойных явных схем. Так что алгоритмы решения являются очень простыми.

Приведены результаты решения типовых задач разрушения твердых деформируемых тел для медленных (квазистатических) и быстрых (динамических) процессов деформации. На основании опыта рас- четов даны рекомендации по моделированию процессов разрушения и обеспечению достоверности численных решений.

The paper reviews the existing approaches to calculating the destruction of solids. The main attention is paid to algorithms using a unified approach to the calculation of deformation both for nondestructive and for the destroyed states of the material. The thermodynamic derivation of the unified rheological relationships taking into account the elastic, viscous and plastic properties of materials and describing the loss of the deformation resistance ability with the accumulation of microdamages is presented. It is shown that the mathematical model under consideration provides a continuous dependence of the solution on input parameters (parameters of the material medium, initial and boundary conditions, discretization parameters) with softening of the material.

Explicit and implicit non-matrix algorithms for calculating the evolution of deformation and fracture development are presented. Non-explicit schemes are implemented using iterations of the conjugate gradient method, with the calculation of each iteration exactly coinciding with the calculation of the time step for two-layer explicit schemes. So, the solution algorithms are very simple.

The results of solving typical problems of destruction of solid deformable bodies for slow (quasistatic) and fast (dynamic) deformation processes are presented. Based on the experience of calculations, recommendations are given for modeling the processes of destruction and ensuring the reliability of numerical solutions.

Работа посвящена построению эффективных и применимых к реальным задачам методов выпуклой оптимизации первого порядка, то есть использующих только значения целевой функции и ее производных. При построении используется быстрый градиентный метод 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.

В данной статье рассматривается задача типа min-min: минимизация по двум группам переменных. Данная задача в чем-то похожа на седловую (min-max), однако лишена некоторых сложностей, присущих седловым задачам. Такого рода постановки могут возникать, если в задаче выпуклой оптимизации присутствуют переменные разных размерностей или если какие-то группы переменных определены на разных множествах. Подобная структурная особенность проблемы дает возможность разбивать ее на подзадачи, что позволяет решать всю задачу с помощью различных смешанных оракулов. Ранее в качестве возможных методов для решения внутренней или внешней задачи использовались только методы первого порядка или методы типа эллипсоидов. В нашей работе мы рассматриваем данный подход с точки зрения возможности применения алгоритмов высокого порядка (тензорных методов) для решения внутренней подзадачи. Для решения внешней подзадачи мы используем быстрый градиентный метод.

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

Стоит отметить, что в качестве метода для решения внутренней подзадачи при отсутствии ограничений мы используем супербыстрый тензорный метод. При решении внутренней подзадачи на компакте используется ускоренный проксимальный тензорный метод для задачи с композитом.

В конце статьи мы также сравниваем теоретические оценки сложности полученных алгоритмов с быстрым градиентным методом, который не учитывает структуру задачи и решает ее как обычную задачу выпуклой оптимизации (замечания 1 и 2).

In this article we consider min-min type of problems or minimization by two groups of variables. In some way it is similar to classic min-max saddle point problem. Although, saddle point problems are usually more difficult in some way. Min-min problems may occur in case if some groups of variables in convex optimization have different dimensions or if these groups have different domains. Such problem structure gives us an ability to split the main task to subproblems, and allows to tackle it with mixed oracles. However existing articles on this topic cover only zeroth and first order oracles, in our work we consider high-order tensor methods to solve inner problem and fast gradient method to solve outer problem.

We assume, that outer problem is constrained to some convex compact set, and for the inner problem we consider both unconstrained case and being constrained to some convex compact set. By definition, tensor methods use high-order derivatives, so the time per single iteration of the method depends a lot on the dimensionality of the problem it solves. Therefore, we suggest, that the dimension of the inner problem variable is not greater than 1000. Additionally, we need some specific assumptions to be able to use mixed oracles. Firstly, we assume, that the objective is convex in both groups of variables and its gradient by both variables is Lipschitz continuous. Secondly, we assume the inner problem is strongly convex and its gradient is Lipschitz continuous. Also, since we are going to use tensor methods for inner problem, we need it to be p-th order Lipschitz continuous ($p > 1$). Finally, we assume strong convexity of the outer problem to be able to use fast gradient method for strongly convex functions.

We need to emphasize, that we use superfast tensor method to tackle inner subproblem in unconstrained case. And when we solve inner problem on compact set, we use accelerated high-order composite proximal method.

Additionally, in the end of the article we compare the theoretical complexity of obtained methods with regular gradient method, which solves the mentioned problem as regular convex optimization problem and doesn’t take into account its structure (Remarks 1 and 2).

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

The article is devoted to studying the application of convex optimization methods to solve the Cauchy problem for the Helmholtz equation, which is ill-posed since the equation belongs to the elliptic type. The Cauchy problem is formulated as an inverse problem and is reduced to a convex optimization problem in a Hilbert space. The functional to be optimized and its gradient are calculated using the solution of boundary value problems, which, in turn, are well-posed and can be approximately solved by standard numerical methods, such as finite-difference schemes and Fourier series expansions. The convergence of the applied fast gradient method and the quality of the solution obtained in this way are experimentally investigated. The experiment shows that the accelerated gradient method — the Similar Triangle Method — converges faster than the non-accelerated method. Theorems on the computational complexity of the resulting algorithms are formulated and proved. It is found that Fourier’s series expansions are better than finite-difference schemes in terms of the speed of calculations and improve the quality of the solution obtained. An attempt was made to use restarts of the Similar Triangle Method after halving the residual of the functional. In this case, the convergence does not improve, which confirms the absence of strong convexity. The experiments show that the inaccuracy of the calculations is more adequately described by the additive concept of the noise in the first-order oracle. This factor limits the achievable quality of the solution, but the error does not accumulate. According to the results obtained, the use of accelerated gradient optimization methods can be the way to solve inverse problems effectively.