### ?

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

P. 10126-10135.

Gadetsky A., Struminsky K., Robinson C. et al., / Bayesian Deep Learning NeurIPS 2019 Workshop. Series 2019 "Bayesian Deep Learning NeurIPS 2019 Workshop". 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

Eduard Gorbunov, 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

Морозов Н. Ю., Гришин Е. М., Правдивец Н. А. et al., Управление большими системами: сборник трудов 2022 № 99 С. 135-156

В связи с ростом объема мультимодальных перевозок ОАО «РЖД» требуется более эффективное использование имеющихся ресурсов. В наши дни наиболее востребованной разновидностью международного грузооборота является доставка морским транспортом с последующей перегрузкой на железную дорогу для доставки до пункта назначения на материке. В настоящей статье предлагается комплексная математическая модель, включающая две подзадачи: задачу назначения причалов (BAP) и ...

Added: December 7, 2022

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

Smirnov S., Voloshinov V., O.V. Sukhoroslov, , in : Proceedings of the 9th International Conference "Distributed Computing and Grid Technologies in Science and Education" (GRID'2021), Dubna, Russia, July 5-9, 2021. : CEUR Workshop Proceedings, 2021. P. 413-417.

ParaSCIP is rather advanced open-source solver for discrete and global optimization problems. This solver is distinguished by that it can run on distributed memory systems and use up to 80,000 cores, solving open problems from the MIPLIB test libraries. Earlier, using this solver, we confirmed the conjecture on optimal packing of nine congruent circles on ...

Added: October 30, 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

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

Alexander A. Lazarev, Gafarov E., 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

Энатская Н.Ю., Колчин А. В., Труды Карельского научного центра РАН. Серия 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., 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

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

Tiapkin D., Alexander Gasnikov, , in : International Conference on Artificial Intelligence and Statistics, 28-30 March 2022, A Virtual Conference. Vol. 151: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics.: PMLR, 2022. P. 9723-9740.

We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs). For this purpose, some variant of Stochastic Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. An important detail is the ability to use inexact values of functional constraints and compute the value of dual variables. We analyze ...

Added: October 16, 2022

D. Derkach, N. Kazeev, R Neychev 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

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

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

Lazarev A. A., Gafarov E., 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

Dvinskikh D., Tominin V., Tominin I. et al., , in : Mathematical Optimization Theory and Operations Research, 21st International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2–6, 2022, Proceedings. Vol. 13367.: Springer, 2022. Ch. 279899. P. 18-33.

Added: October 28, 2022

М. А. Коврижных, Д. Б. Фомин, Прикладная дискретная математика 2022 № 57 С. 5-21

In this paper, we study a generalized construction of (2m, 2m)-functions using monomial and arbitrary m-bit permutations as constituent elements. We investigate the possibility of constructing bijective vectorial Boolean functions (permutations) with specified cryptographic properties that ensure the resistance of encryption algorithms to linear and differential methods of cryptographic analysis. We propose a heuristic algorithm ...

Added: October 8, 2022

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

Tiapkin D., Gasnikov A., Dvurechensky P., Optimization Letters 2022 Vol. 16 No. 7 P. 2145-2175

We consider the population Wasserstein barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. This leads to a complicated stochastic optimization problem where the objective is given as an expectation of a function given as a solution to a random optimization problem. We ...

Added: October 16, 2022

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