?
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
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
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
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
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
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
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
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
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
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
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
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
Kornilov N., Shamir O., Lobanov A. et al., , in : Advances in Neural Information Processing Systems 36 (NeurIPS 2023). : Curran Associates, Inc., 2023.
In this paper, we consider non-smooth stochastic convex optimization with two function evaluations per round under infinite noise variance. In the classical setting when noise has finite variance, an optimal algorithm, built upon the batched accelerated gradient method, was proposed in (Gasnikov et. al., 2022). This optimality is defined in terms of iteration and oracle ...
Added: March 26, 2024
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
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
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
Энатская Н.Ю., Колчин А. В., Труды Карельского научного центра РАН. Серия 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
М. А. Коврижных, Д. Б. Фомин, Прикладная дискретная математика 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
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
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