Preprints and publications

Preprints

• Approximate independence of permutation mixtures
  with Jonathan Niles-Weed, Aug 2024. (slides)

• Causal Inference with High-dimensional Discrete Covariates
  with Zhenghao Zeng, Sivaraman Balakrishnan, and Edward H. Kennedy, May 2024.

• Covariance alignment: from maximum likelihood estimation to Gromov--Wasserstein
  with Philippe Rigollet and George Stepaniants, Nov. 2023.

• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally
  with Nived Rajaraman, Lin F. Yang, Jiantao Jiao, and Kannan Ramchandran, Feb 2022.

• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
  with Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman, Jul 2020. (slides) (video)

• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
  with Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter Glynn, and Yinyu Ye, Apr 2020.

Publications

• Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
  with Fan Chen, Dylan J. Foster, Jian Qian, Alexander Rakhlin, and Yunbei Xu, NeurIPS 2024, to appear (Spotlight).

• Online Estimation via Offline Estimation: An Information-Theoretic Framework
  with Dylan J. Foster, Jian Qian, and Alexander Rakhlin, NeurIPS 2024, to appear.

• Stochastic contextual bandits with graph feedback: from independence number to MAS number
  with Yuxiao Wen and Zhengyuan Zhou, NeurIPS 2024, to appear.

• On the Statistical Complexity of Sample Amplification
  with Brian Axelrod, Shivam Garg, Vatsal Sharan, and Gregory Valiant, The Annals of Statistics, to appear.

• On the amortized complexity of approximate counting
  with Ishaq Aden-Ali, Jelani Nelson, and Huacheng Yu, RANDOM, Aug. 2024.

• Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits
  with Nived Rajaraman, Jiantao Jiao, and Kannan Ramchandran, The Annals of Statistics, to appear. (slides)

• Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes
  with Tianze Jiang and Yihong Wu, COLT, Jul. 2024. (slides)

• Optimal No-regret Learning in Repeated First-price Auctions
  with Zhengyuan Zhou and Tsachy Weissman, Operations Research, Jul. 2024. (slides) (video)

• Online Learning in Multi-unit Auctions
  with Simina Brânzei, Mahsa Derakhshan, and Negin Golrezaei, NeurIPS, Dec. 2023.

• Minimax Optimal Testing by Classification
  with Patrik R. Gerber and Yury Polyanskiy, COLT, Jul. 2023.

• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient
  with Dylan J. Foster and Noah Golowich, COLT, Jul. 2023. (slides)

• Optimal prediction of Markov chains with and without spectral gap
  with Soham Jana and Yihong Wu, IEEE Transactions on Information Theory, Jun. 2023. (NeurIPS’21)

• Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions
  with Wei Zhang, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman, NeurIPS, Nov 2022 (Spotlight).

• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits
  with Yifei Wang, Tavor Baharav, Jiantao Jiao, and David Tse, NeurIPS, Nov 2022.

• Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
  with Nika Haghtalab, Abhishek Shetty, and Kunhe Yang, NeurIPS, Nov 2022 (Designated as Oral).

• On the Value of Interaction and Function Approximation in Imitation Learning
  with Nived Rajaraman, Lin F. Yang, Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran, NeurIPS, Dec 2021.

• Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
  with Kedar Tatwawadi, Zhengqing Zhou, Gowtham Kurri, Vinod Prabhakaran, and Tsachy Weissman, IEEE Transactions on Information Theory, Dec 2021. (ISIT’21) (slides) (video)

• Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints
  with Ayfer Ozgur and Tsachy Weissman, IEEE Transactions on Information Theory, Dec 2021. (COLT’18) (ISIT’18) (COLT slides) (ISIT slides)
  (Errata: Earlier versions (including the conference proceeding) of this paper had a mistake in the lower bound argument for blackboard communication protocols, and the journal version fixes it. Also see the errata.)

• MEOW: A Space-Efficient Non-Parametric Bid Shading Algorithm
  with Wei Zhang, Brendan Kitts, Zhengyuan Zhou, Tingyu Mao, Hao He, Shengjun Pan, Aaron Flores, San Gultekin, and Tsachy Weissman, ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Aug 2021.

• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
  with Xi Chen and Yining Wang, ICML, Jul 2021. (slides) (poster)

• On the High Accuracy Limitation of Adaptive Property Estimation
  AISTATS, Apr 2021. (slides) (poster) (video)

• On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood
  with Kirankumar Shiragur, SODA, Jan 2021. (slides) (video)

• Optimal Rates of Entropy Estimation over Lipschitz Balls
  with Jiantao Jiao, Tsachy Weissman, and Yihong Wu, The Annals of Statistics, Dec 2020. (AoS Special Invited Session at JSM 2021) (slides)

