Caching is a fundamental component of content delivery systems such as cloud services and edge networks. Most existing analytical studies of caching assume that the cache can be updated after every file request; however, this assumption is impractical in real systems due to computational constraints. In this paper, we study an online caching framework in which cache updates occur only at prescribed intervals, resulting in bunched request arrivals between successive updates. We analyze the performance of the Follow-The-Perturbed-Leader (FTPL) algorithm under such constraints while incorporating computation cost into the regret metric. For various combinations of adversarial and stochastic request and arrival processes, we derive upper bounds on regret as a function of the cache update frequency. Our results show that both the regret and the total computation cost can be made sublinear in the time horizon with appropriately chosen update intervals. In particular, significantly tighter bounds are obtained when arrivals follow stochastic processes such as the Poisson distribution.
Mixing time bounds for Markov chains play a central role in characterizing the sample complexity of learning and inference from correlated data. While the mixing behavior of symmetric random walks on standard graph structures such as cycles, tori, and hypercubes is well understood, the impact of transition asymmetry remains less explored. In this work, we study the mixing times of lazy, asymmetric random walks on cycles, tori, and hypercubes, motivated by their relevance in practical applications. For the $n$-cycle, we develop a novel coupling construction that yields an order-wise tight upper bound $O\left(\frac{n^{2}}{p+q}\right)$, explicitly capturing the dependence on asymmetric transition probabilities $p$ and $q$. Numerical results indicate that this dependence is highly accurate. Building on this result, we derive corresponding bounds for $d$-dimensional tori. For asymmetric random walks on $n$-dimensional hypercubes, motivated by applications, we consider the problem of estimating expectations of functions that depend only on a subset $\Delta \ll n$ of coordinates. We show that the effective sample complexity improves to $O(n \log \Delta)$, compared to $O(n \log n)$ for the full chain. In all cases, our bounds recover the tightest known results for symmetric walks as special cases.
Mrudula A Mahindrakar, Hrushikesh A Kant, Avhishek Chatterjee· International Conference on...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
