- talks - lists.cs.princeton.edu

Weikun Yang will present his general exam on Wednesday, May 24, 2017 at 10am in CS 402.
by Nicki Gotsis 17 May '17

17 May '17

Weikun Yang will present his general exam on Wednesday, May 24, 2017 at 10am in CS 402. The members of his committee are: Aarti Gupta (adviser), Andrew Appel, and Zak Kincaid. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Lazy Self-Composition for Security Verification Verification of secure information flow plays an important role in protection of security and privacy in software applications. It can be reduced to safety verification, as shown by Barthe et al., where a “self-composition” of the program is created by duplicating the program on which a safety property is verified. Due to practical challenges of software verification on duplicated copies, Terauchi and Aiken proposed to use type-directed transformation during self-composition. However it relies on static type analysis which can be imprecise. To further reduce the cost of verification, we use an approach based on bounded model checking to encode symbolic and precise propagation of taint, enabling lazy self-composition that duplicates only the tainted parts of the program. Furthermore, we perform additional checks during bounded model checking to enable early termination of security verification, without needing to compute program invariants. We have implemented a prototype information flow checker in the SeaHorn verification platform, which uses Horn-clause based program representations and the Z3 SMT solver in the backend. We present experiments showing effectiveness of our approach on several examples. Research papers: 1. Gilles Barthe, Pedro R. D'Argenio, and Tamara Rezk. 2004. Secure Information Flow by Self-Composition . CSFW ’04. 2. Tachio Terauchi and Alex Aiken. 2005. Secure information flow as a safety problem. SAS’05. 3. Pramod Subramanyan, Sharad Malik, Hareesh Khattri, Abhranil Maiti, and Jason Fung. 2016. Verifying information flow properties of firmware using symbolic execution . DATE ’16. 4. Gilles Barthe, Juan Manuel Crespo, César Kunz. 2011. Relational Verification Using Product Programs. FM’11. 5. Marcelo Sousa and Isil Dillig. 2016. Cartesian hoare logic for verifying k-safety properties. PLDI ’16. 6. José Bacelar Almeida, Manuel Barbosa, Gilles Barthe, François Dupressoir, Michael Emmi. 2016. Verifying constant-time implementations . USENIX’16. 7. Nikolaj Bjørner, Arie Gurfinkel, Ken McMillan, and Andrey Rybalchenko. 2015. Horn Clause Solvers for Program Verification. In Fields of Logic and Computation II. Lecture Notes in Computer Science, vol 9300. 8. Edward J. Schwartz, Thanassis Avgerinos, and David Brumley. 2010. All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask) . SP ’10. 9. A. Sabelfeld and A. C. Myers. 2003. Language-based information-flow security. IEEE J.Sel. A. Commun. 21, 1. and books: 1. Benjamin C. Pierce. 2002. Types and Programming Languages. 2. Aaron R. Bradley and Zohar Manna. 2007. The Calculus of Computation: Decision Procedures with Applications to Verification.

1 0

Sumegha Garg will present her General Exam on Monday, May 22, 2017 at 2pm in CS 302.
by Nicki Gotsis 15 May '17

15 May '17

