Young Researchers Workshop —2024

Session 1 Poster Presenters and Titles
Thursday, October 10, 8:30-9:45am Duffield Hall Atrium

Abstracts

Opening Session—Hosted by Adrian Lewis
Thursday, October 10, (10 a.m. — 11 a.m.) (G10 Biotech)

Yuchen Wu—Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models

Diffusion models have become pivotal in the realm of modern generative modeling, achieving state-of-the-art performance across multiple domains. Despite the high sample quality they obtain, diffusion models generally require hundreds to thousands of sequential neural network evaluations, incurring considerably higher computational costs compared to single-step generators like generative adversarial networks (GANs) and variational auto-encoders (VAEs). While various different acceleration methods have been proposed, the theoretical foundations for accelerating diffusion models remain largely underexplored. In this talk, I will discuss a training-free acceleration algorithm for SDE-based diffusion samplers  based on the stochastic Runge-Kutta method. Our sampler requires $\widetilde O(d^{3/2} / \varepsilon)$ network function evaluations to attain $\varepsilon$ error measured in KL divergence, outperforming the state-of-the-art guarantee $\widetilde O(d^{3} / \varepsilon)$ in terms of dimensional dependency. Numerical simulations validate the efficiency of the proposed method.

Yu Ma—M3H: Multimodal Multitask Machine Learning for Healthcare

Developing an integrated many-to-many framework leveraging multimodal data for multiple tasks is crucial to unifying healthcare applications ranging from diagnoses to operations. In resource-constrained hospital environments, a scalable and unified machine learning framework that improves previous forecast performances could improve hospital operations and save costs. We introduce M3H, an explainable Multimodal Multitask Machine Learning for Healthcare framework that consolidates learning from tabular, time-series, language, and vision data for supervised binary/multiclass classification, regression, and unsupervised clustering. It features a novel attention mechanism balancing self-exploitation (learning source-task), and cross-exploration (learning cross-tasks), and offers explainability through a proposed TIM score, shedding light on the dynamics of task learning interdependencies. M3H encompasses an unprecedented range of medical tasks and machine learning problem classes and consistently outperforms traditional single-task models by on average 11.6% across 40 disease diagnoses from 16 medical departments, three hospital operation forecasts, and one patient phenotyping task. The modular design of the framework ensures its generalizability in data processing, task definition, and rapid model prototyping, making it production ready for both clinical and operational healthcare settings, especially those in constrained environments.

Optimization I—Hosted by Soroosh Shafiee
Thursday, October 10, 11:30 a.m. — 1:00 p.m.  (G10 Biotech)

Xin Jiang—Graph sequences with finite-time convergence for decentralized average consensus and its application in distributed optimization

In decentralized computing, computational resources are abstracted as agents and collaborate to solve a global problem through peer-to-peer interactions. Such a paradigm avoids the communication bottleneck induced by a central coordinator, as does in distributed computing. A fundamental challenge in decentralized computing is computing the average of all agents, also referred to as the average consensus problem.

This talk presents an approach to the average consensus problem which leverages the finite-time consensus property of a sequence of graphs. Graph sequences with the finite-time consensus property have the desirable feature that iterating through the entire graph sequence is equivalent to performing global or exact averaging. Prior results were limited to establishing the finite-time consensus property when the total number of agents is a power of two. In contrast, we develop two novel sequences of graphs, the p-peer hyper-cuboids and sequential doubly stochastic (SDS) graphs, that not only satisfy the finite-time consensus property for an arbitrary number of agents but also account for the inter-and intra-cluster communication structure found in high-performance computing resources.

Xiaopeng Li—Proximal random reshuffling under local Lipschitz continuity

We study proximal random reshuffling for minimizing the sum of locally Lipschitz functions and a proper lower semicontinuous convex function without assuming coercivity or the existence of limit points. The algorithmic guarantees pertaining to near approximate stationarity rely on a new tracking lemma linking the iterates to trajectories of conservative fields. One of the novelties in the analysis consists in handling conservative fields with unbounded values.

Tianjiao Li—A simple uniformly optimal method without line search for convex optimization

Line search (or backtracking) procedures have been widely employed into first-order methods for solving convex optimization problems, especially those with unknown problem parameters (e.g., Lipschitz constant). In this work, we show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. In particular, we present a novel accelerated gradient descent type algorithm called auto-conditioned fast gradient method (AC-FGM) that can achieve an optimal O(1/k^2) rate of convergence for smooth convex optimization without requiring the estimate of a global Lipschitz constant or the employment of line search procedures. We then extend AC-FGM to solve convex optimization problems with Holder continuous gradients and show that it automatically achieves the optimal rates of convergence uniformly for all problem classes with the desired accuracy of the solution as the only input. Finally, we report some encouraging numerical results that demonstrate the advantages of AC-FGM over the previously developed parameter-free methods for convex optimization.

