Все выпуски

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

Microarray datasets are highly dimensional, with a small number of collected samples in comparison to thousands of features. This poses a significant challenge that affects the interpretation, applicability and validation of the analytical results. Matrix factorizations have proven to be a useful method for describing data in terms of a small number of meta-features, which reduces noise, while still capturing the essential features of the data. Three novel and mutually relevant methods are presented in this paper: 1) gradient-based matrix factorization with two adaptive learning rates (in accordance with the number of factor matrices) and their automatic updates; 2) nonparametric criterion for the selection of the number of factors; and 3) nonnegative version of the gradient-based matrix factorization which doesn't require any extra computational costs in difference to the existing methods. We demonstrate effectiveness of the proposed methods to the supervised classification of gene expression data.

В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (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.).

Задача выпуклой онлайн-оптимизации естественно возникают в случаях, когда имеет место обновления статистической информации. Для задач негладкой оптимизации хорошо известен метод зеркального спуска. Зеркальный спуск — это расширение субградиентного метода для решения негладких выпуклых задач оптимизации на случай неевкидова расстояния. Работа посвящена стохастическим аналогам недавно предложенных методов зеркального спуска для задач выпуклой онлайн-оптимизации с выпуклыми липшицевыми (вообще говоря, негладкими) функциональными ограничениями. Это означает, что вместо (суб)градиента целевого функционала и функционального ограничения мы используем их стохастические (суб)градиенты. Точнее говоря, допустим, что на замкнутом подмножестве $n$-мерного векторного пространства задано $N$ выпуклых липшицевых негладких функционалов. Рассматривается задача минимизации среднего арифметического этих функционалов с выпуклым липшицевым ограничением. Предложены два метода для решения этой задачи с использованием стохастических (суб)градиентов: адаптивный (не требует знания констант Липшица ни для целевого функционала, ни для ограничения), а также неадаптивный (требует знания константы Липшица для целевого функционала и ограничения). Отметим, что разрешено вычислять стохастический (суб)градиент каждого целевого функционала только один раз. В случае неотрицательного регрета мы находим, что количество непродуктивных шагов равно $O$($N$), что указывает на оптимальность предложенных методов. Мы рассматриваем произвольную прокс-структуру, что существенно для задач принятия решений. Приведены результаты численных экспериментов, позволяющие сравнить работу адаптивного и неадаптивного методов для некоторых примеров. Показано, что адаптивный метод может позволить существенно улучшить количество найденного решения.

The problem of online convex optimization naturally occurs in cases when there is an update of statistical information. The mirror descent method is well known for non-smooth optimization problems. Mirror descent is an extension of the subgradient method for solving non-smooth convex optimization problems in the case of a non-Euclidean distance. This paper is devoted to a stochastic variant of recently proposed Mirror Descent methods for convex online optimization problems with convex Lipschitz (generally, non-smooth) functional constraints. This means that we can still use the value of the functional constraint, but instead of (sub)gradient of the objective functional and the functional constraint, we use their stochastic (sub)gradients. More precisely, assume that on a closed subset of $n$-dimensional vector space, $N$ convex Lipschitz non-smooth functionals are given. The problem is to minimize the arithmetic mean of these functionals with a convex Lipschitz constraint. Two methods are proposed, for solving this problem, using stochastic (sub)gradients: adaptive method (does not require knowledge of Lipschitz constant neither for the objective functional, nor for the functional of constraint) and non-adaptivemethod (requires knowledge of Lipschitz constant for the objective functional and the functional of constraint). Note that it is allowed to calculate the stochastic (sub)gradient of each functional only once. In the case of non-negative regret, we find that the number of non-productive steps is $O$($N$), which indicates the optimality of the proposed methods. We consider an arbitrary proximal structure, which is essential for decisionmaking problems. The results of numerical experiments are presented, allowing to compare the work of adaptive and non-adaptive methods for some examples. It is shown that the adaptive method can significantly improve the number of the found solutions.

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

