Max Springer

Max Springer

Applied Mathematician at the University of Maryland

Publications

Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost

Published in ICML, 2023

Clustering is a fundamental building block of modern statistical analysis pipelines. Fair clustering has seen much attention from the machine learning community in recent years. We are some of the first to study fairness in the context of hierarchical clustering, after the results of Ahmadian et al. from NeurIPS in 2020. We evaluate our results using Dasgupta’s cost function, perhaps one of the most prevalent theoretical metrics for hierarchical clustering evaluation. Our work vastly improves the previous $O(n^{5/6} polylog(n))$ fair approximation for cost to a near polylogarithmic $O(n^\delta polylog(n))$ fair approximation for any constant $\delta \in (0,1)$. This result establishes a cost-fairness tradeoff and extends to broader fairness constraints than the previous work. We also show how to alter existing hierarchical clusterings to guarantee fairness and cluster balance across any level in the hierarchy.

Recommended citation: Knittel et al. (2023). "Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost" (ICML 2023)

Analysis of a Learning Based Algorithm for Budget Pacing

Published in AAMAS, 2023

In this paper, we analyze a natural learning algorithm for uniform pacing of advertising budgets, equipped to adapt to varying ad sale platform conditions. On the demand side, advertisers face a fundamental technical challenge in automating bidding in a way that spreads their allotted budget across a given campaign subject to hidden, and potentially dynamic, cost functions. This automation and calculation must be done in runtime, implying a necessarily low computational cost for the high frequency auction rate. Advertisers are additionally expected to exhaust nearly all of their sub-interval (by the hour or minute) budgets to maintain budgeting quotas in the long run. To resolve this challenge, our study analyzes a simple learning algorithm that adapts to the latent cost function of the market and learns the optimal average bidding value for a period of auctions in a small fraction of the total campaign time, allowing for smooth budget pacing in real-time. We prove our algorithm is robust to changes in the auction mechanism, and exhibits a fast convergence to a stable average bidding strategy. The algorithm not only guarantees that budgets are nearly spent in their entirety, but also smoothly paces bidding to prevent early exit from the campaign and a loss of the opportunity to bid on potentially lucrative impressions later in the period.

Recommended citation: MohammadTaghi Hajiaghayi and Max Springer. (2022). "Analysis of a Learning Based Algorithm for Budget Pacing" (AAMAS 2023)

Optimal Sparse Recovery with Decision Stumps

Published in AAAI, 2022

Decision trees are widely used for their low computational cost, good predictive performance, and ability to assess the importance of features. Though often used in practice for feature selection, the theoretical guarantees of these methods are not well understood. We here obtain a tight finite sample bound for the feature selection problem in linear regression using single-depth decision trees. We examine the statistical properties of these “decision stumps” for the recovery of the $s$ active features from $p$ total features. Our analysis provides tight sample performance guarantees on high-dimensional sparse systems which align with the finite sample bound of $O(s \log p)$ as obtained by Lasso, improving upon previous bounds for both the median and optimal splitting criteria. Our results extend to the non-linear regime as well as arbitrary sub-Gaussian distributions, demonstrating that tree based methods attain strong feature selection properties under a wide variety of settings and further shedding light on the success of these methods in practice. As a byproduct of our analysis, we show that we can provably guarantee recovery even when the number of active features $s$ is unknown, addressing a well-known limitation of previous results. We further validate our theoretical results and proof methodology using computational experiments.

Recommended citation: Banihashem. et al (2023), Optimal Sparse Recovery with Decision Stumps (AAAI 2023)

Online Algorithms for the Santa Claus Problem

Published in NeurIPS, 2022

The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment exists in the worst case. However, we show that even for arbitrary items, if their arrival order is random, then for any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $\Omega(\log n / \varepsilon^2)$ to every agent. We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even with random arrival order.

Recommended citation: Hajiaghayi. et al (2022), Online Algorithms for the Santa Claus Problem (NeurIPS 2022)

A Machine-Learning Approach for Predicting Impaired Consciousness in Absence Epilepsy

Published in Annals of Clinical and Translational Neurology, 2022

Behavior during 3–4 Hz spike-wave discharges (SWDs) in absence epilepsy can vary from obvious behavioral arrest to no detectible deficits. Knowing if behavior is impaired is crucial for clinical care but may be difficult to determine without specialized behavioral testing, often inaccessible in practice. We aimed to develop a pure electroencephalography (EEG)-based machine-learning method to predict SWD-related behavioral impairment. Our classification goals were 100% predictive value, with no behaviorally impaired SWDs misclassified as spared; and maximal sensitivity. First, using labeled data with known behavior (130 SWDs in 34 patients), we extracted EEG time, frequency domain, and common spatial pattern features and applied support vector machines and linear discriminant analysis to classify SWDs as spared or impaired. We evaluated 32 classification models, optimized with 10-fold cross-validation. We then generalized these models to unlabeled data (220 SWDs in 41 patients), where behavior during individual SWDs was not known, but observers reported the presence of clinical seizures. For labeled data, the best classifier achieved 100% spared predictive value and 93% sensitivity. The best classifier on the unlabeled data achieved 100% spared predictive value, but with a lower sensitivity of 35%, corresponding to a conservative classification of 8 patients out of 23 as free of clinical seizures. Our findings demonstrate the feasibility of machine learning to predict impaired behavior during SWDs based on EEG features. With additional validation and optimization in a larger data sample, applications may include EEG-based prediction of driving safety, treatment adjustment, and insight into mechanisms of impaired consciousness in absence seizures.

Recommended citation: Springer, M. et al (2022), A machine-learning approach for predicting impaired consciousness in absence epilepsy. Ann Clin Transl Neurol. https://doi.org/10.1002/acn3.51647

The pulse: transient fMRI signal increases in subcortical arousal systems during transitions in attention.

Published in NeuroImage, 2021

Studies of attention emphasize cortical circuits for salience monitoring and top-down control. However, subcorti- cal arousal systems have a major influence on dynamic cortical state. We hypothesize that task-related increases in attention begin with a “pulse” in subcortical arousal and cortical attention networks, which are reflected indi- rectly through transient fMRI signals. We conducted general linear model and model-free analyses of fMRI data from two cohorts and tasks with mixed block and event-related design. 46 adolescent subjects at our center and 362 normal adults from the Human Connectome Project participated. We identified a core shared network of transient fMRI increases in subcortical arousal and cortical salience/attention networks across cohorts and tasks. Specifically, we observed a transient pulse of fMRI increases both at task block onset and with individual task events in subcortical arousal areas including midbrain tegmentum, thalamus, nucleus basalis and striatum; corti- cal-subcortical salience network regions including the anterior insula/claustrum and anterior cingulate cortex/ supplementary motor area; in dorsal attention network regions including dorsolateral frontal cortex and inferior parietal lobule; as well as in motor regions including cerebellum, and left hemisphere hand primary motor cor- tex. The transient pulse of fMRI increases in subcortical and cortical arousal and attention networks was consis- tent across tasks and study populations, whereas sustained activity in these same networks was more variable. The function of the transient pulse in these networks is unknown. However, given its anatomical distribution, it could participate in a neuromodulatory surge of activity in multiple parallel neurotransmitter systems facilitating dynamic changes in conscious attention.

Recommended citation: Rong Li, Jun Hwan Ryu, Peter Vincent, Max Springer, Dan Kluger, Erik A. Levinsohn, Yu Chen, Huafu Chen and Hal Blumenfeld. (2021). "The pulse: transient fMRI signal increases in subcortical arousal systems during transitions in attention." Neuroimage, in press.