Zikai Xiong—Enhancing the Solution Methods for Huge-Scale Linear Programming via Level-Set Geometry

Just in the last several years, we have witnessed a dramatic shift in the way linear programs (LPs) are actually solved -- the classic methods (simplex method and interior-point methods) are being replaced by the primal-dual hybrid gradient method (PDHG) to solve the huge-scale LP problems. PDHG, with heuristic enhancements and GPU implementation, has been very successful in solving huge-scale LP problems; however, its performance can have substantial variability, and an intuitive understanding of the drivers of its performance has been lacking. In this talk I will present new results on both the theoretical foundation and the practical performance of PDHG. Furthermore, these results extend to general conic convex optimization. Our analysis shows that the geometry of the primal-dual (sub-)level sets plays a critical role in the performance of PDHG – both in theory and practice. This is both good and bad, because it means that unfavorable geometry of some instances leads to the poor performance of PDHG both in theory and practice. To address this issue, we show how to construct central-path-based linear transformations—including conic rescaling—that can markedly enhance the convergence of PDHG by changing the geometry. Last of all, we present computational results that demonstrate how our rescalings accelerate convergence to high-accuracy solutions and lead to more efficient methods for huge-scale LP problems.

Reinforcement Learning —Hosted by Ziv Scully
Thursday, October 10, 2:00 p.m. — 3:30 p.m.  (G10 Biotech)

Yuchen Hu—Policy Evaluation in Dynamic Experiments

Experiments where treatment assignment varies over time, such as micro-randomized trials and switchback experiments, are essential for guiding dynamic decisions. These experiments often exhibit nonstationarity due to factors like hidden states or unstable environments, posing substantial challenges for accurate policy evaluation.

In this talk, I will discuss how mixing assumptions inform the design of simple yet robust methodologies for policy evaluation in Partially Observed Markov Decision Processes (POMDPs). In the first part of the talk, I will discuss the properties of switchback experiments in finite-sample, non-stationary dynamic systems. We find that, in this setting, standard switchback designs suffer considerably from carryover bias, but judicious use of burn-in periods can considerably improve the situation and enable errors that decay nearly at the parametric rate. In the second part of the talk, I will discuss policy evaluation in micro-randomized experiments and provide further theoretical grounding on mixing-based policy evaluation methodologies. Under a sequential ignorability assumption, we provide rate-matching upper and lower bounds that sharply characterize the hardness of off-policy evaluation in POMDPs. These findings demonstrate the promise of using stochastic modeling techniques to enhance tools for causal inference. Our formal results are mirrored in empirical evaluations based on ride-sharing and mobile health simulators.

Lucy Huo—Asymptotic product-form steady state for multiclass queueing networks in multi-scale heavy traffic

Multiclass queueing networks are essential models for data centers and complex service systems. In this work, we study their stationary distribution under static buffer priority service policies in a multi-scale heavy traffic regime. We prove that the scaled queue lengths converge weakly to a product-form limit, whose components are independent and each component follows an exponential distribution. This closed-form result not only advances the theoretical understanding of multi-class networks, but also provides practical insights into the design and optimization of service policies. 

Yashaswini Murthy—Learning and Control in Countable State-Spaces

We consider policy optimization methods in reinforcement learning settings where the state space is arbitrarily large, or even countably infinite. The motivation arises from control problems in communication networks, matching markets, and other queueing systems. Specifically, we consider the popular Natural Policy Gradient (NPG) algorithm, which has been studied in the past only under the assumption that the cost is bounded and the state space is finite, neither of which holds for the aforementioned control problems. Assuming a Lyapunov drift condition, which is naturally satisfied in some cases and can be satisfied in other cases at a small cost in performance, we design a state-dependent step-size rule which dramatically improves the performance of NPG for our intended applications. In addition to experimentally verifying the performance improvement, we also theoretically show that the iteration complexity of NPG can be made independent of the size of the state space. The key analytical tool we use is the connection between NPG stepsizes and the solution to Poisson's equation. In particular, we provide policy-independent bounds on the solution to Poisson's equation, which are then used to guide the choice of NPG stepsizes.

Ming Yin—Understanding Q*: from sequential decision making to Large language model alignment

Sequential decision-making problems are ubiquitous in everyday life, and different problems have different levels of harness for making good decisions. Given a problem at hand, understanding its “hardness” is vital for deploying strategies. In the first part of this talk, I will provide a fundamental characterization of offline learning hardness which we termed “intrinsic learning bound” when the sequential decision-making problem has discrete state and action spaces. To this end, we design a fine-grained pessimistic uncertainty estimation that adapts the individual instances and uses sharp statistical analysis tools to recover the hardness of the learning problems. Our result explains the major sources of hardness in learning: distribution shift (between data distribution and optimal distribution) and environmental variation (over Q*). Due to its generic form, we believe the intrinsic bound could help illuminate what makes a specific problem hard and reveal the fundamental challenges in offline RL.

