- talks - lists.cs.princeton.edu

Colloquium Speaker: Manfred K. Warmuth, Monday May 22- 12:30pm
by Nicole E. Wagenblast 18 May '17

18 May '17

Colloquium Speaker Manfred K Warmuth, University of California, Santa Cruz Monday, May 22, 12:30pm Computer Science 105 The blessing and the curse of the multiplicative updates - discusses connections between in evolution and the multiplicative updates of online learning Multiplicative updates multiply the parameters by nonnegative factors. These updates are motivated by a Maximum Entropy Principle and they are prevalent in evolutionary processes where the parameters are for example concentrations of species and the factors are survival rates. The simplest such update is Bayes rule and we give an in vitro selection algorithm for RNA strands that implements this rule in the test tube where each RNA strand represents a different model. In one liter of the RNA soup there are approximately 10^15 different strands and therefore this is a rather high-dimensional implementation of Bayes rule. We investigate multiplicative updates for the purpose of learning online while processing a stream of examples. The ``blessing'' of these updates is that they learn very fast in the short term because the good parameters grow exponentially. However their ``curse'' is that they learn too fast and wipe out parameters too quickly. This can have a negative effect in the long term. We describe a number of methods developed in the realm of online learning that ameliorate the curse of the multiplicative updates. The methods make the algorithm robust against data that changes over time and prevent the currently good parameters from taking over. We also discuss how the curse is circumvented by nature. Surprisingly, some of nature's methods parallel the ones developed in Machine Learning, but nature also has some additional tricks. This will be a high level talk. No background in online learning will be required. We will give a number of open problems and discuss how these updates are applied for training feed forward neural nets.

1 0

Cyril Zhang will present his generals exam Thursday, May 25, 2017 at 3pm in CS 402
by Nicki Gotsis 18 May '17

18 May '17

Cyril Zhang will present his generals exam Thursday, May 25, 2017 at 3pm in CS 402 The members of his committee are: Elad Hazan (adviser), Sanjeev Arora, and Matt Weinberg 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. Topic: Two Views of Non-Convex Regret Minimization Abstract: I will discuss the problem of efficient online regret minimization with non-convex loss functions. Two distinct (yet pleasingly nebulously connected) approaches are considered; both results are j oint work with Karan Singh and Prof. Elad Hazan. In the first part of my talk, I will present a new framework for general online non-convex optimization (ONCO). I will introduce the desiderata of such a framework, showing how we must avert issues of computational intractability by defining a suitable notion of regret. I will introduce our time-smoothed regret measure, and justify it with tight upper and lower bounds, along with reductions to the full-information and stochastic offline cases. Finally, I will show some extensions and applications. Primarily, our framework gives rise to a new solution concept in repeated games; I will discuss some natural settings in which our algorithms are practical and give provable guarantees for learning in games. In the second part, I will present a second approach, in which one leverages the structure of an ONCO problem to make it amenable to the tools of online convex optimization (OCO). We consider the non-convex problem of maximum-likelihood online prediction of linear dynamical systems (LDS). Relying upon the spectral theory of Hankel matrices, we formulate an approximate convex relaxation to this problem. This results in a black-box reduction to OCO, from which we derive a simple, practical method for predicting sequences arising from an LDS. Books: - Introduction to Online Convex Optimization. Elad Hazan. - Understanding Machine Learning. Shai Shalev-Shwartz and Shai Ben-David. Papers: - Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. Saeed Ghadimi and Guanghui Lan. - Cubic regularization of Newton method and its global performance. Yurii Nesterov and B.T. Polyak. - The Multiplicative Weights Update Method: A Meta-Algorithm and Applications. Sanjeev Arora, Elad Hazan, Satyen Kale. - Online Convex Programming and Generalized Infinitesimal Gradient Ascent. Martin Zinkevich. - Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. John Duchi, Elad Hazan, and Yoram Singer. - Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. Rie Johnson and Tong Zhang. - Efficient algorithms for online decision problems. Adam Kalai and Santosh Vempala. - Online Linear Optimization via Smoothing. Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. - Matrix Completion has No Spurious Local Minimum. Rong Ge, Jason D. Lee, and Tengyu Ma. - Gradient Descent Learns Linear Dynamical Systems. Moritz Hardt, Tengyu Ma, and Benjamin Recht.