The article provides approaches to evolutionary modelling of synthesis of organised systems and analyses methodological problems of evolutionary computations of this kind. Based on the analysis of works on evolutionary cybernetics, evolutionary theory, systems theory and synergetics, we conclude that there are open problems in formalising the synthesis of organised systems and modelling their evolution. The article emphasises that the theoretical basis for the practice of evolutionary modelling is the principles of the modern synthetic theory of evolution. Our software project uses a virtual computing environment for machine synthesis of problem solving algorithms. In the process of modelling, we obtained the results on the basis of which we conclude that there are a number of conditions that fundamentally limit the applicability of genetic programming methods in the tasks of synthesis of functional structures. The main limitations are the need for the fitness function to track the step-by-step approach to the solution of the problem and the inapplicability of this approach to the problems of synthesis of hierarchically organised systems. We note that the results obtained in the practice of evolutionary modelling in general for the whole time of its existence, confirm the conclusion the possibilities of genetic programming are fundamentally limited in solving problems of synthesizing the structure of organized systems. As sources of fundamental difficulties for machine synthesis of system structures the article points out the absence of directions for gradient descent in structural synthesis and the absence of regularity of random appearance of new organised structures. The considered problems are relevant for the theory of biological evolution. The article substantiates the statement about the biological specificity of practically possible ways of synthesis of the structure of organised systems. As a theoretical interpretation of the discussed problem, we propose to consider the system-evolutionary concept of P.K.Anokhin. The process of synthesis of functional structures in this context is an adaptive response of organisms to external conditions based on their ability to integrative synthesis of memory, needs and information about current conditions. The results of actual studies are in favour of this interpretation. We note that the physical basis of biological integrativity may be related to the phenomena of non-locality and non-separability characteristic of quantum systems. The problems considered in this paper are closely related to the problem of creating strong artificial intelligence.

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

In the article we have obtained some estimates of the rate of convergence for the recently proposed by Yu. E.Nesterov method of minimization of a convex Lipschitz-continuous function of two variables on a square with a fixed side. The idea of the method is to divide the square into smaller parts and gradually remove them so that in the remaining sufficiently small part. The method consists in solving auxiliary problems of one-dimensional minimization along the separating segments and does not imply the calculation of the exact value of the gradient of the objective functional. The main result of the paper is proved in the class of smooth convex functions having a Lipschitz-continuous gradient. Moreover, it is noted that the property of Lipschitzcontinuity for gradient is sufficient to require not on the whole square, but only on some segments. It is shown that the method can work in the presence of errors in solving auxiliary one-dimensional problems, as well as in calculating the direction of gradients. Also we describe the situation when it is possible to neglect or reduce the time spent on solving auxiliary one-dimensional problems. For some examples, experiments have demonstrated that the method can work effectively on some classes of non-smooth functions. In this case, an example of a simple non-smooth function is constructed, for which, if the subgradient is chosen incorrectly, even if the auxiliary one-dimensional problem is exactly solved, the convergence property of the method may not hold. Experiments have shown that the method under consideration can achieve the desired accuracy of solving the problem in less time than the other methods (gradient descent and ellipsoid method) considered. Partially, it is noted that with an increase in the accuracy of the desired solution, the operating time for the Yu. E. Nesterov’s method can grow slower than the time of the ellipsoid method.

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

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

В этой работе мы, во-первых, сделали обзор наиболее популярных методов аппроксимации градиента: конечная прямая/центральная разность (FFD/FCD), покомпонентная прямая/центральная разность (FWC/CWC), прямая/центральная рандомизация на $l_2$ сфере (FSSG2/CFFG2); во-вторых, мы описали текущие теоретические представления шума, вносимого неточностью вычисления функции в точке: враждебный шум, случайный шум; в-третьих, мы провели серию экспериментов на часто встречающихся классах задач, таких как квадратичная задача, логистическая регрессия, SVM, чтобы попытаться определить, соответствует ли реальная природа машинного шума существующей теории. Оказалось, что в реальности (по крайней мере на тех классах задач, которые были рассмотрены в данной работе) машинный шум оказался чем-то средним между враждебным шумом и случайным, в связи с чем текущая теория о влиянии конечности мантиссы на поиск оптимума в задачах безградиентной оптимизации требует некоторой корректировки.

