All issues

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

Conversion of numeric data to the spiking form and information losses in this process are serious problems limiting usage of spiking neural networks in applied informational systems. While physical values are represented by numbers, internal representation of information inside spiking neural networks is based on spikes — elementary objects emitted and processed by neurons. This problem is especially hard in the reinforcement learning applications where an agent should learn to behave in the dynamic real world because beside the accuracy of the encoding method, its dynamic characteristics should be considered as well. The encoding algorithm based on the Gaussian receptive fields (GRF) is frequently used. In this method, one numeric variable fed to the network is represented by spike streams emitted by a certain set of network input nodes. The spike frequency in each stream is determined by proximity of the current variable value to the center of the receptive field corresponding to the given input node. In the standard GRF algorithm, the receptive field centers are placed equidistantly. However, it is inefficient in the case of very uneven distribution of the variable encoded. In the present paper, an improved version of this method is proposed which is based on adaptive selection of the Gaussian centers and spike stream frequencies. This improved GRF algorithm is compared with its standard version in terms of amount of information lost in the coding process and of accuracy of classification models built on spike-encoded data. The fraction of information retained in the process of the standard and adaptive GRF encoding is estimated using the direct and reverse encoding procedures applied to a large sample from the triangular probability distribution and counting coinciding bits in the original and restored samples. The comparison based on classification was performed on a task of evaluation of current state in reinforcement learning. For this purpose, the classification models were created by machine learning algorithms of very different nature — nearest neighbors algorithm, random forest and multi-layer perceptron. Superiority of our approach is demonstrated on all these tests.

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

The paper presents the results of theoretical investigation of the peculiarities of the quasi-harmonic signal’s phase statistical distribution, while the quasi-harmonic signal is formed as a result of the Gaussian noise impact on the initially harmonic signal. The revealed features of the phase distribution became a basis for the original technique elaborated for estimating the parameters of the initial, undistorted signal. It has been shown that the task of estimation of the initial phase value can be efficiently solved by calculating the magnitude of the mathematical expectation of the results of the phase sampled measurements, while for solving the task of estimation of the second parameter — the signal level respectively to the noise level — the dependence of the phase sampled measurements variance upon the sough-for parameter is proposed to be used. For solving this task the analytical formulas having been obtained in explicit form for the moments of lower orders of the phase distribution, are applied. A new approach to quasi-harmonic signal’s parameters estimation based on the method of moments has been developed and substantiated. In particular, the application of this method ensures a high-precision measuring the amplitude characteristics of a signal by means of the phase measurements only. The numerical results obtained by means of conducted computer simulation of the elaborated technique confirm both the theoretical conclusions and the method’s efficiency. The existence and the uniqueness of the task solution by the method of moments is substantiated. It is shown that the function that describes the dependence of the phase second central moment on the sough-for parameter, is a monotonically decreasing and thus the single-valued function. The developed method may be of interest for solving a wide range of scientific and applied tasks, connected with the necessity of estimation of both the signal level and the phase value, in such areas as data processing in systems of medical diagnostic visualization, radio-signals processing, radio-physics, optics, radio-navigation and metrology.

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

The paper provides a solution of a task of calculating the parameters of a Rician distributed signal on the basis of the maximum likelihood principle in limiting cases of large and small values of the signal-tonoise ratio. The analytical formulas are obtained for the solution of the maximum likelihood equations’ system for the required signal and noise parameters for both the one-parameter approximation, when only one parameter is being calculated on the assumption that the second one is known a-priori, and for the two-parameter task, when both parameters are a-priori unknown. The direct calculation of required signal and noise parameters by formulas allows escaping the necessity of time resource consuming numerical solving the nonlinear equations’ s system and thus optimizing the duration of computer processing of signals and images. There are presented the results of computer simulation of a task confirming the theoretical conclusions. The task is meaningful for the purposes of Rician data processing, in particular, magnetic-resonance visualization.

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

