- talks - lists.cs.princeton.edu

Haipeng Luo will present his FPO, "Optimal and Adaptive Online Learning" on Monday, 5/16/2016 at 2pm in CS 302.
by Nicki Gotsis 09 May '16

09 May '16

Haipeng Luo will present his FPO, "Optimal and Adaptive Online Learning" on Monday, 5/16/2016 at 2pm in CS 302. The members of his committee are Robert Schapire (adviser), readers: Elad Hazan and Satyen Kale (Yahoo); nonreaders: Sanjeev Arora and Barbara Engelhardt. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below. Online learning is one of the most important and well-established machine learning models. Generally speaking, the goal of online learning is to make a sequence of accurate predictions “on the fly,” given some information of the correct answers to previous prediction tasks. Online learning has been extensively studied in recent years, and has also become of great interest to practitioners due to its e↵ectiveness in dealing with non-stationary data as well as its applicability to large-scale applications. While many useful ideas are well-established in the o✏ine learning setting where a set of data is available beforehand, their counterparts in the online setting are not always straightforward and require more understanding. Moreover, existing online learning algorithms are not always directly applicable in practice. One important reason is that they usually rely on sophisticated tuning of parameters, a delicate approach that can yield sound theoretical guarantees, but that does not work well in practice. Another reason is that existing algorithms are usually guaranteed to work well in one particular situation or another, but not all. A single algorithm that can ensure worst-case robustness while still enjoying the ability to exploit easier data at the same time is relatively rare and certainly desirable in practice. Motivated by all the above issues, this thesis focuses on designing more practical, adaptive and ready-to-use online learning algorithms, including • novel online algorithms which combine expert advice in an optimal and parameter-free way and work simultaneously under di↵erent patterns of data as well as di↵erent evaluation criteria; • a novel and rigorous theory of online boosting which studies improving the accuracy of any existing online learning algorithm by training and combining several copies of it in a carefully designed manner; iii • a family of highly e#cient online learning algorithms which make use of second order information of the data and enjoy good performance even when dealing with ill-conditioned data. In summary, this thesis develops and analyzes several novel, optimal and adaptive online learning algorithms which greatly improve upon previous work and have great practical potential.

1 0

Matvey Arye will present his FPO, " Data Processing Across Continents" on Tuesday, 5/17/2016 at 10:00am in CS 402.
by Nicki Gotsis 09 May '16

09 May '16

Matvey Arye will present his FPO, " Data Processing Across Continents" on Tuesday, 5/17/2016 at 10:00am in CS 402. The members of his committee are Michael Freedman (adviser), readers: Andrea LaPaugh and Kai Li; nonreaders: Jennifer Rexford and Nick Feamster. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below. An increasing number of data sources create data across the globe. These include everything from server logs owned by Internet-scale companies to military intelligence systems. This thesis addresses the question of how to enable near-real-time analytical queries on such data. Existing systems tend to centralize such data into a single datacenter before analyzing it. However, in light of low and asymmetric bandwidth provisioning in and between certain geographic regions, centralizing all data can be both slow and costly. This thesis have addressed this problem with three complementary research directions. First, we describe a system that queries the data in a distributed manner and centralizes only the data that is needed to fulfill the query. Our system incorporates edge storage and customizable degradation operators in its programming model. These elements allow the system to adjust the data-volumes transferred to match available bandwidth. Second, we explore some challenges due to the interaction between an application level dynamic quality adaptation control loop and TCP (which has its own control loop). These two control loops can create negative feedback e↵ects which reduces system throughput below what the network can sustain. These insights are translated into the domain of Internet video streaming and several solutions are proposed. Our solutions enable video flows to achieve above 90% of its fair-share of throughput, while industry players often achieve less than 50% of their fair-share. Finally, we present a case study of how to optimize queries for wide-area analysis. We optimize the top-k query, which addresses questions of popularity and is thus ubiquitous in modern computer systems. Our algorithms reduce both the bandwidth usage and number of rounds used by such queries. In particular, we propose the first exact two-round top-k algorithm (which still transfers 19% less bytes than the best previously-known exact 3-round algorithm). Our 2-or-3-round exact algorithm transfers 31% less bytes than the best previously-known approximate algorithm. Finally, our approximate algorithm uses 40% less bandwidth than previous algorithms with stronger guarantees.

1 0

Brian Bullins will present his general exam Monday, May 16, 2016 at 4pm in CS 402.
by Nicki Gotsis 09 May '16

09 May '16

