论文检索

General Machine Learning · Clustering

Ameet Gadekar, Suhas Thejaswi Muniyappa

Capacitated fair-range $k$-clustering generalizes classical $k$-clustering by incorporating both capacity constraints and demographic fairness. In this setting, data points are categorized as clients and facilities; each facility has a capacity and may belong to one or more possibly intersecting demographic groups. The task is to select $k$ facilities as centers and assign each client to a center so that: ($a$) no center exceeds its capacity, ($b$) the number of centers selected from each group lies within specified lower and upper bounds (fair-range constraints), and ($c$) the clustering cost (e.g., $k$-median or $k$-means) is minimized. Prior work by Thejaswi et al. (KDD 2022) showed that even satisfying fair-range constraints is \np-hard, thereby making the problem inapproximable to any polynomial factor. Our first main result strengthens this by showing that inapproximability persists even when the fair-range constraints are trivially satisfiable, highlighting the intrinsic computational complexity of the clustering task itself. These inapproximability results hold even on tree metrics and when the number of groups is logarithmic in the size of the facility set. In light of strong inapproximability results, we focus on a practical setting where the number of groups is constant. Our second main result is a polynomial-time $O(\log k)$- and $O(\log^2 k)$-approximation algorithm for $k$-median and $k$-means objectives, respectively, in this regime. Next, we design constant factor approximation algorithms for these problems that run in fixed parameterized tractable time in $k$. All our approximation guarantees match the best bounds for capacitated clustering without fair-range constraints. Finally, as our third main contribution, we show that our polynomial-time algorithms are, to our knowledge, the first to have provable approximation guarantees that can practically solve problem instances of modest size.

Theory · Online Learning and Bandits

Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury

Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension $d$, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of $p$-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear $p$-means regret for the entire range of $p$. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.

Deep Learning · Other Representation Learning

Kenny Peng, Rajiv Movva, Jon Kleinberg, Emma Pierson, Nikhil Garg

While sparse autoencoders (SAEs) have generated significant excitement, a series of negative results have added to skepticism about their usefulness. Here, we establish a conceptual distinction that reconciles competing narratives surrounding SAEs. We argue that even if SAEs may be less effective for *acting on known concepts*, SAEs are especially powerful tools for *discovering unknown concepts*. This distinction separates existing negative results from positive results, and suggests several classes of SAE applications. Specifically, we outline use cases for SAEs in (i) ML interpretability, explainability, fairness, auditing, and safety, and (ii) social and health sciences.

Social Aspects · Fairness

Samuel Gruffaz, Gabriel Singer, Olivier VO VAN, Nicolas Vayatis, Argyris Kalogeratos

In many machine learning applications acquiring reliable ground-truth labels is costly, or unfeasible, leading practitioners to rely on crowdsourcing and aggregation of noisy human annotations. When labels are subjective, however, aggregation may amplify individual biases, particularly with respect to sensitive attributes, raising fairness concerns. Despite this, fairness in crowdsourced aggregation remains largely unexplored, with no existing convergence guarantees and only limited post-processing approaches for enforcing $\varepsilon$-fairness under demographic parity. We address this gap by analyzing fairness properties of crowdsourcing aggregation methods within the $\varepsilon$-fairness framework, focusing on Majority Voting and Optimal Bayesian aggregation. In the small-crowd regime, we derive an upper bound on the fairness gap of Majority Voting in terms of the individual annotators’ fairness gaps. We further show that the fairness gap of the aggregated consensus converges exponentially fast to that of the ground truth under interpretable conditions. Since the ground truth itself may still be unfair, we generalize a state-of-the-art multiclass fairness post-processing algorithm from the continuous to the discrete setting, enabling the enforcement of strict demographic parity constraints for any aggregation rule. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our approach and corroborate the theoretical insights.

Social Aspects · Fairness

Jairo Diaz-Rodriguez

Machine learning research increasingly bifurcates into two disconnected modes: benchmark-driven engineering that prioritizes metrics over understanding, and idealized theory that often fails to transfer to modern systems . In this position paper, we argue that the field focuses too heavily on these endpoints, neglecting the central scientific object: the idea. We propose an Ideas First framework in which *ideas* are valued for the behavioral *signatures* they predict in modern models, and these signatures are tested through *tailored experiments* designed to detect the relevant patterns rather than to win leaderboards. This shift not only bridges the gap between theory and practice but also promotes equity by removing the "complexity premium", enabling rigorous scientific contributions from researchers with modest computational, financial, and human resources. Ultimately, we advocate for a research culture centered on ideas, treating benchmarks and theorems as instruments for testing mechanistic hypotheses rather than as ends in themselves.

