29 citations · 78 across the 20 of their papers we have counts for
24 papers
Multigroup Robustness
Lunjia Hu, Charlotte Peale, Judy Hanwen Shen
To address the shortcomings of real-world datasets, robust learning algorithms have been designed to overcome arbitrary and indiscriminate data corruption. However, practical proce…
Calibration Error for Decision Making
Lunjia Hu, Yifan Wu
Calibration allows predictions to be reliably interpreted as probabilities by decision makers. We propose a decision-theoretic calibration error, the Calibration Decision Loss (CDL…
Testing Calibration in Nearly-Linear Time
Lunjia Hu, Arun Jambulapati, Kevin Tian +1
In the recent literature on machine learning and decision making, calibration has emerged as a desirable and widely-studied statistical property of the outputs of binary prediction…
On Computationally Efficient Multi-Class Calibration
Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum
Consider a multi-class labelling problem, where the labels can take values in , and a predictor predicts a distribution over the labels. In this work, we study the following f…
Simple, Scalable and Effective Clustering via One-Dimensional Projections
Moses Charikar, Monika Henzinger, Lunjia Hu +2
Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and -means+…
When Does Optimizing a Proper Loss Yield Calibration?
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu +1
Optimizing proper loss functions is popularly believed to yield predictors with good calibration properties; the intuition being that for such losses, the global optimum is to pred…
Loss Minimization Yields Multicalibration for Large Neural Networks
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu +2
Multicalibration is a notion of fairness for predictors that requires them to provide calibrated predictions across a large set of protected groups. Multicalibration is known to be…
Generative Models of Huge Objects
Lunjia Hu, Inbal Livni-Navon, Omer Reingold
This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Gol…
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
Lunjia Hu, Charlotte Peale
In many learning theory problems, a central role is played by a hypothesis class: we might assume that the data is labeled according to a hypothesis in the class (usually referred…
A Unifying Theory of Distance from Calibration
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu +1
We study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of perfect calibration is well-understoo…
Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
John Duchi, Vitaly Feldman, Lunjia Hu +1
Recovering linear subspaces from data is a fundamental and important task in statistics and machine learning. Motivated by heterogeneity in Federated Learning settings, we study a…
Loss Minimization through the Lens of Outcome Indistinguishability
Parikshit Gopalan, Lunjia Hu, Michael P. Kim +2
We present a new perspective on loss minimization and the recent notion of Omniprediction through the lens of Outcome Indistingusihability. For a collection of losses and hypothesi…
Omnipredictors for Constrained Optimization
Lunjia Hu, Inbal Livni-Navon, Omer Reingold +1
The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wieder ITCS 2021), suggested a new paradigm for loss minimization. Rather than learning a predictor based on a kn…
Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability
Lunjia Hu, Charlotte Peale, Omer Reingold
We give the first sample complexity characterizations for outcome indistinguishability, a theoretical framework of machine learning recently introduced by Dwork, Kim, Reingold, Rot…
An Improved Local Search Algorithm for k-Median
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu +2
We present a new local-search algorithm for the -median clustering problem. We show that local optima for this algorithm give a -approximation; our result improves up…
Near-Optimal Explainable -Means for All Dimensions
Moses Charikar, Lunjia Hu
Many clustering algorithms are guided by certain cost functions such as the widely-used -means cost. These algorithms divide data points into clusters with often complicated bou…
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization
Moses Charikar, Lunjia Hu
In the non-negative matrix factorization (NMF) problem, the input is an matrix with non-negative entries and the goal is to factorize it as . The $m\ti…
Geometric function theory over quaternionic slice domains
Graziano Gentili, Caterina Stoppato
The theory of quaternionic slice regular functions was introduced in 2006 and successfully developed for about a decade over symmetric slice domains, which appeared to be the natur…
Robust and On-the-fly Dataset Denoising for Image Classification
Jiaming Song, Lunjia Hu, Michael Auli +2
Memorization in over-parameterized neural networks could severely hurt generalization in the presence of mislabeled examples. However, mislabeled examples are hard to avoid in extr…
The Power of Many Samples in Query Complexity
Andrew Bassilakis, Andrew Drucker, Mika Göös +3
The randomized query complexity of a boolean function is famously characterized (via Yao's minimax) by the least number of queries needed to dis…
Towards Understanding Learning Representations: To What Extent Do Different Neural Networks Learn the Same Representation
Liwei Wang, Lunjia Hu, Jiayuan Gu +4
It is widely believed that learning good representations is one of the main reasons for the success of deep neural networks. Although highly intuitive, there is a lack of theory an…
Active Tolerant Testing
Avrim Blum, Lunjia Hu
In this work, we give the first algorithms for tolerant testing of nontrivial classes in the active model: estimating the distance of a target function to a hypothesis class C with…
Capacitated Center Problems with Two-Sided Bounds and Outliers
Hu Ding, Lunjia Hu, Lingxiao Huang +1
In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices , we want to find a subset of vertices , called centers, s…
Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes
Lunjia Hu, Ruihan Wu, Tianhong Li +1
In this work we study the quantitative relation between the recursive teaching dimension (RTD) and the VC dimension (VCD) of concept classes of finite sizes. The RTD of a concept c…