The \emph{orbit} of an n-variate polynomial f(\var x) over a field \F, denoted by \orbit{f}, is the set of polynomials obtained by applying invertible affine transformations on the variables of f(\var x), and the orbit of a polynomial class is the
Prof. Arkadev Chattopadhayay (TIFR), Prof. Prahladh Harsha (TIFR), Prof. Mahan Maharaj (TIFR), Prof. Hariharan Narayanan (TIFR), Prof. Jaikumar Radhakrishnan (TIFR)
Time:
Wednesday, 19 May 2021, 16:00 to 17:30
Covering Contributions of Abel Laureate Avi Wigderson
Arkadev Chattopadhyay "Games Avi Plays To Prove Hardness"
Prahlad Harsha "How Avi copes with Difficulty: A computational perspective on randomness and knowledge"
The query model is a simple model of computation that has led to many deep results. One such class of results relates computational complexity measures such as query complexity/communication complexity to algebraic measures such as degree/rank.
I will present the 2013 NIPS paper by Dan Russo and Van Roy where they introduce the notion of Eluder dimension and use it to analyse the UCB and Thompson Sampling algorithms.
The fact that the polynomial (x1+...+xn)^d can be written as a poly(n,d)-sum of products of univariates is a consequence of what is popularly known as 'the duality trick' in the algebraic complexity circles.
Abstract: Generalization error is the gap between an algorithm's performance on the true data distribution (unknown to us) and its performance on the given dataset (known to us).