75 citations · 194 across the 33 of their papers we have counts for
37 papers
Adversarial Online Classification with a Preview
Roi Livni, Sahil Singla
Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as threshold…
Learning from Equivalence Queries, Revisited
Mark Braverman, Roi Livni, Yishay Mansour +2
Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. Thi…
Margin in Abstract Spaces
Yair Ashlagi, Roi Livni, Shay Moran +1
Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. T…
Reconstructing Template-Memorized Images from Natural Prompts
Sol Yarkoni, Mahmood Sharif, Roi Livni
Recent advances in generative models, such as diffusion models, have raised concerns related to privacy, copyright infringement, and data stewardship. To better understand and cont…
Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization
Shira Vansover-Hager, Tomer Koren, Roi Livni
We study the out-of-sample performance of multi-pass stochastic gradient descent (SGD) in the fundamental stochastic convex optimization (SCO) model. While one-pass SGD is known to…
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…
Credit Attribution and Stable Compression
Roi Livni, Shay Moran, Kobbi Nissim +1
Credit attribution is crucial across various fields. In academic research, proper citation acknowledges prior work and establishes original contributions. Similarly, in generative…
The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
Roi Livni
We analyze the sample complexity of full-batch Gradient Descent (GD) in the setup of non-smooth Stochastic Convex Optimization. We show that the generalization error of GD, with co…
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…
The Sample Complexity Of ERMs In Stochastic Convex Optimization
Daniel Carmon, Roi Livni, Amir Yehudayoff
Stochastic convex optimization is one of the most well-studied models for learning in modern machine learning. Nevertheless, a central fundamental question in this setup remained u…
Can Copyright be Reduced to Privacy?
Niva Elkin-Koren, Uri Hacohen, Roi Livni +1
There is a growing concern that generative AI models will generate outputs closely resembling the copyrighted materials for which they are trained. This worry has intensified as th…
Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
Roi Livni
We examine the relationship between the mutual information between the output model and the empirical sample and the generalization of the algorithm in the context of stochastic co…
Better Best of Both Worlds Bounds for Bandits with Switching Costs
Idan Amir, Guy Azov, Tomer Koren +1
We study best-of-both-worlds algorithms for bandits with switching cost, recently addressed by Rouyer, Seldin and Cesa-Bianchi, 2021. We introduce a surprisingly simple and effecti…
Making Progress Based on False Discoveries
Roi Livni
The study of adaptive data analysis examines how many statistical queries can be answered accurately using a fixed dataset while avoiding false discoveries (statistically inaccurat…
Benign Underfitting of Stochastic Gradient Descent
Tomer Koren, Roi Livni, Yishay Mansour +1
We study to what extent may stochastic gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit to tr…
Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization
Idan Amir, Roi Livni, Nathan Srebro
We consider linear prediction with a convex Lipschitz loss, or more generally, stochastic convex optimization problems of generalized linear form, i.e.~where each instantaneous los…
Never Go Full Batch (in Stochastic Convex Optimization)
Idan Amir, Yair Carmon, Tomer Koren +1
We study the generalization performance of optimization algorithms for stochastic convex optimization: these are first-order methods that only access the exact…
Littlestone Classes are Privately Online Learnable
Noah Golowich, Roi Livni
We consider the problem of online classification under a privacy constraint. In this setting a learner observes sequentially a stream of labelled examples , for $1 \leq…
Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
Steve Hanneke, Roi Livni, Shay Moran
Which classes can be learned properly in the online model? -- that is, by an algorithm that at each round uses a predictor from the concept class. While there are simple and natura…
SGD Generalizes Better Than GD (And Regularization Doesn't Help)
Idan Amir, Tomer Koren, Roi Livni
We give a new separation result between the generalization performance of stochastic gradient descent (SGD) and of full-batch gradient descent (GD) in the fundamental stochastic co…
A Limitation of the PAC-Bayes Framework
Roi Livni, Shay Moran
PAC-Bayes is a useful framework for deriving generalization bounds which was introduced by McAllester ('98). This framework has the flexibility of deriving distribution- and algori…
Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study
Assaf Dauber, Meir Feder, Tomer Koren +1
The notion of implicit bias, or implicit regularization, has been suggested as a means to explain the surprising generalization ability of modern-days overparameterized learning al…
An Equivalence Between Private Classification and Online Prediction
Mark Bun, Roi Livni, Shay Moran
We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers an open question of Alon et al…
Prediction with Corrupted Expert Advice
Idan Amir, Idan Attias, Tomer Koren +2
We revisit the fundamental problem of prediction with expert advice, in a setting where the environment is benign and generates losses stochastically, but the feedback observed by…