Sumegha Garg will present her General Exam on Monday, May 22, 2017 at 2pm in CS 302. The members of her committee are: Mark Braverman (adviser), Ran Raz, and Kyle Jamieson. Everyone is invited to attend her talk and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------- Reading List 1. On the Capacity of Information Networks - Nicholas J. A. Harvey, Robert Kleinberg, April Rasala Lehman 2. Derandomized Squaring of Graphs - Eyal Rozenman, Salil Vadhan 3. Symbol-level Network Coding for Wireless Mesh Networks - Sachin Katti, Dina Katabi, Hari Balakrishnan, and Muriel Medard 4. Optimization-Based Linear Network Coding for General Connections of Continuous Flows - Ying Cui, Muriel M ́edard, Edmund Yeh, Douglas Leith, Ken Duffy 5. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning - Ran Raz 6. A Time-Space Lower Bound for a Large Class of Learning Problems - Ran Raz 7. Information Equals Amortized Communication - Mark Braverman, Anup Rao 8. Fast polynomial factorization and modular composition - Kiran S. Kedlaya, Christopher Umans 9. Query-to-Communication Lifting for BPP - Mika Goos, Toniann Pitassi, Thomas Watson 10. Deterministic Communication vs. Partition Number - Mika Goos, Toniann Pitassi, Thomas Watson (Query-lifting for deterministic case) ------------- Book Computational Complexity: A Modern Approach by Arora and Barak ------------- Abstract The area of network coding addresses the following basic problem: in a distributed communication scenario, can one use coding to outperform packet routing-based solutions? While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured that the answer is ‘no’. In this talk, I will present our result that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs that exhibits a (1 + ε) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G′ whose gap is log(|G′|)^c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G′|), which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G′|)^c from any initial gap. Joint work with Mark Braverman and Ariel Schvartzman

1 0

Talks from David Parkes and Sharon Goldberg Next Week
by Nick Feamster 12 May '17

12 May '17

All, David Parkes and Sharon Goldberg will be giving talks at CITP next Tuesday and Wednesday afternoons, respectively. Please find their talk abstracts below. -Nick ———————— Routing Around the Legal Restrictions on Internet Surveillance Date: Tuesday, May 16, 2017 Time: 4:30 p.m. Location: 101 Sherrerd Hall Internet surveillance for national-security purposes is largely regulated by two legal authorities. The Foreign Intelligence Surveillance Act (FISA) largely regulates surveillance on US territory, while Executive Order (EO) 12333 largely regulates surveillance abroad. Surveillance programs conducted under FISA are subject to legal restrictions imposed by Congress and the courts, while surveillance programs under EO 12333 are conducted solely under the authority of the President. The talk considers that possibility that the legal protections built into in FISA can be circumvented by exploiting the Internet’s routing protocols. Specifically, we consider the possibility that routing hijacks can be used to deliberately divert American traffic abroad, where it can be collected under EO 12333. We analyze the lawfulness of using routing hijacks to circumvent FISA, and discuss how several newly-developed secure routing protocols might (or might not) prevent these hijacks. We conclude with a policy recommendation: Congress should expand FISA to cover the surveillance of any and all Internet traffic collected abroad. ———————— Robust Methods to Elicit Informative Feedback Date: Tuesday, May 16, 2017 Time: 4:30 p.m. Location: 101 Sherrerd Hall Streaming Live: http://mediacentrallive.princeton.edu/ Hashtag: #citptalk Suppose we want to score contributions of information to a platform and thus promote effort amongst participants, but have no easy way to verify the quality of information. Responses may be subjective, or simply too costly to verify; e.g., what emotion do you feel watching video content, is a restaurant good for a family, what grade does a student deserve for an essay, should a paper be accepted to a conference, is a social media story real or fake? Peer prediction (Miller, Resnick and Zeckhauser 2005) seeks to promote effort by scoring contributions based on how predictive they are of contributions by others. But the challenge has been to score contributions without promoting unintended “group think” equilibria or coordinated misreports. In this talk, the correlated agreement mechanism will be described, which uses reports on multiple questions to provide a remarkably robust method of peer prediction. Its properties will be demonstrated on statistical models derived from reports on places in a city and peer-evaluation on a MOOC platform. Time permitting, it will also be explained how it can be coupled with methods from machine learning to handle the heterogeneity of participants. Joint work with Arpit Agarwal (U Penn), Rafael Frongillo (CU Boulder), Matthew Leifer (Harvard), Debmalya Mandal (Harvard), Galen Pickard (Google), Nisarg Shah (Harvard), and Victor Shnayder (Harvard).

1 0

Karan Singh will present his generals exam Monday, May 15, 2017 at 1pm in CS 401
by Nicki Gotsis 12 May '17