Gradient-free optimization methods or zeroth-order methods are widely used in training neural networks, reinforcement learning, as well as in industrial tasks where only the values of a function at a point are available (working with non-analytical functions). In particular, the method of error back propagation in PyTorch works exactly on this principle. There is a well-known fact that computer calculations use heuristics of floating-point numbers, and because of this, the problem of finiteness of the mantissa arises.

In this paper, firstly, we reviewed the most popular methods of gradient approximation: Finite forward/central difference (FFD/FCD), Forward/Central wise component (FWC/CWC), Forward/Central randomization on $l_2$ sphere (FSSG2/CFFG2); secondly, we described current theoretical representations of the noise introduced by the inaccuracy of calculating the function at a point: adversarial noise, random noise; thirdly, we conducted a series of experiments on frequently encountered classes of problems, such as quadratic problem, logistic regression, SVM, to try to determine whether the real nature of machine noise corresponds to the existing theory. It turned out that in reality (at least for those classes of problems that were considered in this paper), machine noise turned out to be something between adversarial noise and random, and therefore the current theory about the influence of the mantissa limb on the search for the optimum in gradient-free optimization problems requires some adjustment.

В данной работе представлены результаты экспериментальной проверки некоторых вопросов, касающихся практического использования методов преодоления катастрофической забывчивости нейронных сетей. Проведено сравнение двух таких современных методов: метода эластичного закрепления весов (EWC, Elastic Weight Consolidation) и метода ослабления скоростей весов (WVA, Weight Velocity Attenuation). Разобраныих преимущества и недостатки в сравнении друг с другом. Показано, что метод эластичного закрепления весов (EWC) лучше применять в задачах, где требуется полностью сохранять выученные навыки на всех задачах в очереди обучения, а метод ослабления скоростей весов (WVA) больше подходит для задач последовательного обучения с сильно ограниченными вычислительными ресурсами или же когда требуется не точное сохранение всех навыков, а переиспользование репрезентаций и ускорение обучения от задачи к задаче. Проверено и подтверждено интуитивное предположение, что ослабление метода WVA необходимо применять к оптимизационному шагу, то есть к приращениям весов нейронной сети, а не к самому градиенту функции потерь, и это справедливо для любого градиентного оптимизационного метода, кроме простейшего стохастического градиентного спуска (SGD), для которого оптимизационный шаг и градиент функции потерь пропорциональны. Рассмотрен выбор оптимальной функции ослабления скоростей весов между гиперболической функцией и экспонентой. Показано, что гиперболическое убывание более предпочтительно, так как, несмотря на сравнимое качество при оптимальных значениях гиперпараметра метода WVA, оно более устойчиво к отклонениям гиперпараметра от оптимального значения (данный гиперпараметр в методе WVA обеспечивает баланс между сохранением старых навыков и обучением новой задаче). Приведены эмпирические наблюдения, которые подтверждают гипотезу о том, что оптимальное значение гиперпараметра не зависит от числа задач в очереди последовательного обучения. Следовательно, данный гиперпараметр может подбираться на небольшом числе задач, а использоваться — на более длинных последовательностях.

This paper presents the results of experimental validation of some structural issues concerning the practical use of methods to overcome catastrophic forgetting of neural networks. A comparison of current effective methods like EWC (Elastic Weight Consolidation) and WVA (Weight Velocity Attenuation) is made and their advantages and disadvantages are considered. It is shown that EWC is better for tasks where full retention of learned skills is required on all the tasks in the training queue, while WVA is more suitable for sequential tasks with very limited computational resources, or when reuse of representations and acceleration of learning from task to task is required rather than exact retention of the skills. The attenuation of the WVA method must be applied to the optimization step, i. e. to the increments of neural network weights, rather than to the loss function gradient itself, and this is true for any gradient optimization method except the simplest stochastic gradient descent (SGD). The choice of the optimal weights attenuation function between the hyperbolic function and the exponent is considered. It is shown that hyperbolic attenuation is preferable because, despite comparable quality at optimal values of the hyperparameter of the WVA method, it is more robust to hyperparameter deviations from the optimal value (this hyperparameter in the WVA method provides a balance between preservation of old skills and learning a new skill). Empirical observations are presented that support the hypothesis that the optimal value of this hyperparameter does not depend on the number of tasks in the sequential learning queue. And, consequently, this hyperparameter can be picked up on a small number of tasks and used on longer sequences.

