- talks - lists.cs.princeton.edu

Chaitanya Aluru will present his FPO "Reconciliation-Based Methods for Identifying the Evolutionary Origins of Tandem Duplications in Repeat Domain Families" on Friday, 12/17/2021 at 1:30PM via Zoom and CS 105
by Nicki Mahler 14 Dec '21

14 Dec '21

Chaitanya Aluru will present his FPO "Reconciliation-Based Methods for Identifying the Evolutionary Origins of Tandem Duplications in Repeat Domain Families" on Friday, 12/17/2021 at 1:30PM via Zoom and in CS 105 Zoom link: https://princeton.zoom.us/j/99860934740 The members of his committee are as follows: Mona Singh (Adviser), Readers: Ben Raphael, Bernard Chazelle, Mona Singh; Examiners: Mona Singh, Olga Troyanskaya, and Barbara Engelhardt A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Domains are the structural, functional, and evolutionary building blocks of protein sequences. Proteins can contain multiple domain instances, and duplications and losses of these domains are a key driver of protein evolution. Of particular interest are families of proteins with consecutive repeats of the same domain. These tandem repeat families are involved in a wide variety of functions, including transcriptional regulation, protein transport, muscle contraction, brain size regulation, and many others. Proteins with tandemly repeated domains form a significant portion of the proteome across the tree of life. Despite their prevalence and importance, the evolutionary histories and functional diversification of many of these protein families are largely unknown. Understanding when domains duplicate, whether individually or together as part of an array of domains, could yield deeper insights into the functions of these proteins. Several attempts have been made to understand the evolution of repeat domains within protein sequences. These approaches can largely be categorized into sequence-based and reconciliation-based methods. Sequence-based approaches attempt to identify the existence of tandem duplications, without placing them in an evolutionary context. Reconciliation based methods, on the other hand, use gene and domain trees to simultaneously infer both tandem duplication events and the genes they occurred in. These methods, while more powerful, have not accurately captured tandem duplication events. In this work, we bridge the gap between these two methods, developing reconciliationbased methods that can accurately identify tandem domain duplication events while also placing them correctly in the evolutionary history of their gene families. We extend existing reconciliation frameworks to include flexible cost models for duplication events. Rather than fixed costs regardless of duplication size, we represent costs as arbitrary functions of duplication length. We tackle the problem of distinguishing tandem duplications from other duplication events by incorporating sequence position information from existing domains. We provide both exact solutions and fast, accurate heuristics to these problems. Finally, we apply these approaches to the largest repeat domain family in humans, the Cys2-His2 zinc fingers. In analysis of 494 Cys2-His2 zinc finger orthogroups, we find evidence of numerous tandem domain duplications throughout the placental mammals.

1 1

Jiaqi Su will present his Pre FPO "Studio Quality Speech Enhancement" on Thursday, December 16, 2021 at 3pm via Zoom
by Nicki Mahler 13 Dec '21

13 Dec '21

Jiaqi Su will present his Pre FPO "Studio Quality Speech Enhancement" on Thursday, December 16, 2021 at 3pm via Zoom Zoom Link https://princeton.zoom.us/j/6073737365 Committee: Examiners: Adam Finkelstein (advisor), Olga Russakovsky, Karthik Narasimhan Readers: Szymon Rusinkiewicz, Zeyu Jin Abstract: Modern speech content creation tasks such as podcasts, video voice-overs, and audio books require studio-quality audio with full bandwidth and balanced equalization. However, real-world recordings captured in natural spaces with consumer-grade devices suffer from noise, reverberation, equalization distortion and bandwidth limitations. The goal of cleaning up such recordings poses a challenge for conventional speech enhancement methods, which typically focus on removing strong acoustic degradations so as to improve speech clarity and intelligibility, but fall short of studio quality. In this talk, I will present an end-to-end deep learning approach for transforming recorded speech to sound as though it had been recorded in a studio. The approach relies on a multi-domain multi-scale GAN, coupled with deep feature matching in the discriminators, to model the perception of sound quality. It also incorporates a separate pre-trained recurrent neural network to predict the acoustic features of the clean target from those of noisy input, which serves as a guide to generate the clean audio. This combined approach incorporates the effectiveness of acoustic features in modeling human perception of speech, while retaining the benefits of waveform-to-waveform conversion. I will first show the model in the context of speech enhancement at 16kHz, and then discuss how to adapt the approach to bandwidth extension for filling in missing high frequency details at 48kHz. These two components placed together form a full studio-quality speech enhancement pipeline for real-world recordings. Finally, with access to a studio quality version of the recording, we can optionally repurpose components of this pipeline to adapt the recording so that it matches the acoustic qualities of a specific target environment.