12 May '17

Karan Singh will present his generals exam Monday, May 15 , 2017 at 1pm in CS 401. The members of his committee are: Elad Hazan (Advisor), Sanjeev Arora, and Ran Raz Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Random Perturbations in Online Learning Adaptivity, Privacy, and Efficiency Explicit regularization (via adding a convex regularizer) is the mainstay of (distribution-free) statistically efficient learning algorithms. [Kalai, Vempala 2002] , also [Hannan 1957] , present an alternative framework (FTPL) for sequential prediction, based on randomly perturbing the history of losses on previous predictions. While these perturbation-based algorithms admit computationally efficient implementations, discounting some simple settings, their statistical efficiency is not well understood (vis-a-vis regularization). Building on some recent progress towards this understanding, we present three compelling cases for the use of perturbation methods for online learning that improve upon the state-of-the-art. The theme unifying the three applications is the utilization of structured noise for perturbations, an element hence so far not employed by the previous analyses. Adapting to the Inherent Structure For the problem of expert advice, when the loss vectors are restricted to some unknown d-dimensional subspace (fondly referred to as low-rank experts ), we demonstrate that a natural variant of FTPL achieves a regret of d^0.75√T , crucially independent of the number of experts. This improves on the previous best of d√T achieved by regularization-based schemes due to [Hazan, Koren, Livni, Mansour 2016] . Privacy for Free We design differentially private algorithms for the problem of online linear optimization in the full information and bandit settings with optimal √T regret bounds . In the full-information setting, our results demonstrate that differential privacy may be ensured for free -- in particular, the regret bounds scale as √T+1/ε . Notably, this phenomenon was unacknowledged even in the (weaker) setting of statistical learning. This separation of the extra (additive) regret suffered to ensure privacy from the non-private regret bound is permitted through a reinterpretation of privacy-aimed noise addition schemes as random perturbations of the objective. For bandit linear optimization, and as a special case, for non-stochastic multi-armed bandits, the proposed algorithm achieves a regret of √T/ε, while the previously best-known regret bound was T^0.75/ε. Efficient Algorithms for Contextual Learning We devise the first algorithm for transductive contextual learning that enjoys optimal √T regret guarantees while admitting computationally efficient implementations at run-time. In contrast, previous works either obtain sub-optimal regret bounds or require explicit enumeration of the policy class on every iteration. Contextual learning (with partial feedback) is a strict, far-reaching generalization of the Markov Decision Process model for policy-based reinforcement learning. Contextual learning offers the same sample complexity bounds without placing any assumption on the underlying state dynamics (for example, conditional Markovian evolution of states). The first and third results are due to collaborations with my advisor Elad Hazan (Princeton). The second result is joint work with Naman Agarwal (Princeton). Reading List Texts Bubeck, Cesa-Bianchi : Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Hazan : Introduction to Online Convex Optimization. Shalev-Shwartz : Online Learning and Online Convex Optimization. Szepesvári: Algorithms for Reinforcement Learning. Papers Contextual Learning Dudik, Hsu, Kale, Karampatziakis, Langford, Reyzin, Zhang : Efficient optimal learning for contextual bandits. UAI 2011 Kakade, Kalai: From batch to transductive online learning. NIPS 2005 Langford, Zhang : The epoch-greedy algorithm for multi-armed bandits with side information. NIPS 2008 Rakhlin, Sridharan : BISTRO: An efficient relaxation-based method for contextual bandits. ICML 2016 Syrgkanis, Krishnamurthy, Schapire : Efficient Algorithms for Adversarial Contextual Learning. ICML 2016 Imitation Learning Chang, Krishnamurthy, Agarwal, Daume, Langford : Learning to search better than your teacher. ICML 2015 Ross, Bagnell: Efficient Reductions for Imitation Learning. AISTATS 2010 Ross, Gordon, Bagnell : A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. AISTATS 2011 Learning with Partial Information Bubeck, Cesa-Bianchi, Kakade, Mannor, Srebro, Williamson : Towards Minimax Policies for Online Linear Optimization with Bandit Feedback. COLT 2012 Dani, Hayes, Kakade: The Price of Bandit Information for Online Optimization. NIPS 2007 Neu, Bartók : Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits. JMLR 2016 Differentially Private Online Learning Dwork, Naor, Pitassi, Rothblum : Differential privacy under continual observation. STOC 2010 Jain, Kothari, Thakurta : Differentially Private Online Learning. COLT 2012 Smith, Thakurta : (Nearly) optimal algorithms for private online learning in full-information and bandit settings. NIPS 2013 Perturbation Schemes in Statistics Abernethy, Lee, Sinha, Tewari : Online Linear Optimization via Smoothing. COLT 2014 Hazan, Jaakkola : On the Partition Function and Random Maximum A-Posteriori Perturbations. ICML 2012 No-Regret Algorithms in Structured Settings Garber, Hazan, Ma : Online Learning of Eigenvectors. ICML 2015 Hazan, Koren, Livni, Mansour: Online Learning with Low-Rank Experts. COLT 2016

