<div dir="ltr"><div dir="ltr"><div>Please join us for the tenth and last theory lunch of the quarter tomorrow!</div><div><br></div><div><div dir="auto"><b>Time: </b>Wednesday, May 28, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> <span style="font-family:Arial;font-size:10pt">Fan Yao</span></div></div><div dir="auto"><br></div><div><b>Title: </b><span style="font-family:Arial;font-size:10pt">Steering multi-agent learning via single-agent poisoning</span></div><div><span style="font-family:Arial;font-size:10pt"><br></span></div><div><span style="font-family:Arial;font-size:10pt"><b>Abstract: </b></span><span style="font-family:Arial;font-size:10pt">We investigate the robustness of multi-agent learning in strongly monotone games with bandit feedback. While previous research has developed learning algorithms that achieve last-iterate convergence to the unique Nash equilibrium (NE) at a polynomial rate, we demonstrate that all such algorithms are vulnerable to adversaries capable of poisoning even a single agent's utility observations. Specifically, we propose an attacking strategy such that for any given time horizon , the adversary can mislead any multi-agent learning algorithm to converge to a point other than the unique NE with a corruption budget that grows sublinearly in . To further understand the inherent robustness of these algorithms, we characterize the fundamental trade-off between convergence speed and the maximum tolerable total utility corruptions for two example algorithms, including the state-of-the-art one. Our theoretical and empirical results reveal an intrinsic efficiency-robustness trade-off: the faster an algorithm converges, the more vulnerable it becomes to utility poisoning attacks. To the best of our knowledge, this is the first work to identify and characterize such a trade-off in the context of multi-agent learning.</span></div></div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Tue, May 20, 2025 at 3:00 PM Alec Sun <<a href="mailto:alecsun@uchicago.edu">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Please join us for the ninth theory lunch of the quarter tomorrow!</div><div><br></div><div><div dir="auto"><b>Time: </b>Wednesday, May 21, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> <span style="font-family:Arial;font-size:10pt">Soham Bonnerjee</span></div></div><div dir="auto"><br></div><div><b>Title: </b><span style="font-family:Arial;font-size:10pt">How Private is Your Attention? Bridging Privacy with In-Context Learning</span></div><div><span style="font-family:Arial;font-size:10pt"><br></span></div><div><span style="font-family:Arial;font-size:10pt"><b>Abstract: </b></span><span style="font-family:Arial;font-size:10pt">In-context learning (ICL)—the ability of transformer-based models to perform new tasks from examples provided at inference time—has emerged as a hallmark of modern language models. While recent works have investigated the mechanisms underlying ICL, its feasibility under formal privacy constraints remains largely unexplored. In this paper, we propose a differentially private pretraining algorithm for linear attention heads and present the first theoretical analysis of the privacy–accuracy trade-off for ICL in linear regression. Our results characterize the fundamental tension between optimization and privacy-induced noise, formally capturing behaviors observed in private training via iterative methods. Additionally, we show that our method is robust to adversarial perturbations of training prompts, unlike standard ridge regression. All theoretical findings are supported by extensive simulations across diverse settings.</span></div><div><span style="font-family:Arial;font-size:10pt"><br></span></div><div><span style="font-family:Arial;font-size:10pt"><b>Note: </b>The final theory lunch of the quarter will be May 28.</span></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 13, 2025 at 12:07 AM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div>Please join us for the eighth theory lunch of the quarter tomorrow!</div><div><br></div><div><div dir="auto"><b>Time: </b>Wednesday, May 14, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> Yuwei Cheng</div></div><div dir="auto"><br></div><div><b>Title: </b><span style="font-family:Arial;font-size:10pt">Personalized Ad Impact with Contextual Markov Decision Processes: Long-Term Poisson Rewards and Near-Optimal Bidding Algorithms</span></div><div><span style="font-family:Arial;font-size:10pt"><br></span></div><div><span style="font-family:Arial;font-size:10pt"><b>Abstract: </b></span><span style="font-family:Arial;font-size:10pt">Online advertising platforms use automated auctions to connect advertisers with potential customers, requiring effective bidding strategies to maximize profits. Accurate ad impact estimation requires considering three key factors: delayed and long-term effects, cumulative ad impacts such as reinforcement or fatigue, and customer heterogeneity. However, these effects are often not jointly addressed in previous studies. To capture these factors, we model ad bidding as a Contextual Markov Decision Process (CMDP) with long-term Poisson rewards. For efficient estimation, we propose a two-stage maximum likelihood estimator combined with data-splitting strategies, ensuring controlled estimation error based on the first-stage estimator's (in)accuracy. Building on this, we design a reinforcement learning algorithm to derive efficient personalized bidding strategies. This approach achieves a near-optimal regret bound of $\Tilde{\mathcal{O}}(dH^2\sqrt{T})$, where $d$ is the contextual dimension, $H$ is the number of rounds, and $T$ is the number of customers.</span></div></div><div><font face="Arial"><span style="font-size:13.3333px"><br></span></font><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 6, 2025 at 11:23 AM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Please join us for the seventh theory lunch of the quarter tomorrow!</div><div><br></div><div><div dir="auto"><b>Time: </b>Wednesday, May 7, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> Mohammad Reza Aminian</div></div><div dir="auto"><br></div><div><b>Title: </b>Stationary Online Contention Resolution Schemes
<br><br><b>Abstract: </b>[See attachment]</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Apr 28, 2025 at 4:36 PM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Please join us for the sixth theory lunch of the quarter tomorrow. Note the change in day of the week, time, and location just for this week!</div><div><br></div><div><b>Time: </b>Tuesday, April 29, 2025, 12:30pm-1:30pm in JCL 298</div><div><br></div><div><b>Speaker: </b>Aditya Prasad</div><div dir="ltr"><br></div><div dir="ltr"><b>Title:</b> Supermodular Combinatorial Contracts<br><br><b>Abstract: </b>We present combinatorial contracts in the single-agent combinatorial action model of [Duetting, Ezra, Feldman, Kesselheim, FOCS 2021] and the multi-agent model of [Duetting, Ezra, Feldman, Kesselheim, STOC 2023]. For the single-agent combinatorial action setting, we give a poly-time algorithm for finding the optimal contract, provided that the agent’s demand problem can be solved efficiently and there are poly-many breakpoints in the agent’s demand. This implies an efficient algorithm for supermodular rewards. For the multi-agent setting, our focus is on settings with supermodular rewards. We give an additive PTAS for a natural class of graph-based rewards when the agents have identical costs, and show that even in this special case it’s NP-hard to obtain any finite multiplicative approximation, or an additive FPTAS.</div><div dir="ltr"><br></div><div dir="ltr"><b>Note: </b>Theory lunch will return to its normal time on Wednesday 12pm for the rest of the quarter.<br><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Apr 22, 2025 at 12:51 PM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Please join us for the fifth theory lunch of the quarter tomorrow!</div><div><br></div><div><div dir="auto"><b>Time: </b>Wednesday, April 23, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> Yifan Wu</div><div dir="auto"><br><b>Title: </b>Calibration Error for Decision Making</div><div dir="auto"><br><b>Abstract</b>: Calibration allows predictions to be reliably interpreted as probabilities by decision makers. We propose a decision-theoretic calibration error, the Calibration Decision Loss (CDL), defined as the maximum improvement in decision payoff obtained by calibrating the predictions, where the maximum is over all payoff-bounded decision tasks. Vanishing CDL guarantees the payoff loss from miscalibration vanishes simultaneously for all downstream decision tasks. We show separations between CDL and existing calibration error metrics, including the most well-studied metric Expected Calibration Error (ECE). Our main technical contribution is a new efficient algorithm for online calibration that achieves near-optimal O(logT / \sqrt{T}) expected CDL, bypassing the Ω(T^{−0.472}) lower bound for ECE by Qiao and Valiant (2021).</div><div dir="auto"><br></div><div><b>Note: </b>Next week JCL 390 and 298 are used for other events on Wednesday, so theory lunch will happen on <b>Tuesday, April 29, 2025, 12pm-1pm in JCL 298</b>.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Apr 16, 2025 at 11:15 AM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Please join us for the fourth theory lunch of the quarter today!</div><div dir="auto"><br></div><div dir="auto"><div dir="auto"><b>Time: </b>Wednesday, April 16, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> Andrzej Kaczmarczyk</div><div dir="auto"><br><b>Title: </b>Learning Real-Life Approval Elections</div><div dir="auto"><br><b>Abstract</b>: We study how to learn an approval election, i.e., an election in which each voter selects which candidates they approve. Specifically, we focus on the independent approval model (IAM), where each candidate has its own approval probability and is approved independently of the other ones. We propose algorithms for learning IAMs and their mixtures from data, using either maximum likelihood estimation or Bayesian learning. We then apply these algorithms to a large set of real-life elections. In particular, we find that single-component models are rarely sufficient to capture the complexity of real-life data, whereas their mixtures perform well.</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Apr 16, 2025 at 11:01 AM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Please join us for the fourth <span>theory lunch</span> of the quarter today!</div><div dir="auto"><br></div><div dir="auto"><div dir="auto"><b>Time: </b>Wednesday, April 16, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker:</b> Andrzej Kaczmarczyk</div><div dir="auto"><br><b>Title: </b>Learning Real-Life Approval Elections</div><div dir="auto"><br><b>Abstract</b>: We study how to learn an approval election, i.e., an election in which each voter selects which candidates they approve. Specifically, we focus on the independent approval model (IAM), where each candidate has its own approval probability and is approved independently of the other ones. We propose algorithms for learning IAMs and their mixtures from data, using either maximum likelihood estimation or Bayesian learning. We then apply these algorithms to a large set of real-life elections. In particular, we find that single-component models are rarely sufficient to capture the complexity of real-life data, whereas their mixtures perform well.</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Apr 8, 2025 at 1:05 PM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Please join us for the third theory lunch of the quarter tomorrow!</div><div dir="auto"><br></div><div dir="auto"><div dir="auto"><b>Time: </b>Wednesday, April 9, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker: </b><span style="font-family:Arial;font-size:10pt">Subhodh Kotekal</span></div><div dir="auto"><br><b>Title: </b><span style="font-family:Arial;font-size:10pt">Variance estimation in compound decision theory under boundedness</span></div><div dir="auto"><br><b>Abstract</b>: <span style="font-family:Arial;font-size:10pt">The normal means model is often studied under the assumption of a known variance. However, ignorance of the variance is a frequent issue in applications and basic theoretical questions still remain open in this setting. This article establishes that the sharp minimax rate of variance estimation in square error is $(\log\log n/\log n)^2$ under arguably the most mild assumption imposed for identifiability: bounded means. The rate-optimal estimator proposed in this article achieves the optimal rate by estimating $O\left(\log n/\log\log n\right)$ cumulants and leveraging a variational representation of the noise variance in terms of the cumulants of the data distribution. The minimax lower bound involves a moment matching construction.</span></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Apr 1, 2025 at 1:38 PM Alec Sun <<a href="mailto:alecsun@uchicago.edu" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div>Please join us for the second theory lunch of the quarter tomorrow!</div><div dir="auto"><br></div><div dir="auto"><div dir="auto"><b>Time: </b>Wednesday, April 2, 2025, 12pm-1pm in JCL 390</div><div dir="auto"> <br><b>Speaker: </b>Dravy Sharma</div><div dir="auto"><br><b>Title: </b>Provable tuning of deep learning model hyperparameters</div><div dir="auto"><br><b>Abstract</b>: Modern machine learning algorithms, especially deep learning-based techniques, typically involve careful hyperparameter tuning to achieve the best performance. Despite the surge of intense interest in practical techniques like Bayesian optimization and random search-based approaches to automating this laborious and compute-intensive task, the fundamental learning-theoretic complexity of tuning hyperparameters for deep neural networks is poorly understood. Inspired by this glaring gap, we initiate the formal study of hyperparameter tuning complexity in deep learning under a powerful data-driven paradigm. A major difficulty is that the utility function as a function of the hyperparameter is very volatile and furthermore, it is given implicitly by an optimization problem over the model parameters. To tackle this challenge, we employ subtle concepts from differential/algebraic geometry and constrained optimization to show that the learning-theoretic complexity of the corresponding family of utility functions is bounded. We instantiate our results and provide sample complexity bounds for concrete applications—tuning a hyperparameter that interpolates neural activation functions and setting the kernel parameter in graph neural networks. The talk is based on joint work with Nina Balcan and Anh Nguyen.</div><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Tue, Mar 25, 2025, 4:52 PM Alec Sun <<a href="mailto:alecsun@uchicago.edu" rel="noreferrer noreferrer" target="_blank">alecsun@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Please join us for the first theory lunch of the quarter tomorrow!<div> </div><div><b>Time: </b>Wednesday, March 26, 2025, 12pm-1pm in JCL 390</div><div> <br><b>Speaker: </b>Olga Medrano</div><div><br><b>Title: </b>Short Visit to Regularity Lemmas</div><div><br><b>Abstract: </b>In this expository talk, we will overview Szémerédi’s regularity lemma, a result from extremal graph theory with different applications. We will then mention some considerations about this result, including the existence of irregular pairs in the partitions obtained, as well as the large size of those partitions. Time permitting, we very briefly reflect on how the proof of Szémerédi's regularity lemma is not algorithmic and mention a few lines of work that were focused on finding algorithms to output regular partitions. In the second half of this talk, we will describe versions of this lemma over certain classes of graphs. In particular, we state both the Ultra-strong regularity lemma, which works for the class of graphs of bounded VC dimension, and the Stable regularity lemma, which works for the class of k-edge stable graphs (namely, those not containing a bi-induced bipartite graph). We conclude by acknowledging that algorithmic questions for both results remain open.</div></div>
</blockquote></div></div></div>
</blockquote></div></div>
</blockquote></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div></div>
</div>
</div>
</blockquote></div></div>
</blockquote></div></div></div>
</blockquote></div></div>
</blockquote></div></div>