1 0

Matthew Weaver will present his Pre FPO "Bicubical Directed Type Theory" on Friday, December 10, 2021 via zoom
by Nicki Mahler 09 Dec '21

09 Dec '21

Matthew Weaver will present his Pre FPO "Bicubical Directed Type Theory" on Friday, December 10, 2021 via zoom. Zoom Link: https://princeton.zoom.us/j/93770491933?pwd=S0g5TW9OR0xEenFOOHBGeHdkK29rdz09 Meeting ID: 937 7049 1933 Passcode: 110745 Committee: Andrew Appel (Advisor) Daniel Licata (Reader) Zachary Kincaid (Reader) David Walker (Examiner) Aarti Gupta (Examiner) Title: Bicubical Directed Type Theory Abstract: In homotopy type theory, each type is equipped with an abstract notion of path, corresponding to the morphisms of a higher groupoid. Voevodsky's univalence axiom states that the type of paths between types is equivalent (a generalization of isomorphism) to the type of equivalences between types, and can be seen as extending type theory with a generic program for lifting equivalences between types along any type family. Defining this lifting for all dependent types is quite subtle, but univalence has recently been given a computational interpretation in various cubical type theories. A natural question is whether there are any directed analogues of homotopy type theory, where types are equipped with a notion of directed morphism and correspond to higher categories, generalizing groupoids. In such a setting, one possible directed analogue of univalence would circumscribe a class of type constructors that represent covariant functors, and provide a means to automatically lift a function or directed morphism along such a type constructor. Directed type theory with directed univalence has some potential applications to computer science that are not possible in ordinary homotopy type theory, such as providing a convenient language for coding the functorial specification of abstract syntax. One approach to directed type theory, developed by Riehl and Shulman, is based on equipping each type with both a notion of path and a separate notion of directed morphism. While ordinary homotopy type theory has models in simplicial sets (a model of homotopy types) the Riehl-Shulman type theory is based on a model in bisimplicial sets, capturing these two notions of path and directed morphism. While this suffices for formalizing mathematics, for applications to computer science we would like a computational interpretation of the type theory, and it is not yet known whether there are constructive models of standard homotopy type theory in simplicial sets. Thus, in this thesis, we instead consider a cubical setting, and give a constructive model of a directed type theory with directed univalence in bicubical sets. We formalize much of this model using Agda as the internal language of a 1-topos, following Orton and Pitts. First, building on the cubical techniques used to give computational models of homotopy type theory, we show that there is a universe of covariant discrete fibrations (covariant functors valued in types that themselves have trivial morphism structure), with a partial directed univalence principle asserting that functions are a retract of morphisms in this universe. To complete this retraction into an equivalence, we refine the model using some recent work on constructive sheaf models by Coquand, Ruch, and Sattler, which builds on Shulman's characterization of fibrations in injective model structures as algebras for the cobar construction. Concretely, this means equipping each fibrant type with an additional operation (an equivalence with the cobar construction on it), from which the final part of the directed univalence equivalence can be defined. In the presence of directed univalence, one would additionally hope for a theory containing directed higher inductive types (DHITs). These types allow for one to inductively define types containing directed structure, and in conjunction with directed univalence allow for novel proof techniques in verification; in particular, the combination allows one to directly formalize functorial semantics using the internal categorical structure of types. We introduce a schema for DHITs based off of the schema for higher inductive types in cubical type theory by Cavallo and Harper. As a part of this work, we additionally define schemas for regular inductive types and higher inductive types. Lastly, we demonstrate how DHITs can be used with directed univalence to encode functorial semantics for formal verification.

1 1

Austin Hounsel will present his Pre FPO “Measuring the Feasibility of DNS Privacy and Security” on Tuesday, December 7th, 2021 at 12pm via Zoom
by Nicki Mahler 03 Dec '21

03 Dec '21

