- talks - lists.cs.princeton.edu

Linda Cai will present her FPO "Algorithmic Decision Making with Imperfect Information and Practical Irrationality" on August 7th, 2024 at 11am in CS 402.
by Gradinfo 19 Jul '24

19 Jul '24

Linda Cai will present her FPO "Algorithmic Decision Making with Imperfect Information and Practical Irrationality" on August 7th, 2024 at 11am in CS 402. Her FPO committee is as follows: Examiners: Matt Weinberg (adviser), Mark Braverman, and Huacheng Yu Readers: Bernard Chazelle and Brendan Lucier (Microsoft Research) Title and abstract follow below. All are welcome to attend. Title: Algorithmic Decision Making with Imperfect Information and Practical Irrationality Abstract: Market algorithms are ubiquitous in modern life, both online and offline. Historically, markets have been fundamental in matching supply with demand, where designers optimize regulations with global goals and participants optimize strategies with individual goals. Decision theory and mechanism design have evolved to study and prescribe the behavior and structure of these markets. This thesis addresses key questions at the intersection of market design and algorithmic decision-making: How do strategic decision-makers navigate choices, and how do resource producers allocate limited resources among strategic participants? The advent of information technology and increased data availability has revolutionized markets, enabling unprecedented scale, efficiency, and control. This development allows mechanism designers to create or modify market conditions, provided we understand their impact on the designer's objectives. In this thesis, we explore market algorithms in dynamic environments and under practical irrationality, analyzing how deviations from ideal models affect the utility of both designers and participants. We examine environmental changes such as market imbalance, resource augmentation, and competition faced by dominant sellers. For participants, we consider agents who are computationally bounded, behaviorally biased, or using learning algorithms. Our work aims to provide insights into the robustness and adaptability of market algorithms amid practical complexities and diverse participant behaviors.

1 0

Srikar Kasi will present his FPO "Quantum Decoding of Error Correction Codes for Wireless Networks" on Wednesday, August 7th, 2024 at 10am in CS 301 and Zoom.
by Gradinfo 16 Jul '24

16 Jul '24