1 0

Ariel Schvartzman Cohenca will present his generals exam Thursday, May 25, 2017 at 1pm in CS 401.
by Nicki Gotsis 18 May '17

18 May '17

Ariel Schvartzman Cohenca will present his generals exam Thursday, May 25, 2017 at 1pm in CS 401. The members of his committee are: Matt Weinberg (adviser), Gillat Kol, and Zeev Dvir. 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. While Nash equilibria are arguably the most studied notion of equilibrium in strategic games, recent results regarding their communication and computational complexity have undermined their prevalence as a predictable solution concept when agents are computationally bounded. In particular, results show that two players cannot converge to any approximate Nash equilibria in the limited communication setting where each player only knows its utility function. For the case of 2-player games, it has been recently shown that even computing approximate Nash equilibria requires poly(n) bits of communication[BR16]. In addition even in the setting where all the payoffs matrices are known Nash equilibria seem to be unnatural due to their computational hardness. Computing any exact Nash equilibrium is known to be PPAD-complete, making it unlikely to have any polynomial time algorithm [CDT09, Daskalakis2009]. Furthermore, it has been shown that under the Exponential Time Hypothesis (ETH) for the class PPAD, eps-approximate Nash equilibria cannot be computed in time faster than quasi-polynomial in the number of strategies per player[Rubinstein16a]. This almost exactly matches the algorithm of [LMM03]. These results suggest that approximate Nash equilibria may not be efficiently computable. Correlated equilibria arise as an alternative equilibrium concept. This notion, introduced in the seminal work of [Aumann74], allows agents to cooperate in order to reach stability. Informally, a strategy profile is a correlated equilibrium when a referee or trusted party can draw strategy samples according to it and recommend them to the players in such a way that they have no incentive to consistently deviate, assuming everyone else plays according to their recommendation. Computationally, correlated equilibria are in sharp contrast to Nash equilibria: there exists an ellipsoid-based algorithm to compute exact correlated equilibrium polynomial time even for multi-player games for a large (but not universal) class of games including graphical games, anonymous games, congestion games and scheduling games[PR2008]. Unfortunately this result is still unsettling: one can imagine many settings where a referee may not have access to all utility functions or where players may not want to share such information with a referee. With this in consideration it becomes more natural to ask whether there is an efficient communication protocol for computing approximate correlated equilibria better than the naive one where each player sends their payoff matrix to a referee who computes the answer. Given recent developments, this is the next fundamental problem between communication complexity and algorithmic game theory that needs to be addressed, both in terms of communication and query complexity. In this work we address the question posed by [BR16] of providing lower bounds for the communication complexity of approximate correlated equilibrium in 2-player games. The arguments used on the lower bound proof rely on tools from information theory, which lower bounds communication cost. While this talk focuses on a single result, my research interests lie in understanding the complexity of approximate solution concepts. There are different lenses through which we analyze problems when studying equilibria: computation, communication, query (amongst others). Other similar projects I have worked on involve bounds for the menu complexity of optimal and approximate mechanism design and understanding the efficiency loss of ‘simple auctions’ when compared to their optimal counterparts in specific settings. Joint work with Young Kun Ko. Reading list: - Algorithmic Game Theory. E. Tardos, T. Roughgarden, V. Vazirani, N. Nisan. 2007. - 20 Lectures in Algorithmic Game Theory. T. Roughgarden. 2016. Papers: - Settling the complexity of computing approximate two-player Nash equilibria. A. Rubinstein. 2016. - Inapproximability of Nash Equilibrium. A. Rubinstein. 2015. - Adaptive procedure, correlated equilibrium, no regret, regret-matching, simple strategies. S. Hart, A. Mas-Collel. 2000. - Communication complexity of approximate Nash equilibria. Y. Babichenko, A. Rubinstein. 2016. - Playing Large Games Using Simple Strategies. R. Lipton, E. Markakis, A. Mehta. 2003 - How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. S. Hart, Y. Mansour. 2010. - The communication complexity of uncoupled nash equilibrium procedures. S. Hart, Y. Mansour. 2007. - The complexity of computing a Nash equilibrium. C. Daskalakis, A. Goldberg, C. Papadimitriou. 2008. - Settling the Complexity of Computing Two-player Nash Equilibria. X. Chen, X. Deng, S. Teng. 2009. - Computing Equilibria: A Computational Complexity Perspective. T. Roughgarden. 2010. - Communication Complexity (for Algorithm Designers), Chapter 7: Lower Bounds in Algorithmic Game Theory. 2016. - Communication Complexity as a Lower Bound for Learning in Games. V. Connitzer, T. Sandholm. 2004.