Austin Hounsel will present his Pre FPO “Measuring the Feasibility of DNS Privacy and Security” on Tuesday, December 7th, 2021 at 12pm via Zoom. Zoom link: https://princeton.zoom.us/j/93647966696 <https://princeton.zoom.us/j/93647966696> - Nick Feamster (advisor): non-reader - Jennifer Rexford: non-reader - Ravi Netravali: non-reader - Prateek Mittal: reader - Kyle Jamieson: reader Abstract: "Virtually every device on the Internet relies on the Domain Name System (DNS) to translate human-readable names to IP addresses. Originally, the DNS was designed without security and privacy concerns in mind. This has left users’ DNS traffic subject to eavesdropping, tampering, and censorship. In response, encrypted DNS protocols and DNS Security Extensions (DNSSEC) have seen increased deployment. Although these technologies are designed to improve users’ security and privacy, two key questions remain unanswered. First, it is unclear whether encrypted DNS protocols yield acceptable performance for popular applications, such as web browsers. Second, it is unclear whether users can reliably retrieve the DNS records that are necessary for client-side DNSSEC validation. Without answers to these questions, popular application developers are unable to determine the feasibility and value of deploying these technologies. This thesis studies the feasibility and value of deploying DNS security and privacy technologies through various Internet measurements. We first present performance measurements of encrypted DNS protocols from data centers and home networks. We not only measure query response times, but also web page load times to understand how these protocols might impact popular applications that issue numerous queries. We find that although encrypted DNS protocols generally result in longer query response times than traditional, unencrypted DNS, these protocols can result in faster page load times. Our work suggests that users don’t need to trade DNS performance for privacy. On the other hand, we also find that the security value of implementing client-side DNSSEC validation is questionable. We present a collaboration with a major browser vendor to measure how often browser users can successfully retrieve DNS records that are necessary for client-side DNSSEC validation. To do so, we deploy a measurement add-on to a global distribution of 5% of the browser’s beta users. The add-on issues queries for various DNS records under a domain name that we control using the browser's locally configured recursive resolver. We find that users were unable to retrieve the correct DNS records they needed to perform client-side DNSSEC validation across approximately 1/3rd of the measurements. Thus, applications may not obtain additional security from DNSSEC beyond querying a recursive resolver that supports it."

1 0

Princeton Wireless Distinguished Seminar Series - Onur Sahin, InterDigital: Wednesday, December 6
by Emily C. Lawrence 30 Nov '21

30 Nov '21