Applications · Language, Speech and Dialog

Bowen Shi, Andros Tjandra, John Hoffman, Helin Wang, YI-CHIAO WU, Luya Gao, Julius Richter, Matthew Le, Apoorv Vyas, Sanyuan Chen 等

General audio source separation is a key capability for multimodal AI systems that can perceive and reason about sound. Despite substantial progress in recent years, existing separation models are either domain-specific, designed for fixed categories such as speech or music, or limited in controllability, supporting only a single prompting modality such as text. In this work, we present SAM AUDIO, a foundation model for general audio separation that unifies text, visual, and temporal span prompting within a single framework. Built on a diffusion transformer architecture, SAM AUDIO is trained with flow matching on large-scale audio data spanning speech, music, and general sounds, and can flexibly separate target sources described by language, visual masks, or temporal spans. The model achieves state-of-the-art performance across a diverse suite of benchmarks, including general sound, speech, music, and musical instrument separation in both in-the-wild and professionally produced audios, substantially outperforming prior general-purpose and specialized systems. Furthermore, we introduce a new real-world separation benchmark with human-labeled multimodal prompts and a reference-free evaluation model that correlates strongly with human judgment.

Social Aspects · Fairness

Arya Fayyazi, Mehdi Kamal, Massoud Pedram

Large language models (LLMs) can reveal and amplify societal biases during chain-of-thought (CoT) generation. We present COFT (Chain of Fair Thought), a training-free decoding method that applies token-level fairness control at decode time, with distribution-free marginal validity guarantees (under exchangeability) for any frozen causal language model. COFT operates in three stages. First, it creates a masked counterfactual prompt by replacing sensitive spans with neutral tokens. Second, it compares the factual and masked logit distributions through lightweight logit fusion to attenuate attribute-driven biases. Third, it uses dual-branch split-conformal calibration to certify per-step candidate token sets at a user-chosen risk level. We evaluate COFT across six models and multiple bias benchmarks. Our method reduces standard bias metrics by 30–55\% (median 38\%) while preserving task utility and language quality. Reasoning accuracies remain unchanged within run-to-run noise margins. The computational overhead is modest, equivalent to one additional cached forward pass (<=11%). COFT offers a clear, auditable path to safer CoT generation with significant bias reduction, negligible utility loss, and no requirement for retraining, auxiliary classifiers, or weight access.

Applications · Health / Medicine

Cong Liu, Milong Ren, Jiaqi Guan, Chengyue Gong, Jinyuan Sun, Xinshi Chen, Wenzhi Xiao

Recent advances in $\textit{de novo}$ protein binder design have enabled increasing experimental validation, yet reported $\textit{in silico}$ metrics remain difficult to interpret or compare across studies due to non-standardized evaluation protocols. We introduce $\textbf{ProtDBench}$, a standardized and throughput-aware evaluation framework for protein binder design. ProtDBench defines unified benchmark tasks, evaluation protocols, and success criteria, enabling systematic analysis of how evaluation design influences observed performance. Using a large wet-lab annotated dataset, we analyze commonly used structure prediction models as evaluation verifiers, revealing substantial verifier-dependent bias and limited agreement under identical filtering protocols. We then benchmark representative open-source generative binder design methods across ten diverse protein targets under a fixed evaluation protocol. Beyond per-sequence success rates, ProtDBench incorporates throughput-aware metrics based on a fixed 24-hour budget, as well as cluster-level success criteria to account for structural diversity. Together, these results expose systematic differences induced by filtering rules, success definitions, and throughput-aware evaluation between computational efficiency, success rate, and structural diversity. Overall, ProtDBench provides a fair and reproducible evaluation pipeline that supports systematic and controlled comparison of protein binder design methods under realistic evaluation settings.

Social Aspects · Fairness

Etam Benger, Katrina Ligett

Binary classification based on predicted probabilities (scores) is a fundamental task in supervised machine learning. While thresholding scores is Bayes-optimal in the unconstrained setting, using a single threshold generally violates statistical group fairness constraints. Under independence (statistical parity) and separation (equalized odds), such thresholding suffices when the scores already satisfy the corresponding criterion. However, this does not extend to sufficiency: even perfectly group-calibrated scores---including true class probabilities---violate predictive parity after thresholding. In this work, we present an exact solution for optimal binary (randomized) classification under sufficiency, assuming finite sets of group-calibrated scores. We provide a geometric characterization of the feasible pairs of positive predictive value (PPV) and false omission rate (FOR) achievable by such classifiers, and use it to derive a simple post-processing algorithm that attains the optimal classifier using only group-calibrated scores and group membership. Finally, since sufficiency and separation are generally incompatible, we identify the classifier that minimizes deviation from separation subject to sufficiency, and show that it can also be obtained by our algorithm, often achieving performance comparable to the optimum.