In the second part of the talk, I will cast Large Language Model alignment problem as a sequential decision-making problem, and design principled decoding by leveraging an implicitly estimated Q* function. One key feature of our algorithm is that we do not need training for alignment. Compared to other training-free LLM alignment methods, our method provides the best performance, and can easily transfer to other similar but different alignment tasks

Markets and Decisions—Hosted by Paul Gölz
Thursday, October 10, 4:00 p.m. — 5:30 p.m. (G10 Biotech)

Nicolas Christianson—Reliable AI-Augmented Algorithms for Energy and Sustainability

Modern AI and ML algorithms can deliver transformative performance improvements for decision-making under uncertainty, where traditional, worst-case algorithms are often too conservative. This can potentially be transformative for energy and sustainability applications, where rapid improvements are crucial to facilitate the energy transition and reduce carbon emissions. However, AI and ML lack worst-case guarantees, hindering their deployment to real-world problems where safety and reliability are critical. In this talk, I will discuss recent work on developing AI-augmented algorithms with provable performance guarantees and their application across the domains of energy systems and sustainable computing. In particular, I will discuss progress on the question of designing optimal algorithms integrating black-box AI “advice” and classic, worst-case strategies in general online optimization problems, while highlighting recent steps toward leveraging uncertainty quantification for risk-aware decision-making in these settings.

Meena Jagadeesan— Safety vs. Performance: How Multi-Objective Learning Reduces Barriers to Market Entry

Emerging marketplaces for large language models and other large-scale machine learning (ML) models appear to exhibit market concentration, which has raised concerns about whether there are insurmountable barriers to entry in such markets. In this work, we study this issue from both an economic and an algorithmic point of view, focusing on a phenomenon that reduces barriers to entry. Specifically, an incumbent company risks reputational damage unless its model is sufficiently aligned with safety objectives, whereas a new company can more easily avoid reputational damage. To study this issue formally, we define a multi-objective high-dimensional regression framework that captures reputational damage, and we characterize the number of data points that a new company needs to enter the market. Our results demonstrate how multi-objective considerations can fundamentally reduce barriers to entry -- the required number of data points can be significantly smaller than the incumbent company's dataset size. En route to proving these results, we develop scaling laws for high-dimensional linear regression in multi-objective environments, showing that the scaling rate becomes slower when the dataset size is large, which could be of independent interest.

Devansh Jalota—Algorithm and Incentive Design for Sustainable Resource Allocation: Beyond Classical Fisher Markets

Technological advances have opened new avenues for designing market mechanisms for resource allocation, from enhancing resource allocation efficiency with widespread data availability to enabling real-time algorithm implementation. While these technological advancements hold significant promise, they also introduce new societal challenges pertaining to equity, privacy, data uncertainty, and security that existing market mechanisms often fail to address. My research develops data-driven and online learning algorithms and incentive schemes to address these challenges of traditional market mechanisms, thereby advancing the science and practice of market design for sustainable and society-aware resource allocation.

In this talk, I focus on addressing data uncertainty and privacy issues in the context of Fisher markets, a classical framework for fair resource allocation where the problem of computing equilibrium prices relies on complete information of user attributes, which are typically unavailable in practice. Motivated by this practical limitation, we study a modified online incomplete information variant of Fisher markets, where users with privately known utility and budget parameters, drawn i.i.d. from a distribution, arrive sequentially. In this novel market, we establish the limitations of static pricing and design dynamic posted-price algorithms with improved guarantees. Our main result is a posted-price algorithm that solely relies on revealed preference (RP) feedback, i.e., observations of user consumption, achieving the best-known guarantees for first-order algorithms in the RP setting while providing a regret analysis of a fairness-promoting logarithmic objective, unlike typical non-negative and bounded efficiency-promoting objectives in online learning.

Jiaqi Zhang—Designing and learning from large-scale interventions

Advances in recent technologies have enabled the possibility to perform and measure the effects of external interventions in many fields. For example, it is now possible to target and perturb single or combinatorial genes in living cells. These provide a unique opportunity to study underlying causal mechanisms behind complex systems, such as the regulatory mechanisms behind cell states. In our work, we focus on three key aspects that have arisen from these new capabilities: (1) how to define and learn the causal programs governing high-dimensional or perceptual data; (2) how to model interventional effects in scenarios where the measurements are incomplete; and (3) how to design the next experiments if one is interested in achieving a desired state. For (1), we establish new causal disentanglement theories that guarantee identifiability of the underlying causal programs, given sufficient samples and regularizing conditions. For (2), we develop a scalable algorithm that models the interventional effect using the discrepancy between distributions. It can capture nuanced changes at the sample level and extrapolate to identify non-additive combinatorial perturbations. Lastly, for (3), we discuss our proposals borrowing ideas from extreme event theory for finding desirable interventions more efficiently. 

Session 2 Poster Presenters and Titles
Friday, October 11, 8:30-9:45am Duffield Hall Atrium