This paper considers coresets for the robust $k$-medians problem with $m$ outliers, and new constructions in various metric spaces are obtained. Specifically, for metric spaces with a bounded VC or doubling dimension $d$, the coreset size is $O(m) + \tilde{O}(kd\varepsilon^{-2})$, which is optimal up to logarithmic factors. For Euclidean spaces, the coreset size is $O(m\varepsilon^{-1}) + \tilde{O}(\min\{k^{4/3}\varepsilon^{-2}, k\varepsilon^{-3}\})$, improving upon a recent result by Jiang and Lou (ICALP 2025). These results also extend to robust $(k,z)$-clustering, yielding, for VC and doubling dimension, a coreset size of $O(m) + \tilde{O}(kd\varepsilon^{-2z})$ with the optimal linear dependence on $m$. This extended result improves upon the earlier work of Huang et al. (SODA 2025). The techniques introduce novel dataset decompositions, enabling chaining arguments to be applied jointly across multiple components.

We investigate a generalized form of submodular maximization, referred to as $k$-submodular maximization, with applications across the domains of social networks and machine learning. In this work, we propose the multilinear extension of $k$-submodular functions and unified Frank-Wolfe-type frameworks based on that. This continuous framework accommodates 1) monotone or non-monotone functions, and 2) various constraint types including matroid constraints, knapsack constraints, and their combinations. Notably, we attain an asymptotically optimal $1/2$-approximation for monotone $k$-submodular maximization problems with knapsack constraints, surpassing previous $1/3$-approximation results, and a factor-$1/3$ approximation for non-monotone $k$-submodular maximization problems with knapsack constraints and matroid constraints which outperforms previous $0.245$-approximation results. The foundation for our analysis stems from new insights into specific linear and monotone properties pertaining to the multilinear extension.

The rapid rise of Generative AI (GenAI) tools has sparked debate over their role in complementing or replacing human workers across job contexts. We present a mathematical framework that models jobs, workers, and worker-job fit, introducing a novel decomposition of skills into decision-level and action-level subskills to reflect the complementary strengths of humans and GenAI. We analyze how changes in subskill abilities affect job success, identifying conditions for sharp transitions in success probability. We also establish sufficient conditions under which combining workers with complementary subskills significantly outperforms relying on a single worker. This explains phenomena such as productivity compression, where GenAI assistance yields larger gains for lower-skilled workers. We demonstrate the framework’s practicality using data from O*NET and Big-Bench Lite, aligning real-world data with our model via subskill-division methods. Our results highlight when and how GenAI complements human skills, rather than replacing them.

Meritocratic systems, from admissions to hiring, aim to impartially reward skill and effort. Yet persistent disparities across race, gender, and class challenge this ideal. Some attribute these gaps to structural inequality; others to individual choice. We develop a game-theoretic model in which candidates from different socioeconomic groups differ in their perceived post-selection value—shaped by social context and, increasingly, by AI-powered tools offering personalized career or salary guidance. Each candidate strategically chooses effort, balancing its cost against expected reward; effort translates into observable merit, and selection is based solely on merit. We characterize the unique Nash equilibrium in the large-agent limit and derive explicit formulas showing how valuation disparities and institutional selectivity jointly determine effort, representation, social welfare, and utility. We further propose a cost-sensitive optimization framework that quantifies how modifying selectivity or perceived value can reduce disparities without compromising institutional goals. Our analysis reveals a perception-driven bias: when perceptions of post-selection value differ across groups, these differences translate into rational differences in effort, propagating disparities backward through otherwise "fair" selection processes. While the model is static, it captures one stage of a broader feedback cycle linking perceptions, incentives, and outcomes—bridging rational-choice and structural explanations of inequality by showing how techno-social environments shape individual incentives in meritocratic systems.

