research
∙
07/13/2023
The complexity of non-stationary reinforcement learning
The problem of continual learning in the domain of reinforcement learnin...
share
research
∙
06/21/2023
Memory-Query Tradeoffs for Randomized Convex Optimization
We show that any randomized first-order algorithm which minimizes a d-di...
research
∙
03/29/2023
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
We study the complexity of finding an approximate (pure) Bayesian Nash e...
research
∙
03/03/2023
Near Optimal Memory-Regret Tradeoff for Online Learning
In the experts problem, on each of T days, an agent needs to follow the ...
research
∙
11/09/2022
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Dynamic algorithms come in three main flavors: 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎𝑙 (insertions-o...
research
∙
07/16/2022
Online Prediction in Sub-linear Space
We provide the first sub-linear space and sub-linear regret algorithm fo...
research
∙
04/22/2022
Memory Bounds for Continual Learning
Continual learning, or lifelong learning, is a formidable current challe...
research
∙
03/27/2022
Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions
Continual learning is an emerging paradigm in machine learning, wherein ...
research
∙
01/01/2022
Dynamic Least-Squares Regression
A common challenge in large-scale supervised learning, is how to exploit...
research
∙
11/05/2021
On the Complexity of Dynamic Submodular Maximization
We study dynamic algorithms for the problem of maximizing a monotone sub...
research
∙
10/25/2021
Dynamic Influence Maximization
We initiate a systematic study on 𝑑𝑦𝑛𝑎𝑚𝑖𝑐 𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑐𝑒 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑡𝑖𝑜𝑛 (DIM). ...
research
∙
06/17/2021
Shuffle Private Stochastic Convex Optimization
In shuffle privacy, each user sends a collection of randomized messages ...
research
∙
06/01/2021
Public Goods Games in Directed Networks
Public goods games in undirected networks are generally known to have pu...
research
∙
05/24/2021
Self-Attention Networks Can Process Bounded Hierarchical Languages
Despite their impressive performance in NLP, self-attention networks wer...
research
∙
10/22/2020
MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
To address the issue that deep neural networks (DNNs) are vulnerable to ...
research
∙
06/20/2020
Training (Overparametrized) Neural Networks in Near-Linear Time
The slow convergence rate and pathological curvature issues of first-ord...
research
∙
06/08/2020
Hedging in games: Faster convergence of external and swap regrets
We consider the setting where players run the Hedge algorithm or its opt...
research
∙
04/19/2019
Stochastic Online Metric Matching
We study the minimum-cost metric perfect matching problem under online i...
research
∙
04/19/2019
Tight Bounds for Online Edge Coloring
Vizing's celebrated theorem asserts that any graph of maximum degree Δ a...
research
∙
10/18/2018
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Huang et al. (STOC 2018) introduced the fully online matching problem, a...
research
∙
11/28/2017