May 2016 - talks - lists.cs.princeton.edu

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

Brian Matejek will present his MSE thesis "Learning Global Features for Neuron Reconstruction in EM Images" today, March 4, 2016 at 4:30pm in CS 401
by Nicki Gotsis 04 May '16

04 May '16

Brian Matejek will present his MSE thesis "Learning Global Features for Neuron Reconstruction in EM Images" today, March 4, 2016 at 4:30pm in CS 401. Tom Funkhouser (adviser) and Sebastian Seung are his committee members. All are welcome to join. Please see thesis title and abstract below. Title: Learning Global Features for Neuron Reconstruction in EM Images Abstract: Connectomics, the study of the neural connections, has gained significant attention in the neuroscience community as a method to understand the complex workings of the brain. Recent advancements in neural image acquisition has created a surplus of data too expensive to manually annotate leading to an influx of automatic reconstruction methods. Most current methods employ hierarchical agglomeration techniques that focus on extracted local features. These techniques fail to utilize overall global structure of neurons and other valuable shape descriptors, leading to early errors which compound over time. This paper introduces novel global and local features for predicting merge candidates in oversegmented neural images. Testing on the SNEMI3D challenge dataset, these new features produce great improvement on traditional agglomeration algorithms.

1 0

Robert MacDavid will be presenting his MSE talk, "Enhanced Compression of Interdomain SDN Policies at Internet Exchange Points" on Thursday, May 5th, 2016 in CS 302.
by Nicki Gotsis 04 May '16

04 May '16

Robert MacDavid will be presenting his MSE talk, "Enhanced Compression of Interdomain SDN Policies at Internet Exchange Points" on Thursday, May 5th, 2016 in CS 302. The members of his committee are Jennifer Rexford (adviser) and Nick Feamster. Title and abstract are below. All are invited to attend. Title: Enhanced Compression of Interdomain SDN Policies at Internet Exchange Points Abstract Internet Exchange Points (IXPs) with Software-Defined Networking (SDN) capabilities are a promising way of shaping the future of interdomain traffic delivery on the Internet---allowing IXP participants to express flexible SDN policies on interdomain traffic. Unfortunately, it has proven difficult to compile interdomain traffic policies into forward table sizes reasonable for available commodity switches, and indeed this shows in state-of-the-art SDN-IXP implementations. To compile interdomain traffic SDN policies, available prefix routes must be factored in to ensure correctness, resulting in a forwarding table size explosion. To address the explosion problem, new compression techniques of forwarding table entries are required. In this talk, we discuss the design and analysis of such a compression technique, which allows near-optimal compilation size of SDN policies for IXPs with large numbers of participants

1 1