Princeton Wireless Distinguished Seminar Series Speaker: Onur Sahin, InterDigital Title: Emerging Pillars and Vision for Beyond-5G/6G Wireless Communications Day: Monday, December 6, 2021 Time: 12:30 pm Room: Virtual, Please register here: [ https://princeton.zoom.us/meeting/register/tJwqceigrTwsHtwqy5-xPNN6bPjUHQEo… | https://princeton.zoom.us/meeting/register/tJwqceigrTwsHtwqy5-xPNN6bPjUHQEo… ] Host: Yasaman Ghasempour and Kyle Jamieson Abstract: The recent shift of focus from research and development to deployment and commercialization of 5G systems has concurrently unveiled the “what comes next?” question embodied in an overarching beyond-5G/6G vision targeting 2030 and beyond. This talk will address some questions pertinent to beyond-5G/6G technologies such as shortcomings of 5G against the grand vision of a “fully-connected world” and the consensus on a beyond-5G/6G vision that has started to shape both in industry and academia. The talk will further elaborate on the emerging pillars of beyond-5G/6G including networks, terminal architectures, and radio, along with necessary evolution and disruption anticipated in some of these pillars. Finally, we will provide an overview of most recent designs and progress on key beyond-5G enablers and challenges, including ultra-high throughput (above 100Gbps) wireless link solutions, joint communication and sensing, and AI/ML as a useful toolbox for air-interface connectivity technologies. Bio: Onur Sahin received his B.S. degree (hons.) in electrical and electronics engineering from Middle East Technical University, Ankara, Turkey, in 2003 and Ph.D. degree in electrical engineering from New York University, USA in 2009. He is currently a Member of Technical Staff at InterDigital Europe. His primary research and development interests are on the next generation telecommunication and wireless systems, with current emphasis on beyond 5G technologies. Dr. Sahin has held technical lead positions at multiple projects on next generation cellular and Wi-Fi systems. He is the co-author of over 45 peer-reviewed scientific articles (h-index: 23), co-inventor of 35 patents and patent applications, and co-recipient of the 2018 IEEE Signal Processing Society Best Paper Award, and 2016 Journal of Communication Networks Best Paper Award.

1 0

Matheus Venturyne Xavier Ferreira will present his FPO "Economics and Computation in Decentralized Systems" on Wednesday, December 1, 2021 at 11AM via Zoom and CS 402
by Nicki Mahler 24 Nov '21

24 Nov '21

Matheus Venturyne Xavier Ferreira will present his FPO "Economics and Computation in Decentralized Systems" on Wednesday, December 1, 2021 at 11AM via Zoom and CS 402. Zoom link: [ https://princeton.zoom.us/my/matheusvxf | https://princeton.zoom.us/my/matheusvxf ] The members of his committee are as follows: Examiners: Matt Weinberg (Adviser), Arvind Narayanan, Ran Raz Readers: Mark Braverman, David C. Parks (Harvard University) A copy of his thesis is available upon request. Please email [ mailto:gardinfo@cs.princeton.edu | gradinfo(a)cs.princeton.edu ] if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Algorithmic game theory studies algorithmic design under incentive constraints, and, in its foundations, the contributions between computer science and economics in this area go both ways. In one direction, economics provides new perspectives in designing secure computer systems: real-world adversaries are often not intentionally malicious but rather rational and economically driven. Notably, Bitcoin has been successful in implementing a decentralized global ledger of transactions. In the other direction, the emergence of decentralized applications poses challenges to traditional assumptions from economic theory. Notably, Internet auctions often lack transparency, and in practice, it is impossible to detect if an auctioneer, over the Internet, is cheating to improve revenue. Here, we study the problem of designing decentralized applications implemented by autonomous rational agents. First, we provide efficient constructions of credible and strategyproof optimal auctions where neither bidders nor the auctioneer has the incentive to be strategic. This result overcomes prior impossibility results in the literature using standard cryptographic assumptions. More importantly, since our auctions are revenue optimal, it shows that the auctioneer need not sacrifice revenue in favor of implementing a more transparent auction that does not rely on the auctioneer’s altruism. Blockchains are a promising tool for designing generic decentralized applications, but constructions relying on Proof-of-Work (PoW) are energy inefficient. We show that energy-efficient alternatives, notably Proof-of-Stake blockchains, can approximate the incentive guarantees of PoW when given access to public randomness. Thus we reduce the problem of designing energy-friendly blockchains to designing a trusted public source of randomness such as the NIST randomness beacon. Third, we show the connections between credible auction design with the problem of allocation block space in blockchains through a transaction fee mechanism. We propose dynamic mechanisms that provide a better user experience than the status quo and are robust manipulation from miners. Under natural conditions, we provide guarantees for the stability of our mechanism and welfare guarantees. In the last part, we investigate the role of policy and regulation in designing a secure decentralized system. Although technical advances have contributed significantly to the security of Internet systems, the proliferation of large-scale DDos attacks shows how incentive misalignment between users and manufacturers of computer devices drives the risk of computer vulnerabilities. Optimal regulations might require intervention from users and manufacturers and might be highly complex. However, we give theoretical evidence that interventions that impact only users or manufacturers can approximate the outcome of optimal ones.

1 0

Yi Zhang will present his FPO "Generalization of Deep Neural Networks in Supervised Learning, Generative Modeling and Adaptive Data Analysis" on Friday, December 3, 2021 at 3PM via Zoom.
by jfarquer＠cs.princeton.edu 22 Nov '21

22 Nov '21

<https://princeton.zoom.us/j/91333853352> Announcement revised 11/22/2021 to include the Zoom link. ---------------------------------------------------------------------------- ----- Yi Zhang will present his FPO "Generalization of Deep Neural Networks in Supervised Learning, Generative Modeling and Adaptive Data Analysis" on Friday, December 3, 2021 at 3PM via Zoom. Zoom Link: https://princeton.zoom.us/j/91333853352 The members of his committee are as follows: Examiners: Sanjeev Arora (Adviser), Jason Lee, Karthik Narasimhan Readers: Chi Jin, Elad Hazan A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Why can neural nets with a vast number of parameters, trained on small datasets, still accurately classify unseen data? This "generalization mystery" has become a central question in deep learning. Besides the traditional supervised learning setting, the success of deep learning extends to many other regimes where our understanding of generalization behavior is even more elusive. In this thesis, we begin with supervised learning and ultimately aim to shed light on the generalization performance of deep neural nets in generative modeling and adaptive data analysis by presenting novel theoretical frameworks and practical tools. First, we prove a generalization bound for supervised deep neural networks building upon an empirical observation that the inference computations of deep nets trained on real-life datasets are highly resistant to noise. Following an information-theoretic principle that noise stability indicates redundancy and compressibility, we propose a new succinct compression of the trained net, which leads to drastically better generalization estimates. Next, we establish a finite capacity analysis of Generative Adversarial Networks (GANs). Our study gives insights into the limitations of GANs' ability to learn distributions, and we provide empirical evidence that well-known GANs approaches do result in degenerate solutions. Despite the negative results, we proceed to demonstrate a surprising positive use case of GANs: the test performance of deep neural net classifiers can be predicted accurately using synthetic data generated from a GAN model that was trained on the same training set. Finally, we probe the question "has deep learning models overfitted to standard datasets such as ImageNet after years of data reuse?" We provide a simple estimate, Rip Van Winkle's Razor, for measuring overfitting due to data overuse. It relies upon a new notion of the amount of information that would have to be provided to an expert referee who is familiar with the field and relevant math and who has just been woken up after falling asleep at the moment of the creation of the test set (like in the fairy tale). We show this estimate is non-vacuous in many ImageNet models.

1 0

Malte Moeser will present his FPO "Cryptocurrency Privacy in Practice" on Tuesday, November 30, 2021 at 3PM via Zoom.
by jfarquer＠cs.princeton.edu 22 Nov '21

22 Nov '21

Malte Moeser will present his FPO "Cryptocurrency Privacy in Practice" on Tuesday, November 30, 2021 at 3PM via Zoom. Zoom link: https://princeton.zoom.us/j/94235413626 The members of his committee are as follows: Examiners: Arvind Narayanan (Adviser), Jonathan Mayer, Nicholas Christin (Carnegie Mellon University) Readers: Matt Weinberg, Rainer Böhme (University of Innsbruck) A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Cryptocurrencies like Bitcoin balance privacy and transparency goals. In these systems, all transactions are public by design, allowing nodes in a decentralized network to validate them. However, this reveals many potentially privacy-sensitive transaction details of users, whose privacy is only protected by varying degrees of pseudonymity. Understanding the privacy cryptocurrencies provide in practice is hence important for users transacting in them as well as law enforcement or regulatory agencies concerned about their illicit use. This thesis explores privacy in cryptocurrencies with differing transparency goals. We find that cryptocurrency privacy is inherently interdependent, as some users' behavior can negatively affect other users' privacy. Furthermore, privacy-sensitive disclosures from a few users can impact the privacy provided by the system at large. Yet, transparency need not come at the expense of privacy, and we show how it could be useful to impede illicit activity. First, analyzing the early use of the privacy-focused cryptocurrency Monero, we find that some users decision to forgo optional privacy protections obfuscating which coins they spend actively reduced those privacy provisions for others who opted for increased privacy. Furthermore, the obfuscation mechanisms employed by the Monero wallet did not match users actual behavior well, negatively affecting the privacy of all transactions. Next, we turn to address clustering, a blockchain analysis technique essential to understanding how Bitcoin is used in practice. As Bitcoin users can use many addresses, increasing their privacy, address clustering aims at revealing all addresses under a users control. However, current techniques haven't been rigorously evaluated or optimized. Using ground truth data extracted from the blockchain based on users privacy-compromising behavior, we build new models to identify users addresses with high accuracy and use them to create enhanced clusterings. Finally, we consider a system intentionally designed to aid law enforcement goals of deterring money laundering and other financial crime. Public blacklists of coins involved in illicit activity can incentivize individual users to reject payments that can be traced back to listed coins, impeding money laundering attempts. We discuss how blacklisting would change the Bitcoin ecosystem and provide a theoretical and empirical evaluation of different tainting policies.

1 0

Karan Singh will present his FPO "The Nonstochastic Control Problem" on Tuesday, November 30, 2021 at 11AM via Zoom.
by jfarquer＠cs.princeton.edu 22 Nov '21

22 Nov '21

Karan Singh will present his FPO "The Nonstochastic Control Problem" on Tuesday, November 30, 2021 at 11AM via Zoom. Zoom link: https://princeton.zoom.us/meeting/97274954815 The members of his committee are as follows: Examiners: Elad Hazan (Adviser), Anirudha Majumdar (MAE), Sanjeev Arora Readers: Karthik Narasimhan, Sham Kakade (University of Washington, Microsoft Research) A copy of Karan's thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Controlling a dynamical system is a fundamental problem, with wide-reaching applications in autonomous systems, engineering, and sciences. This thesis outlines algorithms and their analyses for feedback-driven learning that make progress on several fronts: robustness, adaptivity, generality, and sample efficiency. The focal point of this thesis is the introduction of the nonstochastic control framework, which builds an algorithmic, against the traditionally analytic, foundation for control theory. This segment provides robust algorithmic primitives for basic control subroutines. Concretely, it presents: 1. An efficient algorithm for controlling linear systems in the presence of nonstochastic perturbations with an instance-optimal regret guarantee. Beyond the realm of both robust and stochastic control, such a data-driven notion of optimality offers worst-case guarantees with a promise of exceptional performance on benign problem instances; 2. The first logarithmic regret result for the classical tracking problem, using optimization-based tools that go beyond dynamic programming based approaches; 3. Extensions of the above to the case of unknown system dynamics. The second part of the thesis addresses the challenge of learning to act in non-stationary environments given a handful of trials, a version of the sim-to-real challenge. It provides a provable algorithm that negotiates this challenge using the algorithmic foundation delineated above, and demonstrates its efficacy over known approaches in non-linear settings. The final segment concerns the generalization of the notion of feedback in interactive learning beyond scalar rewards. It provides an efficient reductions-based approach to tackling concave reward functionals, that may increasingly be found in underlying exploration subroutines. This is accomplished via a novel generalization of classical boosting and gradient boosting techniques to the online convex optimization setting.

1 0

Yi Zhang will present his FPO "Generalization of Deep Neural Networks in Supervised Learning, Generative Modeling and Adaptive Data Analysis" on Friday, December 3, 2021 at 3PM via Zoom.
by jfarquer＠cs.princeton.edu 22 Nov '21

22 Nov '21

Yi Zhang will present his FPO "Generalization of Deep Neural Networks in Supervised Learning, Generative Modeling and Adaptive Data Analysis" on Friday, December 3, 2021 at 3PM via Zoom. Zoom Link: The members of his committee are as follows: Examiners: Sanjeev Arora (Adviser), Jason Lee, Karthik Narasimhan Readers: Chi Jin, Elad Hazan A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract follows below: Why can neural nets with a vast number of parameters, trained on small datasets, still accurately classify unseen data? This "generalization mystery" has become a central question in deep learning. Besides the traditional supervised learning setting, the success of deep learning extends to many other regimes where our understanding of generalization behavior is even more elusive. In this thesis, we begin with supervised learning and ultimately aim to shed light on the generalization performance of deep neural nets in generative modeling and adaptive data analysis by presenting novel theoretical frameworks and practical tools. First, we prove a generalization bound for supervised deep neural networks building upon an empirical observation that the inference computations of deep nets trained on real-life datasets are highly resistant to noise. Following an information-theoretic principle that noise stability indicates redundancy and compressibility, we propose a new succinct compression of the trained net, which leads to drastically better generalization estimates. Next, we establish a finite capacity analysis of Generative Adversarial Networks (GANs). Our study gives insights into the limitations of GANs' ability to learn distributions, and we provide empirical evidence that well-known GANs approaches do result in degenerate solutions. Despite the negative results, we proceed to demonstrate a surprising positive use case of GANs: the test performance of deep neural net classifiers can be predicted accurately using synthetic data generated from a GAN model that was trained on the same training set. Finally, we probe the question "has deep learning models overfitted to standard datasets such as ImageNet after years of data reuse?" We provide a simple estimate, Rip Van Winkle's Razor, for measuring overfitting due to data overuse. It relies upon a new notion of the amount of information that would have to be provided to an expert referee who is familiar with the field and relevant math and who has just been woken up after falling asleep at the moment of the creation of the test set (like in the fairy tale). We show this estimate is non-vacuous in many ImageNet models.

1 0