Brian Bullins will present his general exam Monday, May 16, 2016 at 4pm in CS 402. The members of his committee are Elad Hazan (adviser), Sanjeev Arora, and Barbara Engelhardt. 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: Linear regression is a common learning technique for determining the linear relationship between multiple variables and how they may affect a certain outcome. A standard example is that of medical diagnosis, whereby the data gathered for a given patient provides information about their susceptibility to certain illnesses. A major drawback to this process is the work necessary to collect the data, as it requires running numerous tests for each person. In such cases it may be necessary to impose limitations on the amount of data available for each example. For medical diagnosis, this might mean having each patient only undergo a subset of tests. In this talk I will discuss the problem of regression where the learner is allowed to observe only a limited number of attributes per example, known as the limited attribute observation model. In particular, we provide the first lower bounds giving a limit on the precision attainable by any algorithm for several variants of regression, notably regression with absolute loss and squared loss, as well as for classification with hinge loss. We complement this with a general purpose algorithm which achieves an upper bound in terms of the precision limit. This is joint work with Elad Hazan and Tomer Koren. Reading List: Books: Introduction to Online Convex Optimization. Elad Hazan Understanding Machine Learning: From Theory to Algorithms. Shai Shalev-Shwartz and Shai Ben-David Papers: Linear Regression with Limited Observation. E. Hazan and T. Koren Classification with Low Rank and Missing Data. E. Hazan, R. Livni, and Y. Mansour Convergence rates of sub-sampled Newton methods. M. Erdogdu and A. Montanari Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. R. Johnson and T. Zhang Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. J. Duchi, E. Hazan, and Y. Singer Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. J. Abernethy, E. Hazan, and A. Rakhlin Cubic regularization of Newton method and its global performance. Y. Nesterov and B.T. Polyak Deep learning via Hessian-free optimization. J. Martens Escaping from Saddle Points — Online Stochastic Gradient Descent for Tensor Decomposition. R. Ge, F. Huang, C. Jin, and Y. Yuan Online Learning of Eigenvectors. D. Garber, E. Hazan, and T. Ma On the saddle point problem for non-convex optimization. R. Pascanu, Y. Dauphin, S. Ganguli, and Y. Bengio

1 0

Sachin Ravi will present his general exam on Monday, May 16, 2016 at 10am in CS 302
by Nicki Gotsis 09 May '16

09 May '16

Sachin Ravi will present his general exam on Monday, May 16, 2016 at 10am in CS 302. The members of his committee are Kai Li (adviser), Sebastian Seung, and Tom Funkhouser. 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: Automated synapse detection in EM images Abstract The field of Connectomics involves mapping the network structure of neural circuits. Currently, the most promising way to obtain such maps is by automated reconstruction of neural circuits by analyzing 3D electron microscopic (EM) brain images. An important task in this reconstruction is the localization of synapses, the mechanism through which neurons pass electrical or chemical signals to each other. In addition to localization, it is important to know the source and destination of the signal (or polarity of the synapse) in order to derive the true connectivity of the network. In this work, we present an automated method to detect synapses using convolutional networks and evaluate the method on a mouse cortex dataset. Additionally, we discuss a method to achieve equivariance in convolutional networks to a finite group of rotations and reflections. Encoding equivariance in the network makes more efficient use of parameters and could potentially benefit synapse detection and polarity prediction because of the rotational invariance present in EM images. Reading List [1] Yann A LeCun, L´eon Bottou, Genevieve B Orr, and Klaus-Robert M¨uller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9–48. Springer, 2012 [2] Le Cun, B.B., Denker, J.S., Henderson, D., Howard, R.E., Hubbard, W. and Jackel, L.D., 1990. Handwritten digit recognition with a back-propagation network. In Advances in neural information processing systems. [3] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, page 2012 [4] Kisuk Lee, Aleksandar Zlateski, Ashwin Vishwanathan, and H. Sebastian Seung. Recursive training of 2d-3d convolutional networks for neuronal boundary detection. CoRR, abs/1508.04843, 2015 [5] Dan C Cire¸san, Alessandro Giusti, Luca M Gambardella, and J¨urgen Schmidhuber. Mitosis detection in breast cancer histology images with deep neural networks. In Medical Image Computing and Computer-Assisted Intervention–MICCAI 2013, pages 411–418. Springer, 2013 [6] C. J. Becker, K. Ali, G. Knott and P. Fua. Learning Context Cues for Synapse Segmentation, in IEEE Transactions on Medical Imaging, vol. 32, num. 10, p. 1864--1877, 2013 [7] Cohen, T.S. and Welling, M., 2016. Group Equivariant Convolutional Networks. arXiv preprint arXiv:1602.07576. [8] Dieleman, Sander, Jeffrey De Fauw, and Koray Kavukcuoglu. Exploiting Cyclic Symmetry in Convolutional Neural Networks. arXiv preprint arXiv:1602.02660 (2016). [9] Osadchy, M., Cun, Y.L. and Miller, M.L., 2007. Synergistic face detection and pose estimation with energy-based models. The Journal of Machine Learning Research, 8, pp.1197-1215. [10] Jaderberg, M., Simonyan, K. and Zisserman, A., 2015. Spatial transformer networks. In Advances in Neural Information Processing Systems (pp. 2008-2016). Vancouver [11] Yoshua Bengio Ian Goodfellow and Aaron Courville. Deep learning. Book in preparation for MIT Press, 2016. [12] Bishop, Christopher M. Pattern Recognition. Machine Learning (2006).

