18 citations · 38 across the 9 of their papers we have counts for
10 papers
When Does Confidence-Based Cascade Deferral Suffice?
Wittawat Jitkrittum, Neha Gupta, Aditya Krishna Menon +3
Cascades are a classical strategy to enable inference cost to vary adaptively across samples, wherein a sequence of classifiers are invoked in turn. A deferral rule determines whet…
Ensembling over Classifiers: a Bias-Variance Perspective
Neha Gupta, Jamie Smith, Ben Adlam +1
Ensembles are a straightforward, remarkably effective method for improving the accuracy,calibration, and robustness of models on classification tasks; yet, the reasons that underli…
Understanding the bias-variance tradeoff of Bregman divergences
Ben Adlam, Neha Gupta, Zelda Mariet +1
This paper builds upon the work of Pfau (2013), which generalized the bias variance tradeoff to any Bregman divergence loss function. Pfau (2013) showed that for Bregman divergence…
Estimating decision tree learnability with polylogarithmic sample complexity
Guy Blanc, Neha Gupta, Jane Lange +1
We show that top-down decision tree learning heuristics are amenable to highly efficient learnability estimation: for monotone target functions, the error of the decision tree hypo…
Universal guarantees for decision tree induction via a higher-order splitting criterion
Guy Blanc, Neha Gupta, Jane Lange +1
We propose a simple extension of top-down decision tree learning heuristics such as ID3, C4.5, and CART. Our algorithm achieves provable guarantees for all target functions $f: \{-…
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee
We present hardness of approximation results for Correlation Clustering with local objectives and for Hierarchical Clustering with dissimilarity information. For the former, we stu…
Active Local Learning
Arturs Backurs, Avrim Blum, Neha Gupta
In this work we consider active local learning: given a query point , and active access to an unlabeled training set , output the prediction of a near-optimal $h \in H…
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
Guy Blanc, Neha Gupta, Gregory Valiant +1
We consider networks, trained via stochastic gradient descent to minimize loss, with the training labels perturbed by independent noise at each iteration. We characterize…
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression
Neha Gupta, Aaron Sidford
In this paper, we obtain improved running times for regression and top eigenvector computation for numerically sparse matrices. Given a data matrix …
Local Guarantees in Graph Cuts and Clustering
Moses Charikar, Neha Gupta, Roy Schwartz
Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min Cut, Multiway Cut, and Multicut, extensively studied in combinatorial opti…