124 citations · 1.6k across the 112 of their papers we have counts for
91 papers · 1 filter
One Size Does Not Fit All: Curvature-Aware Adaptive Perturbation for SAM
Alessia Rossi, Felipe Campelo, Gabriel L. Oliveira
Poor generalisation in deep neural networks is frequently associated with convergence to sharp minima. Sharpness-Aware Minimisation (SAM) improves generalisation of deep neural net…
Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
Gon Buzaglo, Elad Hazan
We consider binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm using a Ga…
Spectral Distillation: From Nonlinear Dynamics to Linear State-Space Models
Liane Galanti, Devan Shah, Shlomo Fortgang +1
Can nonlinear dynamical systems be learned through a compact linear state-space representation, without directly solving a non-convex system-identification problem? We give a prova…
A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
Yuval Ran-Milo, Angelos Assos, Elad Hazan
Motivated by the challenge of stabilizing a general unknown linear dynamical system (LDS) from observations, we study the natural prerequisite of online prediction. Our goal is to…
The Power of Second Order Methods for Sequence Preconditioning
Annie Marsden, Elad Hazan
Sequence prediction methods for linear dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows linearly with the hidden dimension of…
AI Alignment via Incentives and Correction
Rohit Agarwal, Joshua Lin, Mark Braverman +1
We study AI alignment through the lens of law-and-economics models of deterrence and enforcement. In these models, misconduct is not treated as an external failure, but as a strate…
RubiConv -- Efficient Boundary-Respecting Convolutions
Linda Friso, Annie Marsden, Xinyi Chen +4
Convolutional architectures have emerged as powerful alternatives to Transformers for sequence modeling. The primary advantage is that they offer improved theoretical sequence leng…
SFO: Learning PDE Operators via Spectral Filtering
Noam Koren, Rafael Moschopoulos, Kira Radinsky +1
Partial differential equations (PDEs) govern complex systems, yet neural operators often struggle to efficiently capture the long-range, nonlocal interactions inherent in their sol…
Research Program: Theory of Learning in Dynamical Systems
Elad Hazan, Shai Shalev Shwartz, Nathan Srebro
Modern learning systems increasingly interact with data that evolve over time and depend on hidden internal state. We ask a basic question: when is such a dynamical system learnabl…
Universal Learning of Nonlinear Dynamics
Evan Dogariu, Anand Brahmbhatt, Elad Hazan
We study the fundamental problem of one-step prediction of a marginally stable unknown nonlinear dynamical system. We describe an algorithm for this problem, based on the technique…
Efficient Spectral Control of Partially Observed Linear Dynamical Systems
Anand Brahmbhatt, Gon Buzaglo, Sofiia Druchyna +1
We propose a new method for the problem of controlling linear dynamical systems under partial observation and adversarial disturbances. Our new algorithm, Double Spectral Control (…
SpectraLDS: Provable Distillation for Linear Dynamical Systems
Devan Shah, Shlomo Fortgang, Sofiia Druchyna +1
We present the first provable method for identifying symmetric linear dynamical systems (LDS) with accuracy guarantees that are independent of the systems' state dimension or effec…
Universal Sequence Preconditioning
Annie Marsden, Elad Hazan
We study the problem of preconditioning in sequential prediction. From the theoretical lens of linear dynamical systems, we show that convolving the target sequence corresponds to…
Provable Length Generalization in Sequence Prediction via Spectral Filtering
Annie Marsden, Evan Dogariu, Naman Agarwal +3
We consider the problem of length generalization in sequence prediction. We define a new metric of performance in this setting -- the Asymmetric-Regret -- which measures regret aga…
FutureFill: Fast Generation from Convolutional Sequence Models
Naman Agarwal, Xinyi Chen, Evan Dogariu +6
We address the challenge of efficient auto-regressive generation in sequence prediction models by introducing FutureFill, a general-purpose fast generation method for any sequence…
Flash STU: Fast Spectral Transform Units
Y. Isabel Liu, Windsor Nguyen, Yagiz Devre +3
Recent advances in state-space model architectures have shown great promise for efficient sequence modeling, but challenges remain in balancing computational efficiency with model…
Online Control in Population Dynamics
Noah Golowich, Elad Hazan, Zhou Lu +2
The study of population dynamics originated with early sociological works but has since extended into many fields, including biology, epidemiology, evolutionary game theory, and ec…
Second Order Methods for Bandit Optimization and Control
Arun Suggala, Y. Jennifer Sun, Praneeth Netrapalli +1
Bandit convex optimization (BCO) is a general framework for online decision making under uncertainty. While tight regret bounds for general convex losses have been established, exi…
Adaptive Regret for Bandits Made Possible: Two Queries Suffice
Zhou Lu, Qiuyi Zhang, Xinyi Chen +3
Fast changing states or volatile environments pose a significant challenge to online optimization, which needs to perform rapid adaptation under limited observation. In this paper,…
Chain of LoRA: Efficient Fine-tuning of Language Models via Residual Learning
Wenhan Xia, Chengwei Qin, Elad Hazan
Fine-tuning is the primary methodology for tailoring pre-trained large language models to specific tasks. As the model's scale and the diversity of tasks expand, parameter-efficien…
Spectral State Space Models
Naman Agarwal, Daniel Suo, Xinyi Chen +1
This paper studies sequence modeling for prediction tasks with long range dependencies. We propose a new formulation for state space models (SSMs) based on learning linear dynamica…
An Efficient Interior-Point Method for Online Convex Optimization
Elad Hazan, Nimrod Megiddo
A new algorithm for regret minimization in online convex optimization is described. The regret of the algorithm after time periods is - which is the minimu…
Online Nonstochastic Model-Free Reinforcement Learning
Udaya Ghai, Arushi Gupta, Wenhan Xia +2
We investigate robust model-free reinforcement learning algorithms designed for environments that may be dynamic or even adversarial. Traditional state-based policies often struggl…
Optimal Rates for Bandit Nonstochastic Control
Y. Jennifer Sun, Stephen Newman, Elad Hazan
Linear Quadratic Regulator (LQR) and Linear Quadratic Gaussian (LQG) control are foundational and extensively researched problems in optimal control. We investigate LQR and LQG pro…