11 papers
An Optimal Agnostic PAC Algorithm
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Let be a class of finite VC dimension . Writing for the binary risk and , we construct a learner achieving the statistical…
Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation
Jian Qian, Jiachen Xu
We revisit transductive learning where predictions are made with the set of all covariates known in advance. In the leave-one-out (LOO) setting, the prediction is made with labels…
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
Fan Chen, Jian Qian, Alexander Rakhlin +1
Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet ex…
Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
Spencer Compton, Gábor Lugosi, Jaouad Mourtada +2
We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density , the goal is to construct an estimator such that…
Sigmoid-FTRL: Design-Based Adaptive Neyman Allocation for AIPW Estimators
Fangyi Chen, Shu Ge, Jian Qian +1
We consider the problem of Adaptive Neyman Allocation for the class of AIPW estimators in a design-based setting, where potential outcomes and covariates are deterministic. As each…
Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses
Jian Qian, Chen-Yu Wei
In adversarial multi-armed bandits, two performance measures are commonly used: static regret, which compares the learner to the best fixed arm, and dynamic regret, which compares…