BGBalázs Gerencsér

Balázs Gerencsér

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Stochastic approximation in a Markovian framework revisited: Lipschitz continuity of the Poisson equation

    by Algo Carè, Balázs Csanád Csáji, Balázs Gerencsér, László Gerencsér, Miklós Rásonyi

    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.

  • Mixing on the cycle with constant size perturbation

    by Shi Feng, Balázs Gerencsér

    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

    Kutatók Éjszakája – avagy mi a közös a farkasokban, a vadászokban és a zenészekben?

    by Balázs Szabolcs Gerencsér, Anett Pogácsás, Ágnes Tahyné Kovács

  • Open Access

    Digitalizáció a közigazgatásban

    by Petra Lea Láncos, Balázs Szabolcs Gerencsér, Lilla Berkes, György Sántha

  • Open Access

    Low complexity convergence rate bounds for push-sum algorithms with homogeneous correlation structure

    by Balázs Gerencsér, Miklós Kornyik

    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

    by John Fernley, Balázs Gerencsér

    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

    by Shi Feng, Balázs Gerencsér

    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.

  • Cutoff for a class of auto‐regressive models with vanishing additive noise

    by Balázs Gerencsér, Andrea Ottolini

    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.

  • Low Complexity Convergence Rate Bounds for the Synchronous Gossip Subclass of Push-Sum Algorithms

    by Balázs Gerencsér, Miklós Kornyik

    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

    by John Fernley, Balázs Gerencsér

    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.