- talks - lists.cs.princeton.edu

Orestis Plevrakis will present his General Exam "A Theoretical Analysis of Contrastive Unsupervised Representation Learning" on May 13, 2019 at 2pm in CS 401
by Nicki Mahler 07 May '19

07 May '19

Orestis Plevrakis will present his General Exam "A Theoretical Analysis of Contrastive Unsupervised Representation Learning" on May 13, 2019 at 2pm in CS 401. The members of his committee are Sanjeev Arora (adviser), Elad Hazan, and Rob Schapire. 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. Abstract: Recent empirical works have successfully used unlabeled data to learn feature representations that are broadly useful in downstream classification tasks. Several of these methods are reminiscent of the well-known word2vec embedding algorithm: leveraging availability of pairs of semantically “similar” data points and “negative samples,” the learner forces the inner product of representations of similar pairs with each other to be higher on average than with negative samples. We use the term contrastive learning for such algorithms and we present a theoretical framework for analyzing them by introducing latent classes and hypothesizing that semantically similar points are sampled from the same latent class. This framework allows us to show provable guarantees on the performance of the learned representations on the average classification task that is comprised of a subset of the same set of latent classes. Our generalization bound also shows that learned representations can reduce the (labeled) sample complexity on downstream tasks. We conduct controlled experiments in both the text and image domains to support the theory. References: 1. Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. 2. Logeswaran, L. and Lee, H. An efficient framework for learning sentence representations. In Proceedings of the International Conference on Learning Representations , 2018. 3. Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. 2015. Rand-walk: A latent variable model approach to word embeddings. arXiv preprint arXiv:1502.03520 (2015). 4. Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. Distributed representations of words and phrases and their compositionality. In Neural Information Processing Systems , 2013. 5. Blum, A. and Mitchell, T. Combining labeled and unlabeled data with co-training. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory , COLT’ 98, 1998. 6. Kumar, A., Niculescu-Mizil, A., Kavukcoglu, K., and Daume ́, H. A binary classification framework for two-stage multiple kernel learning. In Proceedings of the 29th International Conference on Machine Learning , ICML’12, 2012. 7. Srebro, N. How Good is a Kernel When Used as a Similarity Measure. In COLT , 2007. 8. Brian Kulis. Metric learning: A survey. Foundations and Trends in Machine Learning , 5(4):287–364, 2012. 9. Gutmann, M. and Hyvarinen, A. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pp. 297–304, 2010. 10. Ma, Z. and Collins, M. (2018). Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency. arXiv preprint arXiv:1809.01812 .

1 0

Jiaxin Guan will present his General Exam "Simple Schemes in the Bounded Storage Model" on May 13, 2019 at 2pm in CS 402.
by Nicki Mahler 07 May '19

07 May '19

Jiaxin Guan will present his General Exam "Simple Schemes in the Bounded Storage Model" on May 13, 2019 at 2pm in CS 402. The members of his committee are Mark Zhandry (adviser), Arvind Narayanan, 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. Abstract: The bounded storage model promises unconditional security proofs against computationally unbounded adversaries, so long as the adversary’s space is bounded. In this work, we develop simple new constructions of two-party key agreement, bit commitment, and oblivious transfer in this model. In addition to simplicity, our constructions have several advantages over prior work, including an improved number of rounds and enhanced correctness. Our schemes are based on Raz’s lower bound for learning parities. Reading List: Textbook: Katz, Jonathan, and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2014. Papers (in alphabetic order): Badrinarayanan, Saikrishna, et al. "Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2016. Barak, Boaz, et al. "On the (im) possibility of obfuscating programs." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2001. De Santis, Alfredo, Giuseppe Persiano, and Moti Yung. "One-message statistical Zero-Knowledge Proofs and space-bounded verifier." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 1992. Ding, Yan Zong, et al. "Constant-round oblivious transfer in the bounded storage model." Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2004. Ding, Yan Zong. "Oblivious transfer in the bounded storage model." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2001. Goldreich, Oded, and Leonid A. Levin. "A hard-core predicate for all one-way functions." Proceedings of the twenty-first annual ACM symposium on Theory of computing. ACM, 1989. Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208. Kilian, Joe. "Founding crytpography on oblivious transfer." Proceedings of the twentieth annual ACM symposium on Theory of computing. ACM, 1988. Maurer, Ueli M. "Conditionally-perfect secrecy and a provably-secure randomized cipher." Journal of Cryptology 5.1 (1992): 53-66. Raz, Ran. "Fast learning requires good memory: A time-space lower bound for parity learning." Journal of the ACM (JACM) 66.1 (2018): 3.

