### ?

## Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation

Cornell University
,
2024.

We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation technique to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We significantly extend previous results by providing an expansion of the mean-squared error of the resulting estimator with respect to the number of iterations n. More precisely, we show that the mean-squared error can be decomposed into the sum of two terms: a leading one of order $n^{-1/2}$ with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order $n^{-3/4}$ where the power 3/4 can not be improved in general. We also extend this result to the p-th moment bound keeping optimal scaling of the remainders with respect to n. Our analysis relies on the properties of the SGD iterates viewed as a time-homogeneous Markov chain. In particular, we establish that this chain is geometrically ergodic with respect to a suitably defined weighted Wasserstein semimetric.

Durmus A., Moulines E., Naumov A. et al., / Cornell University. Series arXiv "math". 2023.

In this paper, we establish novel deviation bounds for additive functionals of geometrically ergodic Markov chains similar to Rosenthal and Bernstein-type inequalities for sums of independent random variables. We pay special attention to the dependence of our bounds on the mixing time of the corresponding chain. Our proof technique is, as far as we know, ...

Added: June 18, 2023

Sheresheva M. Y., Kolesnik N. A., Industrial Marketing Management 2011 Vol. 40 P. 979–987

This article investigates contemporary distribution processes in the industrial market. The main trend in distribution during the recent decades manifests itself in a growing number of network-type distribution chains. Based on the evolutionary trends in distribution research, we came up with the idea to investigate distribution networks processes using mathematical tools of probability theory. We ...

Added: July 27, 2012

Konakov V., Mammen E., Probability Theory and Related Fields 2009 Vol. 143 No. 1 P. 137–176

We consider triangular arrays of Markov chains that converge weakly to a diffusion process. Second order Edgeworth type expansions for transition densities are proved. The paper differs from recent results in two respects. We allow nonhomogeneous diffusion limits and we treat transition densities with time lag converging to zero. Small time asymptotics are motivated by ...

Added: December 4, 2012

Belomestny D., Moulines E., Samsonov S., Statistics and Computing 2022 Vol. 32 No. 1 Article 16

In this paper, we propose an efficient variance reduction approach for additive functionals of Markov chains relying on a novel discrete-time martingale representation. Our approach is fully non-asymptotic and does not require the knowledge of the stationary distribution (and even any type of ergodicity) or specific structure of the underlying density. By rigorously analyzing the ...

Added: August 31, 2020

Konakov V., Mammen E., Bernoulli: a journal of mathematical statistics and probability 2005 Vol. 11 No. 4 P. 591–641

We consider triangular arrays of Markov chains that converge weakly to a diffusion process. We prove Edgeworth-type expansions of order o(n-1-δ),δ>0, for transition densities. For this purpose we apply the parametrix method to represent the transition density as a functional of densities of sums of independent and identically distributed variables. Then we apply Edgeworth expansions ...

Added: December 4, 2012

Konakov V., Mammen E., Probability Theory and Related Fields 2000 Vol. 117 No. 4 P. 551–587

We consider triangular arrays of Markov chains that converge weakly to a diffusion process. Local limit theorems for transition
densities are proved. ...

Added: October 15, 2012

Нужный А. С., Однолько И. С., Глухов А. Ю. et al., Прикладная математика и вопросы управления 2021 № 1 С. 7–22

The paper proposes a mathematical model to optimize the operation of the tar hydrocracking unit.
The purpose of modeling is to improve the economic effect of product output by selecting optimal parameters,
such as hydrogen flow rate and reactor temperature. Hot Filtered Precipitation (HFT) is used as a target.
The model involves the search for the minimum value ...

Added: April 11, 2021

Barcelona: IEEE, 2017

International Conference on Control, Decision and Information Technologies. ...

Added: January 17, 2018

М.: Физматлит, 2013

Conference is devoted to application of the integrated models and soft computing in artificial intelligence. ...

Added: May 26, 2013

Shmid A., Novopashin M. A., Berezin A. A., IOSR Journal of Computer Engineering (IOSR-JCE) 2017 Vol. 19 No. 3 P. 113–121

The paper deals with the Forrester’s approach to analysis of heart electrical dynamics based on the hypothesis that heart belongs to the class of Complex Systems and its dynamics can be described by coupled Van der Pol differential equations with a time lag. The chain of such equations suggested by Ginzburg and Landau was used ...

Added: June 13, 2018

Goldengorin B. I., European Journal of Operational Research 2009 Vol. 198 No. 1 P. 102–112

Added: July 31, 2012

Kalyagin V.A., Koldanov A.P., Koldanov P.A. et al., Physica A: Statistical Mechanics and its Applications 2014 Vol. 413 No. 1 P. 59–70

A general approach to measure statistical uncertainty of different filtration techniques for market network analysis is proposed. Two measures of statistical uncertainty are introduced and discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases ...

Added: July 19, 2014

М.: ИКИ РАН, 2011

Added: March 26, 2013

Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114–125

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

Added: September 7, 2017

Springer, 2020

This volume offers a collection of carefully selected, peer-reviewed papers presented at the BIOMAT 2019 International Symposium, which was held at the University of Szeged, Bolyai Institute and the Hungarian Academy of Sciences, Hungary, October 21st-25th, 2019. The topics covered in this volume include tumor and infection modeling; dynamics of co-infections; epidemic models on networks; ...

Added: March 11, 2021

Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706–721

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...

Added: January 30, 2021

Lanham: University Press of America, 2012

The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...

Added: February 13, 2013

Marshirov V. V., Marshirova L. E., Сибирский журнал индустриальной математики 2013 Т. XVI № 4 С. 111–120

The paper considers the problem of determining the rate of cooling of metal during solidification at the intersection of the liquidus temperature under intense heat sink from the surface. The solution to this problem it is necessary to determine the process conditions, the boundary and initial conditions for which it is possible to get new ...

Added: November 17, 2013

Blakeway S., Gromov D., Gromova E. et al., Vestnik Sankt-Peterburgskogo Universiteta, Prikladnaya Matematika, Informatika, Protsessy Upravleniya 2019 Vol. 15 No. 1 P. 22–38

We describe a novel game-theoretic formulation of the optimal mobile agents’ placement problem which arises in the context of Mobile Ad-hoc Networks (MANETs). This problem is modelled as a sequential multistage game. The definitions of both the Nash equilibrium and cooperative solution are given. A modification was proposed to ensure the existence of a Nash ...

Added: March 13, 2020

Malyshev D., Alekseev V., Дискретный анализ и исследование операций 2008 Т. 15 № 1 С. 3–10

Доказывается полиномиальная разрешимость задачи о независимом множестве для бесконечного семейства подмножеств класса планарных графов. ...

Added: August 31, 2012

Boissard E., Le Gouic T., Loubes J., Bernoulli: a journal of mathematical statistics and probability 2015 P. 740–759

In this paper, we tackle the problem of comparing distributions of random variables and defining a mean pattern between a sample of random events. Using barycenters of measures in the Wasserstein space, we propose an iterative version as an estimation of the mean distribution. Moreover, when the distributions are a common measure warped by a ...

Added: October 13, 2018

Vyalyi M., Дискретная математика 1991 Т. 3 № 3 С. 35–45

Added: October 17, 2014

Kotelnikova M. V., Aistov A., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183–189

The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...

Added: January 28, 2020

Malyshev D., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860–1865

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...

Added: April 7, 2014