Applications · Health / Medicine

Lingzhao Meng, Shuai Guo, Weishan Zhang, Zengxiang Li, Han Yu, Nan Liu, Daniel Ting, Yuru Liu, Tao Chen, Shudong Wang

Group fairness can ensure equitable performance across different demographic subgroups for medical image analysis. However, the current fine-tuned foundation models (FMs) exhibit significant subgroup disparity. One-shot federated learning (OFL) can potentially mitigate this by leveraging cross-institutional data diversity within a single communication round. But heterogeneous distributions across medical institutions may cause OFL local models to diverge severely, resulting in parameter conflicts that amplify disparity upon aggregation. To address these challenges, we propose Fair-FedMOE, a group-fair OFL framework for medical FMs. During local training, Fairness-aware Expert Routing routes samples to group-specific experts via learnable prototypes, enabling subgroup-specialized learning to capture group-specific features without inter-group interference. During model aggregation, Prototype-guided Differential Aggregation computes personalized weights based on prototype similarity and applies differentiated aggregation strategies to filter conflicting updates. We propose RES-AUC, a Rawlsian justice-inspired metric based on worst-group performance that remains stable as groups increase. Comprehensive experiments on diverse retinal datasets covering different modalities and diseases, using retinal-specific and general-purpose FMs, show consistent fairness gains without sacrificing accuracy. Code available at https://anonymous.4open.science/r/Fair-FedMOE-2624.

Social Aspects · Fairness

Qifen Yang, Yuhui Deng, Jiande Huang, Peng Zhou, Xiwen Lu, Lin Cui

With the widespread application of data-driven classifiers in high-risk domains, group fairness has increasingly become a key research focus. However, most existing methods rely on model constraints or data reweighting, which often suffer from limited interpretability and may distort the original data distribution. Granular-ball computing (GBC), as a structured and highly interpretable learning framework, provides a natural foundation for incorporating group fairness into the data partitioning process. Building on this insight, we first propose a $\textbf{Fair}$ $\textbf{G}$ranular-$\textbf{B}$all $\textbf{G}$eneration framework (FairGBG), which employs the fair clustering algorithm to ensure a balanced proportion of sensitive groups within each granular-ball (GB) during its construction, aiming to enhance within-ball group fairness. Theoretical analysis shows that FairGBG preserves high purity within each GB while satisfying group fairness. Furthermore, we introduce a $\textbf{Fair} \textbf{G}$ranular-$\textbf{B}$all-based $\textbf{F}$air data $\textbf{C}$lassification method (FairGBFC), which enhances classification fairness by leveraging group fairness within GBs. Experimental results on multiple benchmark datasets demonstrate that, compared to existing methods, FairGBFC significantly improves classification fairness while maintaining competitive accuracy. Notably, FairGBFC exhibits superior classification performance compared to standard GB-based methods across all benchmark datasets. Furthermore, compared with state-of-the-art fairness-aware baselines, it achieves a superior trade-off between accuracy and fairness, effectively mitigating bias while preserving high utility.

Social Aspects · Fairness

Zeyu Tang, Alex John London, Atoosa Kasirzadeh, Sarah de Ramirez, Peter Spirtes, Kun Zhang, Sanmi Koyejo

Algorithmic fairness research has largely framed _unfairness as discrimination_ along _sensitive attributes_. However, this approach limits visibility into _unfairness as structural injustice_ instantiated through _social determinants_, which are contextual variables that shape attributes and outcomes without pertaining to specific individuals. **This position paper argues that the field should quantify structural injustice via social determinants, beyond sensitive attributes.** Drawing on cross-disciplinary insights, we argue that prevailing technical paradigms fail to adequately capture unfairness as structural injustice, because contexts are potentially treated as noise to be normalized rather than signal to be audited. We further demonstrate the practical urgency of this shift through a theoretical model of college admissions, a demographic study using U.S. census data, and a high-stakes domain application regarding breast cancer screening within an integrated U.S. healthcare system. Our results indicate that mitigation strategies centered solely on sensitive attributes can introduce new forms of structural injustice. We contend that auditing structural injustice through social determinants must precede mitigation, and call for new technical developments that move beyond sensitive-attribute-centered notions of fairness as non-discrimination.

