11 papers
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…
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…
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…
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…
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…
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…
A General Reduction for High-Probability Analysis with General Light-Tailed Distributions
Amit Attia, Tomer Koren
We describe a general reduction technique for analyzing learning algorithms that are subject to light-tailed (but not necessarily bounded) randomness, a scenario that is often the…
How Free is Parameter-Free Stochastic Optimization?
Amit Attia, Tomer Koren
We study the problem of parameter-free stochastic optimization, inquiring whether, and under what conditions, do fully parameter-free methods exist: these are methods that achieve…
SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance
Amit Attia, Tomer Koren
We study Stochastic Gradient Descent with AdaGrad stepsizes: a popular adaptive (self-tuning) method for first-order stochastic optimization. Despite being well studied, existing a…
Uniform Stability for First-Order Empirical Risk Minimization
Amit Attia, Tomer Koren
We consider the problem of designing uniformly stable first-order optimization algorithms for empirical risk minimization. Uniform stability is often used to obtain generalization…
Algorithmic Instabilities of Accelerated Gradient Descent
Amit Attia, Tomer Koren
We study the algorithmic stability of Nesterov's accelerated gradient method. For convex quadratic objectives, Chen et al. (2018) proved that the uniform stability of the method gr…