February 2024 - Info-theory - huji-cs listserver

ITA seminar 4/3, 10:00 - Alon Kipnis (Reichman)
by Or Ordentlich 27 Feb '24

27 Feb '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place on Monday, March 4 at 10:00, in room A500. The speaker is Alon Kipnis, who will tell us about uniformity testing from a minimiax risk perspective. See you there, Or, Oron, Yuval and Alex --------------------------------------------- *Title*: The minimax risk in testing uniformity under missing ball alternatives *Abstract*: We study the problem of "uniformity testing," i.e., testing the goodness of fit of categorical data to the uniform distribution over the categories. As a class of alternative hypotheses, we consider the removal of an $\ell_p$ ball of radius $\epsilon$ around the uniform rate sequence for $p \leq 2$. When the number of samples $n$ and number of categories $N$ go to infinity while $\epsilon$ is small, we show that the minimax risk $R_\epsilon^*$ in testing based on the sample's histogram (number of absent categories, singletons, collisions, ...) asymptotes to $2\Phi(-n N^{2-2/p} \epsilon^2/\sqrt{8N})$; $\Phi(x)$ is the normal CDF. As it turns out, the minimax test relies on collisions in the very small sample limit but otherwise behaves like the chisquared test. Empirical studies over a range of problem parameters show that our estimate is accurate in finite samples and that the minimax test is significantly better than the chisquared test or a test that only uses collisions. Our result settles several known challenges in uniformity and "identity" testing from the last two decades. In particular, it allows the comparison of the many estimators previously proposed for this problem at the constant level rather than at the rate of convergence of the risk or the scaling order of the sample complexity. Our analysis introduces several new methods by adapting techniques previously used by Ingster and Suslina for Gaussian signal detection.

1 0

ITA seminar 26/2, 10:00 - Dor Tsur, BGU
by Or Ordentlich 25 Feb '24

25 Feb '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place on Monday, February 26 at 10:00, in room A500. The speaker is Dor Tsur, who will tell us about how estimating the mutual information between "good" projections of random vectors, and why this is useful. See you there, Or, Oron, Yuval and Alex --------------------------------------------- *Title*: Max-Sliced Mutual Information: Analysis, Applications and Interpretations *Abstract*: Quantifying dependence between high-dimensional random variables is central to statistical learning and inference. Two classical methods are canonical correlation analysis (CCA), which identifies maximally correlated projected versions of the original variables, and Shannon’s mutual information, which is a universal dependence measure that also captures higher-order dependencies. However, CCA only accounts for linear dependence, while mutual information is often infeasible to compute/estimate in high dimensions. We propose max-sliced mutual information (mSMI), which equals the maximal mutual information between low-dimensional projections of the high-dimensional variables and enjoys the best of both worlds: capturing intricate dependencies in the data while being amenable to fast computation and scalable estimation from samples. We show that mSMI retains favorable structural properties of Shannon’s mutual information and propose an efficiently computable neural estimator, which we couple with formal non-asymptotic error bounds. We present experiments that demonstrate the utility of mSMI for several contemporary learning tasks and draw connections to fundamental problems in statistics and information theory.

1 1

[Learning club] Thursday - 29/2/24: Anatoly Khina - Geometry-oriented Measures of Dependence
by Or Ordentlich 22 Feb '24

22 Feb '24

Hi all, In addition to Dor Tsur's talk on Monday 26.2 in the ITA seminar, there will be another talk that should be of interest for the ITA audience, in the learning club next week (Thursday). The speaker is Anatoly Khina from TAU. See details below. Best, Or, Alex, Oron and Yuval ========== *Time and Place* Thursday, February 29th, 2024, 10:30 AM, room C221 *Speaker* Anatoly Khina (TAU) *Title* Geometry-oriented Measures of Dependence *Abstract:* One of the fundamental problems of statistics and data science is identifying and measuring dependence. This problem dates back to the works of Bravais, Galton, and Pearson in the 18th century on dependence measure design, and to the work of Rényi in the late 1950s on axiomatizing the desired properties of such measures. For discrete random variables, categorical dependence measures—primarily those based on Shannon's mutual information and entropy, and maximal correlation—are valid choices when only the information content is important. However, when some possible underlying physical interpretation is of the essence, other measures need to be sought after. Consequently, much effort has been put into both the design and property axiomatization of such dependence measures when the dependence strength is dictated by the inference quality with respect to some metric. In this talk, I will first propose a new set of natural axioms that reflect desired innate geometric properties. I will show that, in fact, none of the existing dependence measures satisfies this set of axioms and has a known feasible evaluation algorithm. Finally, I will propose a new computationally efficient dependence measure that satisfies all the proposed axioms and compare its performance to that of classical dependence measures such as maximal correlation and correlation ratio, as well as recently proposed measures such as xicor (Chatterjee JASA ‘21), distance correlation (Székely et al. Ann. Stat. ‘07), and maximal information coefficient (Reshef et al. Science ‘11). Joint work with Elad Domanovitz and Yoad Nitzan. *Bio:* Anatoly Khina is a faculty member in the School of Electrical Engineering, Tel Aviv University,from which he holds B.Sc. (2006), M.Sc. (2010), and Ph.D. (2016) degrees. Parallel to his studies, he worked as an engineer in various roles focused on algorithms, data science, software and hardware. He was a Postdoctoral Scholar in the Department of Electrical Engineering, California Institute of Technology(Caltech), from 2015 to 2018, and a Research Fellow at the Simons Institute for the Theory of Computing, University of California, Berkeley, during the spring of 2018. His research interests include Information Theory, Control Theory,Signal Processing and Statistics. *Link for the Panopto Meeting* https://huji.cloud.panopto.eu/Panopto/Pages/Sessions/List.aspx#folderID=%22… <https://www.google.com/url?q=https://huji.cloud.panopto.eu/Panopto/Pages/Se…> *Link to past lectures* https://www.youtube.com/channel/UC_HCN9bzu4KACEWuB5zKP5A <https://www.google.com/url?q=https://www.youtube.com/channel/UC_HCN9bzu4KAC…> *Online Calendar* Learning Club @ HUJI https://www.google.com/calendar/embed?src=pqvap0i55u7ctv9uv3mblf152o%40grou… <https://www.google.com/url?q=https://www.google.com/calendar/embed?src%3Dpq…> Calendar ID: pqvap0i55u7ctv9uv3mblf152o(a)group.calendar.google.com *Mailing List* subscription-manager: http://mailman.cs.huji.ac.il/mailman/listinfo/learning-club <https://www.google.com/url?q=http://mailman.cs.huji.ac.il/mailman/listinfo/…>

1 0

No seminar this week
by Or Ordentlich 11 Feb '24

11 Feb '24

Hi all, We will skip this week's seminar. Ou seminars for the remainder of the semester are: February 26 - Dor Tzur (BGU) March 4 - Alon Kipnis (Riechman) Best, Oron, Yuvak, Alex and Or

1 0

2024

Info-theory February 2024 ----- 2024 ----- November 2024 October 2024 September 2024 August 2024 July 2024 June 2024 May 2024 April 2024 March 2024 February 2024 January 2024

Info-theory February 2024