- Info-theory - huji-cs listserver

ITA seminar 18/11, 10:00 - Shachar Shayovitz, TAU
by Or Ordentlich 12 Nov '24

12 Nov '24

Hi all, Our next Information Theory and Applications seminar for the academic year will take place on Monday, November 18 at 10:00, in room A500. The speaker this week is Shachar Shayovitz, who will tell us about the role of information theory in active learning. See title and abstract below. See you there, Or, Oron, Yuval and Alex --------------------------------------------- Title: Information Theoretic Active Learning Abstract: Active learning is a machine learning paradigm aimed at improving model efficiency by strategically selecting the most informative data points for labeling, thereby reducing reliance on large annotated datasets. This is particularly relevant in privacy-sensitive applications where user data cannot be easily or fully annotated. Unlike traditional active learning approaches, which assume that the training and test sets share the same distribution, our research introduces novel methodologies that function effectively without this assumption, both in stochastic (probabilistic) and individual (non-probabilistic) settings. In the first part of our research, we address active learning within the stochastic setting, where data is governed by a probability distribution from a known hypothesis class. We propose a novel information-theoretic criterion for active learning, grounded in the Redundancy-Capacity theorem from universal source coding. This criterion naturally balances the exploration-exploitation trade-off in feature selection and offers a more robust alternative to heuristic-based methods. Both theoretical analysis and empirical validation demonstrate that our approach outperforms conventional methods in various tasks. The second part of our research focuses on active learning in the individual setting, where no probabilistic relationship between the training and test sets is assumed. Drawing on universal source coding principles, we introduce a new criterion for selecting data points that minimizes the min-max regret on the test set. For tasks such as binary classification and linear regression, our criterion coincides with established active learning strategies, offering a unified framework for general hypothesis classes. However, applying active learning to deep learning models presents a unique challenge due to the complexity and high-dimensionality of modern neural networks. In deep learning scenarios, existing active learning techniques often struggle with computational efficiency and accuracy, as neural networks require a large amount of labeled data to generalize effectively. To address these challenges, we extended our criterion by incorporating variational inference to approximate the posterior distribution of model parameters. This approach allowed us to develop a highly efficient, low-complexity algorithm tailored for deep learning applications. Our algorithm not only simplifies the task of selecting informative data points but also enhances the performance of neural networks in scenarios where labeled data is scarce. Experimental results demonstrate that our approach outperforms state-of-the-art active learning methods for deep learning. In particular, we achieved a reduction of 15.4%, 11%, and 35.1% in the required labeled data for CIFAR10, EMNIST, and MNIST datasets, respectively, even in the presence of out-of-distribution data. These results highlight the robustness and practical applicability of our method in reducing the labeling effort for deep learning tasks, making it a promising solution for real-world applications where large-scale data annotation is prohibitive. Joint work with Meir Feder

1 0

ITA seminar 4/11, 10:00 - Royi Jacobovic, TAU
by Or Ordentlich 03 Nov '24

03 Nov '24

Hi all, Our first Information Theory and Applications seminar for the academic year will take place on Monday, November 4 at 10:00, in room A500. The speaker this week is Royi Jacobovic, who will tell us about new results on Moran's single-split test. See title and abstract below. See you there, Or, Oron, Yuval and Alex --------------------------------------------- Title: Simple sufficient condition for inadmissibility of Moran's single-split test. Abstract: Suppose that a statistician has two iid observations that each of them is equal to the parameter of the model plus a random noise. His purpose is to test whether the parameter is zero with a pre-defined significance level. Moran (1973) suggested a test which is based on a single split of the data, i.e., to use the second observation in order to conduct a one-sided test in the direction of the first observation. Moran mentioned that when the noise is distributed according to a normal distribution, the power of this test is not greater than the power of the standard two-sided Z-test. In this work, we generalize this result by providing a condition on the distribution of the noise under which Moran's test is inadmissible. The proof of these results follows from an analysis of a new notion, regular admissibility of tests. Furthermore, when the parameter (and the observations) are vectors, the current analysis yields a new characterization of the multivariate normal distribution via convex likelihood ratios. The seminar is based on two works: Jacobovic, R. (2022). Simple sufficient condition for inadmissibility of Moran’s single-split test. Electronic Journal of Statistics, 16, 3036-3059. Jacobovic, R., & Kella, O. (2022). A characterization of normality via convex likelihood ratios. Statistics & Probability Letters , 186 , 109455.