Optimization · Large Scale, Parallel and Distributed

Benjamin Thérien, Xiaolong Huang, Aaron Defazio, Irina Rish, Eugene Belilovsky

DiLoCo is a powerful framework for training large language models (LLMs) under networking constraints, allowing for increased parallelism and accelerator utilization in data center settings. A critical but often overlooked factor in DiLoCo’s behavior is the choice of inner optimizer, which shapes the pseudogradient used by the outer optimizer. Given the recent success of Muon relative to AdamW for data parallel (DP) training, in this work, we examine how Muon's normalized optimizer steps can affect the pseudogradient's quality. Empirically, we find that, relative to AdamW, Muon yields more \emph{directionally correct} pseudogradients as the number of workers ($K$) is increased. In our experiments pre-training language models, we conduct extensive hyperparameter tuning across 150M, 416M, 914M, 1.76B, and 3.1B models for DiLoCo, MuLoCo, AdamW DP, and Muon DP. Consistently across all scales, we find that with $K\geq1$ workers, MuLoCo (Muon inner optimizer DiLoCo) achieves superior performance to DiLoCo in absolute terms and for $K>2$ it outperforms DiLoCo relative to their data parallel baselines, while being compatible with quantization, streaming, and long synchronization intervals. At $K=1$, we find that MuLoCo can even outperform the data-parallel gold standard while having larger optimal and critical batch sizes.

Deep Learning · Large Language Models

Yuxiang Wei, Zhiqing Sun, Emily McMilin, Jonas Gehring, David Zhang, Gabriel Synnaeve, Daniel Fried, LINGMING ZHANG, Sida Wang

While current software agents powered by large language models (LLMs) and reinforcement learning (RL) can boost programmer productivity, their reliance on human-curated training data and environments creates a fundamental barrier to superintelligence. In this paper, we present Self-play SWE-RL (SSR), a first step toward training superintelligent software agents under minimal data assumptions. SSR requires only access to sandboxed repositories with source code and dependencies, no need for human-labeled is sues or test commands. Grounded in real-world codebases, a single LLM agent is trained via RL in a self-play setting to inject and repair increasingly complex bugs. The bugs are formally specified by test suite improvements proposed by the agent rather than natural language issue descriptions. On the SWE-bench Verified and SWE-Bench Pro benchmarks, SSR achieves clear self-improvement (+10.4 and +7.8 points) and consistently outperforms the human-data baseline throughout training, generalizing to natural language bug descriptions not seen in training. Overall, our results point toward a paradigm where agents autonomously gather extensive learning experiences from real software repositories, ultimately enabling superintelligent systems that exceed human capabilities in understanding, modifying, and creating software from scratch.

Social Aspects · Fairness

Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

Ensuring fairness in matching algorithms is a key challenge in allocating scarce resources and positions. Focusing on Optimal Transport (OT), we introduce a novel notion of group fairness requiring that the probability of matching two individuals from any two given groups in the OT plan satisfies a predefined target. We first propose a modified Sinkhorn algorithm to compute perfectly fair transport plans efficiently. Since exact fairness can significantly degrade matching quality in practice, we then develop two relaxation strategies. The first one involves solving a penalized OT problem, for which we derive novel finite-sample complexity guarantees. Our second strategy leverages bilevel optimization to learn a ground cost that induces a fair OT solution, and we establish a bound on the deviation of fairness when matching unseen data. Finally, we present empirical results illustrating the performance of our approaches and the trade-off between fairness and transport cost.

Social Aspects · Fairness

Emmanouil Kariotakis, Aritra Konar

PageRank (PR) is a fundamental algorithm in graph machine learning tasks. Owing to the increasing importance of algorithmic fairness, we consider the problem of computing PR vectors subject to various group-fairness criteria based on sensitive attributes of the vertices. At present, principled algorithms for this problem are lacking - some cannot guarantee that a target fairness level is achieved, while others do not feature optimality guarantees. In order to overcome these shortcomings, we put forth a unified in-processing convex optimization framework, termed FairRARI, for tackling different group-fairness criteria in a ``plug and play'' fashion. Leveraging a variational formulation of PR, the framework computes fair PR vectors by solving a strongly convex optimization problem with fairness constraints, thereby ensuring that a target fairness level is achieved. We further introduce three different fairness criteria which can be efficiently tackled using FairRARI to compute fair PR vectors with the same asymptotic time-complexity as the original PR algorithm. Extensive experiments on real-world datasets showcase that FairRARI outperforms existing methods in terms of utility, while achieving the desired fairness levels across multiple vertex groups; thereby highlighting its effectiveness.