1 0

Sotirios Apostolakis will present his general exam on Wednesday, May 24, 2017 at 3pm in CS 401.
by Nicki Gotsis 17 May '17

17 May '17

Sotirios Apostolakis will present his general exam on Wednesday, May 24, 2017 at 3pm in CS 401. The members of his committee are: David August (adviser), Nick Feamster, and Andrew Appel. 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. Enabling Practical Full System Containment Abstract: Acknowledging that modern computing systems are too complex to be vulnerability free, we advocate for a single, simple component that would quarantine the ill effects of compromised system components. Work on a system called TrustGuard has shown that it is feasible for a simple and pluggable hardware element, called the Sentry, to offer containment of untrusted hardware, by ensuring that the system only outputs results of correct execution of signed programs. TrustGuard’s original focus was to protect against hardware vulnerabilities and signed programs needed to be entirely trusted. This work extends TrustGuard’s checking scheme with a new programming model. This new model exposes the Sentry to programmers by allowing them to reduce the amount of code that is trusted and checked by the Sentry. We implemented a library for runtime integrity checking of key-value database operations to demonstrate the practicality of the enhanced checking scheme and exemplify how Sentry produces trusted output using untrusted applications, OS and hardware. Reading list: Books: * Andrew W. Appel, Modern Compiler Implementation in ML. Cambridge University Press, 1998 * Ross J. Anderson. 2008. Security Engineering: A Guide to Building Dependable Distributed Systems (2 ed.). Wiley Publishing. (Chapters 3,4,5,11,16) * John L. Hennessy and David A. Patterson. 2011. Computer Architecture, Fifth Edition: A Quantitative Approach (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA Papers: * Riad S. Wahby, Max Howald, Siddharth J. Garg, Abhi Shelat, and Michael Walfish. Verifiable ASICs. In IEEE S&P 2016. * Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish. 2013. Verifying computations with state. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). * G.E. Suh, D Clarke, B. Gassend, M. van Dijk, S. Devadas. AEGIS: architecture for tamper-evident and tamper-resistant processing. In Proceedings of the 17th annual international conference on Supercomputing, ICS’03 * T. M. Austin, "DIVA: a reliable substrate for deep submicron microarchitecture design," Microarchitecture, 1999. MICRO-32. Proceedings. 32nd Annual International Symposium on, Haifa, 1999 * A. Miller, M. Hicks, J. Katz, and E. Shi. Authenticated data structures, generically. In POPL 2014. * Goodrich, Michael T., Roberto Tamassia, and Andrew Schwerin. "Implementation of an authenticated dictionary with skip lists and commutative hashing." DISCEX'01, 2001. * Premkumar T. Devanbu, Michael Gertz, Charles U. Martel, and Stuart G. Stubblebine. Authentic third-party data publication. In DBSec, volume 201 of IFIP Conference Proceedings, 2000. * B. Rogers, S. Chhabra, M. Prvulovic and Y. Solihin, "Using Address Independent Seed Encryption and Bonsai Merkle Trees to Make Secure Processors OS- and Performance-Friendly”, MICRO 2007.

