### ?

## Low-Variance Black-Box Gradient Estimates for the Plackett-Luce Distribution

P. 10126-10135.

Gadetsky A., Struminsky K., Robinson C. et al., Low-variance Gradient Estimates for the Plackett-Luce Distribution / . 2019.

Learning models with discrete latent variables using stochastic gradient descent remains a challenge due to the high variance of gradients. Modern variance reduction techniques mostly consider categorical distributions and have limited applicability when the number of possible outcomes becomes large. In this work, we consider models with latent permutations and propose control variates for the Plackett-Luce distribution. Our proof-of-concept experiment ...

Added: January 9, 2020

Gorbunov E., Kovalev D., Makarenko D. et al., , in: Advances in Neural Information Processing Systems 33 (NeurIPS 2020). .: Curran Associates, Inc., 2020.. P. 20889-20900.

Added: December 7, 2020

Fomin D., Математические вопросы криптографии 2020 Т. 11 № 3 С. 121-138

We generalize the method of construction of permutations based on the Butterfly structure for the case of arbitrary arithmetic space with even dimension over the field of two elements. An approach to the construction of permutations by means of nonbalanced (2m,m)-functions with high nonlinearity is suggested. ...

Added: November 25, 2020

Ignatov A., Posypkin M., , in: Optimization and Applications: 12th International Conference, OPTIMA 2021, Petrovac, Montenegro, September 27 – October 1, 2021, Proceedings. .: Switzerland: Springer, 2021.. P. 336-350.

Restoration of the 3D structure of a protein from the sequence of its amino acids (“folding”) is one of the most important and challenging problems in computational biology. The most accurate methods require enormous computational resources due to the large number of variables determining a protein’s shape. Coarse-grained models combining several protein atoms into one ...

Added: May 20, 2022

Lazarev A. A., Tarasov I., , in: VI International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2015), Petrovac, Montenegro, September 2015. .: M.: -, 2015.. P. 198-199.

A railway connection of two stations by a single railway track is usually found on branch lines of railway network and is very common in various manufacturing supply chains. Our paper isДля книг на иностранных языках concerned with a scheduling problem for two stations with a single railway track with one siding. On single-track railway ...

Added: October 20, 2015

Belomestny D., Iosipoi L., Paris Q. et al., Bernoulli: a journal of mathematical statistics and probability 2022 Vol. 28 No. 2 P. 1382-1407

We study the problem of empirical minimization for variance-type functionals over functional classes. Sharp non-asymptotic bounds for the excess variance are derived under mild conditions. In particular, it is shown that under some restrictions imposed on the functional class fast convergence rates can be achieved including the optimal non-parametric rates for expressive classes in the ...

Added: April 17, 2022

Karademir S., Kong N., Prokopyev O., Optimization Methods and Software 2014 Vol. 29 No. 1 P. 42-67

In this paper we consider the two-stage stochastic linear assignment (2SSLA) problem, which is a stochastic extension of the classical deterministic linear assignment problem. For each agent and job, the decision maker has to decide whether to make assignments now or to wait for the second stage. Assignments of agents and jobs, for which decisions ...

Added: October 19, 2016

Dvinskikh D., Tyurin A., Gasnikov A. et al., Mathematical notes 2020 Vol. 108 No. 3-4 P. 511-522

A new method for deriving estimates of the rate of convergence of optimal methods for solving problems of smooth (strongly) convex stochastic optimization is described. The method is based on the results of stochastic optimization derived from results on the convergence of optimal methods under the conditions of inexact gradients with small noises of nonrandom ...

Added: February 5, 2021

Enatskaya N., Колчин А. В., Труды Карельского научного центра РАН. Серия 10: Математическое моделирование и информационные технологии 2014 № 4 С. 80-86

We consider several procedures to number all outcomes of a permutation scheme, establish a one-to-one correspondence between the outcome and its number generated in the numbering procedure, and give some methods to simulate the outcomes. ...

Added: March 13, 2015

Fomin D., Прикладная дискретная математика. Приложение 2021 № 14 С. 51-55

The paper studies new ways of con- structing differentially 2δ-uniform bijections over F_{2^{2m}} , m≥3, that are based on TU-construction. Some well known results on the constructing differentially 4-uniform permutations over F_{2^{2m}} are generalized in this work. The core idea is to use TU-construction and differentially δ-uniform bijections to construct 2^t · δ-uniform permutations. A generalized method for constructing 2m-bit differentially 4-uniform permutations ...

Added: September 22, 2021

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

Derkach D., Kazeev N., Нейчев Р. Г. et al., Journal of Physics: Conference Series 2017 Vol. 898 No. 6 P. 1-6

The LHCb experiment stores around 1011 collision events per year. A typical physics analysis deals with a final sample of up to 107 events. Event preselection algorithms (lines) are used for data reduction. Since the data are stored in a format that requires sequential access, the lines are grouped into several output file streams, in ...

