Stochastic Processes
on Networks

Talk Title

Bipartite matching under communication constraints

Abstract

Data centre networks require new transport protocols in view of the large bandwidth and low RTT in the network together with strict latency requirement for distributed compute. Low latency can be achieved by stall free scheduling between a sender receiver pair to ensure minimal buffering at the intermediate switches. The main technical challenge in such protocols is to establish large number of matched sender receiver pairs for concurrent message transfer. We propose a novel distributed bipartite matching algorithm with local information that improves the mean matching size in random bipartite graphs that model the data centre network communication.

Biography

Talk Title

On Uniformly Sampled Integer valued Lipschitz Functions on regular Trees

Abstract

The problem of studying uniformly sampled Lipschitz functions on graphs, i.e. functions whose values differ by at most 1 at adjacent sites with prescribed boundary conditions, has attracted a great deal of interest recently in both the probability and combinatorics communities. In particular, one seeks to establish limiting properties for such functions on families of graphs that grow. On trees and certain expanders, it is known that the value of a randomly sampled function at the root is tight, that is the corresponding sequence of probability measures on the integer line concentrate on a given compact set. In the case of regular trees, we are able to go one step further, and explicitly characterize when the distribution of this random variable converges. In particular convergence holds if and only if the branching number is strictly less than 8. When the branching number is greater than or equal to 8, we demonstrate how the non convergence follows from an alternating pattern which holds with high probability, thus verifying a form of long range order.

Biography

Talk Title

TBA (To Be Announced)

Abstract

The abstract details for this lecture are pending.

Biography

Talk Title

TBA (To Be Announced)

Abstract

TBA

Biography

Talk Title

Which Model to Train? A Budgeted Bandit Approach to Adaptive Fine-Tuning

Abstract

Given a basket of large language models (LLMs), a certain task of interest (e.g., text summarization), and a finite computational/monetary budget B, we address the problem of generating the optimally fine-tuned model for the task. The challenge here is that the learning curves of the different models are a priori unknown, meaning the most suitable base-LLM (the one that would achieve the best performance post fine-tuning using the budget B) must be learnt via exploration. We formulate this scenario as a non-stationary multi-armed bandit (MAB), seeking to minimize the pseudo regret, which captures the difference in quality between the fine-tuned model output by the algorithm, and that produced by an oracle that knows the learning curves a priori. We derive lower bounds on the pseudo regret under any algorithm, propose algorithms that match the lower bound up to multiplicative factors, and validate the algorithms extensively against real-world fine-tuning datasets. This work was done jointly with Sarvesh Gharat, Utkarsh Chavan and Nikhil Karamchandani.

Biography

Talk Title

Random fixed points, systemic risk and resilience of heterogeneous financial network

Abstract

We consider a large random network, in which the performance of a node depends upon that of its neighbours and some external random influence factors. This results in random vector valued fixed-point (FP) equations in large dimensional spaces, and our aim is to study their almost-sure solutions. An underlying directed random graph defines the connections between various components of the FP equations. Existence of an edge between nodes i,j implies the i-th FP equation depends on the j-th component. We consider a special case where any component of the FP equation depends upon an appropriate aggregate of that of the random `neighbour' components. We obtain finite-dimensional limit FP equations in a much smaller dimensional space, whose solutions aid to approximate the solution of FP equations for almost all realizations, as the number of nodes increases. We use Maximum theorem for non-compact sets to prove this convergence. We apply the results to study systemic risk in an example financial network with large number of heterogeneous entities. We utilized the simplified limit system to analyse trends of default probability (probability that an entity fails to clear its liabilities) and expected surplus (expected-revenue after clearing liabilities) with varying degrees of interconnections between two diverse groups. We illustrated the accuracy of the approximation using exhaustive Monte-Carlo simulations. Our approach can be utilized for a variety of financial networks (and others); the developed methodology provides approximate small-dimensional solutions to large-dimensional FP equations that represent the clearing vectors in case of financial networks.

Biography

Talk Title

Phase Transition for Elephant Random Walks with Two Memory Channels

Abstract

Random processes with strong memory arise naturally in various disciplines including physics, economics, biology, geology, etc. Memory can be multifaceted and can arise due to interactions of more than one underlying phenomena. Many of these processes exhibit superdiffusive growth due to the effect of memory. A class of one-dimensional, discrete-time such models called “random walk with m memory channels” was introduced and discussed in a recent paper on statistical physics by Saha (2022). In these models, the information of m independently chosen steps from the walker’s entire history is needed to decide the future step. The aforementioned work carried out heuristic calculations of variance, and conjectured phase transitions from diffusive to superdiffusive and from superdiffusive to ballistic regimes in the m=2 case. We have proved these conjectures rigorously (with mild corrections), and discovered a new regime at one of the transition boundaries. These results will be presented along with several open problems. (This talk is based on a joint work with Krishanu Maulik and Tamojit Sadhukhan.)

Biography