1 0

Princeton Research Day, Thursday, May 9!
by Emily Lawrence 06 May '19

06 May '19

Princeton Research Day 2019 <http://www.cs.princeton.edu/events/25857> Time: 10 a.m. to 5 p.m. Date: Thursday, May 9, 2019 Location: Frist Campus Center Hashtag: #PRD19 Schedule of CS participants: http://www.cs.princeton.edu/events/25857 Facebook Event: https://www.facebook.com/events/245031396189128/ Come celebrate the research and creative endeavors of Princeton University students and early career researchers at the fourth annual Princeton Research Day on Thursday, May 9. Princeton Research Day highlights all types of discovery at the University, from laboratory research to the creation and interpretation of artistic work. Enjoy the more than 200 talks, posters, performances, art exhibitions, demonstrations and digital presentations on topics in the natural sciences, social sciences, engineering, humanities and the arts. Princeton Research Day is free and open to the public. No registration is required. Drop in for a few presentations, or stay the whole time. Each presentation is designed to be accessible to all. You'll have a great time and - we hope - learn a thing or two. Definitely stay for the highlight talks on the Mainstage beginning at 3 p.m. Check out the schedule and plan your day with the Guidebook app <https://guidebook.com/g/prd2019/> . Princeton Research Day is a collaborative initiative between the offices of the Dean of the College, the Dean of the Faculty, the Dean of the Graduate School and the Dean for Research, with support from the Office of the Provost.

1 0

Zhiyuan Li will present his General Exam "A trajectory analysis for gradient descent on over-paramterized neural nets" on May 16, 2019 at 2pm in CS 301.
by Nicki Mahler 03 May '19

03 May '19

Zhiyuan Li will present his General Exam " A trajectory analysis for gradient descent on over-paramterized neural nets " on May 16, 2019 at 2pm in CS 301. The members of his committee are as follows: Sanjeev Arora (adviser), Elad Hazan, and Ryan Adams 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. Abstract: Rademacher complexity measures the ability of a funciton class to fit random labels, and thus upper bounds the gap between training loss and testing loss. Traditional wisdom thinks that optimization over a function class with high rademacher complexity, such as a over-parametrized neurel net, will induce overfitting, and thus harm the generalization. However, recent works showed empirically that over-parametrization will not degenerate the test accuracy, and that the trajectory of the parameters by (stochastic) gradient descent seem to have much better properties than the whole parameter space, which motivates people to study the trajectory determined by the algorithm. In this talk, we will use trajectory analysis to show gradient descent over an over-parametrized two-layer net with relu activation has some kernel-like limiting behaviour. Informally, when the net is sufficiently wide, gd always converge to 0 training loss while the l2 distance moved by parameters from initialization remains bounded by some RKHS norm of the training labels, indepedent of width, and the trained network make the almost same predictions on unseen data to the kernel regression solution with the so-called Neural Tangent Kernel(NTK). We also prove a generalization bound for this over-parametrized 2 layer neural nets with relu activation which only relies on the l2 distance moved by the parameter. Thus we conclude that the generalization gap is bounded by the data-dependent RKHS norm, and this explains why adding noise to labels will suffer larger generalization gap while using the same network architecture. Our recent work also shows that this kernel-type limiting behavior holds for multilayer overparametrized neural net. This talk is based on a joint work with Sanjeev Arora(Princeton University & IAS), Simon S. Du(CMU), Wei Hu(Princeton University) and Ruosong Wang(CMU), “Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks”, and another joint work with Sanjeev Arora(Princeton University & IAS), Simon S. Du(CMU), Wei Hu(Princeton University), Ruslan Salakhutdinov(CMU) and Ruosong Wang(CMU), “On Exact Computation with an Infinitely Wide Neural Net”. References: 1. Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. 2. Jacot, Arthur, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems. 2018. 3. Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in neural information processing systems, pages 342–350, 2009. 4. Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019. 5. Christopher KI Williams. Computing with infinite networks. In Advances in neural information processing systems, pages 295–301, 1997. 6. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the International Conference on Learning Representations (ICLR), 2017, 2017. 7. Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 3:463–482, Nov 2002. 8. Neyshabur, Behnam, Srinadh Bhojanapalli, and Nathan Srebro. "A pac-bayesian approach to spectrally-normalized margin bounds for neural networks." arXiv preprint arXiv:1707.09564 (2017). 9. Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. arXiv Prepr. arXiv1409.1556, Sep 2014. 10. Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.03962, 2018b. 11. Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv:1804.11271, 2018.