We study the robust geometric median problem in Euclidean space $\mathbb{R}^d$, with a focus on coreset construction. A coreset is a compact summary of a dataset $P$ of size $n$ that approximates the robust cost for all centers $c$ within a multiplicative error $\varepsilon$. Given an outlier count $m$, we construct a coreset of size $\tilde{O}(\varepsilon^{-2} \cdot \min \\{ \varepsilon^{-2}, d \\})$ when $n \geq 4m$, eliminating the $O(m)$ dependency present in prior work [Huang et al., 2022 & 2023]. For the special case of $d = 1$, we achieve an optimal coreset size of $\tilde{\Theta}(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$, revealing a clear separation from the vanilla case studied in [Huang et al., 2023; Afshani and Chris, 2024]. Our results further extend to robust $(k,z)$-clustering in various metric spaces, eliminating the $m$-dependence under mild data assumptions. The key technical contribution is a novel non-component-wise error analysis, enabling substantial reduction of outlier influence, unlike prior methods that retain them. Empirically, our algorithms consistently outperform existing baselines in terms of size-accuracy tradeoffs and runtime, even when data assumptions are violated across a wide range of datasets.

We study the problem of constructing coresets for $(k, z)$-clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of a coreset is inherently challenging, as the true underlying dataset is unobserved. To address this, we investigate coreset construction using surrogate error metrics that are tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new error metric that more closely aligns with the true cost. Although our metric is defined independent of the noise distribution, it enables approximation guarantees that scale with the noise level. We design a coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an $\varepsilon$-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metrics. In particular, we prove that the coreset size can improve by a factor of up to $\mathrm{poly}(k)$, where $n$ is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.

Designing small-sized coresets, which approximately preserve the costs of the solutions for large datasets, has been an important research direction for the past decade. We consider coreset construction for a variety of general constrained clustering problems. We introduce a general class of assignment constraints, including capacity constraints on cluster centers, and assignment structure constraints for data points (modeled by a convex body B ). We give coresets for clustering problems with such general assignment constraints that significantly generalize and improve known results. Notable implications include the first ε-coreset for capacitated and fair k-MEDIAN with m outliers in Euclidean spaces whose size is Õ (m + k2ε-4), generalizing and improving upon the prior bounds in [BCJ+ 22, HJLW23] (for capacitated k-MEDIAN, the coreset size bound obtained in [BCJ+22] is Õ (k3ε-6), and for k-MEDIAN with m outliers, the coreset size bound obtained in [HJLW23] is Õ (m + k3ε-5)), and the first ε-coreset of size poly(kε-1) for fault-tolerant clustering for various types of metric spaces.

The$(k, z)$-Clusteringproblem in Euclidean space$\mathbb {R}^{d}$has been extensively studied. Given the scale of data involved, compression methods for the Euclidean$(k, z)$-Clusteringproblem, such as data compression and dimension reduction, have received significant attention in the literature. However, the space complexity of the clustering problem, specifically, the number of bits required to compress the cost function within a multiplicative error$\varepsilon $, remains unclear in existing literature. This paper initiates the study of space complexity for Euclidean$(k, z)$-Clusteringand offers both upper and lower bounds. Our space bounds are nearly tight whenkis constant, indicating that storing a coreset, a well-known data compression approach, serves as the optimal compression scheme. Furthermore, our lower bound result for$(k, z)$-Clusteringestablishes a tight space bound of$\Theta (n d)$for terminal embedding, wherenrepresents the dataset size. Our technical approach leverages new geometric insights for principal angles and discrepancy methods, which may hold independent interest.

The $(k, z)$-Clustering problem in Euclidean space $\mathbb{R}^d$ has been extensively studied. Given the scale of data involved, compression methods for the Euclidean $(k, z)$-Clustering problem, such as data compression and dimension reduction, have received significant attention in the literature. However, the space complexity of the clustering problem, specifically, the number of bits required to compress the cost function within a multiplicative error $\varepsilon$, remains unclear in existing literature. This paper initiates the study of space complexity for Euclidean $(k, z)$-Clustering and offers both upper and lower bounds. Our space bounds are nearly tight when $k$ is constant, indicating that storing a coreset, a well-known data compression approach, serves as the optimal compression scheme. Furthermore, our lower bound result for $(k, z)$-Clustering establishes a tight space bound of $Θ( n d )$ for terminal embedding, where $n$ represents the dataset size. Our technical approach leverages new geometric insights for principal angles and discrepancy methods, which may hold independent interest.

Accurate quantification of ecosystem water use efficiency (eWUE), defined as the ratio of gross primary production (GPP) and evapotranspiration (ET), is vital to deepen our understanding of global water and carbon cycles. However, the influence of varying abiotic and biotic factors on GPP and ET is still not thoroughly understood, and thus accurate estimation of GPP and ET is still challenging, which may introduce uncertainties into eWUE. Here, we applied the random forest (RF) machine learning model to directly estimate the 8-day observed eWUE collected from the 197 globally distributed flux sites involved in the FLUXNET2015 dataset. Additionally, the RF model was also intercompared with the widely used Moderate Resolution Imaging Spectroradiometer (MODIS) and Penman-Monteith-Leuning version 2 (PMLv2) products. Our results show that the RF model could well reproduce the 8-day observed eWUE, as indicated by the root mean square error (RMSE) = 1.01 g C Kg-1H2O, the coefficient of determination (R2) = 0.66, and the mean prediction error (Bias) = 0.00 g C Kg-1H2O. More importantly, the RF model showed considerable improvements over the MODIS and PMLv2 products in simulating 8-day eWUE, with decreasing the RMSE by 1.03 g C Kg-1H2O and 0.86 g C Kg-1H2O, increasing the R2by 0.65 and 0.49, and reducing the Bias by 0.64 g C Kg-1H2O and 0.32 g C Kg-1H2O, respectively. This study indicates a promising avenue for using machine learning models to simulate eWUE directly.

Constructing small-sized coresets for various clustering problems in different metric spaces has attracted significant attention for the past decade. A central problem in the coreset literature is to understand what is the best possible coreset size for (k,z)-clustering in Euclidean space. While there has been significant progress in the problem, there is still a gap between the state-of-the-art upper and lower bounds. For instance, the best known upper bound for k-means (z=2) is min{O(k3/2 ε−2),O(k ε−4)} [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS’22], while the best known lower bound is Ω(kε−2) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22]. In this paper, we make significant progress on both upper and lower bounds. For a large range of parameters (i.e., ε, k), we have a complete understanding of the optimal coreset size. In particular, we obtain the following results: (1) We present a new coreset lower bound Ω(k ε−z−2) for Euclidean (k,z)-clustering when ε ≥ Ω(k−1/(z+2)). In view of the prior upper bound Õz(k ε−z−2) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22], the bound is optimal. The new lower bound is surprising since Ω(kε−2) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22] is “conjectured” to be the correct bound in some recent works (see e.g., [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22; Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS’22]). Our new lower bound instance is a delicate construction with multiple clusters of points, which is a significant departure from the previous construction in [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22] that contains a single cluster of points. The new lower bound also implies improved lower bounds for (k,z)-clustering in doubling metrics. (2) For the upper bound, we provide efficient coreset construction algorithms for (k,z)-clustering with improved or optimal coreset sizes in several metric spaces. In particular, we provide an Õz(k2z+2/z+2 ε−2)-sized coreset, with a unfied analysis, for (k,z)-clustering for all z≥ 1 in Euclidean space. This upper bound improves upon the Õz(k2ε−2) upper bound by [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22] (when k≤ ε−1), and matches the recent independent results [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS’22] for k-median and k-means (z=1,2) and extends them to all z≥ 1.

