- talks - lists.cs.princeton.edu

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

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

05 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

Miles Carlsten will present his MSE talk, "The impact of transaction fees on Bitcoin mining strategies" on Friday, May 6 at 1:30pm in CS 301.
by Nicki Gotsis 05 May '16

05 May '16

Miles Carlsten will present his MSE talk, "The impact of transaction fees on Bitcoin mining strategies" on Friday, May 6 at 1:30pm in CS 301. The members of his committee are Arvind Narayanan (adviser) and Mark Braverman. The title and abstract follow below. Everyone is invited to attend. Title: The impact of transaction fees on Bitcoin mining strategies Abstract: There are two incentives for Bitcoin miners to mine Bitcoin blocks. The miners are rewarded both from the minting reward of creating a new block and from the transaction fees on the transactions included in the block mined. Traditionally, the minting reward has always been significantly larger than the transaction fees, but as time goes on the minting fee is designed to diminish, and it is expected that the transaction fees will take its place. We look into the unverified claim that once incentives shift to mostly transaction fees, the security of the system will be the same as it was when it was based on minting rewards. We show that this change can lead to very uneven blocks, which can give rational miners an incentive to intentionally try to fork the blockchain. Additionally, we reexamine a previously known alternate mining strategy, known as Selfish Mining, and show that it will become profitable for any miner (regardless of their hash power) to utilize this strategy.

1 0

Themistoklis Melissaris will present his general exam on Wednesday, May 11, 2016 at 4:30pm in CS 402.
by Nicki Gotsis 04 May '16

04 May '16

Themistoklis Melissaris will present his general exam on Wednesday, May 11, 2016 at 4:30pm in CS 402. The members of his committee are Margaret Martonosi (adviser), Kyle Jamieson, and JP Singh. The title and abstract follow below. Everyone is invited to attend the talk and those faculty wishing to remain for the oral exam are welcome to do so. Title: LOCOMOTIVE: Optimizing mobile web traffic using selective compression Abstract Global mobile traffic is growing at a rapid rate, following an increase in connected mobile devices and adoption of services and mobile apps. A common practice is to reduce web traffic by utilizing compression. However, universal application of compression can introduce latency and energy overheads and raises the need to pinpoint the conditions for compression insertion. My talk will discuss LOCOMOTIVE (Latency Optimizations by COmpressing MObile Transfers In Variable Environments), a framework that determines whether to use compression on the fly based on the traffic and on network conditions. LOCOMOTIVE uses a simple latency model to drive its decisions. The results of this approach indicate savings in both latency and energy, while reducing the data overhead. My work has explored characteristics of mobile traffic across different mobile devices and has studied the energy and latency impact of compression. Reading List 1. Armando Fox, Steven D. Gribble, Eric A. Brewer, and Elan Amir. 1996. Adapting to network and client variability via on-demand dynamic distillation. In Proceedings of the seventh international conference on Architectural support for programming languages and operating systems (ASPLOS VII). ACM, New York, NY, USA, 160-170. DOI=http://dx.doi.org/10.1145/237090.237177 2. Jeffrey C. Mogul, Fred Douglis, Anja Feldmann, and Balachander Krishnamurthy. 1997. Potential benefits of delta encoding and data compression for HTTP. In Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication (SIGCOMM '97), Martha Steenstrup (Ed.). ACM, New York, NY, USA, 181-194. DOI=http://dx.doi.org/10.1145/263105.263162 3. Victor Agababov, Michael Buettner, Victor Chudnovsky, Mark Cogan, Ben Greenstein, Shane McDaniel, Michael Piatek, Colin Scott, Matt Welsh, and Bolian Yin. 2015. Flywheel: Google's data compression proxy for the mobile web. In Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation (NSDI'15). USENIX Association, Berkeley, CA, USA, 367-380. 4. Feng Qian, Junxian Huang, Jeffrey Erman, Z. Morley Mao, Subhabrata Sen, and Oliver Spatscheck. 2013. How to reduce smartphone traffic volume by 30%?. In Proceedings of the 14th international conference on Passive and Active Measurement (PAM'13), Matthew Roughan and Rocky Chang (Eds.). Springer-Verlag, Berlin, Heidelberg, 42-52. DOI=http://dx.doi.org/10.1007/978-3-642-36516-4_5 5. Christopher M. Sadler and Margaret Martonosi. 2006. Data compression algorithms for energy-constrained devices in delay tolerant networks. In Proceedings of the 4th international conference on Embedded networked sensor systems (SenSys '06). ACM, New York, NY, USA, 265-278. DOI=http://dx.doi.org/10.1145/1182807.1182834 6. Kenneth Barr and Krste Asanović. 2003. Energy aware lossless data compression. In Proceedings of the 1st international conference on Mobile systems, applications and services (MobiSys '03). ACM, New York, NY, USA, 231-244. DOI=http://dx.doi.org/10.1145/1066116.1066123 7. Niranjan Balasubramanian, Aruna Balasubramanian, and Arun Venkataramani. 2009. Energy consumption in mobile phones: a measurement study and implications for network applications. InProceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (IMC '09). ACM, New York, NY, USA, 280-293. DOI=http://dx.doi.org/10.1145/1644893.1644927 8. Feng Qian, Subhabrata Sen, and Oliver Spatscheck. 2014. Characterizing resource usage for mobile web browsing. In Proceedings of the 12th annual international conference on Mobile systems, applications, and services (MobiSys '14). ACM, New York, NY, USA, 218-231. DOI=http://dx.doi.org/10.1145/2594368.2594372 9. Hossein Falaki, Dimitrios Lymberopoulos, Ratul Mahajan, Srikanth Kandula, and Deborah Estrin. 2010. A first look at traffic on smartphones. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement (IMC '10). ACM, New York, NY, USA, 281-287. DOI=http://dx.doi.org/10.1145/1879141.1879176 10. Larry L. Peterson and Bruce S. Davie. 2011. Computer Networks, Fifth Edition: A Systems Approach (5th ed.), Chapters 1,5,7,9. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

1 0