1 0

James Bartusek will present his MSE thesis talk "Obfuscating Simple Functionalities" on Monday, May 6, 2019 at 2:30pm in CS 105
by Nicki Mahler 03 May '19

03 May '19

James Bartusek will present his MSE thesis talk "Obfuscating Simple Functionalities" on Monday, May 6, 2019 at 2:30pm in CS 105. The members of his committee are Mark Zhandry (adviser) and Zeev Dvir. Everyone is invited to attend his talk. His abstract follows below. Title: Obfuscating Simple Functionalities Abstract: Program obfuscation is the study of how to securely hide secrets within computer programs. An obfuscator is a compiler that takes as input a computer program P and scrambles it to produce a new program P' that maintains the functionality of P but hides as much as possible about how P is implemented. While constructing a secure and efficient obfuscator that works for any program P appears out of reach with current techniques, there has been a long line of research constructing secure and efficient obfuscators that work for certain simple classes of programs. In this thesis, we continue this line of research and improve on existing work in various ways. In one direction, we present novel obfuscation constructions that are simple, efficient, and secure under standard assumptions. We focus on obfuscating conjunction functions, and construct one obfuscator that is secure under the LPN (learning parity with noise) assumption and another that is secure information theoretically. In another direction, we consider additional security properties that may be useful in the context of obfuscation, such as encrypted inputs and non-malleability. In particular, we give a construction of obfuscation with encrypted inputs that can be compiled into a public-key function-private hidden vector encryption scheme, resolving an open problem of Boneh, Raghunathan, and Segev (Asiacrypt 2013). In addition, we give a standard model construction of point function obfuscation that is provably non-malleable under a large class of mauling functions.

1 2

Rob Harrison will present his FPO "Scalable, Network-wide Telemetry with Programmable Switches" on Tuesday, May 14, 2019 at 2pm in CS 402.
by Nicki Mahler 03 May '19

03 May '19

Rob Harrison will present his FPO "Scalable, Network-wide Telemetry with Programmable Switches" on Tuesday, May 14, 2019 at 2pm in CS 402. The members of his committee are as follows: Jennifer Rexford (adviser), Readers: Nick Feamster and Nate Foster (Cornell University); Nonreaders: David Walker and Kyle Jamieson A copy of his thesis, is available upon request. Everyone is invited to attend his/her talk. The talk title and abstract follow below: Managing modern networks requires collecting and analyzing network traffic from distributed switches in real time, i.e., performing network-wide telemetry. Telemetry systems must be flexible and fine-grained to support myriad queries about the security, performance, and reliability of networks. Yet, they must also scale as the number of queries, link speeds, and the size of the networks increase. Realizing these goals requires balancing the division of labor between high-speed, but resource constrained, network switches and general purpose CPUs to support flexible telemetry at scale. First, we present Sonata, a flexible and scalable network telemetry system that uses the compute resources of both stream-processing servers and a single Protocol Independent Switch Architecture (PISA) switch. PISA switches offer both high-speed processing and limited programmability. We show how to execute Sonata’s high-level queries at line rate by first compiling them to PISA primitives. Next, we model the resource constraints of PISA switches to solve an optimization problem that minimizes the load on the stream processor by executing portions of queries directly in the switch. Sonata can support a wide range of monitoring queries and reduces the stream processor’s workload by orders of magnitude over existing telemetry systems. Second, we present Herd, a system for implementing a subset of Sonata queries distributed across several switches. Herd determines network-wide heavy hitters, i.e., flows that consist of many more packets than most others, by counting flows at the switches, without maintaining per-flow state, and probabilistically reporting to a central coordinator. Based on these reports, the coordinator adapts parameters at each switch based on the spatial locality of the flows. Simulations using packet traces show that our prototype can detect network-wide heavy hitters accurately with 17% savings in communication overhead and 38% savings in switch state compared to existing approaches. We then present an algorithm to tune system parameters in order to maximize detection accuracy under switch memory and bandwidth constraints. Together, Sonata and Herd provide network operators the ability to execute a set of network-wide telemetry queries from a single interface that combines the strengths of both programmable data planes and general-purpose CPUs.

