Executive Summary : | Online content caching for web applications has recently become one of the most important opportunistic technologies for advanced 5G wireless networks and beyond. The main goal of this technology is to pre-fetch a small number of files from the main server and store in a small local server called cache, to satisfy future file requests generated by one or multiple users with reduced latency. Classically the online algorithms for caching were proposed and analysed with various stationarity assumptions on the file request sequence. However, as the file request sequence in many modern 5G services are highly non-stationary, construction and analysis of online algorithms with sublinear regret, in short, no-regret algorithms, have recently received a lot of attention. The online caching policies receive reward at each time for predicting cache configuration. For general reward structures, the online caching is hard because it corresponds to the online subset selection problem which is, in general, hard to solve. On the other hand, sparse recovery is a powerful tool in optimization which is used in numerous technologies, like compressed sensing, deep learning, to name a few, for providing data compression and dimensionality reduction. Sparse recovery provides an exact solution to the offline subset selection problem when the measurement matrix satisfies the so called Restricted Isometry Property (RIP). The online version of sparse recovery and its applications as a potential technology for enabling low latency and high performance online web caching with general reward structure is a promising idea which has received relatively little attention in literature. The goal of this project is 1) to develop sparsity-aided novel online algorithms, based on the novel framework of online sparse recovery for online caching with general reward structure, termed as the generalized online caching; 2) to extend the arsenal of popular greedy algorithms for sparse recovery like orthogonal matching pursuit (OMP), orthogonal least squares (OLS), iterated hard thresholding (IHT), hard thresholding pursuit (HTP), etc, to the online caching scenario to obtain online sparsity aided greedy algorithms for generalized caching enjoying sublinear regret/approximate regret as well as efficient implementation. Furthermore, one crucial aspect of this project will be developing theoretical analysis of such algorithms to obtain either sublinear regret or, at least, sublinear approximate regret. Moreover, the project will also aim to extend all the above development to the more practical bandit feedback setting where exact reward functions are not revealed to the policy at each step. |