More Like this

1. Kernel Multiaccuracy

   https://doi.org/10.4230/LIPIcs.FORC.2025.7  

   Long, Carol Xuan; Alghamdi, Wael; Glynn, Alexander; Wu, Yixuan; Calmon, Flavio P (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bun, Mark (Ed.)

   Predefined demographic groups often overlook the subpopulations most impacted by model errors, leading to a growing emphasis on data-driven methods that pinpoint where models underperform. The emerging field of multi-group fairness addresses this by ensuring models perform well across a wide range of group-defining functions, rather than relying on fixed demographic categories. We demonstrate that recently introduced notions of multi-group fairness can be equivalently formulated as integral probability metrics (IPM). IPMs are the common information-theoretic tool that underlie definitions such as multiaccuracy, multicalibration, and outcome indistinguishably. For multiaccuracy, this connection leads to a simple, yet powerful procedure for achieving multiaccuracy with respect to an infinite-dimensional class of functions defined by a reproducing kernel Hilbert space (RKHS): first perform a kernel regression of a model’s errors, then subtract the resulting function from a model’s predictions. We combine these results to develop a post-processing method that improves multiaccuracy with respect to bounded-norm functions in an RKHS, enjoys provable performance guarantees, and, in binary classification benchmarks, achieves favorable multiaccuracy relative to competing methods. 

   more » « less
2. Principal Composite Kernel Feature Analysis: Data-Dependent Kernel Approach

   https://doi.org/10.1109/TKDE.2012.110  

   Motai, Yuichi; Yoshida, Hiroyuki (August 2013, IEEE Transactions on Knowledge and Data Engineering)
3. On the Random Conjugate Kernel and Neural Tangent Kernel

   Hu, Zhengmian; Huang, Heng (January 2021, Thirty-eighth International Conference on Machine Learning (ICML 2021))
4. Fair Kernel Regression via Fair Feature Embedding in Kernel Space

   https://doi.org/10.1109/ICTAI.2019.00200  

   Okray, Austin; Hu, Hui; Lan, Chao (November 2019, IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI))
5. Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation

   Bakshi, Ainesh; Kacham, Praneeth; Indyk, Piotr; Silwal, Sandeep; Zhou, Samson (January 2023, International Conference on Learning Representations)

   Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency – given n input points, most kernel-based algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring Ω(n^2) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain subquadratic time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving lin- ear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recently developed Kernel Density Estimation framework, which (after preprocessing in time subquadratic in n) can return estimates of row/column sums of the kernel matrix. In particular, we de- velop efficient reductions from weighted vertex and weighted edge sampling on kernel graphs, simulating random walks on kernel graphs, and importance sampling on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in sublinear (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsi- fication, where we observe a 9x decrease in the number of kernel evaluations over baselines for LRA and a 41x reduction in the graph size for spectral sparsification. 

   more » « less