ACO Student Seminar

Abstract: This talk presents a quantum algorithm for Bayesian posterior sampling, developed in collaboration with researchers at the Bank for International Settlements, the Central Bank of Chile, and the University of Chicago. The approach encodes discretized posterior distributions into quantum states, with measurement producing samples for Monte Carlo estimation. While the method does not currently yield a computational advantage over classical approaches like Markov Chain Monte Carlo, it provides a simulation-based implementation of Bayesian inference in Qiskit and highlights key bottlenecks, particularly in state preparation. The talk concludes by discussing challenges in high-dimensional uncertainty quantification relevant to financial risk measurement. Joint work with Jon Frost, Carlos Madeira, and Harald Uhlig.

Abstract: The problem of Empirical Risk Minimization (ERM), stated roughly as optimizing a linear objective over a product space of convex constraints, is a fundamental problem in machine learning and optimization, and can also be seen as a generalization of linear programming.

Breakthroughs in interior point methods have given us near linear time algorithms for linear programming when our constraint matrix is tall and dense; however, the techniques use complex Lee-Sidford machinery, and it is still wide open whether those can be extended to ERM despite years of active research. We give the first near linear time algorithm for tall dense ERM through a different, more combinatorial method. To do so, we present a data structure for adaptive matrix sparsification, which can be seen as extending spectral sparsification to general matrices.

This is joint work with Yang P. Liu, Richard Peng, Colin Tang, and Junzhao Yang.

Abstract: Tutte’s theorem states that every 4-connected graph with no $K_{3,3}$ minor has a Hamilton cycle. Wigal and Yu proved that every internally 4-connected graph $G$ with no $K_{3,3}$ minor has a cycle of length at least $2/3 |V(G)|$. For $t$ at least 4, it was shown by Chen, Yu, and Zang that all 3-connected graphs with no $K_{3,t}$ minor have a cycle of length at least $\alpha(t) |V(G)|^\beta$ for some constants $\alpha(t), \beta >0$. It is believed that a linear lower bound should hold for all internally 4-connected graphs. In this talk, we will review some related results and give an overview of our progress towards establishing a linear lower bound. This work is joint with Tianchi Yang and Xingxing Yu.

TLDR: Small changes in the design of a college admissions mechanism can have non-monotonic, counter-intuitive effects on admitted student quality, especially with competition between multiple universities.

Abstract: We study how the design of admissions policies affects the ability of students admitted to universities. In our model, applicants have a multi-dimensional ability from the point of view of the university, which is a combination of a “type” and of “soft skills.” Universities may differ in how they evaluate quality and have differing preferences on type and soft skills. Then, university admissions rely on a single noisy aggregate signal, such as a test score, that may not fully align with the university's preferences, and a university evaluates applicants through the posterior expectations of their preference metric given the observed signal. Our main results highlight that the design of good admission policies can be counter-intuitive. Assuming there's only a single university, when holding the number of qualified applicants constant, increasing the usefulness of the signal (by aligning it more closely with the university preferences) leads to a worse average type and soft skill for admitted students. Further, a university cannot affect the composition of students that are strong on type versus soft skills by changing their preferences. The picture becomes even more complicated under competition between as few as two universities: self-selection effects among students admitted to both universities can lead to part of the applicant pool switching which university they prefer, even under small changes in the design of the noisy signal. This can, in particular, lead to sudden and non-monotonic loss in the quality of admitted students when changing the alignment between signal and university preferences. Further, a university can get more students by increasing their selectivity. Joint work with Diptangshu Sen, Juba Ziani. 

Abstract: We present a sparse augmented Lagrangian (AL) method for solving large-scale linear programs (LPs). Our proposed method solves a sequence of R-LPs, i.e., restrictions of the LP to the simplex $\Delta_R=\{x\in\R_{+}^{n} : e^T x ≤ R\}$, which compactifies the nonnegative orthant and hence makes the Frank--Wolfe (FW) linear minimization oracle well-defined. Each R-LP is solved by LP-AL, a fixed-radius inexact AL method whose subproblems, namely, convex quadratic problems over the simplex, are approximately solved by an enhanced Frank--Wolfe (EFW) method that alternates support-restricted accelerated composite gradient steps with full FW steps and is warm-started from the previous outer iterate. The outer loop of LP-AL performs a full multiplier update and geometrically increases the penalty parameter \beta until a joint criterion on the primal residual and the FW gap is satisfied. It is shown that LP-AL performs at most a logarithmic number of penalty updates and that its total number of inner iterations is bounded by $O(\varepsilon_p^{-2}+\varepsilon_g^{-2})$, where $\varepsilon_p$ and $\varepsilon_g$ denote the primal-feasibility and FW-gap tolerances, respectively.

Since a radius containing an optimal solution of the LP is generally not known in advance, a variable-radius method (VR-LP) is also presented, which calls LP-AL on a doubling sequence of radii and stops as soon as an approximate complementarity measure is sufficiently small. It is shown that VR-LP terminates in a number of stages that is logarithmic in the ratio of a solution radius to the initial one. Finally, computational results on synthetic and benchmark LP instances, obtained with both CPU and GPU implementations, are presented showing that our method is competitive with simplex, interior-point, PDLP, and other first-order LP solvers.

This paper is joint work with Renato D.C. Monteiro and Anton J. Kleywegt.

Abstract: TBD

Abstract: TBD

Abstract: TBD

Abstract: TBD