1 0

Brian Bullins will present his general exam Monday, May 16, 2016 at 4pm in CS 402.
by Nicki Gotsis 09 May '16

09 May '16

Brian Bullins will present his general exam Monday, May 16, 2016 at 4pm in CS 402. The members of his committee are Elad Hazan (adviser), Sanjeev Arora, and Barbara Engelhardt. 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: Linear regression is a common learning technique for determining the linear relationship between multiple variables and how they may affect a certain outcome. A standard example is that of medical diagnosis, whereby the data gathered for a given patient provides information about their susceptibility to certain illnesses. A major drawback to this process is the work necessary to collect the data, as it requires running numerous tests for each person. In such cases it may be necessary to impose limitations on the amount of data available for each example. For medical diagnosis, this might mean having each patient only undergo a subset of tests. In this talk I will discuss the problem of regression where the learner is allowed to observe only a limited number of attributes per example, known as the limited attribute observation model. In particular, we provide the first lower bounds giving a limit on the precision attainable by any algorithm for several variants of regression, notably regression with absolute loss and squared loss, as well as for classification with hinge loss. We complement this with a general purpose algorithm which achieves an upper bound in terms of the precision limit. This is joint work with Elad Hazan and Tomer Koren. Reading List: Books: Introduction to Online Convex Optimization. Elad Hazan Understanding Machine Learning: From Theory to Algorithms. Shai Shalev-Shwartz and Shai Ben-David Papers: Linear Regression with Limited Observation. E. Hazan and T. Koren Classification with Low Rank and Missing Data. E. Hazan, R. Livni, and Y. Mansour Convergence rates of sub-sampled Newton methods. M. Erdogdu and A. Montanari Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. R. Johnson and T. Zhang Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. J. Duchi, E. Hazan, and Y. Singer Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. J. Abernethy, E. Hazan, and A. Rakhlin Cubic regularization of Newton method and its global performance. Y. Nesterov and B.T. Polyak Deep learning via Hessian-free optimization. J. Martens Escaping from Saddle Points — Online Stochastic Gradient Descent for Tensor Decomposition. R. Ge, F. Huang, C. Jin, and Y. Yuan Online Learning of Eigenvectors. D. Garber, E. Hazan, and T. Ma On the saddle point problem for non-convex optimization. R. Pascanu, Y. Dauphin, S. Ganguli, and Y. Bengio ________________________________________ From: Nicki Gotsis [ngotsis(a)cs.princeton.edu] Sent: Monday, May 09, 2016 9:49 AM To: Sachin Ravi; yichenc; Nick Larry Turner; Brian A. Bullins Subject: DUE TODAY!!!: Generals reading list and abstract due (even if there are no changes) DUE TODAY!!!: Generals reading list and abstract due (even if there are no changes) ----- Forwarded Message ----- From: "Nicol Gotsis" <ngotsis(a)cs.princeton.edu> To: "Sachin Ravi" <sachinr(a)cs.princeton.edu>, "yichenc" <yichenc(a)cs.princeton.edu>, "nturner" <nturner(a)cs.princeton.edu>, "bbullins" <bbullins(a)cs.princeton.edu>, "Ruth Dannenfelser" <rd6(a)cs.princeton.edu>, "kalodner" <kalodner(a)cs.princeton.edu>, "Jennifer Gossels" <jgossels(a)cs.princeton.edu>, "pe5" <pe5(a)cs.princeton.edu>, "laurar" <laurar(a)cs.princeton.edu>, "jzung" <jzung(a)cs.princeton.edu> Sent: Friday, May 6, 2016 3:18:44 PM Subject: Generals reading list and abstract due (even if there are no changes) due 1 week prior to your general exam Dear all, Please make sure to send me your generals reading list and abstract 1 week prior to your general exam (even if there are no changes) so I can send the announcement out. Nicki Gotsis Graduate Coordinator Room 310, Computer Science (609) 258-5387 ngotsis(a)cs.princeton.edu