Accurately quantifying ecosystem water use efficiency (WUE) is essential for advancing our understanding of carbon and water exchanges between the land surface and atmosphere. Routinely, WUE is estimated by first predicting gross primary production (GPP) and evapotranspiration (ET) and then calculating WUE as the ratio of GPP to ET. However, this approach can lead to amplified errors in WUE estimates due to uncertainties in GPP and ET predictions. Here, we proposed a novel random forest (RF)-based WUE estimation model, referred to as the DRF model, which directly predicts WUE as the targeted variable to improve WUE estimation. The DRF model was trained using a combination of remote sensing (RS), meteorological reanalysis, and digital elevation model (DEM) datasets, along with in situ WUE observations at 261 global flux tower sites from the FLUXNET2015 and AmeriFlux FLUXNET datasets. Moreover, the DRF model was intercompared with the routine WUE estimation method using the RF model (the IRF model) as well as the widely used Moderate-Resolution Imaging Spectroradiometer (MODIS) and Penman-Monteith–Leuning version 2 (PMLv2) products in WUE estimation. Our results demonstrated that the DRF model well-reproduced 8-day in situ WUE, with the root-mean-square error (RMSE) of 1.07 g C kg−1 H2O, the coefficient of determination ($R^{2}$) of 0.59, and the mean bias error (Bias) of 0.00 g C kg−1 H2O, and showed significant improvement over the IRF model with the RMSE of 1.20 g C kg−1 H2O,$R^{2}$of 0.50, and Bias of −0.09 g C kg−1 H2O. Moreover, the DRF model considerably outperformed the MODIS product (RMSE =1.93 g C kg−1 H2O,$R^{2} =0.01$, and Bias$= -0.49$g C kg−1 H2O) and the PMLv2 product (RMSE =1.70 g C kg−1 H2O,$R^{2} =0.22$, and Bias =0.25 g C kg−1 H2O). Finally, the DRF model better captured seasonal fluctuations of in situ WUE than the other three models/products. Our study indicates that the DRF model is a promising alternative to routine WUE estimation methods and has the potential to produce more accurate global WUE estimates in future studies.