Srikar Kasi will present his FPO "Quantum Decoding of Error Correction Codes for Wireless Networks" on Wednesday, August 7th, 2024 at 10am in CS 301 and Zoom. The members of his committee are as follows: Examiners: Kyle Jamieson (adviser), Margaret Martonosi, Yasaman Ghasempour Readers: Ravi Netravali, John Kaewell (InterDigital, Inc.), Paul Warburton (UCL) Location: CS 301, Zoom (https://princeton.zoom.us/j/5169139659) All are welcome to attend. Title: Quantum Decoding of Error Correction Codes for Wireless Networks Abstract: Error correction codes are essential for reliability and capacity in wireless networks. By correcting errors in real-time, they reduce re-transmissions, conserve bandwidth, and enhance network performance. However, these advantages come at the price of high decoding complexity and high latency which compels network designers to make sub-optimal deployment choices such as considering approximate decoding algorithms, limiting parallelism, bit-precision, and iteration counts, sacrificing the potential capacity and performance gains. Moreover, the ever-increasing user demand in wireless networks poses additional challenges in managing power consumption, operational costs, and the carbon footprint of base stations and terminals. This highlights the need for continued innovation in wireless network baseband architecture and implementation strategies. This dissertation introduces quantum computing-based processing architectures for decoding error correction codes, offering new computational paradigms to address these challenges at scale. By harnessing the principles of quantum mechanics, we propose a transformative shift in the way decoding is achieved, benefiting wireless performance and capacity, through the design and implementation of the following systems: (1) QBP, quantum annealing decoder for LDPC codes, (2) HyPD, hybrid classical--quantum annealing decoder for Polar codes, (3) QGateD, quantum amplitude amplification decoder for generic XOR-based error correction codes, (4) FDeQ, quantum gate decoder flexible to both LDPC and Polar codes, (5) QAVP, quantum annealing approach to vector perturbation precoding (a multi-user MIMO downlink baseband optimization problem). These systems collectively fall under the thesis that quantum computing is a promising approach for baseband processing, warranting further justification from an economic and environmental impact perspective. To address this and to make the case for quantum computing in wireless industry, (6) the dissertation presents a comprehensive cost and carbon footprint analysis of quantum hardware, both quantitatively and qualitatively. This may be of potential interest to NextG wireless networks and quantum architectures.

1 0

ECE Seminar: Daniel Genkin, July 16
by Emily C. Lawrence 11 Jul '24

11 Jul '24

ECE SEMINAR Speaker: Daniel Genkin, School of Cybersecurity and Privacy at Georgia Tech. Title: Side Channel Attacks: Lessons Learned or Troubles Ahead? Day: July 16, 2024 Time: 11:00am Location: B205 Engineering Quadrangle Hosts: David Wentzlaff Abstract : The security and architecture communities will remember the past five years as the era of side channels. Starting from Spectre and Meltdown, time and again we have seen how basic performance-improving features can be exploited to violate fundamental security guarantees. Making things worse, the rise of side channels points to a much larger problem, namely the presence of large gaps in the hardware-software execution contract on modern hardware. In this talk, I will give an overview of this gap, in terms of both security and performance. First, I will give a high-level survey on speculative execution attacks such as Spectre and Meltdown. I will then talk about how speculative attacks are still a threat to both kernel and browser isolation primitives, highlighting new issues on emerging architectures. Next, from the performance perspective, I will discuss new techniques for microarchitectural code optimizations, with an emphasis on compute-heavy workloads such as cryptographic protocols. Here I will show how seemingly simple, functionally equivalent, code modifications can lead to significant changes in the underlying microarchitectural behavior, resulting in dramatic performance improvements. The talk will be interactive and include attack demonstrations. Bio: Daniel Genkin is an Alan and Anne Taetle Early Career Associate Professor at the School of Cybersecurity and Privacy at Georgia Tech. Daniel’s research interests are in hardware and system security, with particular focus on side channel attacks and defenses. Daniel’s work has been recognized by best paper awards in multiple academic and industry venues, as well as covered by national and scientific press. Recently, Daniel has been part of the team performing the first analysis of speculative and transient execution, resulting in the discovery of Spectre, Meltdown and follow ups. Daniel has a PhD in Computer Science from the Technion Israel’s Institute of Technology and has been awarded the 2024 Alfred P. Sloan Research Fellowship.

1 0

Dingli Yu will present his FPO "Efficient Scaling of Large Models: Principles in Optimization and Data Aspects" on Thursday, July 18, 2024 at 1:30 PM in CS 402 and Zoom.
by gradinfo＠cs.princeton.edu 09 Jul '24

09 Jul '24

Dingli Yu will present his FPO "Efficient Scaling of Large Models: Principles in Optimization and Data Aspects" on Thursday, July 18, 2024 at 1:30 PM in CS 402 and Zoom. Location: Zoom link: https://princeton.zoom.us/j/7188314894?omn=99115109336 The members of Dingli's committee are as follows: Examiners: Sanjeev Arora (Adviser), Elad Hazan, Chi Jin Readers: Danqi Chen, Mark Braverman A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: Deep learning has advanced remarkably in recent decades. Yet, its theoretical foundations, particularly in the realm of large models, still lag behind. This thesis focuses on research that combines strong theoretical foundations with practical applications in efficiently scaling up large models. In the first part of the thesis, we focus on the training dynamics of neural nets by covering the theory of overparametrized neural nets. We will briefly introduce the theory of Neural Tangent Kernel (NTK), and proceed with Hyperparameter Transfer, an important application of the Tensor Program framework. We cover some of the earliest papers that establish NTK as a research field, along with the limitations of NTK. Hyperparameter Transfer is a novel and efficient paradigm for hyperparameter tuning by providing the optimal strategy for scaling up models. We introduce the characterization of the training dynamics for deep neural nets and offer an efficient hyperparameter selection scheme where optimal hyperparameters selected by tuning on shallow nets also work for deep nets. In the second part of the thesis, we focus on the data aspect of large model scaling. We will first introduce Skill-Mix, a novel and unique evaluation that sidesteps issues of traditional large language model (LLM) evaluations like data contamination and cramming for leaderboard. Skill-Mix randomly selects k language skills, then prompts the LLM to produce a concise text that demonstrates the chosen skills. The exponentially growing number of skill combinations provably prevent data contamination and can further reveal the novelty of successful answers by powerful LLMs. We then introduce ConceptMix, an extension of Skill-Mix to evaluate the capabilities of text-to-image models to combine k random selected visual concepts. Finally, we uncover the capabilities of LLMs to learn and generalize skill compositions given good responses from Skill-Mix. The results show that a few thousand of such data is enough to significantly improve the model performance in unseen skill combinations, beating models with much larger sizes. It suggests incorporating skill-rich synthetic text into training is an efficient way to scale up the data.

1 0

Nataly Brukhim will present her FPO "New Directions in Boosting" on Friday, June 28, 2024 at 11:00 AM in CS 402.
by Grad Info 07 Jun '24

07 Jun '24

Nataly Brukhim will present her FPO "New Directions in Boosting" on Friday, June 28, 2024 at 11:00 AM in CS 402 . Location: CS 402 The members of Nataly's committee are as follows: Examiners: Elad Hazan (Adviser), Ryan Adams, Robert Schapire (Microsoft Research) Readers: Sanjeev Arora, Shay Moran (Technion) A copy of her thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend her talk. Abstract follows below: Boosting is a fundamental methodology in machine learning used to boost the accuracy of weak learning models, transforming them into strong learners. This thesis establishes new directions in boosting theory, presenting algorithms and their analyses for complex learning scenarios that go beyond the realm of traditional classification. These developments extend the benefits of the boosting methodology to modern and challenging learning settings. This thesis is divided into two main parts: Multiclass Boosting and Boosting for Sequential Decision Making. Part I explores the generalization of classical boosting theory to the multiclass setting, specifically focusing on the challenging case of an extremely large label space. Initially, we present a hardness result that illustrates that boosting does not easily from the binary to the multiclass case. Subsequently, within the broader context of multiclass learning, we develop novel algorithmic strategies which provide a complete characterization of multiclass learnability, resolving a longstanding open problem. Finally, leveraging these novel ideas, we also introduce new boosting techniques that circumvent the aforementioned hardness barrier, leading to efficient multiclass boosting methods. In Part II, we develop boosting frameworks for sequential decision making. Sequential decision making tasks such as control, bandit and reinforcement learning, can be thought of as challenging generalized variants of statistical learning, which take into account interactive interactions with the environment. As boosting was developed for static datasets, extending the technique to these tasks poses significant challenges, and requires grappling with the effects of feedback and systems that change over time. In this line of work we develop boosting frameworks in various sequential decision making tasks. Namely, the online agnostic learning setting, online control of dynamical systems, the bandit setting in online learning, and reinforcement learning.

1 0

Deniz Oktay will present his FPO "Translating Between Scientific Computing and Machine Learning with Automatic Differentiation" on Tuesday, June 18, 2024 at 1:00 PM in CS 401.
by Grad Info 31 May '24

31 May '24

Deniz Oktay will present his FPO "Translating Between Scientific Computing and Machine Learning with Automatic Differentiation" on Tuesday, June 18, 2024 at 1:00 PM in CS 401 . Location: CS 401 The members of Deniz' committee are as follows: Examiners: Ryan Adams (Adviser), Benjamin Eysenbach, Sigrid Adriaenssens Readers: Elad Hazan, Szymon Rusinkiewicz A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: Scientific computing and machine learning, although historically separate fields, have seen much effort in unification as of recent years, especially as machine learning techniques have shown promise in scientific problems. In this thesis, I present work in the intersection of these areas, using automatic differentiation (AD) as the common language between the two. First, I present a methodological advancement in AD: Randomized Automatic Differentiation, a technique to reduce the memory usage of AD, and show that it can provide memory improvements in both machine learning and scientific computing applications. Next, I focus on mechanical design. I first describe Varmint: A Variational Material Integrator, which is a robust simulator for the statics of large deformation elasticity, using automatic differentiation as a first class citizen. Building this simulator allows us easy interoperability between machine learning and solid mechanics problems, and has been used as in several published and in submission works. I will then describe Neuromechanical Autoencoders, where we coupled neural network controllers with mechanical metamaterials to create artificial mechanical intelligence. The neural network "encoder" consumes a representation of the task-in this case, achieving a particular deformation-and nonlinearly transforms this into a set of linear actuations which play the role of the latent encoding. These actuations then displace the boundaries of the mechanical metamaterial inducing another nonlinear transformation due to the complex learned geometry of the pores; the resulting deformation corresponds to the "decoder".

1 0

Susan Tan will present her FPO "Transpilation Utilizing Language-agnostic IR and Interactivity for Parallelization" on 05/30/2024 at 1pm in Friend Center 004.
by Gradinfo 29 May '24

29 May '24

Susan Tan will present her FPO "Transpilation Utilizing Language-agnostic IR and Interactivity for Parallelization" on 05/30/2024 at 1pm in Friend Center 004. The members of her committee are as follows: Examiners: Amit Levy, Aarti Gupta, Zachary Kincaid, David August (Adviser) Readers: Johannes Doerfert (LLNL), Michael Kruse (AMD), and David August All are welcome to attend. Abstract: Migrating codes between architectures is difficult because different execution models require different types of parallelism for optimal performance. Previous approaches, like libraries or source-level tools, generate correct and natural-looking syntax for the new parallel model with limited optimization and largely leave performance engineering to the programmer. Recent approaches, such as transpilation at the compiler intermediate representation (IR) level, can automate performance engineering, but profitability can be limited by not having facts known only to the programmer. Decompiling the optimized program could leverage the strength of existing compilers to provide programmers with a natural compiler-parallelized starting point for further parallelization or refinement. Despite this potential, existing decompilers fail to do this because they do not generate portable parallel source code compatible with arbitrary compilers of the source language. This thesis provides a method for migrating code such that the compiler and programmer work together to generate code with optimal performance. To achieve this, it introduces Tulip🌷 , a source-to-source code generation framework that operates via IR-level transpilation. Transpilation at the IR level enables Tulip to generalize the transformations applied to retarget parallelism. Furthermore, Tulip integrates the state-of-the-art automatic parallelization framework to explore additional parallelism expressible only in the target parallel programming model. It then generates natural source code through a novel decompiler, SPLENDID, in a high-level parallel programming language (OpenMP), which can be interactively optimized and tuned with programmer intervention. For 19 Polybench benchmarks, Tulip-generated OpenMPCUDA offloading programs perform 14% faster than the original CUDA sources on NVIDIA GPUs. Moreover, transpilation to the CPU leads to a 2.9x speedup over the best state-of-the-art transpiler. Tulip-generated portable parallel code is also more natural than what existing decompilers produce, resulting in a 39x higher average BLEU score. This thesis includes contributions from Yebin Chon, Ziyang Xu, Sophia Zhang, and David I. August from Princeton Liberty Research Group, Brian Homerding, Yian Su, and Simone Campanoni from Northwestern Arcana Lab, Michael Kruse (AMD), Johannes Doerfert (LLNL), William S. Moses (UIUC), and Ivan R. Ivanov (Tokyo Tech).

2 1

Shaowei Zhu will present his FPO "Monotone Termination Analysis" on June 6, 2024 at 12pm in CS 105.
by Nicki Mahler 22 May '24

22 May '24

Shaowei Zhu will present his FPO "Monotone Termination Analysis" on June 6, 2024 at 12pm in CS 105. The members of his committee are as follows: Examiners: Zak Kincaid (Adviser), Andrew Appel, and Lennart Beringer Readers: David Walker, Aarti Gupta All are welcome to attend. Abstract follows below: Many decision problems, particularly those concerning program semantics, are undecidable. One prominent example is determining whether a program terminates. To address this, modern static analyzers employ heuristics to prove termination, which could be effective for certain programs but not all. Users of these analyzers struggle to understand why the tool works or not for their source programs, due to the unpredictable behavior of heuristics. For instance, annotating a loop with an invariant might make a tool that previously worked fail or not terminate. This dissertation investigates methodologies for designing termination analyses that can prove termination of real-world programs while ensuring predictability through monotonicity. A monotone analysis maintains or improves its results with additional input information, such as more loop invariants or assumptions that limit the program's state space. Monotonicity aligns with user expectations that analysis results should not deteriorate with more information given to the analysis. To achieve a monotone program analysis, we extend the algebraic program analysis framework, which uses regular expressions to represent finite program paths and interpret labels and operators within these expressions. We introduce a framework for compositional and monotone termination analysis on whole programs by incorporating an omega operator to represent infinite paths, and we develop various monotone termination analyses through different implementations of this operator based on various techniques, including analyzing phase transitions in loops, abstracting the behavior of the loop into a linear dynamical system, or synthesizing (lexicographic) polynomials ranking functions. Experimental results demonstrate that it is possible to design monotone static termination analysis that is effective for both linear and nonlinear programs and competitive with the state-of-the-art non-monotone methods in terms of the number of benchmark tasks solved and running time.

1 0

Peter Halmos will present his General Exam "DeST-OT: Alignment of Spatiotemporal Transcriptomics Data" on Friday, May 17, 2024 at 3:00 PN in CS 301 and via zoom.
by CS Grad Department 14 May '24

14 May '24

Peter Halmos will present his General Exam "DeST-OT: Alignment of Spatiotemporal Transcriptomics Data" on Friday, May 17, 2024 at 3:00 PN in CS 301 and via zoom. Zoom link: https://princeton.zoom.us/s/5942235413 Committee Members: Ben Raphael (advisor), Ellen Zhong, Olga Troyanskaya Abstract: Spatially resolved transcriptomics (SRT) measures mRNA transcripts at thousands of locations within a tissue slice, revealing spatial variations in gene expression and distribution of cell types. In recent studies, SRT has been applied to tissue slices from multiple timepoints during the development of an organism. Alignment of this spatiotemporal transcriptomics data can provide insights into the gene expression programs governing the growth and differentiation of cells over space and time. We introduce DeST-OT (Developmental SpatioTemporal Optimal Transport), a method to align SRT slices from pairs of developmental time points using the framework of optimal transport (OT). DeST-OT uses semi-relaxed optimal transport to precisely model cellular growth, death, and differentiation processes that are not well-modeled by existing alignment methods. We demonstrate the advantage of DeST-OT on simulated slices. We further introduce two metrics to quantify the plausibility of a spatiotemporal alignment: a growth distortion metric which quantifies the discrepancy between the inferred and the true cell type growth rates, and a migration metric which quantifies the distance traveled between ancestor and descendant cells. DeST-OT outperforms existing methods on these metrics in the alignment of spatiotemporal transcriptomics data from the development of mouse kidney and axolotl brain. Moreover, DeST-OT shows better correlation with the expression of annotated proliferation and apoptosis genes. Reading List: https://docs.google.com/document/d/1vYk8ZLMaOgIiMaQpQSIBh-z0KIotPOcMa6p8Nh2… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

PPH Lunch seminar: Chandra Theesfeld and Rachel Kaletsky, Friday at 12 pm at 252 Nassau Street
by Emily C. Lawrence 14 May '24

14 May '24

Please join the Princeton Precision Health Initiative for the next talks in our lunch time seminar series this Friday, May 17, at 12:00 pm, in our new space at 252 Nassau Street. Chandra Theesfeld from Genomics and PPH will present a talk titled, “Unraveling the heterogeneity of complex disease: data-driven analysis of genotype, phenotype, and environment”, and Rachel Kaletsky from Genomics and Mol Bio will present a talk titled, “Defining a biological clock for female reproductive decline”. Lunch will be provided. Please note that getting to the seminar space currently requires that you climb a set of stairs. If an accommodation is needed, please contact PPH in advance at: [ mailto:princetonPPH@princeton.edu | princetonPPH(a)princeton.edu ] The PPH Team ************************************ Princeton Precision Health [ http://pph.princeton.edu/ | pph.princeton.edu ] [ mailto:princetonpph@princeton.edu | princetonpph(a)princeton.edu ]

1 0