Doctoral Thesis: Characterizing the non-asymptotic behavior in massive multiple access and streaming system identification

Suhas S. Kowshik

Abstract: 

Non-asymptotic understanding of information theoretic and algorithmic limits of estimation in statistical problems is indispensable for practical applications in engineering. There are two broad approaches to this end. The first: tools and advances in modern probability theory aid in deriving fully non-asymptotic bounds for such problems. This approach, while useful, is sometimes insufficient as the bounds it yields usually have suboptimal constants and unavoidable logarithmic factors. Consequently, in some situations where the primary goal is to obtain sharp characterizations, e.g., error exponents, it can be highly non-trivial to derive fully non-asymptotic results that serve this purpose, particularly in high dimensional problems of recent times. In aforesaid circumstances there is a second approach: recourse to certain asymptotics that can serve as a reasonable or a good substitute for finite length behavior. In our work, we employ both these approaches for two different problems. 

First, we provide asymptotic high dimensional bounds for energy efficiency in massive multiple access which is an important consideration in upcoming wireless networks. In particular we consider the model of quasi-static Rayleigh fading many-user multiple access channel (MAC) and provide tight bounds on the (asymptotic in blocklength) minimum energy-per-bit required to achieve a target per-user error for fixed payload size and user density. Although asymptotic, the results are expected to be a good proxy for the finite blocklength performance in modern unsourced MAC. We confirm the presence of the promising almost perfect multi-user interference cancellation, first observed in the AWGN setting, in the quasi-static case. 

Next, we turn towards streaming system identification where the goal is to learn the system parameters of a dynamical system using a single trajectory in an online or a streaming fashion. In particular we consider certain linear and generalized linear (nonlinear) dynamical systems with full state observation. We develop a novel algorithm called SGD with Reverse Experience Replay for online identification of the system. We provide tight non-asymptotic bounds showing the optimality of our method.

Details

• Date: Tuesday, April 12
• Time: 3:15 pm - 5:00 pm
• Location: 32-D677

Additional Location Details:

Thesis Supervisor: Prof. Yury Polyanskiy

Zoom link: Upon request, suhask@mit.edu