1 1

ITA seminar 15/7, 10:00 - Student Seminars
by Or Ordentlich 14 Jul '24

14 Jul '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place tomorrow (Monday), July 15, at 10:00, in room A500. The meeting will consist of two presentations, given by Moshe Shenfeld and Aharon Rips. They will describe to us research papers they have read. I (Or) am sick and will not be able to make it to the seminar. My apologies to the speakers. Best, Or, Oron, Yuval and Alex

1 0

ITA seminar 1/7, 10:00 - Student Seminars
by Or Ordentlich 30 Jun '24

30 Jun '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place tomorrow (Monday), July 1, at 10:00, in room A500. The meeting will consist of two presentations, given by Nadav Lustig and Maya Swisa. They will describe to us research papers they have read. See you there, Or, Oron, Yuval and Alex

1 0

ITA seminar 17/6, 10:00 - Anelia Somekh-Baruch (Bar Ilan)
by Or Ordentlich 13 Jun '24

13 Jun '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place on Monday, June 17 at 10:00, in room A500. The speaker is Anelia Somekh-Baruch, who will tell us about an exciting new technique for proving impossibility results for various communication setups. See you there, Or, Oron, Yuval and Alex --------------------------------------------- *Title:* A new framework for proving converse theorems for channel coding *Abstract: *The problem of determining the fundamental limits of channel coding in the case of sub-optimal decoding, also known as "mismatched decoding," is a longstanding question that has numerous applications in fields such as communications, information theory, and computer science. For instance, the zero-error capacity of a channel is a special example of a mismatched channel coding scenario. In this talk, I will provide an overview of this problem and introduce a new bounding technique called the "multicasting approach." This approach yields multiple single-letter converse (impossibility) bounds for stationary memoryless channels that are non-trivial. Additionally, I will discuss how refining this method leads to state-of-the-art converse bounds on the reliability function (error exponent) for channel coding of discrete memoryless channels with maximum-likelihood decoding.

1 0

ITA seminar 3/6, 10:00 - Dor Elimelch (BGU)
by Or Ordentlich 03 Jun '24

03 Jun '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place on Monday, June 3 at 10:00, in room A500. The speaker is Dor Elimelch, who will tell us about error correction in constrained systems. See you there, Or, Oron, Yuval and Alex --------------------------------------------- *Title:* Quantized-Constraint Concatenation and the Covering Radius of Constrained Systems *Abstract:* We introduce a novel framework for implementing error-correction in constrained systems. The main idea of our scheme, called Quantized-Constraint Concatenation (QCC), is to employ a process of embedding the codewords of an error-correcting code in a constrained system as a (noisy, non-invertible) quantization process. This is in contrast to traditional methods, such as concatenation and reverse concatenation, where the encoding into the constrained system is reversible. The possible number of channel errors QCC is capable of correcting is linear in the block length $n$, improving upon the $O(\sqrt{n})$ possible with the state-of-the-art known schemes. For a given constrained system, the performance of QCC depends on a new fundamental parameter of the constrained system -- its covering radius. Motivated by QCC, we study the covering radius of constrained systems in both combinatorial and probabilistic settings. We reveal an intriguing characterization of the covering radius of a constrained system using ergodic theory, which we use in order to establish efficiently computable upper bounds on the covering radius.

1 1

ITA seminar 20/5, 10:00
by Or Ordentlich 15 May '24

15 May '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place on Monday, May 20 at 10:00, in room A500. I will speak about some recent advancements in the lattice covering problem. See you there, Or (and Oron, Yuval and Alex) --------------------------------------------- Title: Bounds on the density of smooth lattice coverings Abstract: The epsilon-smooth covering density of a unit co-volume lattice L with respect to a convex body K is defined as the minimum volume of a dilate rK such that each point x\in R^n is rK-covered by (1\pm epsilon)Vol(r K) points in L. For any convex body K in R^n we show that for almost all lattices (with respect to the natural Haar-Siegel measure on the space of lattices) the epsilon-smooth covering density is polynomial in n. We also show similar results for random construction A lattices, provided that the ratio between the covering and packing radii of Z^n with respect to K is at most polynomial in n. Our proofs utilize a recent result of Dhar and Dvir on the discrete Kakeya problem. Joint work with Oded Regev and Barak Weiss

1 0

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

2024

Info-theory ----- 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