We consider the problem of subset selection where one is given multiple rankings of items and the goal is to select the highest "quality" subset. Score functions from the multiwinner voting literature have been used to aggregate rankings into quality scores for subsets. We study this setting of subset selection problems when, in addition, rankings may contain systemic or unconscious biases toward a group of items. For a general model of input rankings and biases, we show that requiring the selected subset to satisfy group fairness constraints can improve the quality of the selection with respect to unbiased rankings. Importantly, we show that for fairness constraints to be effective, different multiwinner score functions may require a drastically different number of rankings: While for some functions, fairness constraints need an exponential number of rankings to recover a close-to-optimal solution, for others, this dependency is only polynomial. This result relies on a novel notion of "smoothness" of submodular functions in this setting that quantifies how well a function can "correctly" assess the quality of items in the presence of bias. The results in this paper can be used to guide the choice of multiwinner score functions for the subset selection setting considered here; we additionally provide a tool to empirically enable this.

We consider the problem of constructing small coresets for $k$-Median in Euclidean spaces. Given a large set of data points $P\subset \mathbb{R}^d$, a coreset is a much smaller set $S\subset \mathbb{R}^d$, so that the $k$-Median costs of any $k$ centers w.r.t. $P$ and $S$ are close. Existing literature mainly focuses on the high-dimension case and there has been great success in obtaining dimension-independent bounds, whereas the case for small $d$ is largely unexplored. Considering many applications of Euclidean clustering algorithms are in small dimensions and the lack of systematic studies in the current literature, this paper investigates coresets for $k$-Median in small dimensions. For small $d$, a natural question is whether existing near-optimal dimension-independent bounds can be significantly improved. We provide affirmative answers to this question for a range of parameters. Moreover, new lower bound results are also proved, which are the highest for small $d$. In particular, we completely settle the coreset size bound for $1$-d $k$-Median (up to log factors). Interestingly, our results imply a strong separation between $1$-d $1$-Median and $1$-d $2$-Median. As far as we know, this is the first such separation between $k=1$ and $k=2$ in any dimension.

We study the power of uniform sampling for $k$-Median in various metric spaces. We relate the query complexity for approximating $k$-Median, to a key parameter of the dataset, called the balancedness $\beta \in (0, 1]$ (with $1$ being perfectly balanced). We show that any algorithm must make $\Omega(1 / \beta)$ queries to the point set in order to achieve $O(1)$-approximation for $k$-Median. This particularly implies existing constructions of coresets, a popular data reduction technique, cannot be query-efficient. On the other hand, we show a simple uniform sample of $\mathrm{poly}(k \epsilon^{-1} \beta^{-1})$ points suffices for $(1 + \epsilon)$-approximation for $k$-Median for various metric spaces, which nearly matches the lower bound. We conduct experiments to verify that in many real datasets, the balancedness parameter is usually well bounded, and that the uniform sampling performs consistently well even for the case with moderately large balancedness, which justifies that uniform sampling is indeed a viable approach for solving $k$-Median.

Accurate quantification of terrestrial gross primary production (GPP) is essential for enhancing our in-depth understanding of the global carbon budget and climate change [1] [2] . The two-leaf light use efficiency (TL-LUE) model, considering more deeply the disparities of photosynthesis capacity between sunlit and shaded leaves, has been proven to be a more efficient and potent approach than the big-leaf light use efficiency (BL-LUE) model for global GPP simulations [3] . However, the TL-LUE model is theoretically applicable for sunny days and fails to reflect the real configuration of the canopy under overcast and cloudy days, since the direct radiation could be shaded by clouds and thus all the leaves within the canopy are in reality shaded leaves (i.e., no sunlit leaves should exist). This mismatch between the theory and reality could definitely introduce a certain degree of systematic errors into the GPP simulations by the TL-LUE model. Here, we proposed a revised two-leaf light use efficiency (RTL-LUE) model for improving GPP estimation through better quantifying the sunlit and shaded leaf area index (LAI) under different sky conditions.

Accurate quantification of gross primary production (GPP) in agroecosystems not only improves our ability to understand global carbon budget but also ensures basic human survival supplements. Here, we improved the MODIS-GPP algorithm by two main perspectives: (1) taking the seasonal variations of maximum light use efficiency (LUE) into modeling consideration; (2) separately parameterizing maximum LUE with a recently proposed vegetation index (VI) NIRv during vegetative stage and senescence stage. Performances of the revised and traditional MODIS-GPP algorithms were tested at three FLUXNET crop sites planted with maize and soybean. The revised model was well validated, indicated by the root mean square error (RMSE), coefficient of determination$(\mathrm{R}^{2})$and Bias being 2.33$\text{gC m}^{-2}$day${}^{-1}, 0.91$and 0.48$\text{gC m}^{-2}$da y -l for maize, respectively, and being 1.51$\text{gC} \mathrm{m}^{-2}\text{day}^{-1},0.91$and 0.43$\text{gC m}^{-2}$day$-1$for soybean, respectively. Overall, compared to the traditional MODIS-GPP algorithm, the proposed algorithm reduced RMSE by 29.6% and 27.4%, increased$\mathrm{R}^{2}$by 10.9% and 10.9%, and reduced Bias by 41.5% and 36.8% for maize and soybean, respectively. This paper demonstrates that incorporating seasonal fluctuations of maximum LUE into MODIS-GPP algorithm and distinguishing the different photosynthesis rates among vegetative and senescence stages significantly benefit the retrieval accuracy of daily model-estimated GPP.