1 0

Fwd: EE Seminar - May 9, 2019, 10:00 am, E-Quad B327 - Ted K. Woodward, Ph.D. Facebook, Inc.
by Jennifer Rexford 03 May '19

03 May '19

> > From: "Lori A. Bailey" <lbailey(a)princeton.edu> > Subject: EE Seminar - May 9, 2019, 10:00 am, E-Quad B327 - Ted K. Woodward, Ph.D. Facebook, Inc. > Date: May 3, 2019 at 2:34:19 PM EDT > To: ee-seminar(a)princeton.edu > Reply-To: "Lori A. Bailey" <lbailey(a)princeton.edu> > > > > Department of Electrical Engineering > Seminar > > > > Speaker: Ted K. Woodward, Ph.D. > Facebook, Inc. > Title: Facebook Connectivity: challenges and progress in bringing more people to a faster Internet > Date: Thursday, May 9, 2019 > Time: 10:00 am > Room: E-Quad, Room B327 > Host: Prof. Kaushik Sengupta > > Abstract: The Facebook connectivity organization works to stimulate global broadband connectivity. I will summarize some of the many challenges associated with the task and describe some of the work the group is doing to make progress toward the goal. > > For more information visit: http://connectivity.fb.com/ <http://connectivity.fb.com/> > > Bio: Ted K. Woodward, Ph.D. manages the Connectivity Labs group at Facebook, a program-centric organization focused on early stage activity in support of the larger Facebook Connectivity organization. Before joining the Connectivity team at Facebook, from 2015 to 2018 Dr. Woodward was a Program Manager in the Strategic Technologies Office of the Defense Advanced Research Projects Agency (DARPA), where he led programs in Communications, Networking, and RF systems. Before that, he spent more than 25 years in diverse communication and networking research, development, and product companies including Telcordia Technologies and follow-on entities, Bell Laboratories Research, Ciena Corporation, and Internet Photonics, Inc., which he co-founded. >

1 0

EE Seminar - May 9, 2019, 10:00 am, E-Quad B327 - Ted K. Woodward, Ph.D. Facebook, Inc.
by Emily Lawrence 03 May '19

03 May '19

Department of Electrical Engineering Seminar Speaker: Ted K. Woodward, Ph.D., Facebook, Inc. Title: Facebook Connectivity: challenges and progress in bringing more people to a faster Internet Date: Thursday, May 9, 2019 Time: 10:00 am Room: E-Quad, Room B327 Host: Prof. Kaushik Sengupta Abstract: The Facebook connectivity organization works to stimulate global broadband connectivity. I will summarize some of the many challenges associated with the task and describe some of the work the group is doing to make progress toward the goal. For more information visit: http://connectivity.fb.com/ Bio: Ted K. Woodward, Ph.D. manages the Connectivity Labs group at Facebook, a program-centric organization focused on early stage activity in support of the larger Facebook Connectivity organization. Before joining the Connectivity team at Facebook, from 2015 to 2018 Dr. Woodward was a Program Manager in the Strategic Technologies Office of the Defense Advanced Research Projects Agency (DARPA), where he led programs in Communications, Networking, and RF systems. Before that, he spent more than 25 years in diverse communication and networking research, development, and product companies including Telcordia Technologies and follow-on entities, Bell Laboratories Research, Ciena Corporation, and Internet Photonics, Inc., which he co-founded.

1 0

LOCATION CHANGE-Michael Uhlar and Sathya Gunasekar today at 12:30 in CS 302
by Emily Lawrence 03 May '19

03 May '19