1 0

Reid Oda will present his FPO, "Tools and Techniques for Rhythmic Synchronization in Networked Musical Performance" on Tuesday, May 23, 2017 at 12:00 PM in CS 302.
by Nicki Gotsis 17 May '17

17 May '17

Reid Oda will present his FPO, "Tools and Techniques for Rhythmic Synchronization in Networked Musical Performance" on Tuesday, May 23, 2017 at 12:00 PM in CS 302. The members of his committee are: Readers: Rebecca Fiebrink (adviser), Adam Finkelstein (adviser), and Daniel Trueman (Music); Nonreaders: Marshini Chetty, Rebecca Fiebrink, and Chris Chafe (Stanford) A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. Abstract is attached to this email.

1 0

Fermi Ma will present his generals exam Friday, May 26, 2017 at 10am in CS 302.
by Nicki Gotsis 17 May '17

17 May '17

Fermi Ma will present his generals exam Friday, May 26, 2017 at 10am in CS 302. The members of his committee are: Mark Zhandry (adviser) Zeev Dvir, and Ed Felten 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. We define the concept of an encryptor combiner. Roughly, such a combiner takes as input n public keys for a public key encryption scheme, and produces a new combined public key. Anyone knowing a secret key for one of the input public keys can learn the secret key for the combined public key, but an outsider who just knows the input public keys (who can therefore compute the combined public key for himself) cannot decrypt ciphertexts from the combined public key. We actually think of public keys more generally as encryption procedures, which can correspond to, say, encrypting to a particular identity under an IBE scheme or encrypting to a set of attributes under an ABE scheme. We show that encryptor combiners satisfying certain natural properties can give natural constructions of multi-party non-interactive key exchange, low-overhead broadcast encryption, and hierarchical identity-based encryption. We then show how to construct two different encryptor combiners. Our first is built from universal samplers (which can in turn be built from indistinguishability obfuscation) and is sufficient for each application above, in some cases improving on existing obfuscation-based constructions. Our second is built from lattices, and is sufficient for hierarchical identity-based encryption. Thus, encryptor combiners serve as a new abstraction that (1) is a useful tool for designing cryptosystems, (2) unifies constructing hierarchical IBE from vastly different assumptions, and (3) provides a target for instantiating obfuscation applications from better tools. The sub-area of cryptography that my research / reading list focuses on is obfuscation. The reading list is as follows: On the (Im)possibility of Obfuscating Programs (2010) Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation (2013) Dan Boneh and Mark Zhandry https://eprint.iacr.org/2013/642.pdf Candidate Multilinear Maps from Ideal Lattices (2012) Sanjam Garg, Craig Gentry, and Shai Halevi https://eprint.iacr.org/2012/610.pdf Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits (2013) Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters https://eprint.iacr.org/2013/451.pdf Practical Multilinear Maps over the Integers (2013) Jean-Sebastien Coron, Tancrede Lepoint, and Mehdi Tibouchi https://eprint.iacr.org/2013/183.pdf Cryptanalysis of the Multilinear Map over the Integers (2014) Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehle https://eprint.iacr.org/2014/906.pdf Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13 (2016) Eric Miles, Amit Sahai, and Mark Zhandry https://eprint.iacr.org/2016/147.pdf Secure Obfuscation in a Weak Multilinear Map Model: A Simple Construction Secure Against All Known Attacks (2016) Eric Miles, Amit Sahai, and Mark Zhandry https://eprint.iacr.org/2016/588.pdf and the textbook "Introduction to Modern Cryptography: Principles and Protocols" by Katz and Lindell.

1 0

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