5 citations · 10 across the 22 of their papers we have counts for
26 papers
Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits
Idan Attias, Orin Levy, Alexander Ryabchenko +2
Can vanilla policy optimization explore enough to achieve near-optimal regret in stochastic contextual bandits? We show that standard exponential policy updates driven by offline r…
Capacity-Constrained Online Convex Optimization with Delayed Feedback
Alexander Ryabchenko, Idan Attias, Daniel M. Roy
Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives. In practice, tracking resources are finite, and…
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the S…
Positive Distribution Shift as a Framework for Understanding Tractable Learning
Marko Medvedev, Idan Attias, Elisabetta Cornacchia +3
We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training di…
A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
Alexander Ryabchenko, Idan Attias, Daniel M. Roy
We develop a reduction-based framework for online learning with delayed feedback that recovers and improves upon existing results for both first-order and bandit convex optimizatio…
On the Hardness of Learning Regular Expressions
Idan Attias, Lev Reyzin, Nathan Srebro +1
Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computat…
Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles on arbitra…
Learning-Augmented Algorithms for Boolean Satisfiability
Idan Attias, Xing Gao, Lev Reyzin
Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') fro…
Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
Alexander Ryabchenko, Idan Attias, Daniel M. Roy
We study online learning with oblivious losses and delays under a novel ``capacity constraint'' that limits how many past rounds can be tracked simultaneously for delayed feedback.…
PAC Learning with Improvements
Idan Attias, Avrim Blum, Keziah Naggita +3
One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes samples to learn to error (and more, if the…
On Traceability in Stochastic Convex Optimization
Sasha Voitovych, Mahdi Haghifam, Idan Attias +3
In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under geometries. Informally, we say a learning a…
Fixed Point Computation: Beating Brute Force with Smoothed Analysis
Idan Attias, Yuval Dagan, Constantinos Daskalakis +2
We propose a new algorithm that finds an -approximate fixed point of a smooth function from the -dimensional unit ball to itself. We use the general framew…
Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
Ziyi Liu, Idan Attias, Daniel M. Roy
We study the fundamental problem of sequential probability assignment, also known as online learning with logarithmic loss, with respect to an arbitrary, possibly nonparametric hyp…
Sample Compression Scheme Reductions
Idan Attias, Steve Hanneke, Arvind Ramaswami
We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings to binary sample compression scheme…
Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals
Ziyi Liu, Idan Attias, Daniel M. Roy
In this work, we investigate the problem of adapting to the presence or absence of causal structure in multi-armed bandit problems. In addition to the usual reward signal, we assum…
Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam +2
In this work, we investigate the interplay between memorization and learning in the context of \emph{stochastic convex optimization} (SCO). We define memorization via the informati…
Online Learning and Solving Infinite Games with an ERM Oracle
Angelos Assos, Idan Attias, Yuval Dagan +2
While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms…
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Idan Attias, Steve Hanneke, Alkis Kalavasis +2
In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had establi…
Adversarially Robust PAC Learnability of Real-Valued Functions
Idan Attias, Steve Hanneke
We study robustness to test-time adversarial attacks in the regression setting with losses and arbitrary perturbation sets. We address the question of which function class…
Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers
Eitan-Hai Mashiah, Idan Attias, Yishay Mansour
We consider a seller faced with buyers which have the ability to delay their decision, which we call patience. Each buyer's type is composed of value and patience, and it is sample…
A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
Idan Attias, Steve Hanneke, Yishay Mansour
We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We address the question of how many labeled and unlabeled…
Fat-Shattering Dimension of -fold Aggregations
Idan Attias, Aryeh Kontorovich
We provide estimates on the fat-shattering dimension of aggregation rules of real-valued function classes. The latter consists of all ways of choosing functions, one from each…
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Idan Attias, Edith Cohen, Moshe Shechner +1
Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing ro…
Domain Invariant Adversarial Learning
Matan Levi, Idan Attias, Aryeh Kontorovich
The phenomenon of adversarial examples illustrates one of the most basic vulnerabilities of deep neural networks. Among the variety of techniques introduced to surmount this inhere…