**Please note, the location of this talk has changed to room CS 302. Michael Uhlar and Sathya Gunasekar from Facebook Friday, May 3 at 12:30pm Computer Science - 302 https://www.cs.princeton.edu/events/25851 CacheLib - Unifying & Abstracting HW for caching @ Facebook In order to operate with high efficiency, Facebook’s infrastructure relies on caching in many different backend services. These services place very different demands on their caches, e.g., in terms of working set sizes, access patterns, and throughput requirements. Historically, each service used a different cache implementation, leading to inefficiency, duplicated code and effort. CacheLib is an embedded caching engine, which addresses this requirement with a unified API for building a cache implementation across many HW mediums. CacheLib transparently combines volatile and non-volatile storage in a single caching abstraction. To meet the varied demands, CacheLib successfully provides a flexible, high-performance solution for many different services at Facebook. In this talk, we describe CacheLib’s design, challenges, and several lessons learned.

1 0

Farhan Damani will present his General Exam "Inferring cognitive learning rules from behavior with probabilistic models" on Thursday, May 9, 2019 at 1pm in CS 401.
by Nicki Mahler 03 May '19

03 May '19

Farhan Damani will present his General Exam " Inferring cognitive learning rules from behavior with probabilistic models" on Thursday, May 9, 2019 at 1pm in CS 401. The members of his committee are as follows: Ryan Adams (adviser), Jonathan Pillow, and Tom Griffiths 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: Inferring cognitive learning rules from behavior with probabilistic models Abstract: High-throughput behavioral neuroscience presents an exciting opportunity to investigate the dynamics of learning during decision making. We describe a probabilistic model that captures a learner's underlying time-dependent decision making strategy while learning a forced choice discrimination task. Through priors that explicitly characterize how learner's update their knowledge state, our approach presents the opportunity to infer an evolving decision-making strategy despite observing only a single sequence of decisions. Importantly, our model is probabilistic, which means we can reason about a learner's competence, learning rate, and preference for simpler models using the marginal likelihood. We apply our method to large-scale behavioral datasets and discover personalized learning rules explaining vast differences in the learning dynamics across learners while also finding shared explanations for simpler models and skill-specific learning rates. Reading list: Textbook: Koller, D., Friedman, N., & Bach, F. (2009). Probabilistic graphical models: principles and techniques . MIT press 1. Hoffman, M. D., Blei, D. M., Wang, C., & Paisley, J. (2013). Stochastic variational inference. The Journal of Machine Learning Research , 14 (1), 1303-1347. 2. Kucukelbir, A., Tran, D., Ranganath, R., Gelman, A., & Blei, D. M. (2017). Automatic differentiation variational inference. The Journal of Machine Learning Research , 18 (1), 430-474. 3. Kingma, D. P., & Welling, M. (2013). Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 . 4. Archer, E., Park, I. M., Buesing, L., Cunningham, J., & Paninski, L. (2015). Black box variational inference for state space models. arXiv preprint arXiv:1511.07367 . 5. Johnson, M., Duvenaud, D. K., Wiltschko, A., Adams, R. P., & Datta, S. R. (2016). Composing graphical models with neural networks for structured representations and fast inference. In Advances in neural information processing systems (pp. 2946-2954). 6. Krishnan, R. G., Shalit, U., & Sontag, D. (2017, February). Structured inference networks for nonlinear state space models. In Thirty-First AAAI Conference on Artificial Intelligence 7. Smith, A. C., Frank, L. M., Wirth, S., Yanike, M., Hu, D., Kubota, Y., ... & Brown, E. N. (2004). Dynamic analysis of learning in behavioral experiments. Journal of Neuroscience , 24 (2), 447-461. 8. Bak, J. H., Choi, J. Y., Akrami, A., Witten, I., & Pillow, J. W. (2016). Adaptive optimal training of animal behavior. In Advances in neural information processing systems (pp. 1947-1955) 9. Paninski, L., Ahmadian, Y., Ferreira, D. G., Koyama, S., Rad, K. R., Vidne, M., ... & Wu, W. (2010). A new look at state-space models for neural data. Journal of computational neuroscience , 29 (1-2), 107-126. 10. Prerau, M. J., Smith, A. C., Eden, U. T., Kubota, Y., Yanike, M., Suzuki, W., ... & Brown, E. N. (2009). Characterizing learning by simultaneous analysis of continuous and binary measures of performance. Journal of neurophysiology , 102 (5), 3060-3072.

1 0