1 1

EE Seminar - May 15, 2017, 11:00 am, E-Quad B205 - Prof. Veljko Milutinovic
by Nicole E. Wagenblast 12 May '17

12 May '17

Department of Electrical Engineering Seminar Speaker: Prof. Veljko Milutinovic University of Belgrade Title: DataFlow SuperComputing for BigData Date: Monday, May 15, 2017 Time: 11:00 am – 12 pm, Hands-on Tutorial 1 – 3 pm Room: E -Quad, Room B205 Host: Prof. Ruby Lee Abstract: This presentation analyses the essence of DataFlow SuperComputing, defines its advantages and sheds light on the related programming model. DataFlow computers, compared to ControlFlow computers, offer speedups of 20 to 200 (even 2000 for some applications), power reductions of about 20, and size reductions of also about 20. However, the programming paradigm is different, and has to be mastered. The talk explains the paradigm, using Maxeler as an example, and sheds light on the ongoing research in the field. Examples include: Trading and Finances, CreditDerivatives and numerous related BankingApplications, SignalProcessing, GeoPhysics, WeatherForecast, OilGas, DataEngineering, DataMining, SmartGrid, ScientificSimulations, BrainResearch, Genomics, etc. Also, a recent study from Tsinghua University in China is presented, which reveals that, for Shallow Water Weather Forecast (a BigData problem), on the 1U level, the Maxeler DataFlow machine is 14 times faster than the Tianhe machine, at the time of the study, rated #1 on the Top 500 list (based on Linpack, which is a smalldata benchmark). Given enough time, the talk also gives a tutorial about the programming in space, which is the programming paradigm used for the Maxeler dataflow machines (established in 2014 by Stanford, Imperial, Tsinghua, and the University of Tokyo). The talk concludes with selected examples and a tool overview ( appgallery.maxeler.com and webIDE.maxeler.com ). A more detailed tutorial on programming in space will be available after the talk, including the information on MaxGenFD. Related hands-on activities will be performed by remote login ( maxeler.mi.sanu.ac.rs ). Since December 2016, Maxeler is also available via Amazon AWS. In December 2016, Hitachi of Japan announced its partnership with Maxeler (also available via Amazon AWS), stating that, for their finance and cryptography applications, Maxeler was orders of magnitude faster than any other ControlFlow platform (i.e., CPU or GPU). Hands-on Tutorial : 1 – 3 pm in B205 Bio: Prof. Veljko Milutinovic (1951) received his PhD from the University of Belgrade, spent about a decade on various faculty positions in the USA (mostly at Purdue University), and was a co-designer of the DARPAs first GaAs RISC microprocessor. Later, for almost 3 decades, he taught and conducted research at the University of Belgrade, in EE, BA, MATH, and PHYS/CHEM. Now he serves as the Chairman of the Board for the Maxeler operation in Belgrade, Serbia. His research is mostly in datamining algorithms and dataflow computing, with the emphasis on mapping of data analytics algorithms onto fast energy efficient architectures. For 7 of his books, forewords were written by 7 different Nobel Laureates with whom he cooperated on his past industry sponsored projects. He has over 40 IEEE journal papers, over 40 papers in other SCI journals (4 in ACM journals), over 400 Thomson-Reuters citations, and about 4000 Google Scholar citations. Short courses on the subject he delivered so far in a number of universities worldwide: MIT, Harvard, Boston, NEU, Columbia, NYU, Princeton, Temple, Purdue, IU, UIUC, Michigan, EPFL, ETH, Karlsruhe, Heidelberg, etc. Also at the World Bank in Washington DC, BNL, IBM TJ Watson, ABB, Oracle, Yahoo, etc. Save

