### ?

## Conference on Learning Theory, 25-28 June 2019, Phoenix, USA

Vol. 99.
2019.

Under the general editorship: A. Beygelzimer, D. Hsu

Volume 99: Conference on Learning Theory, 25-28 June 2019, Phoenix, USA

Gasnikov A., Dvurechensky P., Gorbunov E. et al., , in : Conference on Learning Theory, 25-28 June 2019, Phoenix, USA. Vol. 99.: [б.и.], 2019. P. 1374-1391.

We consider convex optimization problems with the objective function having Lipshitz-continuous p-th order derivative, where p≥1. We propose a new tensor method, which closes the gap between the lower Ω( ε^(−2/(3p+1)) and upper O( ε^(−1/p+1)) iteration complexity bounds for this class of optimization problems. We also consider uniformly convex functions, and show how the proposed ...

Added: October 31, 2020

Ivanova A., Стонякин Ф., Пасечнюк Д. et al., / Working papers by Cornell University. Series "Optimization and Control". 2019.

Network utility maximization is the most important problem in network traffic management. Given the growth of modern communication networks, we consider the utility maximization problem in a network with a large number of connections (links) that are used by a huge number of users. To solve this problem an adaptive mirror descent algorithm for many ...

Added: October 25, 2020

Dvurechensky P., Gasnikov A., Остроухов П. et al., / Working papers by Cornell University. Series "Optimization and Control". 2020.

Motivated by convex problems with linear constraints and, in particular, by entropy-regularized optimal transport, we consider the problem of finding ε-approximate stationary points, i.e. points with the norm of the objective gradient less than ε, of convex functions with Lipschitz p-th order derivatives. Lower complexity bounds for this problem were recently proposed in [Grapiglia and Nesterov, arXiv:1907.07053]. However, the ...

Added: October 25, 2020

Protasov V., Jungers R., Linear Algebra and its Applications 2013 Vol. 438 No. 11 P. 4448-4468

We introduce a new approach to evaluate the largest Lyapunov exponent of a family of nonnegative matrices. The method is based on using special positive homogeneous functionals on , which gives iterative lower and upper bounds for the Lyapunov exponent. They improve previously known bounds and converge to the real value. The rate of convergence ...

Added: February 23, 2016

Rodomanov A., Kropotov D., SIAM Journal on Optimization 2020 Vol. 30 No. 3 P. 1878-1904

We analyze the coordinate descent method with a new coordinate selection strategy, called volume sampling. This strategy prescribes selecting subsets of variables of certain size proportionally to the determinants of principal submatrices of the matrix, which bounds the curvature of the objective function. In the particular case when the size of the subsets equals one, ...

Added: July 29, 2020

Bergou E. H., Eduard Gorbunov, Richtarik P., SIAM Journal on Optimization 2020 Vol. 30 No. 4 P. 2726-2749

In this paper we consider the unconstrained minimization problem of a smooth function in $\mathbb{R}^n$ in a setting where only function evaluations are possible. We design a novel randomized derivative-free algorithm---the stochastic three points (STP) method---and analyze its iteration complexity. At each iteration, STP generates a random search direction according to a certain fixed probability law. Our ...

Added: November 10, 2020

Dvurechensky P., Gasnikov A., Journal of Optimization Theory and Applications 2016 Vol. 171 No. 1 P. 121-145

In this paper, we introduce new methods for convex optimization problems with stochastic inexact oracle. Our first method is an extension of the Intermediate Gradient Method proposed by Devolder, Glineur and Nesterov for problems with deterministic inexact oracle. Our method can be applied to problems with composite objective function, both deterministic and stochastic inexactness of ...

Added: October 31, 2020

Zhivotovskiy N., Hanneke S., Theoretical Computer Science 2018 Vol. 9 No. 742 P. 27-49

In statistical learning the excess risk of empirical risk minimization (ERM) is controlled by (COMPn(F)n)α, where n is a size of a learning sample, COMPn(F) is a complexity term associated with a given class F and α∈[12,1] interpolates between slow and fast learning rates. In this paper we introduce an alternative localization approach for binary classificationthat leads to a novel complexity measure: fixed points of the local empirical entropy. We show that this ...

Added: December 6, 2018

Ivanova A., Gasnikov A., Dvurechensky P. et al., / Working papers by Cornell University. Series "Optimization and Control". 2020.

Ubiquitous in machine learning regularized empirical risk minimization problems are often composed of several blocks which can be treated using different types of oracles, e.g., full gradient, stochastic gradient or coordinate derivative. Optimal oracle complexity is known and achievable separately for the full gradient case, the stochastic gradient case, etc. We propose a generic framework ...

Added: October 25, 2020

Guminov S., Nesterov Y., Dvurechensky P. et al., Doklady Mathematics 2019 Vol. 99 No. 2 P. 125-128

A new version of accelerated gradient descent is proposed. The method does not require any a priori information on the objective function, uses a linesearch procedure for convergence acceleration in practice, converge according to well-known lower bounds for both convex and nonconvex objective functions, and has primal-dual properties. A universal version of this method is ...

Added: October 31, 2020

Gorbunov E., Danilova M., Shibaev I. et al., / arXiv. Series arXiv:2106.05958 "arXiv:2106.05958". 2021.

Thanks to their practical efficiency and random nature of the data, stochastic first-order methods are standard for training large-scale machine learning models. Random behavior may cause a particular run of an algorithm to result in a highly suboptimal objective value, whereas theoretical guarantees are usually proved for the expectation of the objective value. Thus, it ...

Added: October 25, 2021

Nesterov Y., Gasnikov A., Guminov S. et al., Optimization Methods and Software 2021 Vol. 36 No. 4 P. 773-810

In this paper, a new variant of accelerated gradient descent is proposed. The proposed method does not require any information about the objective function, uses exact line search for the practical accelerations of convergence, converges according to the well-known lower bounds for both convex and non-convex objective functions, possesses primal–dual properties and can be applied ...

Added: August 4, 2020

Воронцова Е. А., Gasnikov A., Gorbunov E., Автоматика и телемеханика 2019 Т. 80 № 4 С. 126-143

We consider smooth convex optimization problems whose full gradient is not available for their numerical solution. In 2011, Yu.E. Nesterov proposed accelerated gradient-free methods for solving such problems. Since only unconditional optimization problems were considered, Euclidean prox-structures were used. However, if one knows in advance, say, that the solution to the problem is sparse, or ...

Added: October 10, 2020

Belov A. A., Andrianova O., Automation and Remote Control 2020 Vol. 81 No. 4 P. 649-661

The design problems of robust static controllers for discrete-time systems with normbounded parametric uncertainties and random input disturbances are considered. The controllers under consideration stabilize the plant for all possible values of uncertainty from a
given set of parameters and also guarantee a desired suppression level for random exogenous
disturbances. A numerical example is given. ...

Added: October 21, 2020

Ingacheva A., Кохан В. В., Ershov E. et al., Сенсорные системы 2018 Т. 32 № 4 С. 332-341

In this paper we consider the task of inner objects mapping for the building with a bunch of moving around it autonomous agents which use narrow beam of radio waves using WiFi frequency (2.4 GHz). Linear model of pixel-wise radio waves attenuation is considered. SIRT algorithm with TV and Tikhonov regularizations is used for the ...

Added: February 9, 2020

Vorontsova E., Gasnikov A., Dvurechensky P. et al., Automation and Remote Control 2019 Vol. 80 No. 8 P. 1487-1501

We propose an accelerated gradient-free method with a non-Euclidean proximal operator associated with the p-norm (1 ⩽ p ⩽ 2). We obtain estimates for the rate of convergence of the method under low noise arising in the calculation of the function value. We present the results of computational experiments. ...

Added: December 10, 2019

Kamzolov D., Dvurechensky P., Gasnikov A., Optimization Methods and Software 2021 Vol. 36 No. 6 P. 1289-1316

In this paper, we propose new first-order methods for minimization of a convex function on a simple convex set. We assume that the objective function is a composite function given as a sum of a simple convex function and a convex function with inexact Hölder-continuous subgradient. We propose Universal Intermediate Gradient Method. Our method enjoys ...

Added: August 4, 2020

Bogachev T., / Cornell University. Series math "arxiv.org". 2022.

In this research a continuous model for resource allocations in a queuing system is considered and a local prediction on the system behavior is developed. As a result we obtain a set of possible cases, some of which lead to quite clear optimization problems. Currently, the main result of this research direction is an algorithm ...

Added: October 21, 2022

Ivanova A., Пасечнюк Д., Dvurechensky P. et al., / Cornell University. Серия "Working papers by Cornell University". 2019.

In this paper, we consider the resource allocation problem in a network with a large number of connections which are used by a huge number of users. The resource allocation problem, which we consider is a maximization problem with linear inequality constraints. To solve this problem we construct the dual problem and propose to use ...

Added: October 23, 2020

Zhivotovskiy N., Proceedings of Machine Learning Research 2017 Vol. 65 P. 2023-2065

Under margin assumptions, we prove several risk bounds, represented via the distribution dependent local entropies of the classes or the sizes of specific sample compression schemes. In some cases, our guarantees are optimal up to constant factors for families of classes. We discuss limitations of our approach and give several applications. In particular, we provide ...

Added: December 6, 2018

Dvurechensky P., Eduard Gorbunov, Gasnikov A., European Journal of Operational Research 2021 Vol. 290 No. 2 P. 601-621

We consider smooth stochastic convex optimization problems in the context of algorithms which are based on directional derivatives of the objective function. This context can be considered as an intermediate one between derivative-free optimization and gradient-based optimization. We assume that at any given point and for any given direction, a stochastic approximation for the directional ...

Added: September 25, 2020

Toldova S., Azerkovich I., Гришина Ю. et al., / НИУ ВШЭ. Series WP BRP "Linguistics". 2015.

Building benchmark corpora in the domain of coreference and anaphora resolution is an important task for developing and evaluating NLP systems and models. Our study is aimed at assessing the feasibility of enhancing corpora with information about coreference relations. The annotation procedure includes identification of text segments that are subjects to annotation (markables), marking their ...

Added: December 15, 2015

Kiselyova N. N., Dudarev V.A., Korzhuev M. A., Inorganic Materials: Applied Research 2016 Vol. 7 No. 1 P. 34-39

A database (DB) on the bandgap of inorganic substances available via the Internet (http://bg.imetdb.ru) was developed for the information service of specialists in the sphere of inorganic chemistry and materials science. The DB is integrated with other information systems on the properties of inorganic substances and materials, which provides the search of a wide range ...

Added: February 23, 2016

Baibikova T., Domoratsky E., Вестник Московского финансово-юридического университета 2017 № 1 С. 200-206

Some questions of scientific visualization are under consideration in this paper. This article also discusses the peculiarities of application of cognitive computer graphics, singles out a range of tasks of scientific visualization. The paper gives a brief overview of modern support tools for program visualization, tendencies of their development and their main characteristics. A module ...

Added: June 10, 2017

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