Added: October 10, 2017

Springer, 2016

This book constitutes the proceedings of the 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016, held in Vladivostok, Russia, in September 2016.
The 39 full papers presented in this volume were carefully reviewed and selected from 181 submissions. They were organized in topical sections named: discrete optimization; scheduling problems; facility location; mathematical programming; ...

Added: September 12, 2016

Cham: Springer, 2020

This book constitutes the proceedings of the 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020, held in Novosibirsk, Russia, in July 2020. The 31 full papers presented in this volume were carefully reviewed and selected from 102 submissions. The papers are grouped in these topical sections: discrete optimization; mathematical programming; game ...

Added: September 2, 2020

Shylo O., Korenkevych D., Pardalos P. M., , in: Parallel Problem Solving from Nature - PPSN XII. Issue 7492.: Saarbrücken: Springer, 2012.. P. 227-286.

Global Equilibrium Search (GES) is a meta-heuristic framework that shares similar ideas with the simulated annealing method. GES accumulates a compact set of information about the search space to generate promising initial solutions for the techniques that require a starting solution, such as the simple local search method. GES has been successful for many classic ...

Added: December 29, 2012

Lazarev A. A., Gafarov E. R., Wernerb F., Mathematical Social Sciences 2013 Vol. 65 No. 3 P. 232

In the article E.R. Gafarov, A.A. Lazarev, F. Werner, Single machine scheduling problems with financial resource constraints: Some complexity results and properties, Mathematical Social Sciences, 62 (2011), 7–13, the following mistake is found in Section 3.2, where the authors consider the problem denoted as 1|NR, dj = d, gj = g| Tj and claim ...

Added: October 15, 2014

Lazarev A. A., Gafarov E. R., Werner F., Information Processing Letters 2012 Vol. 112 No. 3 P. 72-76

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs ...

Added: October 15, 2014

Sadiev A., Beznosikov A., Dvurechensky P. et al., Communications in Computer and Information Science 2021 Vol. 1476 P. 71-85

Saddle-point problems have recently gained an increased attention from the machine learning community, mainly due to applications in training Generative Adversarial Networks using stochastic gradients. At the same time, in some applications only a zeroth-order oracle is available. In this paper, we propose several algorithms to solve stochastic smooth (strongly) convex-concave saddle-point problems using zeroth-order ...

Added: October 14, 2021

Pardalos P. M., Shylo O., Korenkevych D., Lecture Notes in Computer Science 2012 Vol. 7492 LNCS No. 2 P. 277-286

Global Equilibrium Search (GES) is a meta-heuristic framework that shares similar ideas with the simulated annealing method. GES accumulates a compact set of information about the search space to generate promising initial solutions for the techniques that require a starting solution, such as the simple local search method. GES has been successful for many classic ...

Added: February 7, 2013

Lazarev A. A., Правдивец Н. А., Grishin E. et al., Journal of Physics: Conference Series 2021

The branch and bound method is used to obtain exact solutions of the single machine scheduling problem with the objective function of maximum lateness minimization. Lower bounds are estimated by solving dual problems. A machine-independent value, namely the number of branching points in the search tree, is used as the complexity index of instances. The ...

Added: February 4, 2022

Beznosikov A., Novitskii V., Gasnikov A., Lecture Notes in Computer Science 2021 Vol. 12755 P. 144-158

In this paper, we analyze gradient-free methods with one-point feedback for stochastic saddle point problems. For non-smooth and smooth cases, we present an analysis in a general geometric setup with the arbitrary Bregman divergence. For problems with higher order smoothness, the analysis is carried out only in the Euclidean case. The estimates we have obtained ...

Added: October 14, 2021

Fomin D., Journal of Computer Virology and Hacking Techniques 2022 Vol. 18 P. 61-67

Currently numerous cryptographic systems are based on SP-networks. These primitives are supposed to be secure but recent investigations show that some attacks are possible. The aim of this work is to study how secure the Russian standardized block cipher Kuznyechik over invariant attacks. We study the already known decompositions of its permutation and show the ...

Added: November 29, 2021

Belomestny D., Moulines E., Iosipoi L. et al., Statistics and Computing 2020 No. 30 P. 973-997

In this paper we propose a novel variance reduction approach for additive functionals of Markov chains based on minimization of an estimate for the asymptotic variance of these functionals over suitable classes of control variates. A distinctive feature of the proposed approach is its ability to significantly reduce the overall finite sample variance. This feature ...

Added: October 10, 2019

Pavlovets M., Вестник Санкт-Петербургского университета. Серия 9. Филология. Востоковедение. Журналистика 2014 № 4 С. 156-163

"Designing" the complete works of his own is an important part of Aleksander Kondratov's creations, a neofuturist poet from Leningrad. One of the prospects of his future collection, "My Trinities" makes it possible to restore the poet's concept to create "The Concretions", a volume of concretist texts, which has not been fully implemented. These texts ...

Added: January 29, 2015