1 0

Muneeb Ali will present his FPO on Friday, May 19, 2017 at 1:30pm in CS 105.
by Nicki Gotsis 12 May '17

12 May '17

Muneeb Ali will present his FPO on Friday, May 19, 2017 at 1:30pm in CS 105. The members of his committee are: Andrea LaPaugh (adviser); Readers: Mike Freedman and Arvind Narayanan; Nonreaders: Jennifer Rexford and Brian Kernighan All are welcome to attend. The talk title and abstract follow below. Trust-to-Trust Design of a New Internet The internet’s original design, guided by the end-to-end design principle, pushed all application-specific logic and complexity to the edges of the network and kept the core of the network focused on the simple task of delivering data. The original end-to-end principle, however, did not explicitly account for trust and security. There are several central points of trust and failure on the traditional internet. These include root servers for the Domain Name System (DNS) and public-key infrastructure like Certificate Authorities (CAs) that publish security certificates. Further, the success of cloud hosted services in the last decade means that most user data is stored on remote servers and end-users need to trust these remote servers for correct execution of their applications. In this thesis, we present a new internet architecture that explicitly follows the trust-totrust design principle, i.e., end-users don’t need to trust the core of the network for anything, and end-users can use applications and services in a fully decentralized way. We make the observation that cryptocurrency blockchains, like Bitcoin, can be used to bootstrap trust for new nodes joining a network. We identify the various limitations, like high latency and limited bandwidth, of contemporary blockchains and discuss how our architecture can scale by moving most operations outside of the blockchain layer. We detail our experience of running a large production system on top of a cryptocurrency blockchain and how that experience guided our design. We present the implementation of a new decentralized internet, called Blockstack, that takes the trust-to-trust architecture from a theoretical concept to a production system. Deploying new systems by modifying production blockchains is hard because it requires coordination and agreement from several parties. We introduce virtualchains, a virtual blockchain constructed by processing data from underlying blockchains, to enable the seamless introduction of new functionality on top of blockchains without requiring any consensus-breaking changes. Blockstack is already powering several fully decentralized applications, like OpenBazaar; it’s released as open-source software and, to date, more than 70,000 domains have been registered on it.

1 0

Andrej Risteski will present his pre-FPO on Tuesday, May 16th, 2017 at 1pm in CS 302
by Nicki Gotsis 11 May '17

11 May '17

