Fundamental Limits Of Learning In Data-Driven Problems
Yanjun Han (Simons Institute)
3925 - 3936 of 19186 Results
Format results
Harish-Chandra bimodules in complex rank
Aleksandra Utiralova Massachusetts Institute of Technology (MIT)
Information, Learning, And Incentive Design For Societal Networks
Manxi Wu (UC Berkeley)Fair And Reliable Machine Learning For High-Stakes Applications:approaches Using Information Theory
Sanghamitra Dutta (JP Morgan)Mechanism Design Via Machine Learning: Overfitting, Incentives, and Privacy
Ellen Vitercik (UC Berkeley)Efficient Universal Estimators For Symmetric Property Estimation
Kirankumar Shiragur (Stanford University)Quantum Black Holes and Holographic Complexity
Antonia Micol Frassino Universitat de Barcelona
Fundamental Limits Of Learning In Data-Driven Problems
Yanjun Han (Simons Institute)What is the best we can do with the amount of data at our disposal with a given learning task? Modern learning problems---with a modest amount of data or subject to data processing constraints---frequently raise the need to understand the fundamental limits and make judicious use of the available small or imperfect data. This talk will cover several examples of learning where exploiting the key structure, as well as optimally trading between real-world resources, are vital to achieve statistical efficiency.Choosing Between Dags Can Be Hard
Richard Guo (University of Cambridge)Current methods for causal discovery typically report a single directed acyclic graph (DAG). Through an example, I hope to convince you that this might not be the best practice. In fact, depending on how two DAGs intersect and the local geometry at the intersection, the hardness of this problem can vary dramatically.Causal Inference With Corrupted Data: Measurement Error, Missing Values, Discretization, And Differential Privacy
Rahul Singh (MIT)Even the most carefully curated economic data sets have variables that are noisy, missing, discretized, or privatized. The standard workflow for empirical research involves data cleaning followed by data analysis that typically ignores the bias and variance consequences of data cleaning. We formulate a semiparametric model for causal inference with corrupted data to encompass both data cleaning and data analysis. We propose a new end-to-end procedure for data cleaning, estimation, and inference with data cleaning-adjusted confidence intervals. We prove consistency, Gaussian approximation, and semiparametric efficiency for our estimator of the causal parameter by finite sample arguments. The rate of Gaussian approximation is $n^{-1/2}$ for global parameters such as average treatment effect, and it degrades gracefully for local parameters such as heterogeneous treatment effect for a specific demographic. Our key assumption is that the true covariates are approximately low rank. In our analysis, we provide nonasymptotic theoretical contributions to matrix completion, statistical learning, and semiparametric statistics. We verify the coverage of the data cleaning-adjusted confidence intervals in simulations calibrated to resemble differential privacy as implemented in the 2020 US Census.Causal Inference And Data-Driven Decision-Making
Angela Zhou (UC Berkeley)I will provide a brief overview of previous work on credible inference in the context of causal inference and statistical machine learning, and discuss ongoing directions on interfaces of causal inference embedded in complex operational systems.Possibility of causal loops without superluminal signalling -- a general framework
Vilasini Venkatesh University of York
Causality is fundamental to science, but it appears in several different forms. One is relativistic causality, which is tied to a space-time structure and forbids signalling outside the future. On the other hand, causality can be defined operationally using causal models by considering the flow of information within a network of physical systems and interventions on them. From both a foundational and practical viewpoint, it is useful to establish the class of causal models that can coexist with relativistic principles such as no superluminal signalling, noting that causation and signalling are not equivalent. We develop such a general framework that allows these different notions of causality to be independently defined and for connections between them to be established. The framework first provides an operational way to model causation in the presence of cyclic, fine-tuned and non-classical causal influences. We then consider how a causal model can be embedded in a space-time structure and propose a mathematical condition (compatibility) for ensuring that the embedded causal model does not allow signalling outside the space-time future. We identify several distinct classes of causal loops that can arise in our framework, showing that compatibility with a space-time can rule out only some of them. We then demonstrate the mathematical possibility of causal loops embedded in Minkowski space-time that can be operationally detected through interventions, without leading to superluminal signalling. Our framework provides conditions for preventing superluminal signalling within arbitrary (possibly cyclic) causal models and also allows us to model causation in post-quantum theories admitting jamming correlations. Applying our framework to such scenarios, we show that post-quantumjamming can indeed lead to superluminal signalling contrary to previous claims. Finally, this work introduces a new causal modelling concept of ``higher-order affects relations'' and several related technical results, which have applications for causal discovery in fined-tuned causal models.
Harish-Chandra bimodules in complex rank
Aleksandra Utiralova Massachusetts Institute of Technology (MIT)
Deligne tensor categories are defined as an interpolation of the categories of representations of groups GL_n, O_n, Sp_{2n} or S_n to the complex values of the parameter n. One can extend many classical representation-theoretic notions and constructions to this context. These complex rank analogs of classical objects provide insights into their stable behavior patterns as n goes to infinity.
I will talk about some of my results on Harish-Chandra bimodules in Deligne categories. It is known that in the classical case simple Harish-Chandra bimodules admit a classification in terms of W-orbits of certain pairs of weights. However, the notion of weight is not well-defined in the setting of Deligne categories. I will explain how in complex rank the above-mentioned classification translates to a condition on the corresponding (left and right) central characters.
Another interesting phenomenon arising in complex rank is that there are two ways to define Harish-Chandra bimodules. That is, one can either require that the center acts locally finitely on a bimodule M or that M has a finite K-type. The two conditions are known to be equivalent for a semi-simple Lie algebra in the classical setting, however, in Deligne categories that is no longer the case. I will talk about a way to construct examples of Harish-Chandra bimodules of finite K-type using the ultraproduct realization of Deligne categories.Zoom Link: https://pitp.zoom.us/j/93951304913?pwd=WVk1Uk54ODkyT3ZIT2ljdkwxc202Zz09
Information, Learning, And Incentive Design For Societal Networks
Manxi Wu (UC Berkeley)Today's data-rich platforms are reshaping the operations of societal networks by providing information, recommendations, and matching services to a large number of users. How can we model the behavior of human agents in response to services provided by these platforms, and develop tools to improve the aggregate outcomes in a socially desirable manner? In this talk, I will briefly summarize our works that tackle this question from three aspects: 1) Game-theoretic analysis of the impact of information platforms (navigation apps) on the strategic behavior and learning processes of travelers in uncertain networks; 2) Market mechanism design for efficient carpooling and toll pricing in the presence of autonomous driving technology; 3) Security analysis and resource allocation for robustness under random or adversarial disruptions.Fair And Reliable Machine Learning For High-Stakes Applications:approaches Using Information Theory
Sanghamitra Dutta (JP Morgan)How do we make machine learning (ML) algorithms fair and reliable? This is particularly important today as ML enters high-stakes applications such as hiring and education, often adversely affecting people's lives with respect to gender, race, etc., and also violating anti-discrimination laws. When it comes to resolving legal disputes or even informing policies and interventions, only identifying bias/disparity in a model's decision is insufficient. We really need to dig deeper into how it arose. E.g., disparities in hiring that can be explained by an occupational necessity (code-writing skills for software engineering) may be exempt by law, but the disparity arising due to an aptitude test may not be (Ref: Griggs v. Duke Power `71). This leads us to a question that bridges the fields of fairness, explainability, and law: How can we identify and explain the sources of disparity in ML models, e.g., did the disparity entirely arise due to the critical occupational necessities? In this talk, I propose a systematic measure of "non-exempt disparity," i.e., the bias which cannot be explained by the occupational necessities. To arrive at a measure for the non-exempt disparity, I adopt a rigorous axiomatic approach that brings together concepts in information theory (in particular, an emerging body of work called Partial Information Decomposition) with causality.Mechanism Design Via Machine Learning: Overfitting, Incentives, and Privacy
Ellen Vitercik (UC Berkeley)Machine learning is increasingly being used for mechanism design, with applications such as price optimization on online marketplaces and ad auction design. In this talk, I will give an overview of my research on mechanism design via machine learning, touching on statistical problems such as overfitting, incentive problems, and privacy preservation.Efficient Universal Estimators For Symmetric Property Estimation
Kirankumar Shiragur (Stanford University)Given i.i.d samples from an unknown distribution, estimating its symmetric properties is a classical problem in information theory, statistics and computer science. Symmetric properties are those that are invariant to label permutations and include popular functionals such as entropy and support size. Early work on this question dates back to the 1940s when R. A. Fisher and A. S. Corbet studied this to estimate the number of distinct butterfly species in Malaysia. Over the past decade, this question has received great attention leading to computationally efficient and sample optimal estimators for various symmetric properties. All these estimators were property specific and the design of a single estimator that is sample optimal for any symmetric property remained a central open problem in the area. In a recent breakthrough, Acharya et. al. showed that computing an approximate profile maximum likelihood (PML), a distribution that maximizes the likelihood of the observed multiset of frequencies, allows statistically optimal estimation of any symmetric property. However, since its introduction by Orlitsky et. al. in 2004, efficient computation of an approximate PML remained a well known open problem. In our work, we resolved this question by designing the first efficient algorithm for computing an approximate PML distribution. In addition, our investigations have led to a deeper understanding of various computational and statistical aspects of PML and universal estimators.Quantum Black Holes and Holographic Complexity
Antonia Micol Frassino Universitat de Barcelona
In this talk, I will consider quantum effects on some specific black hole solutions and take into account their gravitational backreaction. In particular, I will describe the holographic construction of the quantum BTZ black hole (quBTZ) from an exact four-dimensional bulk solution. I will present some of the thermodynamic properties of these black holes, focus on the generalized first law and analyze the different complexity proposals for the quBTZ. Our results indicate that Action Complexity fails to account for the additional quantum contributions and does not lead to the correct classical limit. On the other hand, the Volume Complexity admits a consistent quantum expansion and agrees with known limits.