8 citations · 20 across the 14 of their papers we have counts for
15 papers
Lookahead identification in adversarial bandits: accuracy and memory bounds
Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto
We study an identification problem in multi-armed bandits. In each round a learner selects one of arms and observes its reward, with the goal of eventually identifying an arm t…
Learning Conditional Averages
Marco Bressan, Nataly Brukhim, Nicolo Cesa-Bianchi +4
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in…
A note on the distinct distances problem over finite fields
Nataly Brukhim, Ariel Bruner, Orit E. Raz
We study a finite-field analogue of the Erdős distinct distances problem under the Hamming metric. For a set \(S\subseteq \mathbb{F}_q^n\) let denote the set of Hamming dist…
On the Hardness of Bandit Learning
Nataly Brukhim, Aldo Pacchiano, Miroslav Dudik +1
We study the task of bandit learning, also known as best-arm identification, under the assumption that the true reward function f belongs to a known, but arbitrary, function class…
Of Dice and Games: A Theory of Generalized Boosting
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi +4
Cost-sensitive loss functions are crucial in many real-world prediction problems, where different types of errors are penalized differently; for example, in medical diagnosis, a fa…
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Nataly Brukhim, Amit Daniely, Yishay Mansour +1
We study a generalization of boosting to the multiclass setting. We introduce a weak learning condition for multiclass classification that captures the original notion of weak lear…
A Unified Model and Dimension for Interactive Estimation
Nataly Brukhim, Miroslav Dudik, Aldo Pacchiano +1
We study an abstract framework for interactive learning called interactive estimation in which the goal is to estimate a target from its "similarity'' to points queried by the lear…
Projection-free Adaptive Regret with Membership Oracles
Zhou Lu, Nataly Brukhim, Paula Gradu +1
In the framework of online convex optimization, most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. To tackle…
A Characterization of Multiclass Learnability
Nataly Brukhim, Daniel Carmon, Irit Dinur +2
A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general m…
A Boosting Approach to Reinforcement Learning
Nataly Brukhim, Elad Hazan, Karan Singh
Reducing reinforcement learning to supervised learning is a well-studied and effective approach that leverages the benefits of compact function approximation to deal with large-sca…
Online Boosting with Bandit Feedback
Nataly Brukhim, Elad Hazan
We consider the problem of online boosting for regression tasks, when only limited information is available to the learner. We give an efficient regret minimization method that has…
Online Agnostic Boosting via Regret Minimization
Nataly Brukhim, Xinyi Chen, Elad Hazan +1
Boosting is a widely used machine learning approach based on the idea of aggregating weak learning rules. While in statistical learning numerous boosting methods exist both in the…
Boosting for Control of Dynamical Systems
Naman Agarwal, Nataly Brukhim, Elad Hazan +1
We study the question of how to aggregate controllers for dynamical systems in order to improve their performance. To this end, we propose a framework of boosting for online contro…
Following High-level Navigation Instructions on a Simulated Quadcopter with Imitation Learning
Valts Blukis, Nataly Brukhim, Andrew Bennett +2
We introduce a method for following high-level navigation instructions by mapping directly from images, instructions and pose estimates to continuous low-level velocity commands fo…
Predict and Constrain: Modeling Cardinality in Deep Structured Prediction
Nataly Brukhim, Amir Globerson
Many machine learning problems require the prediction of multi-dimensional labels. Such structured prediction models can benefit from modeling dependencies between labels. Recently…