Negative pairs, especially hard negatives as combined with common negatives (easy to discriminate), are essential in contrastive learning, which plays a role of avoiding degenerate solutions in the sense of constant representation across different instances. Inspired by recent hard negative mining methods via pairwise mixup operation in vision, we propose M-Mix, which dynamically generates a sequence of hard negatives. Compared with previous methods, M-Mix mainly has three features: 1) adaptively choose samples to mix; 2) simultaneously mix multiple samples; 3) automatically assign different mixing weights to the selected samples. We evaluate our method on two image datasets (CIFAR-10, CIFAR-100), five node classification datasets (PPI, DBLP, Pubmed, etc), five graph classification datasets (IMDB, PTC_MR, etc), and two downstream combinatorial tasks (graph edit distance and node clustering). Results show that it achieves state-of-the-art performance under self-supervised settings. Code is available at: https://github.com/Sherrylone/m-mix.

The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective function in a distorted or noisy form because of the uncertain nature or the errors involved in the evaluation. This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by Hassidim and Singer (2017). For a cardinality constraint, we propose an algorithm achieving a near-optimal (1-1/e-O(epsilon))-approximation guarantee (for arbitrary epsilon > 0) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of Singer and Hassidim (2018). For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction.

Vertical federated learning (VFL), where data features are stored in multiple parties distributively, is an important area in machine learning. However, the communication complexity for VFL is typically very high. In this paper, we propose a unified framework by constructing \emph{coresets} in a distributed fashion for communication-efficient VFL. We study two important learning tasks in the VFL setting: regularized linear regression and $k$-means clustering, and apply our coreset framework to both problems. We theoretically show that using coresets can drastically alleviate the communication complexity, while nearly maintain the solution quality. Numerical experiments are conducted to corroborate our theoretical findings.

We present an optimization framework for learning a fair classifier in the presence of noisy perturbations in the protected attributes. Compared to prior work, our framework can be employed with a very general class of linear and linear-fractional fairness constraints, can handle multiple, non-binary protected attributes, and outputs a classifier that comes with provable guarantees on both accuracy and fairness. Empirically, we show that our framework can be used to attain either statistical rate or false positive rate fairness guarantees with a minimal loss in accuracy, even when the noise is large, in two real-world datasets.

Gross Primary Production (GPP) and evapotranspiration (ET) play a critical role of the global carbon, water and energy cycle. Accurate quantification of the global GPP and ET could improve our ability to understand global climate change and energy budget. However, most of the GPP and ET remote sensing models fail to take the coupled relationship between vegetation transpiration (Et) and photosynthesis into consideration. More importantly, these models might ignore the difference of transpiration and photosynthesis rate in different groups of leaves (sunlit and shaded). Here, we coupled the estimates of daily GPP and ET at 84 global forest sites based on the Two-Leaf Light Use Efficiency model and the Penman-Monteith equation that were linked by the Ball-Berry conductance model. The developed model was well calibrated with the root mean square error (RMSE) and the coefficient of determination (R2) being 1.97 gC/m2 day and 0.77 for GPP respectively, and being 21.91 W/m2and 0.65 for ET, respectively. In the meantime, the validation results demonstrated the good performance of the coupled model, with the RMSE and R2 being 1.95 gC/m2 day and 0.77 for GPP, respectively, and being 21.34 W/m2and 0.66 for ET, respectively.

We study the problem of constructing coresets for clustering problems with time series data. This problem has gained importance across many fields including biology, medicine, and economics due to the proliferation of sensors facilitating real-time measurement and rapid drop in storage costs. In particular, we consider the setting where the time series data on $N$ entities is generated from a Gaussian mixture model with autocorrelations over $k$ clusters in $\mathbb{R}^d$. Our main contribution is an algorithm to construct coresets for the maximum likelihood objective for this mixture model. Our algorithm is efficient, and under a mild boundedness assumption on the covariance matrices of the underlying Gaussians, the size of the coreset is independent of the number of entities $N$ and the number of observations for each entity, and depends only polynomially on $k$, $d$ and $1/\varepsilon$, where $\varepsilon$ is the error parameter. We empirically assess the performance of our coreset with synthetic data.

