160 citations · 1.5k across the 122 of their papers we have counts for
16 papers · 1 filter
Sequence Length Independent Norm-Based Generalization Bounds for Transformers
Jacob Trauger, Ambuj Tewari
This paper provides norm-based generalization bounds for the Transformer architecture that do not depend on the input sequence length. We employ a covering number based approach to…
Apple Tasting: Combinatorial Dimensions and Minimax Rates
Vinod Raman, Unique Subedi, Ananth Raman +1
In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts ``1". First studied by \cite{helmbold2000apple}, we rev…
On the Computational Complexity of Private High-dimensional Model Selection
Saptarshi Roy, Zehua Wang, Ambuj Tewari
We consider the problem of model selection in a high-dimensional sparse linear regression model under privacy constraints. We propose a differentially private (DP) best subset sele…
Online Infinite-Dimensional Regression: Learning Linear Operators
Vinod Raman, Unique Subedi, Ambuj Tewari
We consider the problem of learning linear operators under squared loss between two infinite-dimensional Hilbert spaces in the online setting. We show that the class of linear oper…
On the Minimax Regret in Online Ranking with Top-k Feedback
Mingyuan Zhang, Ambuj Tewari
In online ranking, a learning algorithm sequentially ranks a set of items and receives feedback on its ranking in the form of relevance scores. Since obtaining relevance scores typ…
Multiclass Online Learnability under Bandit Feedback
Ananth Raman, Vinod Raman, Unique Subedi +2
We study online multiclass classification under bandit feedback. We extend the results of Daniely and Helbertal [2013] by showing that the finiteness of the Bandit Littlestone dime…