Andrej Risteski will present his pre-FPO on Tuesday, May 16th, 2017 at 1pm in CS 302. The members of his committee are: Readers: Sanjeev Arora (advisor), Rong Ge (Duke University), Elad Hazan Non-readers: Bernard Chazelle, Mark Braverman The talk title and abstract follow below. All are welcome to attend. Title : New techniques for learning and inference in probabilistic graphical models Abstract : A common theme in machine learning is succinct modeling of distributions over large domains. Probabilistic graphical models are one of the most expressive frameworks for doing this. The two major tasks involving graphical models are learning and inference. Learning is the task of calculating the best fit graphical model from raw data, while inference is the task of answering probabilistic queries for a known graphical model (for example what is the marginal distribution of one of the variables or what is the distribution of a subset of variables, after conditioning on the values of some other subset of variables). Learning can be thought of as finding a graphical model that “explains” the raw data, while the inference queries extract the “knowledge” the graphical model contains. This talk will concern new provable techniques for performing both of these tasks. I will focus on a few vignettes: in the context of inference, I will talk about a new understanding of a class of algorithms for calculating partition functions, called variational methods through a combination of convex programming hierarchies — a recent area of interest in the area of combinatorial optimization — and entropy approximations based on low-order moments of a distribution. In the context of learning, I will talk about alternating-minimization and method-of-moments techniques for learning noisy-or Bayesian networks and topic modeling. The former are used for modeling the causal structure of diseases and symptoms, and the later for modeling the latent structure of text.

1 0

Ohad Fried will present his FPO on Wednesday, May 17, 2017 at 1:30pm in CS 401.
by Nicki Gotsis 10 May '17

10 May '17

Ohad Fried will present his FPO on Wednesday, May 17, 2017 at 1:30pm in CS 401. The members of his committee are: Adam Finkelstein (adviser); readers: Tom Funkhouser and Eli Shechtman (Adobe); examiners: Szymon Rusinkiewicz and David Dobkin. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk title and abstract follow below: PHOTO MANIPULATION, THE EASY WAY The typical smartphone user has many thousands of photos in their personal collection. Photo acquisition is effortless, and the next challenge is in devising methods to easily edit such large collections. Specifically, we need manipulation algorithms that are powerful enough for experts, yet simple for novices to master. We identified three key directions to empower novice users with expert-level editing capabilities while maintaining an overall simplicity in the process. Those directions are (1) better selection masks, (2) high-level goal-centric algorithms and (3) domain specific algorithms. In this thesis we give examples from each category. Given a photo, a novice user will typically either not edit it at all, or apply a simple global operation such as exposure correction. In contrast, a professional photo editor might perform local edits, specifying a selection mask to limit the operation to specific photo regions, or combining regions from several photos into a single composition. To ease selection mask creation we present a new patch embedding technique that allows for single-click selection masks. Novices often think in terms of goals (e.g. improve lighting, de-clutter photo) and less in technical terms such as color spaces and image layers. One example of a high-level goal is the removal of distracting elements from photos. The task is motivated by the way professional photographers operate. They carefully frame the scene and might move objects around in order to stage the perfect photo. We define “photo distractors” as the elements that, if removed, would improve the photo. Using a simple slider interaction we allow users to automatically remove such distractors from photos. It is at times useful to tailor solutions to specific photo types. As an example we show that, specifically for human heads, simple controls can induce sophisticated edits. Given a single portrait photo as input, we can change the pose of the head and the camera distance. This allows users to correct the “selfie effect”, i.e. big noses and small ears or to transform distant photos into selfies. We conclude by discussing how each of these directions can be further explored to enable better image editing tools for novices.

1 0

Colloquium Speaker: Nima Anari, Tuesday, May 9th, 12:30pm
by Nicole E. Wagenblast 09 May '17

09 May '17

Colloquium Speaker Dr. Nima Anari, Stanford Univeristy Tuesday, May 9- 12:30pm Computer Science 105 Algorithm Design Using Polynomials In this talk I will present new methods for algorithm design and showcase results and breakthroughs obtained by looking through the lens of polynomials. I will start with the best known approximation algorithm for estimating the solution of the asymmetric traveling salesman problem, one of the oldest problems in computer science and optimization. Then, I will discuss a general framework based on computing inner products of polynomials that is used to design approximation algorithms for several important computational problems: volume maximization, counting matchings in bipartite graphs, Nash welfare maximization, and computing the permanent of positive semidefinite matrices. Nima Anari is a postdoctoral researcher at Stanford University working with Amin Saberi. His research interests are in the design and analysis of algorithms, with a recent focus on applications of polynomials in this endeavor. He recently completed his Ph.D. in computer science at UC Berkeley, where he was advised by Satish Rao and was part of the theory group. Prior to that he received his B.Sc. in computer engineering and mathematics from Sharif university of technology.