Рассмотрена модель горения предварительно перемешанной смеси газов с одной глобальной химической реакцией, включающая в себя уравнения второго порядка относительно температуры смеси и концентраций топлива и окислителя, в правые части которых входит функция скорости реакции. Эта функция зависит от пяти неизвестных параметров глобальной реакции и служит приближением для многоступенчатого механизма реакций. Модель сводится к одному уравнению второго порядка относительно температуры смеси, которое после замены переменных преобразуется к уравнению первого порядка относительно производной температуры, зависящей от температуры, в которое входит параметр скорости распространения пламени. Таким образом, для вычисления параметра скорости распространения пламени необходимо решить задачу Дирихле для уравнения первого порядка, в результате чего получится модельная зависимость скорости распространения пламени от эквивалентного отношения смеси при заданных параметрах скорости реакции. При наличии экспериментальных данных зависимости скорости распространения пламени от эквивалентного отношения смеси ставится задача оптимального подбора параметров скорости реакции, исходя из минимизации среднеквадратичного отклонения модельных значений скорости распространения пламени от эксперимента. Целью работы является исследование однозначности решения этой задачи. Для этого применяется вычислительный эксперимент, в ходе которого решается задача глобального поиска оптимумов с помощью мультистарта градиентного спуска. В ходе вычислительного эксперимента выяснено, что обратная задача в такой постановке является недоопределенной, и всякий раз при запуске градиентного метода из новой точки получается новая предельная точка. Исследована структура множества предельных точек в пятимерном пространстве параметров и показано, что это множество может быть описано тремя линейными уравнениями. Таким образом, будет некорректным табулировать все пять параметров скорости реакции исходя из одного лишь критерия соответствия модели данным скорости распространения пламени. Вывод исследования заключается в том, что для корректного табулирования параметров необходимо указать значения двух из них исходя из дополнительных критериев оптимальности.

A model of combustion of premixed mixture of gases with one global chemical reaction is considered, the model includes equations of the second order for temperature of mixture and concentrations of fuel and oxidizer, and the right-hand sides of these equations contain the reaction rate function. This function depends on five unknown parameters of the global reaction and serves as approximation to multistep reaction mechanism. The model is reduced, after replacement of variables, to one equation of the second order for temperature of mixture that transforms to a first-order equation for temperature derivative depending on temperature that contains a parameter of flame propagation velocity. Thus, for computing the parameter of burning velocity, one has to solve Dirichlet problem for first-order equation, and after that a model dependence of burning velocity on mixture equivalence ratio at specified reaction rate parameters will be obtained. Given the experimental data of dependence of burning velocity on mixture equivalence ratio, the problem of optimal selection of reaction rate parameters is stated, based on minimization of the mean square deviation of model values of burning velocity on experimental ones. The aim of our study is analysis of uniqueness of this problem solution. To this end, we apply computational experiment during which the problem of global search of optima is solved using multistart of gradient descent. The computational experiment clarifies that the inverse problem in this statement is underdetermined, and every time, when running gradient descent from a selected starting point, it converges to a new limit point. The structure of the set of limit points in the five-dimensional space is analyzed, and it is shown that this set can be described with three linear equations. Therefore, it might be incorrect to tabulate all five parameters of reaction rate based on just one match criterion between model and experimental data of flame propagation velocity. The conclusion of our study is that in order to tabulate reaction rate parameters correctly, it is necessary to specify the values of two of them, based on additional optimality criteria.

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