12 papers
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…
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.…