The paper provides a solution of the two-parameter task of joint signal and noise estimation at data analysis within the conditions of the Rice distribution by the techniques of mathematical statistics: the maximum likelihood method and the variants of the method of moments. The considered variants of the method of moments include the following techniques: the joint signal and noise estimation on the basis of measuring the 2-nd and the 4-th moments (MM24) and on the basis of measuring the 1-st and the 2-nd moments (MM12). For each of the elaborated methods the explicit equations’ systems have been obtained for required parameters of the signal and noise. An important mathematical result of the investigation consists in the fact that the solution of the system of two nonlinear equations with two variables — the sought for signal and noise parameters — has been reduced to the solution of just one equation with one unknown quantity what is important from the view point of both the theoretical investigation of the proposed technique and its practical application, providing the possibility of essential decreasing the calculating resources required for the technique’s realization. The implemented theoretical analysis has resulted in an important practical conclusion: solving the two-parameter task does not lead to the increase of required numerical resources if compared with the one-parameter approximation. The task is meaningful for the purposes of the rician data processing, in particular — the image processing in the systems of magnetic-resonance visualization. The theoretical conclusions have been confirmed by the results of the numerical experiment.

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

The paper presents the results of the fundamental research directed on the theoretical study and computer simulation of peculiarities of the quasi-harmonic signal’s phase statistical distribution. The quasi-harmonic signal is known to be formed as a result of the Gaussian noise impact on the initially harmonic signal. By means of the mathematical analysis the formulas have been obtained in explicit form for the principle characteristics of this distribution, namely: for the cumulative distribution function, the probability density function, the likelihood function. As a result of the conducted computer simulation the dependencies of these functions on the phase distribution parameters have been analyzed. The paper elaborates the methods of estimating the phase distribution parameters which contain the information about the initial, undistorted signal. It has been substantiated that the task of estimating the initial value of the phase of quasi-harmonic signal can be efficiently solved by averaging the results of the sampled measurements. As for solving the task of estimating the second parameter of the phase distribution, namely — the parameter, determining the signal level respectively the noise level — a maximum likelihood technique is proposed to be applied. The graphical illustrations are presented that have been obtained by means of the computer simulation of the principle characteristics of the phase distribution under the study. The existence and uniqueness of the likelihood function’s maximum allow substantiating the possibility and the efficiency of solving the task of estimating signal’s level relative to noise level by means of the maximum likelihood technique. The elaborated method of estimating the un-noised signal’s level relative to noise, i. e. the parameter characterizing the signal’s intensity on the basis of measurements of the signal’s phase is an original and principally new technique which opens perspectives of usage of the phase measurements as a tool of the stochastic data analysis. The presented investigation is meaningful for solving the task of determining the phase and the signal’s level by means of the statistical processing of the sampled phase measurements. The proposed methods of the estimation of the phase distribution’s parameters can be used at solving various scientific and technological tasks, in particular, in such areas as radio-physics, optics, radiolocation, radio-navigation, metrology.

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

Fault-tolerance of a finite computing net with arbitrary graph, containing elements with certain probability of fault and restore, is analyzed. Algorithm for net growth at each work cycle is suggested. It is shown that if the rate of net increase is sufficiently big then the probability of infinity faultless work is positive. Estimated critical net increase rate is logarithmic over the number of work cycles.

В данной статье исследуется метод машинного обучения на основе теории случайных функций. Одной из основных проблем данного метода является то, что вид решающего правила модели метода, построенной на данных обучающей выборки, становится более громоздким при увеличении количества примеров выборки. Решающее правило модели является наиболее вероятной реализацией случайной функции и представляется в виде многочлена с количеством слагаемых, равным количеству обучающих элементов выборки. В статье будет показано, что для рассматриваемого метода существует быстрый способ сокращения обучающей выборки и, соответственно, вида решающего правила. Уменьшение примеров обучающей выборки происходит за счет поиска и удаления малоинформативных (слабых) элементов, которые незначительно влияют на итоговый вид решающей функции, и шумовых элементов выборки. Для каждого $(x_i,y_i)$-го элемента выборки было введено понятие значимости, выражающееся величиной отклонения оцененного значения решающей функции модели в точке $x_i$, построенной без $i$-го элемента, от реального значения $y_i$. Будет показана возможность косвенного использования найденных слабых элементов выборки при обучении модели метода, что позволяет не увеличивать количество слагаемых в полученной решающей функции. Также в статье будут описаны проведенные эксперименты, в которых показано, как изменение количества обучающих данных влияет на обобщающую способность решающего правила модели в задаче классификации.