In many judicial systems -- including the United States courts of appeals, the European Court of Justice, the UK Supreme Court and the Supreme Court of Canada -- a subset of judges is selected from the entire judicial body for each case in order to hear the arguments and decide the judgment. Ideally, the subset selected is representative, i.e., the decision of the subset would match what the decision of the entire judicial body would have been had they all weighed in on the case. Further, the process should be fair in that all judges should have similar workloads, and the selection process should not allow for certain judge's opinions to be silenced or amplified via case assignments. Lastly, in order to be practical and trustworthy, the process should also be interpretable, easy to use, and (if algorithmic) computationally efficient. In this paper, we propose an algorithmic method for the judicial subset selection problem that satisfies all of the above criteria. The method satisfies fairness by design, and we prove that it has optimal representativeness asymptotically for a large range of parameters and under noisy information models about judge opinions -- something no existing methods can provably achieve. We then assess the benefits of our approach empirically by counterfactually comparing against the current practice and recent alternative algorithmic approaches using cases from the United States courts of appeals database.

We initiate the study of coresets for clustering in graph metrics, i.e., the shortest-path metric of edge-weighted graphs. Such clustering problems are essential to data analysis and used for example in road networks and data visualization. A coreset is a compact summary of the data that approximately preserves the clustering objective for every possible center set, and it offers significant efficiency improvements in terms of running time, storage, and communication, including in streaming and distributed settings. Our main result is a near-linear time construction of a coreset for k-Median in a general graph $G$, with size $O_{\epsilon, k}(\mathrm{tw}(G))$ where $\mathrm{tw}(G)$ is the treewidth of $G$, and we complement the construction with a nearly-tight size lower bound. The construction is based on the framework of Feldman and Langberg [STOC 2011], and our main technical contribution, as required by this framework, is a uniform bound of $O(\mathrm{tw}(G))$ on the shattering dimension under any point weights. We validate our coreset on real-world road networks, and our scalable algorithm constructs tiny coresets with high accuracy, which translates to a massive speedup of existing approximation algorithms such as local search for graph k-Median.

A panel dataset contains features or observations for multiple individuals over multiple time periods and regression problems with panel data are common in statistics and applied ML. When dealing with massive datasets, coresets have emerged as a valuable tool from a computational, storage and privacy perspective, as one needs to work with and share much smaller datasets. However, results on coresets for regression problems thus far have only been available for cross-sectional data ($N$ individuals each observed for a single time unit) or longitudinal data (a single individual observed for $T>1$ time units), but there are no results for panel data ($N>1$, $T>1$). This paper introduces the problem of coresets to panel data settings; we first define coresets for several variants of regression problems with panel data and then present efficient algorithms to construct coresets of size that are independent of $N$ and $T$, and only polynomially depend on $1/\varepsilon$ (where $\varepsilon$ is the error parameter) and the number of regression parameters. Our approach is based on the Feldman-Langberg framework in which a key step is to upper bound the “total sensitivity” that is roughly the sum of maximum influences of all individual-time pairs taken over all possible choices of regression parameters. Empirically, we assess our approach with a synthetic and a real-world datasets; the coreset sizes constructed using our approach are much smaller than the full dataset and coresets indeed accelerate the running time of computing the regression objective.

Given a collection of n points in ℝ d , the goal of the (k,z)-clustering problem is to find a subset of k “centers” that minimizes the sum of the z-th powers of the Euclidean distance of each point to the closest center. Special cases of the (k,z)-clustering problem include the k-median and k-means problems. Our main result is a unified two-stage importance sampling framework that constructs an ε-coreset for the (k,z)-clustering problem. Compared to the results for (k,z)-clustering in [Feldman and Langberg, STOC 2011], our framework saves a ε2 d factor in the coreset size. Compared to the results for (k,z)-clustering in [Sohler and Woodruff, FOCS 2018], our framework saves a poly(k) factor in the coreset size and avoids the exp(k/ε) term in the construction time. Specifically, our coreset for k-median (z=1) has size Õ(ε−4 k) which, when compared to the result in [Sohler and Woodruff, STOC 2018], saves a k factor in the coreset size. Our algorithmic results rely on a new dimensionality reduction technique that connects two well-known shape fitting problems: subspace approximation and clustering, and may be of independent interest. We also provide a size lower bound of Ω(k· min{2 z/20,d }) for a 0.01-coreset for (k,z)-clustering, which has a linear dependence of size on k and an exponential dependence on z that matches our algorithmic results.