• Minimax Optimal Nonparametric Estimation of Heterogeneous Treatment Effects
  with Zijun Gao, NeurIPS, Dec 2020 (Spotlight).

• Minimax Estimation of KL Divergence between Discrete Distributions
  with Jiantao Jiao and Tsachy Weissman, Journal on Selected Areas in Information Theory, Nov 2020. (an earlier version) (ISITA’16, Student Paper Award) (slides) (code)

• Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information
  with Leighton Barnes and Ayfer Ozgur, Journal of Machine Learning Research, Oct 2020. (ISIT’19)

• Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
  with Jayadev Acharya, Clement L. Canonne, Ziteng Sun, and Himanshu Tyagi, COLT, Jul 2020. (short slides) (long slides) (video)

• Bias Correction with Jackknife, Bootstrap, and Taylor Series
  with Jiantao Jiao, IEEE Transactions on Information Theory, Jul 2020.

• On Estimation of $L_r$-norms in Gaussian White Noise Models
  with Jiantao Jiao and Rajarshi Mukherjee, Probability Theory and Related Fields, Jun 2020. (slides)

• Constrained Functional Value under General Convexity Conditions with Applications to Distributed Simulation
  ISIT, Jun 2020.

• Batched Multi-armed Bandits Problem
  with Zijun Gao, Zhimei Ren, and Zhengqing Zhou, NeurIPS, Dec 2019 (Oral). (slides) (poster)

• Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
  with Jiantao Jiao, Irena Fischer-Hwang, and Tsachy Weissman, IEEE Transactions on Information Theory, Oct 2019.

• Expectation of the Largest Bet Size in the Labouchere System
  with Guanyang Wang, Electronic Communications in Probability, Feb 2019.

• Entropy Rate Estimation for Markov Chains with Large State Space
  with Jiantao Jiao, Chuan-Zheng Lee, Tsachy Weissman, Yihong Wu, and Tiancheng Yu, NIPS, Dec 2018 (Spotlight). (slides) (poster)

• The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal
  with Jiantao Jiao and Weihao Gao, NIPS, Dec 2018 (Spotlight). (slides) (poster)

• Minimax Estimation of the Distance
  with Jiantao Jiao and Tsachy Weissman, IEEE Transactions on Information Theory, Oct 2018. (ISIT’16, Best Student Paper Finalist)

• Local Moment Matching: a Unified Methodology for Symmetric Functional Estimation and Distribution Estimation under Wasserstein Distance
  with Jiantao Jiao and Tsachy Weissman, COLT, Jul 2018. (COLT slides) (Long slides)

• Generalizations of Maximal Inequalities to Arbitrary Selection Rules
  with Jiantao Jiao and Tsachy Weissman, Statistics & Probability Letters, Jan 2018. (ISIT’17)

• Maximum Likelihood Estimation of Functionals of Discrete Distributions
  with Jiantao Jiao, Kartik Venkat, and Tsachy Weissman, IEEE Transactions on Information Theory, Oct 2017. (ISIT’15a) (ISIT’15b)

• Mutual Information Bounds via Adjacency Events
  with Or Ordentlich and Ofer Shayevitz, IEEE Transactions on Information Theory, Nov 2016.

• Performance Limits and Geometric Properties of Array Localization
  with Yuan Shen, Xiao-Ping Zhang, Moe Z. Win, and Huadong Meng, IEEE Transactions on Information Theory, Feb 2016. (ICASSP’14)

• Minimax Estimation of Discrete Distributions under $ell_1$ Loss
  with Jiantao Jiao and Tsachy Weissman, IEEE Transactions on Information Theory, Nov 2015. (ISIT’15)

• On the Ergodic Capacity of MIMO Free-Space Optical Systems over Turbulence Channels
  with Jiayi Zhang, Linglong Dai, Yu Zhang, and Zhaocheng Wang, IEEE Journal on Selected Areas in Communications, Sept 2015.

• Minimax Estimation of Functionals of Discrete Distributions
  with Jiantao Jiao, Kartik Venkat, and Tsachy Weissman, IEEE Transactions on Information Theory, May 2015. (ISIT’15) (code)

• Adaptive Estimation of Shannon Entropy
  with Jiantao Jiao and Tsachy Weissman, Technical report, Feb 2015. (ISIT’15) (slides)

• Beyond Maximum Likelihood: from Theory to Practice
  with Jiantao Jiao, Kartik Venkat, and Tsachy Weissman, Technical report, Sept 2014. (Asilomar’16)