This article explores a method of machine learning based on the theory of random functions. One of the main problems of this method is that decision rule of a model becomes more complicated as the number of training dataset examples increases. The decision rule of the model is the most probable realization of a random function and it's represented as a polynomial with the number of terms equal to the number of training examples. In this article we will show the quick way of the number of training dataset examples reduction and, accordingly, the complexity of the decision rule. Reducing the number of examples of training dataset is due to the search and removal of weak elements that have little effect on the final form of the decision function, and noise sampling elements. For each $(x_i,y_i)$-th element sample was introduced the concept of value, which is expressed by the deviation of the estimated value of the decision function of the model at the point $x_i$, built without the $i$-th element, from the true value $y_i$. Also we show the possibility of indirect using weak elements in the process of training model without increasing the number of terms in the decision function. At the experimental part of the article, we show how changed amount of data affects to the ability of the method of generalizing in the classification task.

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

A classical for nonlinear dynamics model, Brusselator, is considered, being augmented by addition of a third variable, which plays the role of a fast-diffusing inhibitor. The model is investigated in one-dimensional case in the parametric domain, where two types of diffusive instabilities of system’s homogeneous stationary state are manifested: wave instability, which leads to spontaneous formation of autowaves, and Turing instability, which leads to spontaneous formation of stationary dissipative structures, or Turing structures. It is shown that, due to the subcritical nature of Turing bifurcation, the interaction of two instabilities in this system results in spontaneous formation of stationary dissipative structures already before the passage of Turing bifurcation. In response to different perturbations of spatially uniform stationary state, different stable regimes are manifested in the vicinity of the double bifurcation point in the parametric region under study: both pure regimes, which consist of either stationary or autowave dissipative structures; and mixed regimes, in which different modes dominate in different areas of the computational space. In the considered region of the parametric space, the system is multistable and exhibits high sensitivity to initial noise conditions, which leads to blurring of the boundaries between qualitatively different regimes in the parametric region. At that, even in the area of dominance of mixed modes with prevalence of Turing structures, the establishment of a pure autowave regime has significant probability. In the case of stable mixed regimes, a sufficiently strong local perturbation in the area of the computational space, where autowave mode is manifested, can initiate local formation of new stationary dissipative structures. Local perturbation of the stationary homogeneous state in the parametric region under investidation leads to a qualitatively similar map of established modes, the zone of dominance of pure autowave regimes being expanded with the increase of local perturbation amplitude. In two-dimensional case, mixed regimes turn out to be only transient — upon the appearance of localized Turing structures under the influence of wave regime, they eventually occupy all available space.

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

We consider a model of spontaneous formation of a computational structure in the human brain for solving a given class of tasks in the process of performing a series of similar tasks. The model is based on a special definition of a numerical measure of the complexity of the solution algorithm. This measure has an informational property: the complexity of a computational structure consisting of two independent structures is equal to the sum of the complexities of these structures. Then the probability of spontaneous occurrence of the structure depends exponentially on the complexity of the structure. The exponential coefficient requires experimental determination for each type of problem. It may depend on the form of presentation of the source data and the procedure for issuing the result. This estimation method was applied to the results of a series of experiments that determined the strategy for solving a series of similar problems with a growing number of initial data. These experiments were described in previously published papers. Two main strategies were considered: sequential execution of the computational algorithm, or the use of parallel computing in those tasks where it is effective. These strategies differ in how calculations are performed. Using an estimate of the complexity of schemes, you can use the empirical probability of one of the strategies to calculate the probability of the other. The calculations performed showed a good match between the calculated and empirical probabilities. This confirms the hypothesis about the spontaneous formation of structures that solve the problem during the initial training of a person. The paper contains a brief description of experiments, detailed computational schemes and a strict definition of the complexity measure of computational structures and the conclusion of the dependence of the probability of structure formation on its complexity.

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