In a recent study, Friedler et al. pointed out that several fair classification algorithms are not stable with respect to variations in the training set – a crucial consideration in several applications. Motivated by their work, we study the problem of designing classification algorithms that are both fair and stable. We propose an extended framework based on fair classification algorithms that are formulated as optimization problems, by introducing a stability-focused regularization term. Theoretically, we prove an additional stability guarantee, that was lacking in fair classification algorithms, and also provide an accuracy guarantee for our extended framework. Our accuracy guarantee can be used to inform the selection of the regularization parameter in our framework. We assess the benefits of our approach empirically by extending several fair classification algorithms that are shown to achieve the best balance between fairness and accuracy over the \textbf{Adult} dataset. Our empirical results show that our extended framework indeed improves the stability at only a slight sacrifice in accuracy.

In a recent work, \cite{chierichetti2017fair} studied the following ``fair'' variants of classical clustering problems such as k-means and k-median: given a set of n data points in R^d and a binary type associated to each data point, the goal is to cluster the points while ensuring that the proportion of each type in each cluster is roughly the same as its underlying proportion. Subsequent work has focused on either extending this setting to when each data point has multiple, non-disjoint sensitive types such as race and gender \cite{bera2019fair}, or to address the problem that the clustering algorithms in the above work do not scale well. The main contribution of this paper is an approach to clustering with fairness constraints that involve {\em multiple, non-disjoint} attributes, that is {\em also scalable}. Our approach is based on novel constructions of coresets: for the k-median objective, we construct an \eps-coreset of size O(\Gamma k^2 \eps^{-d}) where \Gamma is the number of distinct collections of groups that a point may belong to, and for the k-means objective, we show how to construct an \eps-coreset of size O(\Gamma k^3\eps^{-d-1}). The former result is the first known coreset construction for the fair clustering problem with the k-median objective, and the latter result removes the dependence on the size of the full dataset as in~\cite{schmidt2018fair} and generalizes it to multiple, non-disjoint attributes. Importantly, plugging our coresets into existing algorithms for fair clustering such as \cite{backurs2019scalable} results in the fastest algorithms for several cases. Empirically, we assess our approach over the \textbf{Adult} and \textbf{Bank} dataset, and show that the coreset sizes are much smaller than the full dataset; applying coresets indeed accelerates the running time of computing the fair clustering objective while ensuring that the resulting objective difference is small.

We study the problem of constructing ε-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An ε-coreset is a weighted subset S ⊆ X with weight function w : S → ℝ≥0, such that for any k-subset C ∈ [X]k, it holds that Σx∈Sw(x) · dz(x, C) ∈ (1 ± ε) · Σx∈Xdz(x, C). We present an efficient algorithm that constructs an ε-coreset for the (k, z)-clustering problem in M(X, d), where the size of the coreset only depends on the parameters k, z, ε and the doubling dimension ddim(M). To the best of our knowledge, this is the first efficient c-coreset construction of size independent of |X| for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of M(X, d) and the shattering dimension (or VC-dimension) of the range space induced by the distance d. Such a relation is not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small (1 ± ε)-distortion of the distance function d (the distorted distance is called the smoothed distance function), the shattering dimension can be upper bounded by O(ε-O(ddim(M))). For the purpose of coreset construction, the above bound does not suffice as it only works for unweighted spaces. Therefore, we introduce the notion of τ-error probabilistic shattering dimension, and prove a (drastically better) upper bound of O(ddim(M)·log(1/ε)+log log 1/τ) for the probabilistic shattering dimension for weighted doubling metrics. As it turns out, an upper bound for the probabilistic shattering dimension is enough for constructing a small coreset. We believe the new relation between doubling and shattering dimensions is of independent interest and may find other applications. Furthermore, we study robust coresets for (k, z)-clustering with outliers in a doubling metric. We show an improved connection between α-approximation and robust coresets. This also leads to improvement upon the previous best known bound of the size of robust coreset for Euclidean space [Feldman and Langberg, STOC 11]. The new bound entails a few new results in clustering and property testing. As another application, we show constant-sized (ε, k, z)centroid sets in doubling metrics can be constructed by extending our coreset construction. Prior to our result, constantsized centroid sets for general clustering problems were only known for Euclidean spaces. We can apply our centroid set to accelerate the local search algorithm (studied in [Friggstad et al., FOCS 2016]) for the (k, z)-clustering problem in doubling metrics.

Multiwinner voting rules are used to select a small representative subset of candidates or items from a larger set given the preferences of voters. However, if candidates have sensitive attributes such as gender or ethnicity (when selecting a committee), or specified types such as political leaning (when selecting a subset of news items), an algorithm that chooses a subset by optimizing a multiwinner voting rule may be unbalanced in its selection -- it may under or over represent a particular gender or political orientation in the examples above. We introduce an algorithmic framework for multiwinner voting problems when there is an additional requirement that the selected subset should be ``fair'' with respect to a given set of attributes. Our framework provides the flexibility to (1) specify fairness with respect to multiple, non-disjoint attributes (e.g., ethnicity and gender) and (2) specify a score function. We study the computational complexity of this constrained multiwinner voting problem for monotone and submodular score functions and present several approximation algorithms and matching hardness of approximation results for various attribute group structure and types of score functions. We also present simulations that suggest that adding fairness constraints may not affect the scores significantly when compared to the unconstrained case.

