Balázs Gerencsér
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Balázs Gerencsér has a total of 52 co-authors. Here are the top co-authors by number of shared publications:
- Julien M. Hendrickx
ICTEAM Institute, UCLouvain, Louvain-la-Neuve, Belgium
8 shared publications - Viktor Harangi
ALFRÉD RÉNYI INSTITUTE OF MATHEMATICS BUDAPEST HUNGARY
7 shared publications - László Gerencsér
HUN-REN Institute for Computer Science and Control, Hungarian Research Network, Budapest, Hungary
4 shared publications - Ágnes Backhausz
Department of Probability Theory and Statistics, Faculty of Science, ELTE Eötvös Loránd University, Budapest, Hungary
3 shared publications - Algo Carè
Department of Information Engineering, University of Brescia, Brescia, Italy
2 shared publications - Baris Fidan
Department of Mechanical and Mechatronics Engineering, University of Waterloo, Waterloo, ON, Canada
2 shared publications
Latest Publications
- Open Access
- 27 March 2026
- Published by Springer Nature in Mathematics of Control, Signals, and Systems
- Vol. 38 (2) , 291-333
Stochastic approximation in a Markovian framework revisited: Lipschitz continuity of the Poisson equation
In this paper, we revisit a fundamental technical issue within the theory of stochastic approximation (SA) in a Markovian framework, first proposed in the book by Derevitskii and Fradkov (Applied theory of discrete adaptive control systems, Nauka, 1981), and further developed in much detail in the book by Benveniste, Métivier, and Priouret (Adaptive algorithms and stochastic approximations, Springer, Berlin, 1990). This theory is instrumental in many application areas such as the statistical analysis of Hidden Markov Models arising in telecommunication, quantized linear stochastic systems, and reinforcement learning. The problem at hand is the verification of the existence, uniqueness, and Lipschitz continuity of the solution of a parameter-dependent Poisson equation, in an appropriate weighted sup-norm, associated with a collection of Markov chains on general state spaces. Verification of the above facts is vital in the analysis of SA processes presented in the cited book via the ODE (ordinary differential equations) method, requiring substantial technical effort. The motivation and focus of the paper is to address this technical issue, by presenting a simple set of conditions, under which the above properties of the Poisson equation at hand can be conveniently established. A distinctive feature of our work is that it is based on a remarkable result of Hairer and Mattingly (2011), proving that by tilting standard conditions of mainstream stability theory for Markov chains, the transition kernels prove to be contractions in the space of differences of probability measures in a suitable metric. To demonstrate the applicability of our results, the proposed conditions are verified for a class of queuing system with open-loop control.
- 27 March 2026
- Published by Springer Nature in Mathematics of Control, Signals, and Systems
- Vol. 38 (2) , 291-333
Open AccessStochastic approximation in a Markovian framework revisited: Lipschitz continuity of the Poisson equation
In this paper, we revisit a fundamental technical issue within the theory of stochastic approximation (SA) in a Markovian framework, first proposed in the book by Derevitskii and Fradkov (Applied theory of discrete adaptive control systems, Nauka, 1981), and further developed in much detail in the book by Benveniste, Métivier, and Priouret (Adaptive algorithms and stochastic approximations, Springer, Berlin, 1990). This theory is instrumental in many application areas such as the statistical analysis of Hidden Markov Models arising in telecommunication, quantized linear stochastic systems, and reinforcement learning. The problem at hand is the verification of the existence, uniqueness, and Lipschitz continuity of the solution of a parameter-dependent Poisson equation, in an appropriate weighted sup-norm, associated with a collection of Markov chains on general state spaces. Verification of the above facts is vital in the analysis of SA processes presented in the cited book via the ODE (ordinary differential equations) method, requiring substantial technical effort. The motivation and focus of the paper is to address this technical issue, by presenting a simple set of conditions, under which the above properties of the Poisson equation at hand can be conveniently established. A distinctive feature of our work is that it is based on a remarkable result of Hairer and Mattingly (2011), proving that by tilting standard conditions of mainstream stability theory for Markov chains, the transition kernels prove to be contractions in the space of differences of probability measures in a suitable metric. To demonstrate the applicability of our results, the proposed conditions are verified for a class of queuing system with open-loop control.
- 1 January 2026
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 31 (none) , 1-27
Mixing on the cycle with constant size perturbation
Considering a Markov chain defined on a cycle, near-quadratic improvement of mixing is shown when only a subtle perturbation is introduced to the structure and non-reversible transition probabilities are used. More precisely, a mixing time of O(n k+2 k+1) can be achieved by adding k random edges to the cycle, keeping k fixed while n→∞. The construction builds upon a biased random walk along the cycle.
- 1 January 2026
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 31 (none) , 1-27
Mixing on the cycle with constant size perturbation
Considering a Markov chain defined on a cycle, near-quadratic improvement of mixing is shown when only a subtle perturbation is introduced to the structure and non-reversible transition probabilities are used. More precisely, a mixing time of O(n k+2 k+1) can be achieved by adding k random edges to the cycle, keeping k fixed while n→∞. The construction builds upon a biased random walk along the cycle.
- Open Access
- 12 December 2025
- Published by Pázmány Péter Katolikus Egyetem in Iustum Aequum Salutare
- Vol. 21 (4) , 217-224
Kutatók Éjszakája – avagy mi a közös a farkasokban, a vadászokban és a zenészekben?
- 12 December 2025
- Published by Pázmány Péter Katolikus Egyetem in Iustum Aequum Salutare
- Vol. 21 (4) , 217-224
Open AccessKutatók Éjszakája – avagy mi a közös a farkasokban, a vadászokban és a zenészekben?
- Open Access
- 12 December 2025
- Published by Pázmány Péter Katolikus Egyetem in Iustum Aequum Salutare
- Vol. 21 (4) , 95-97
Digitalizáció a közigazgatásban
- 12 December 2025
- Published by Pázmány Péter Katolikus Egyetem in Iustum Aequum Salutare
- Vol. 21 (4) , 95-97
Open AccessDigitalizáció a közigazgatásban
- Open Access
Low complexity convergence rate bounds for push-sum algorithms with homogeneous correlation structure
The objective of this work is to establish an upper bound for the almost sure convergence rate for a class of push-sum algorithms. The current work extends the methods and results of the authors on a similar low-complexity bound on push-sum algorithms with some particular synchronous message passing schemes and complements the general approach of Gerencsér and Gerencsér from 2022 providing an exact, but often less accessible description. Furthermore, a parametric analysis is presented on the ``weight'' of the messages, which is found to be convex with an explicit expression for the gradient. This allows the fine-tuning of the algorithm used for improved efficiency. Numerical results confirm the speedup in evaluating the computable bounds without deteriorating their performance, for a graph on 120 vertices the runtime drops by more than 4 orders of magnitude.
Open AccessLow complexity convergence rate bounds for push-sum algorithms with homogeneous correlation structure
The objective of this work is to establish an upper bound for the almost sure convergence rate for a class of push-sum algorithms. The current work extends the methods and results of the authors on a similar low-complexity bound on push-sum algorithms with some particular synchronous message passing schemes and complements the general approach of Gerencsér and Gerencsér from 2022 providing an exact, but often less accessible description. Furthermore, a parametric analysis is presented on the ``weight'' of the messages, which is found to be convex with an explicit expression for the gradient. This allows the fine-tuning of the algorithm used for improved efficiency. Numerical results confirm the speedup in evaluating the computable bounds without deteriorating their performance, for a graph on 120 vertices the runtime drops by more than 4 orders of magnitude.
- Open Access
The Supermarket Model on a Dynamic Regular Hypergraph
The supermarket model is a system of $n$ queues each with serving rates $1$ and arrival rates $λ$ per vertex, where tasks will move on arrival to the shortest adjacent queue. We consider the supermarket model in the small $λ$ regime on a large dynamic configuration hypergraph with stubs swapping their hyperedge membership at rate $κ$. This interpolates previous investigations of the supermarket model on static graphs of bounded degree (where an exponential tail produces a logarithmic queue) and with independently drawn neighbourhoods (where the ``power of two choices'' phenomenon is a doubly logarithmic queue). We find with high probability, over any polynomial timeframe, the order of the longest queue is \[ \log\log n + \frac{\log n}{\log κ} \wedge \log n \] so in the sense of controlling the order of maximal queue length, we identify which speed orders are sufficiently fast that there is no gain in moving the environment faster. Additional results describe mixing of the system and propagation of chaos over time.Open AccessThe Supermarket Model on a Dynamic Regular Hypergraph
The supermarket model is a system of $n$ queues each with serving rates $1$ and arrival rates $λ$ per vertex, where tasks will move on arrival to the shortest adjacent queue. We consider the supermarket model in the small $λ$ regime on a large dynamic configuration hypergraph with stubs swapping their hyperedge membership at rate $κ$. This interpolates previous investigations of the supermarket model on static graphs of bounded degree (where an exponential tail produces a logarithmic queue) and with independently drawn neighbourhoods (where the ``power of two choices'' phenomenon is a doubly logarithmic queue). We find with high probability, over any polynomial timeframe, the order of the longest queue is \[ \log\log n + \frac{\log n}{\log κ} \wedge \log n \] so in the sense of controlling the order of maximal queue length, we identify which speed orders are sufficiently fast that there is no gain in moving the environment faster. Additional results describe mixing of the system and propagation of chaos over time. - Open Access
Mixing on the cycle with constant size perturbation
Considering a Markov chain defined on a cycle, near-quadratic improvement of mixing is shown when only a subtle perturbation is introduced to the structure and non-reversible transition probabilities are used. More precisely, a mixing time of $O(n^{\frac{k+2}{k+1}})$ can be achieved by adding $k$ random edges to the cycle, keeping $k$ fixed while $n\to\infty$. The construction builds upon a biased random walk along the cycle.Open AccessMixing on the cycle with constant size perturbation
Considering a Markov chain defined on a cycle, near-quadratic improvement of mixing is shown when only a subtle perturbation is introduced to the structure and non-reversible transition probabilities are used. More precisely, a mixing time of $O(n^{\frac{k+2}{k+1}})$ can be achieved by adding $k$ random edges to the cycle, keeping $k$ fixed while $n\to\infty$. The construction builds upon a biased random walk along the cycle. - 20 August 2024
- Published by Wiley in Scandinavian Journal of Statistics
- Vol. 52 (1) , 314-331
Cutoff for a class of auto‐regressive models with vanishing additive noise
We analyze the convergence rates for a family of auto‐regressive Markov chains on Euclidean space depending on a parameter , where at each step a randomly chosen coordinate is replaced by a noisy damped weighted average of the others. The interest in the model comes from the connection with a certain Bayesian scheme introduced by de Finetti in the analysis of partially exchangeable data. Our main result shows that, when n gets large (corresponding to a vanishing noise), a cutoff phenomenon occurs.
- 20 August 2024
- Published by Wiley in Scandinavian Journal of Statistics
- Vol. 52 (1) , 314-331
Cutoff for a class of auto‐regressive models with vanishing additive noise
We analyze the convergence rates for a family of auto‐regressive Markov chains on Euclidean space depending on a parameter , where at each step a randomly chosen coordinate is replaced by a noisy damped weighted average of the others. The interest in the model comes from the connection with a certain Bayesian scheme introduced by de Finetti in the analysis of partially exchangeable data. Our main result shows that, when n gets large (corresponding to a vanishing noise), a cutoff phenomenon occurs.
- 31 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 8, 1283-1288
Low Complexity Convergence Rate Bounds for the Synchronous Gossip Subclass of Push-Sum Algorithms
We develop easily accessible quantities for bounding the almost sure exponential convergence rate of push-sum algorithms. We analyze the scenario of i.i.d. synchronous gossip, every agent communicating independently towards at most a single target at every step. Multiple bounding expressions are developed depending on the generality of the setup, all functions of the network’s spectrum. Numerical experiments demonstrate the quality of the bounds obtained together with the computational speedup for acquiring them.
- 31 May 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 8, 1283-1288
Low Complexity Convergence Rate Bounds for the Synchronous Gossip Subclass of Push-Sum Algorithms
We develop easily accessible quantities for bounding the almost sure exponential convergence rate of push-sum algorithms. We analyze the scenario of i.i.d. synchronous gossip, every agent communicating independently towards at most a single target at every step. Multiple bounding expressions are developed depending on the generality of the setup, all functions of the network’s spectrum. Numerical experiments demonstrate the quality of the bounds obtained together with the computational speedup for acquiring them.
- Open Access
Simultaneous Cutoff on the Multitype Configuration Model
We find Gaussian cutoff profiles for the total variation distance to stationarity of a random walk on a multiplex network: a finite number of directed configuration models sharing a vertex set, each with its own bounded degree distribution and edge probability. Further we consider the minimal total variation distance over this space of possible doubly stochastic edge probabilities at each point in time. Looking at all possible dynamics simultaneously on one realisation of the random graph, we find that this sequence of minimal distances converges in probability to the same cutoff profile as the chain with entropy maximising transition probabilities.
Open AccessSimultaneous Cutoff on the Multitype Configuration Model
We find Gaussian cutoff profiles for the total variation distance to stationarity of a random walk on a multiplex network: a finite number of directed configuration models sharing a vertex set, each with its own bounded degree distribution and edge probability. Further we consider the minimal total variation distance over this space of possible doubly stochastic edge probabilities at each point in time. Looking at all possible dynamics simultaneously on one realisation of the random graph, we find that this sequence of minimal distances converges in probability to the same cutoff profile as the chain with entropy maximising transition probabilities.