Social Aspects · Fairness

Lingfeng Zhang, Jingran Yang, Zhaohui Wang, Min Zhang, Qing Zhang

Machine learning fairness research documents trade-offs but lacks quantitative frameworks to measure intrinsic metric compatibility without requiring causal graphs. We introduce a game-theoretic framework that decomposes metrics into interaction vectors, enabling compatibility measurement between metrics via cosine similarity and mechanistic attribution to attribute coalitions. Through analysis of 6 datasets, 7 models, and 6 debiasing methods, we reveal that fairness and utility are often structurally orthogonal (median compatibility $\approx 0$) rather than diametrically opposed, with conflicts driven by sparse, low-order interactions. We further show that debiasing improves fairness by compressing the compatibility space—reducing compatibility of both synergistic and conflicting relationships—rather than eliminating conflicts, providing a mechanistic basis for understanding metric alignment.

Social Aspects · Fairness

Li Zhang, Yuyuan Li, XiaoHua Feng, Jiaming Zhang, Fengyuan Yu, Chaochao Chen

Ensuring fair and equitable treatment across diverse groups, particularly in multi-class classification tasks, poses a significant challenge due to the persistent biases inherent in machine learning models. Most existing bias mitigation techniques are tailored to binary settings, and the presence of multi-dimensional outputs and complex fairness mechanisms makes their extension to multi-class scenarios neither straightforward nor effective. In this paper, we investigate two fundamental, unresolved challenges in fair classification: (i) *characterizing the optimal accuracy-fairness frontier in multi-class settings*, and (ii) *designing practical algorithms that attain this optimum across different training phases*. To tackle these challenges, we first specify an analytically tractable probabilistic formulation of the optimal classifier under fairness constraints. Building upon this, we propose two attribute-blind algorithms to enforce fairness requirements in practice: an in-processing approach for fairness intervention during training via the reduction approach, and a post-processing approach for fine-tuning output probabilities with plug-in estimation. Theoretical analysis reveals that both methods converge to the optimal accuracy-fairness Pareto frontier. Experiments conducted on multiple datasets demonstrate the superior performance of our methods in balancing accuracy and fairness.

Social Aspects · Accountability, Transparency, and Interpretability

Hao Huang, JiaTang Luo, Ruihua Zhou, Yunpeng Li, Yuling Liu

As Large Language Models (LLMs) integrate into writing workflows, precise governance requires distinguishing ''how AI participated'' rather than merely ''whether AI was used.'' Traditional binary detection often misclassifies ``AI-polished'' content as generated, creating fairness risks. We propose shifting from passive post-hoc detection to active intent attribution, focusing on the distinction between Editing (source-anchored) and Generation (unanchored). We introduce \textbf{IACW-Instruct}, a corpus of diverse editing operations constructed via a Director--Actor--Judge pipeline to enable systematic evaluation. Building on this benchmark, we propose \textbf{Intent-Aware Controllable Watermarking (IACW)}, featuring intent-adaptive entropy gating for semantically lossless embedding. Experiments show that IACW achieves 95\% attribution accuracy under 20\% token deletion while preserving near-unwatermarked semantic fidelity, establishing a practical paradigm for fine-grained provenance.

Social Aspects · Fairness

Sheng&amp;#x27;en Li, Dongmian Zou

Online link recommendation on evolving graphs is performative: by choosing which candidate links to show users, the system changes which links form and what feedback it later observes. Consequently, fairness estimates from logged outcomes can be misleading and may drift after deployment when the recommendation policy is updated. We introduce COPF, a decision-layer framework for deployment-stable fairness monitoring and control in online link recommendation. COPF (i) defines group-level opportunity gaps on exposure (shown vs. not shown) counterfactuals, (ii) makes them estimable by explicit exploration and by logging the probability (propensity) that each candidate is shown, and (iii) audits and controls fairness using residual outcome indistinguishability (OI) over a configurable auditor family with graph-aware doubly robust (GA-DR) estimators. We provide a noisy transfer theorem showing that Residual-OI on estimated GA-DR residuals implies bounds on exposure-counterfactual group gaps under temporal mixing and bounded local interference, and we instantiate an online multicalibration auditor together with a primal--dual controller. Experiments on two TGB streams and a controlled synthetic bipartite stream show that COPF reduces worst-case spikes in exposure-counterfactual group disparities with modest impact on ranking utility. Our code is available at https://anonymous.4open.science/r/fairlink-4EA0.