Solving geometric optimization problems over uncertain data has become increasingly important in many applications and has attracted a lot of attentions in recent years. In this paper, we study two important geometric optimization problems, the k-center problem and the j-flat-center problem, over stochastic/uncertain data points in Euclidean spaces. For the stochastic k-center problem, we would like to find k points in a fixed dimensional Euclidean space, such that the expected value of the k-center objective is minimized. For the stochastic j-flat-center problem, we seek a j-flat (i.e., a j-dimensional affine subspace) such that the expected value of the maximum distance from any point to the j-flat is minimized. We consider both problems under two popular stochastic geometric models, the existential uncertainty model, where the existence of each point may be uncertain, and the locational uncertainty model, where the location of each point may be uncertain. We provide the first PTAS (Polynomial Time Approximation Scheme) for both problems under the two models. Our results generalize the previous results for stochastic minimum enclosing ball and stochastic enclosing cylinder.

With the dramatic growth in the number of application domains that generate probabilistic, noisy and uncertain data, there has been an increasing interest in designing algorithms for geometric or combinatorial optimization problems over such data. In this paper, we initiate the study of constructing epsilon-kernel coresets for uncertain points. We consider uncertainty in the existential model where each point's location is fixed but only occurs with a certain probability, and the locational model where each point has a probability distribution describing its location. An epsilon-kernel coreset approximates the width of a point set in any direction. We consider approximating the expected width (an epsilon-EXP-KERNEL), as well as the probability distribution on the width (an (epsilon, tau)-QUANT-KERNEL) for any direction. We show that there exists a set of O(epsilon^{-(d-1)/2}) deterministic points which approximate the expected width under the existential and locational models, and we provide efficient algorithms for constructing such coresets. We show, however, it is not always possible to find a subset of the original uncertain points which provides such an approximation. However, if the existential probability of each point is lower bounded by a constant, an epsilon-EXP-KERNEL is still possible. We also provide efficient algorithms for construct an (epsilon, tau)-QUANT-KERNEL coreset in nearly linear time. Our techniques utilize or connect to several important notions in probability and geometry, such as Kolmogorov distances, VC uniform convergence and Tukey depth, and may be useful in other geometric optimization problem in stochastic settings. Finally, combining with known techniques, we show a few applications to approximating the extent of uncertain functions, maintaining extent measures for stochastic moving points and some shape fitting problems under uncertainty.

Distributed clustering has attracted significant attention in recent years. In this paper, we study the k-means problem in the distributed dimension setting, where the dimensions of the data are partitioned across multiple machines. We provide new approximation algorithms, which incur low communication costs and achieve constant approximation ratios. The communication complexity of our algorithms significantly improve on existing algorithms. We also provide the first communication lower bound, which nearly matches our upper bound in a certain range of parameter setting. Our experimental results show that our algorithms outperform existing algorithms on real data-sets in the distributed dimension setting.

Markov Chain Monte Carlo (MCMC) method is a widely used algorithm design scheme with many applications. To make efficient use of this method, the key step is to prove that the Markov chain is rapid mixing. Canonical paths is one of the two main tools to prove rapid mixing. However, there are much fewer success examples comparing to coupling, the other main tool. The main reason is that there is no systematic approach or general recipe to design canonical paths. Building up on a previous exploration by McQuillan [18], we develop a general theory to design canonical paths for MCMC: We reduce the task of designing canonical paths to solving a set of linear equations, which can be automatically done even by a machine. Making use of this general approach, we obtain fully polynomial-time randomized approximation schemes (FPRAS) for counting the number of b-matching with b ≤ 7 and b-edge-cover with b ≤ 2. They are natural generalizations of matchings and edge covers for graphs. No polynomial time approximation was previously known for these problems.

We consider the multi-shop ski rental problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a consumer has to make decisions on when and where to buy. We are interested in the optimal online (competitive-ratio minimizing) mixed strategy from the consumer's perspective. For our problem in its basic form, we obtain exciting closed-form solutions and a linear time algorithm for computing them. We further demonstrate the generality of our approach by investigating three extensions of our basic problem, namely ones that consider costs incurred by entering a shop or switching to another shop. Our solutions to these problems suggest that the consumer must assign positive probability in exactly one shop at any buying time. Our results apply to many real-world applications, ranging from cost management in IaaS cloud to scheduling in distributed computing.