Theoretical analysis of co-training and disagreement-based algorithms.
problem Addressing theoretical issues in disagreement-based learning approaches.
method Theoretical analyses of co-training and its variants.
result Provides a theoretical foundation for co-training and similar algorithms.
We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various a…
We study agnostic active learning, where the goal is to learn a classifier in a pre-specified hypothesis class interactively with as few label queries as possible, while making no assumptions on the true function generating the labels. The main algorithms for this problem are {\em{disagreement-based active learning}}, …
New algorithm reduces label queries in online learning with bounded errors.
problem Minimizing label queries while limiting prediction errors in streaming data.
method Disagreement-based online learning algorithm for a general hypothesis space under Tsybakov noise.
result The proposed algorithm achieves an optimal label complexity of O(dT2−α2−2αlog2T) with a matching lower bound. New algorithms for learning under s-concave distributions, including Pareto and t-distributions.
problem Learning under broad and natural generalizations of log-concave distributions, including fat-tailed ones.
method Introduce new convex geometry tools to study s-concave distributions and use these properties to provide bounds on learning quantities. result Significantly generalize prior results for margin-based, disagreement-based, and passive learning of intersections of halfspaces.
Combines active learning and logged data for better classifier learning.
problem Learning classifier on entire population from logged data.
method Combines active learning and controlled random experimentation, modifies disagreement-based algorithms.
result Achieves best of active learning and logged data approaches.
Improved active learning for counterfactual learning from observational data.
problem Learning a classifier from observational data with selection bias.
method Active learning with a counterfactual risk minimizer, modifying both risk and active learning process.
result Statistically consistent and more label-efficient algorithm compared to prior work.
New algorithms find the best subset of distributions with minimal samples.
problem Finding the best subset of distributions with minimal samples.
method Design of new algorithms for combinatorial pure exploration in multi-arm bandit framework.
result Achieve new sample-complexity bounds with polynomial improvements.
Study improves resilience against adversarial clean-label attacks in real and noisy settings.
problem Ensuring accurate predictions in the presence of adversarial clean-label samples.
method Sequential learning from a stream of i.i.d. data, allowing abstention for uncertain predictions.
result Theoretical analysis and adaptations for the agnostic setting with a clean-label adversary and noise.
Efficient algorithm for near-optimal online learning with generalized linear functions.
problem Exponential gap between statistically optimal regret and efficient regret for some function classes.
method Computational efficient algorithm for realizable K-wise linear classification and over-parameterized polynomial featurization.
result First algorithm with log(T/σ) regret for realizable K-wise linear classification.
New algorithms improve contextual bandit performance by adapting to problem difficulty.
problem Improving contextual bandit performance on problems with varying difficulty.
method Introducing complexity measures and oracle-efficient algorithms.
result Achieves optimal instance-dependent regret bounds for rich policy classes.