Abstract:

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 several possible definitions and derive their min-max optimal solutions. Interestingly, the proposed approach can be used to obtain Elias codes for universal representation of the integers. We further 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 suggest a multiple universality approach for general linear models, including linear regression, and logistic regression and Perceptrons.  Finally, we conjecture that multiple universality, with its non-uniform convergence and regret bounds, can be applied to explain and design learning schemes in general “over-parameterized” model classes such as deep neural networks, transformers and so on.

Joint work with Yaniv Fogel.

Bio:

Meir Feder received the B.Sc and M.Sc degrees in Electrical Engineering in 1980 and 1984 from Tel-Aviv University and 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 the School of Electrical Engineering, Tel-Aviv University, where he is now the Jokel Chaired 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 Peach Networks that developed an interactive TV solution (Acq: MSFT) and Amimon that provided the highest quality, robust, no latency 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).