Export
YinTat Lee
· 1 previous affiliation
- University of WashingtonSince 2017
- Assistant Professor · Since 2017
Research Overview
YinTat Lee focuses on the development of efficient algorithms for high-dimensional sampling, convex optimization, and privacy-preserving machine learning. His work primarily addresses the theoretical limits and practical implementations of algorithms operating in high-dimensional spaces, particularly when faced with constraints, non-smoothness, or ill-conditioned distributions. By leveraging tools from differential geometry and oracle-based complexity analysis, Lee contributes to the understanding of how fundamental optimization and sampling tasks can be accelerated or scaled to handle modern computational demands in fields such as systems biology and large-scale model training.
Research Trajectory
Lee’s research trajectory is characterized by a dual focus on the theoretical foundations of optimization and the practical challenges of high-dimensional data processing. In 2021, his work centered on the complexity of convex optimization under various oracle models, investigating the fundamental limits of parallelism and acceleration. This period involved refining lower bounds for non-smooth optimization and exploring new algorithmic primitives, such as ball optimization oracles, to surpass traditional gradient-based limits.
By 2022, Lee’s focus expanded toward the intersection of geometry and sampling, as well as the theoretical underpinnings of differential privacy in high-dimensional learning. This shift represented a move from purely optimization-centric problems to broader questions of how geometric structure can be exploited to improve the efficiency of probabilistic inference and the utility of private models. Throughout this evolution, a consistent theme has been the pursuit of algorithms whose performance is less sensitive to the "curse of dimensionality" or poor conditioning, whether through the use of Riemannian manifolds in sampling or subspace analysis in differential privacy.
High-Dimensional Sampling and Constraints
A significant portion of Lee’s recent work addresses the difficulty of sampling from complex, high-dimensional distributions. Traditional sampling methods often struggle with ill-conditioned or non-smooth distributions, especially when they are confined to constrained spaces such as polytopes. In Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space, Lee and his collaborators introduced an algorithm that utilizes Riemannian Hamiltonian Monte Carlo (RHMC) to sample from distributions in upwards of 100,000 dimensions.
This research is notable for maintaining sparsity while incorporating constraints directly into the Riemannian metric, which allows the algorithm to achieve mixing rates that are largely independent of the distribution's smoothness or condition number. The practical utility of this approach was demonstrated through its application to metabolic networks, specifically the RECON3D model, where it achieved a 1,000-fold speed-up over existing software packages. This work bridges the gap between the theoretical advantages of Riemannian manifolds and the practical requirements of large-scale biological modeling and linear programming.
Complexity and Oracle Models in Optimization
Lee has contributed extensively to the study of oracle complexity in convex optimization, focusing on the theoretical bounds that govern how quickly an algorithm can converge given specific types of access to a function. In Complexity of Highly Parallel Non-Smooth Convex Optimization, Lee participated in research that re-examined the optimality of gradient descent in parallel settings. While gradient descent is known to be optimal for non-smooth convex optimization when queries are sequential, this work investigated the "highly parallel" setting where an oracle can answer multiple gradient queries simultaneously. The research established that gradient descent remains optimal only up to a certain threshold of interaction rounds, specifically improving a decades-old lower bound to show that $\tilde{O}(\sqrt{d})$ rounds are necessary, even with polynomial parallelism.
Further exploring alternative oracle models, Lee contributed to the development of accelerated methods in Acceleration with a Ball Optimization Oracle. This work considers a "ball optimization oracle" that returns the minimizer of a function within an $l_2$ ball of a given radius. The research demonstrated that while a naive approach would require $r^{-1} \log(1/\epsilon)$ calls to find an approximate minimizer, an accelerated algorithm can achieve this in $r^{-2/3} \log(1/\epsilon)$ queries. This result, accompanied by a matching lower bound, provides a new framework for understanding acceleration beyond the standard gradient-based paradigm and offers potential implementations using variants of Newton’s method for functions with locally stable Hessians.
Differential Privacy and Model Scale
In the domain of machine learning, Lee has collaborated on investigations into the behavior of differentially private (DP) algorithms in high-dimensional regimes. A persistent question in private learning is why large, high-dimensional models often achieve better-than-expected utility, seemingly contradicting theoretical results that suggest privacy-utility trade-offs should degrade as model size increases.
In When Does Differentially Private Learning Not Suffer in High Dimensions?, Lee and his co-authors identified that the performance of DP convex learning is heavily influenced by the magnitudes of gradients when projected onto specific subspaces. By characterizing these projections, the research provides a more precise explanation for why high-dimensional models can remain performant under privacy constraints. This work contributes to the broader effort to align the theoretical understanding of differential privacy with the empirical success of large-scale private fine-tuning, suggesting that the effective dimensionality of the problem, rather than the raw parameter count, is the primary determinant of success.
Profile updated
| Title | Venue | Year |
|---|---|---|
| Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space | NeurIPS | 2022 |
| Acceleration with a Ball Optimization Oracle | NeurIPS | 2020 |
| Complexity of Highly Parallel Non-Smooth Convex Optimization | NeurIPS | 2019 |
Loading new papers…
Other researchers whose papers cluster into the same research directions — a proxy for overlapping technical interests and shared intellectual neighborhoods.
See something wrong? Report a mistake