1 0

Naman Agarwal will present his general exam on Monday, May 9th, 2016 at 3pm in CS 302.
by Nicki Gotsis 09 May '16

09 May '16

Naman Agarwal will present his general exam on Monday, May 9th, 2016 at 3pm in CS 302. The members of his committee are Elad Hazan (adviser), Sanjeev Arora, and Barbara Engelhardt. 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 Stochastic optimization and, in particular, first-order stochastic methods are a cornerstone of modern machine learning due to their extremely efficient per-iteration computational cost. Second-order methods, while able to provide faster per-iteration convergence, have been much less explored due to the high cost of computing the second-order information. In this talk I will present a second-order stochastic method for optimization problems arising in machine learning based on novel matrix randomization techniques that match the per-iteration cost of gradient descent, yet enjoy the linear-convergence properties of second-order optimization. We further show that the algorithm can be coupled generically with known first order algorithms and matrix sampling techniques to match the best known theoretical guarantees as well as improve these guarantees for a broad class of parameters. The algorithm also adapts well in the case when inputs are sparse . I will also demonstrate the efficacy of the algorithm empirically on several standard convex benchmarks. This is joint work with Brian Bullins and Elad Hazan Reading List Books/Lecture Notes - Introduction to Online Convex Optimization : E. Hazan Numerical Optimization: Jorge Nocedal and Stephen J. Wright Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems : S. Bubeck and N. Cesa-Bianchi Research Papers - Adaptive Subgradient Methods for Online Learning and Stochastic Optimization: J. Duchi, E. Hazan and Y. Singer Accelerating Stochastic Gradient Descent using Predictive Variance Reduction : R. Johnson and T. Zhang Convergence rates of sub-sampled Newton methods : M. Erdogdu and A. Montanari Escaping from Saddle Points — Online Stochastic Gradient Descent for Tensor Decomposition : R. Ge, F. Huang, C. Jin, Y. Yuan Cubic regularization of Newton method and its global performance : Y. Nesterov and B.T. Polyak On the saddle point problem for non-convex optimization, R. Pascanu, Y.N. Dauphin, S. Ganguli and Y. Bengio Fast and Simple PCA via Convex Optimization : D. Garber and E. Hazan On Graduated Optimization for Stochastic Non-Convex Problems : E. Hazan, K. Levi and S. Shalev-Shwartz Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization : J. Abernety, E. Hazan and A. Rakhlin The price of Bandit Optimization : V. Dani, S. M. Kakade and T. P. Hayes Towards Minimax Policies for Online Linear Optimization with Bandit Feedback : S. Bubeck, N. Cesa-Bianchi and S. M. Kakade Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier : J. Abernathy and E. Hazan Clustering with Bregman Divergences : A. Banerjee, S. Merugu, I. S. Dhillon and J. Ghosh

1 1

Shivam Agarwal will present his MSE talk on Monday, May 9th at 5 pm in CS 302.
by Nicki Gotsis 06 May '16

06 May '16

Shivam Agarwal will present his MSE talk on Monday, May 9th at 5 pm in CS 302. The members of his committee are Arvind Narayanan (adviser) and Jennifer Rexford. Everyone is welcome to attend. The talk title and abstract follow below. Title: Using Machine Learning to detect online tracking Abstract: Currently, the tools which are being used to detect online tracking like ad blocker, ghostery, etc. rely on huge manually labelled lists of urls or regular expressions making it unscalable and less accurate as the web grows. My work has been to develop a tool which will use machine learning on the fly to detect tracking websites. We construct feature vectors from the behavior of these websites on user’s browser and then classify them as tracking or non-tracking. This has an added advantage of behavioral tracking detection besides the syntactic url based tracking detection which current tools do. Our analysis over the data crawled by OpenWPM (a tool developed by CITP which crawls websites and logs data) over top 100K sites has given us as high as 98.5% accuracy with as low as 0.5% false positive rate.

1 0

Yuanzhi Li will be presenting his general exam on Tuesday, May 10, 2016 at 1:30pm in CS 302.
by Nicki Gotsis 06 May '16

06 May '16

