56 citations · 497 across the 85 of their papers we have counts for
91 papers
Gefen: Optimized Stochastic Optimizer
Nadav Benedek, Tomer Koren, Ohad Fried
AdamW is a default optimizer for deep learning, but its moment states add two parameter-sized buffers to training memory, increasing the cost of large-scale pretraining. We propose…
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg +1
Mirror Descent (MD) extends Gradient Descent (GD) beyond Euclidean geometry and has recently reappeared as a lens for KL-regularized policy optimization in reinforcement learning a…
Near-Optimal Decentralized Stochastic Convex Optimization over Networks
Nitai Kluger, Amit Attia, Tomer Koren
We study decentralized stochastic smooth convex optimization, where workers minimize an average objective using local stochastic gradients and neighbor-only communication over…
Cost-Aware Learning
Clara Mohri, Amir Globerson, Haim Kaplan +2
We consider the problem of Cost-Aware Learning, where sampling different components of a finite-sum objective incurs different costs. The objective is to reach a target error while…
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Liad Erez, Fan Chen, Alon Cohen +4
We study contextual bandits in the stochastic i.i.d.\ setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set , and aims…
Towards Fully Parameter-Free Stochastic Optimization: Grid Search with Self-Bounding Analysis
Yuheng Zhao, Yu-Hu Yan, Amit Attia +3
Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with opt…
Statistical Learning from Attribution Sets
Lorne Applebaum, Robert Busa-Fekete, August Y. Chen +3
We address the problem of training conversion prediction models in advertising domains under privacy constraints, where direct links between ad clicks and conversions are unavailab…
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke +4
The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both…
The Hidden Cost of Approximation in Online Mirror Descent
Ofir Schlisselberg, Uri Sherman, Tomer Koren +1
Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making. The OMD iterates…
Flat Minima and Generalization: Insights from Stochastic Convex Optimization
Matan Schliserman, Shira Vansover-Hager, Tomer Koren
Understanding the generalization behavior of learning algorithms is a central goal of learning theory. A recently emerging explanation is that learning algorithms are successful in…
Optimal Learning from Label Proportions with General Loss Functions
Lorne Applebaum, Travis Dick, Claudio Gentile +2
Motivated by problems in online advertising, we address the task of Learning from Label Proportions (LLP). We introduce a novel and versatile low-variance debiasing methodology to…
Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
Amit Attia, Matan Schliserman, Uri Sherman +1
We study population convergence guarantees of stochastic gradient descent (SGD) for smooth convex objectives in the interpolation regime, where the noise at optimum is zero or near…
Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
Uri Sherman, Tomer Koren, Yishay Mansour
We study reinforcement learning (RL) in the agnostic policy learning setting, where the goal is to find a policy whose performance is competitive with the best policy in a given cl…
Optimal Rates in Continual Linear Regression via Increasing Regularization
Ran Levinstein, Amit Attia, Matan Schliserman +4
We study realizable continual linear regression under random task orderings, a common setting for developing continual learning theory. In this setup, the worst-case expected loss…
Nearly Optimal Sample Complexity for Learning with Label Proportions
Robert Busa-Fekete, Travis Dick, Claudio Gentile +3
We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each…
Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
Matan Schliserman, Tomer Koren
We study the generalization performance of unregularized gradient methods for separable linear classification. While previous work mostly deal with the binary case, we focus on the…
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…
From Continual Learning to SGD and Back: Better Rates for Continual Linear Models
Itay Evron, Ran Levinstein, Matan Schliserman +4
We study the common continual learning setup where an overparameterized model is sequentially fitted to a set of jointly realizable tasks. We analyze forgetting, defined as the los…
Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimization
Amit Attia, Tomer Koren
The learning rate in stochastic gradient methods is a critical hyperparameter that is notoriously costly to tune via standard grid search, especially for training modern large-scal…
Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Uri Sherman, Tomer Koren, Yishay Mansour
Modern policy optimization methods roughly follow the policy mirror descent (PMD) algorithmic template, for which there are by now numerous theoretical convergence results. However…
From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
Liad Erez, Tomer Koren
We study the problem of contextual combinatorial semi-bandits, where input contexts are mapped into subsets of size of a collection of possible actions. In each round, the…
Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization
Matan Schliserman, Tomer Koren
We study the problem of learning vector-valued linear predictors: these are prediction rules parameterized by a matrix that maps an -dimensional feature vector to a -dimensio…
Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching
Amit Attia, Ofir Gaash, Tomer Koren
We consider the problem of asynchronous stochastic optimization, where an optimization algorithm makes updates based on stale stochastic gradients of the objective that are subject…
The Real Price of Bandit Information in Multiclass Classification
Liad Erez, Alon Cohen, Tomer Koren +2
We revisit the classical problem of multiclass classification with bandit feedback (Kakade, Shalev-Shwartz and Tewari, 2008), where each input classifies to one of possible lab…