2 1

Alexander Beatson will present his general exam on Wednesday, May 10, 2017 at 3pm in CS 301.
by Nicki Gotsis 09 May '17

09 May '17

Alexander Beatson will present his general exam on Wednesday, May 10 , 2017 at 3pm in CS 301. The members of his committee are: Han Liu (ORFE, adviser), Elad Hazan, and Arvind Narayanan. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Title: Deep learning in some non-iid settings In real-world settings observed data may often be non-iid. There might be differences between the training and deployment distributions, which we can model in the worst case as perturbation by an adversary [1], or the training data may be drawn from different distributions at different times or at different locations, and we might wish to learn from the global distribution without storing or communicating the data [12]. I will discuss some work on attacks on machine learners and on non-iid distributed deep learning with communication constraints. Attacks on machine learners: One threat model for machine learning involves an adversary perturbing the training set. We show that even a “blind” adversary with no knowledge of the training data can harm learning (meaningfully lower-bound the learner’s effective sample size) via simple data injection strategies. Another threat model involves an adversary perturbing the examples observed in deployment. Linear and deep models are particularly vulnerable to such adversarial examples [2-4]. We show that deep generative models can be used to correctly classify adversarial examples or detect them as being far from the manifold of real data. Non-iid distributed deep learning: “Federated learning” [12] features communication constraints and data distributed non-iid across nodes. We propose an asynchronous algorithm for this setting which uses the Hessian of the likelihood at each node to weight model averaging and compute proximal constraints. This may be derived as an iterated natural proximal method or an application of the Laplace approximation [9]. Experiments show this converges faster than other asynchronous algorithms when data are non-iid across nodes. We may approximate the algorithm by sending only a small fraction of the variable updates from each node, sampled according to diagonal of that node’s Hessian. This maintains improved convergence in the non-iid setting, and in both iid and non-iid settings reduces the communication volume needed to reach a given accuracy. Reading List: Attacks on machine learners: Overview of the field: [1] Concrete problems in AI safety . Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, Dan Mané. Adversarial examples in deep learning: [2] Explaining and harnessing adversarial examples . Ian J. Goodfellow, Jonathon Shlens, Christian Szegedy. [3] Practical black-box attacks against deep learning systems using adversarial examples . Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, Ananthram Swami. [4] Towards Evaluating the Robustness of Neural Networks . Nicholas Carlini, David Wagner. Previously proposed defenses: [5] Biologically inspired protection of deep networks from adversarial attacks . Aran Nayebi, Surya Ganguli. [6] Parseval Networks: Improving Robustness to Adversarial Examples . Cisse Moustapha, Bojanowski Piotr, Grave Edouard, Dauphin Yann, Usunier Nicolas. Deep generative models: [7] Generative Adversarial Networks . Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, Yoshua Bengio. [8] Auto-Encoding Variational Bayes . Diederik P Kingma, Max Welling. Non-iid and distributed deep learning: The Laplace approximation: [9] A practical Bayesian framework for backpropogation networks . David J. C. MacKay. Using the Laplace approximation to estimating weight importances in deep learning: [10] Optimal Brain Damage . Yann LeCun, John S. Denker, Sara A. Solla. [11] Overcoming catastrophic forgetting in neural networks . James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, Raia Hadsell. Federated learning: [12] Communication-Efficient Learning of Deep Networks from Decentralized Data . H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, Blaise Agüera y Arcas. [13] Federated Learning: Strategies for Improving Communication Efficiency . Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, Dave Bacon. Textbook: [14] Deep Learning . Ian Goodfellow, Yoshua Bengio, Aaron Courville.

1 1