Yuanzhi Li will be presenting his general exam on Tuesday, May 10, 2016 at 1:30pm in CS 302. The members of his committee are Sanjeev Arora (adviser), Elad Hazan, and Barbara Engelhardt. 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: Towards a better understanding of streaming PCA. Abstract: Principle Component Analysis (PCA) is one of the most fundamental tools in machine learning and data analysis. Traditionally, PCA was usually solved by putting the data all together and doing a joint singular value decomposition, which requires quadric size of memory and liner number of passes of the data. However, nowadays, it is often the case that the data set is giant and we can not afford more than one pass of the data, or the entire data set is too large to fit into the memory. To deal with with this issue, there is a on-going popular line of research which considers solving PCA in a streaming stochastic model, which picks one data point at a time and perform stochastic gradient descent according to it. In this talk, I will present the proof of convergence of this algorithm from random initialization. Previously, only the convergence from warm start was known. The proof is built upon the solution of Kardison-Singer by Adam Marcus, Dan Spielman and Nikhil Srivastava; as well as the recent on-going work of off-line gap-free PCA by Zeyuan Allen-Zhu and myself. Reading List: Books: (1). Elad Hazan, Introduction to Online Convex Optimization (2). Sanjeev Arora, Lecture Note (COS 521), http://www.cs.princeton.edu/courses/archive/fall14/cos521/. (3). Shalev-Schwartz, Understanding Machine Learning: From Theory to Algorithms (4). Yurii Nesterov and Arkadii Nemirovskii, Interior point polynomial algorithms in convex programming. Papers: (1). Prateek Jain Chi Jin Sham M. Kakade Praneeth Netrapalli Aaron Sidford, Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm (2). Ohad Shamir, Convergence of Stochastic Gradient Descent for PCA (3). Ohad Shamir, Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity (4). Dan Garber and Elad Hazan, Fast and Simple PCA via Convex Optimization (5). Kenneth L. Clarkson, David P. Woodruff, Low Rank Approximation and Regression in Input Sparsity Time (6). Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi, Tighter Low-rank Approximation via Sampling the Leveraged Element (7). Cameron Musco and Christopher Musco, Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition

1 1

Srinivas Narayana will present his FPO, "Declarative Network Path Queries" on Friday, 5/13/2016 in CS 302 at 2pm.
by Nicki Gotsis 06 May '16

06 May '16

Srinivas Narayana will present his FPO, "Declarative Network Path Queries" on Friday, 5/13/2016 in CS 302 at 2pm. The members of his committee are Jennifer Rexford (adviser), Readers: Davis Walker and Sanjay Rao (Purdue University); Nonreaders: Nick Feamster and Aarti Gupta. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follow below. Effective management of computer networks is crucial to ensure the availability and performance of “always online” Internet services that we depend on. Towards this goal, programmatic tools can remove slow and expensive human involvement in management. Recently, Software-Defined Networking (SDN) technology has eased programmatic control of networks, but there has been little attention on programmatic measurement of networks. This thesis focuses on a broad class of measurement questions that analyze the flow of traffic along network paths. Today, network operators measure traffic flow by “synthesizing” multiple data streams— including updates to forwarding, traffic observations from packet samples, and changes in network topology. However, this approach has significant limitations: it makes measurements indirect for operators to express, and forces operators to make a difficult trade-off between measurement accuracy and overhead. In this thesis, we approach network path measurement with two key principles: (1) Enable operators to specify the measurements they need in a declarative query language; and (2) Drive network measurement according to operator-specified queries. We realize these principles in three parts, as follows. First, we present a declarative query language, that enables paths to be specified as regular expressions over predicates on packet locations and header values. The language also has SQL-like “groupby” constructs for aggregating results anywhere along a path. We show several realistic measurement queries corresponding to resource management, policy enforcement, and troubleshooting. Second, we present a query run-time system that translates path queries into accurate measurement that runs on commodity switch hardware. The run-time first compiles queries into a deterministic finite automaton. The automaton’s transition function is then partitioned, compiled into ‘match-action’ rules (that run on commodity hardware), and distributed over the switches. Storing the automaton state requires only a small amount of extra space (2-4 bytes) on packets. Third, we present optimizations which address fundamental bottlenecks in compilation, caused by queries and forwarding policies requiring different actions on overlapping sets of packets. Experiments indicate that our run-time system can enable “interactive debugging,” allowing an operator to compile multiple queries in a few seconds. Further, the generated switch rules fit comfortably in modern switch rule memories.

1 0

Colloquium Speaker: John Langford, Friday May 6, 12:30pm
by Nicole E. Wagenblast 06 May '16

06 May '16

Colloquium Speaker John Langford, Microsoft Research Friday, May 6, 12:30pm Computer Science 105 How to make an Infovore An Infovore is an information-based entity that explores the world, learns, and applies these learnings effectively. In essence: a form of weak AI. We have been working on a general-purpose infovore for making decisions using elements of contextual bandits, systems, and experts-style learning that has now been successfully deployed at large scale. I will discuss the architecture of the infovore, the key results upon which it relies, and how everything works together to enable true open-loop learning in the real world.

1 0