Multiple and Hierarchical Universality
Universal coding, prediction and learning usually consider the case where the data generating mechanism is unknown or non-existent, and the goal of the universal scheme is to compete with the best hypothesis from a given hypothesis class, either on the average or in a worst-case scenario. Multiple universality considers the case where the hypothesis class is also unknown: there are several hypothesis classes with possibly different complexities. In hierarchical universality, the simpler classes are nested within more complex classes. The main challenge is to correctly define the universality criterion so that the extra "regret" for not knowing the class is monitored. We propose possible definitions and derive their min-max optimal solutions. Interestingly, the proposed solutions can be used to obtain Elias codes for universal representation of the integers. We also utilize this approach for variable-memory Markov models (unifilar models), presenting a new interpretation for the bound over the regret of the celebrated context-tree weighting algorithm and propose a 3-part code that (slightly) out-performs it. Finally, we conjecture that multiple universality with its non-uniform regret can be used in other "overparameterized" model classes including deep neural networks.
Joint work with Yaniv Fogel
Meir Feder received the Sc.D degree in Electrical Engineering and Ocean Engineering in 1987 from the Massachusetts Institute of Technology (MIT) and the Woods Hole Oceanographic Institution (WHOI). After being a Research Associate and a Lecturer in MIT, he joined in 1990 the School of Electrical Engineering, Tel-Aviv University, where he is now the Jokel Chair Professor and the head of the newly established Tel-Aviv university center for Artificial intelligence and Data science (TAD). He is also a Visiting Professor with the Department of EECS, MIT. Parallel to his academic career, he is closely involved with the high-tech industry. He founded 5 companies, among them are Peach Networks that developed an interactive TV solution (Acq: MSFT) and Amimon that provided the highest quality, robust and no delay wireless high-definition A/V connectivity (Acq:LON.VTC). Recently, with his renewed interest in machine learning and AI, he cofounded Run:ai, a virtualization, orchestration, and acceleration platform for AI infrastructure. He is also an active angel investor and serves on the board/advisory board of several US and Israeli companies. Prof. Feder received several academic and professional awards including the IEEE Information Theory Society best paper award for his work on universal prediction, the "creative thinking" award of the Israeli Defense Forces and the Research Prize of the Israeli Electronic Industry, awarded by the President of Israel. For the development of Amimon's chip-set, that uses a unique MIMO implementation of joint source-channel coding for wireless video transmission he received the 2020 Scientific and Engineering Award of the Academy of Motion Picture Arts and Sciences (Oscar) and was announced as the principal inventor of the technology that attained the 73rd Engineering Emmy Award of the Television Academy.