"Towards optimal sampling algorithms"

Abstract

Sampling is a fundamental task with applications in many different areas from probabilistic inference to generative artificial intelligence and fairness. Many sampling problems involve high-dimensional and complex target distributions, making naive heuristics ineffective. Markov chains are widely employed for sampling and are believed to be highly efficient. However, existing studies on Markov chains either provide suboptimal runtime guarantees or are limited to specific settings.

In this talk, I will give the best possible bound on the runtime of Markov chain algorithms in the most general setting possible using “entropic independence”, a framework that I have developed in the past few years. My work results in simple and optimally fast algorithms and has settled many long-standing open problems. The technical tools I develop for analyzing Markov chains have also found unexpected applications in other algorithmic tasks such as learning and optimization.
 

Biography

Thuy-Duong “June” Vuong is a fifth-year PhD student at Stanford advised by Nima Anari and Moses Charikar. She completed her undergraduate at MIT in 2019, double majoring in Mathematics and Computer Science.  Her research is in designing and analyzing algorithms for sampling, particularly Markov chains. Her research has been supported by a Microsoft PhD Fellowship.

Research Interests/Area

Theory, Algorithms Design, Algorithm for sampling, Markov chains

"Integrating Theory and Practice in Complex Privacy-Preserving Data Analysis"

Abstract

With growing concerns about large-scale data collection and surveillance, the development of privacy-preserving tools can help alleviate public fears about the misuse of personal data. The field of differential privacy (DP) offers powerful data analysis tools that provide worst-case privacy guarantees. However, the transition of differential privacy from academic research to practice introduces many new technical challenges, which range from fundamental theory to large-scale deployment and broader privacy concerns. 

In this talk, I will discuss my research efforts in tackling two major challenges: 1 How to reason about more complex privacy accounting? 2. How to identify and protect privacy beyond DP’s individual-oriented focus? 

To answer the first question, I will show the optimal composition theorems for concurrently composing multiple interactive mechanisms, even in scenarios where we adaptively select privacy-loss parameters and create new mechanisms. These results offer strong theoretical foundations for enabling full adaptivity and interactivity in DP systems. Towards the second challenge, I will talk about a broader non-individual privacy for protecting sensitive global properties of a dataset, e.g., proprietary information or IP contained in the data. I will introduce an attack to identify the dataset-level privacy vulnerabilities; and a solution, consisting of a theoretical framework to capture this global property privacy and mechanisms to achieve that. I will conclude the talk with my future directions.

Biography

Wanrong Zhang is an NSF Computing Innovation Fellow in the Theory of Computing group at Harvard John A. Paulson School of Engineering and Applied Sciences. She is also a member of the Harvard Privacy Tools/OpenDP project. Her primary focus is to address new challenges introduced by real-world deployments of differential privacy. Before joining Harvard, she received her Ph.D. from Georgia Institute of Technology. She is a recipient of a Best Paper Award at CCS (2023), a Computing Innovation Fellowship from CCC/CRA/NSF. She was selected as a rising star in EECS in 2022 and a rising star in Data Science in 2021. 

Research Interests/Area

Data privacy, responsible computing

"Recent Advances in Strongly Polynomial Algorithms for Linear Programming"

Abstract

Whereas ellipsoid methods and interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. 
 
An important unresolved question in operations research, theoretical computer science, and related fields, concerns the existence of a strongly polynomial algorithm for linear programming. Such an algorithm's running time would solely depend on the problem's dimension and the number of constraints, independent of any additional condition numbers. This question, first articulated by Megiddo in the 1980s, has gained prominence as Smale's 9th problem.
 
In the first part of our talk, we introduce a new polynomial-time path-following interior point method where the number of iterations admits a combinatorial upper bound that is exponential in the number of constraints. More precisely, the iteration count of our algorithm is at most a small polynomial factor times the segment count of any piecewise linear trajectory within a wide neighborhood of the central path. Notably, it parallels the iteration count of any path-following interior point method, with an adjustment for this polynomial factor.
 
In the second part of our talk, we give a strongly polynomial algorithm for minimum cost generalized flow, and hence all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. This provides a next milestone towards answering Smale’s 9th problem.

Biography

Bento Natura is a Ronald J. and Carol T. Beerman/ARC Postdoctoral Fellow in ISyE at Georgia Tech. He obtained his PhD in the Department of Mathematics at the London School of Economics, where he was supervised by László Végh. His doctoral thesis earned him the departmental Dissertation Prize and placed as a runner-up for the PhD Prize awarded by the OR Society of the United Kingdom. Prior to his PhD, Bento earned Bachelor's and Master's degrees in Mathematics from the University of Bonn, under the supervision of Stephan Held and Jens Vygen. Bento's current research interests are centered on algorithms, optimization, and game theory.

Research Interests/Area

Algorithms and Optimization

CS Department Events

CSPAC Workshop Series

Other Events & Opportunities

Towards Human-centered AI: How to Generate Useful Explanations for Human-AI Decision Making

CS News

NU News