COLT 2023

169 papers

$\ell_p$-Regression in the Arbitrary Partition Model of Communication Yi Li, Honghao Lin, David Woodruff
PDF
A Blackbox Approach to Best of Both Worlds in Bandits and Beyond Chris Dann, Chen-Yu Wei, Julian Zimmert
PDF
A High-Dimensional Convergence Theorem for U-Statistics with Applications to Kernel-Based Testing Kevin H. Huang, Xing Liu, Andrew Duncan, Axel Gandy
PDF
A Lower Bound for Linear and Kernel Regression with Adaptive Covariates Tor Lattimore
PDF
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points Daniel Kane, Ilias Diakonikolas
PDF
A New Ranking Scheme for Modern Data and Its Application to Two-Sample Hypothesis Testing Doudou Zhou, Hao Chen
PDF
A Pretty Fast Algorithm for Adaptive Private Mean Estimation Rohith Kuditipudi, John Duchi, Saminul Haque
PDF
A Second-Order Method for Stochastic Bandit Convex Optimisation Tor Lattimore, András György
PDF
A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs Dirk Hoeven, Lukas Zierahn, Tal Lancewicki, Aviv Rosenberg, Nicolò Cesa-Bianchi
PDF
Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond David Martínez-Rubio, Elias Wirth, Sebastian Pokutta
PDF
Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties David Martínez-Rubio, Sebastian Pokutta
PDF
Active Coverage for PAC Reinforcement Learning Aymen Al-Marjani, Andrea Tirinzoni, Emilie Kaufmann
PDF
Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian
PDF
Algorithmic Gaussianization Through Sketching: Converting Data into Sub-Gaussian Random Designs Michał Dereziński
PDF
Algorithmically Effective Differentially Private Synthetic Data Yiyun He, Roman Vershynin, Yizhe Zhu
PDF
Allocating Divisible Resources on Arms with Unknown and Random Rewards Wenhao Li, Ningyuan Chen
PDF
Approximately Stationary Bandits with Knapsacks Giannis Fikioris, Éva Tardos
PDF
Asymptotic Confidence Sets for Random Linear Programs Shuyu Liu, Florentina Bunea, Jonathan Niles-Weed
PDF
Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning Zeyuan Allen-Zhu, Yuanzhi Li
PDF
Bagging Is an Optimal PAC Learner Kasper Green Larsen
PDF
Bandit Learnability Can Be Undecidable Steve Hanneke, Liu Yang
PDF
Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization Spencer Frei, Gal Vardi, Peter Bartlett, Nathan Srebro
PDF
Best-of-Three-Worlds Analysis for Linear Bandits with Follow-the-Regularized-Leader Algorithm Fang Kong, Canzhe Zhao, Shuai Li
PDF
Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds Shinji Ito, Kei Takemura
PDF
Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures Rares-Darius Buhai, David Steurer
PDF
Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD Matthew Faw, Litu Rout, Constantine Caramanis, Sanjay Shakkottai
PDF
Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation Yuanhao Wang, Qinghua Liu, Yu Bai, Chi Jin
PDF
Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation Qiwen Cui, Kaiqing Zhang, Simon Du
PDF
Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise Zijian Liu, Jiawei Zhang, Zhengyuan Zhou
PDF
Bregman Deviations of Generic Exponential Families Sayak Ray Chowdhury, Patrick Saux, Odalric Maillard, Aditya Gopalan
PDF
Causal Matrix Completion Anish Agarwal, Munther Dahleh, Devavrat Shah, Dennis Shen
PDF
Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix Julia Gaudio, Nirmit Joshi
PDF
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda
PDF
Condition-Number-Independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh Vempala
PDF
Contexts Can Be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms Osama A Hanna, Lin Yang, Christina Fragouli
PDF
Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression Aleksandrs Slivkins, Karthik Abinav Sankararaman, Dylan J Foster
PDF
Convergence of AdaGrad for Non-Convex Objectives: Simple Proofs and Relaxed Assumptions Bohan Wang, Huishuai Zhang, Zhiming Ma, Wei Chen
PDF
Curvature and Complexity: Better Lower Bounds for Geodesically Convex Optimization Christopher Criscitiello, Nicolas Boumal
PDF
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique Guy Bresler, Tianze Jiang
PDF
Detection-Recovery Gap for Planted Dense Cycles Cheng Mao, Alexander S. Wein, Shenduo Zhang
PDF
Deterministic Nonsmooth Nonconvex Optimization Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, Manolis Zampetakis
PDF
Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap Raef Bassily, Cristóbal Guzmán, Michael Menart
PDF
Differentially Private and Lazy Online Convex Optimization Naman Agarwal, Satyen Kale, Karan Singh, Abhradeep Thakurta
PDF
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions Ilias Diakonikolas, Sushrut Karmalkar, Jong Ho Park, Christos Tzamos
PDF
Efficient Algorithms for Sparse Moment Problems Without Separation Zhiyuan Fan, Jian Li
PDF
Efficient Median of Means Estimator Stanislav Minsker
PDF
Empirical Bayes via ERM and Rademacher Complexities: The Poisson Model Soham Jana, Yury Polyanskiy, Anzo Z. Teh, Yihong Wu
PDF
Entropic Characterization of Optimal Rates for Learning Gaussian Mixtures Zeyu Jia, Yury Polyanskiy, Yihong Wu
PDF
Exploring Local Norms in Exp-Concave Statistical Learning Nikita Puchkin, Nikita Zhivotovskiy
PDF
Exponential Hardness of Reinforcement Learning with Linear Function Approximation Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári
PDF
Fast Algorithms for a New Relaxation of Optimal Transport Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
PDF
Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions Gavin Brown, Samuel Hopkins, Adam Smith
PDF
Find a Witness or Shatter: The Landscape of Computable PAC Learning. Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer
PDF
Fine-Grained Distribution-Dependent Learning Curves Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, Ilya Tolstikhin
PDF
Finite-Sample Symmetric Mean Estimation with Fisher Information Rate Shivam Gupta, Jasper C. H. Lee, Eric Price
PDF
From High-Dimensional & Mean-Field Dynamics to Dimensionless ODEs: A Unifying Approach to SGD in Two-Layers Networks Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro
PDF
From Pseudorandomness to Multi-Group Fairness and Back Cynthia Dwork, Daniel Lee, Huijia Lin, Pranay Tankala
PDF
Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage Ibrahim Issa, Amedeo Roberto Esposito, Michael Gastpar
PDF
Generalization Guarantees via Algorithm-Dependent Rademacher Complexity Sarah Sachs, Tim Erven, Liam Hodgkinson, Rajiv Khanna, Umut Şimşekli
PDF
Geodesically Convex $m$-Estimation in Metric Spaces Victor-Emmanuel Brunel
PDF
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization David Gamarnik, Eren C. Kizildağ, Will Perkins, Changji Xu
PDF
Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems Stefan Tiegel
PDF
Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing Mahdi Soltanolkotabi, Dominik Stöger, Changzhi Xie
PDF
Improper Multiclass Boosting Nataly Brukhim, Steve Hanneke, Shay Moran
PDF
Improved Bounds for Multi-Task Learning with Trace Norm Regularization Weiwei Liu
PDF
Improved Dimension Dependence of a Proximal Algorithm for Sampling Jiaojiao Fan, Bo Yuan, Yongxin Chen
PDF
Improved Discretization Analysis for Underdamped Langevin Monte Carlo Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, Murat A. Erdogdu
PDF
Improved Dynamic Regret for Online Frank-Wolfe Yuanyu Wan, Lijun Zhang, Mingli Song
PDF
Inference on Strongly Identified Functionals of Weakly Identified Functions Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, Masatoshi Uehara
PDF
InfoNCE Loss Provably Learns Cluster-Preserving Representations Advait Parulekar, Liam Collins, Karthikeyan Shanmugam, Aryan Mokhtari, Sanjay Shakkottai
PDF
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
PDF
Information-Directed Selection for Top-Two Algorithms Wei You, Chao Qin, Zihao Wang, Shuoguang Yang
PDF
Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory Andrew J. Wagenmaker, Dylan J. Foster
PDF
Intrinsic Dimensionality and Generalization Properties of the R-Norm Inductive Bias Navid Ardeshir, Daniel J. Hsu, Clayton H. Sanford
PDF
Is Planted Coloring Easier than Planted Clique? Pravesh Kothari, Santosh S Vempala, Alexander S Wein, Jeff Xu
PDF
Kernelized Diffusion Maps Loucas Pillaud-Vivien, Francis Bach
PDF
Law of Large Numbers for Bayesian Two-Layer Neural Network Trained with Variational Inference Arnaud Descours, Tom Huix, Arnaud Guillin, Manon Michel, Éric Moulines, Boris Nectoux
PDF
Learning and Testing Latent-Tree Ising Models Efficiently Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, Davin Choo
PDF
Learning Hidden Markov Models Using Conditional Samples Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, Cyril Zhang
PDF
Learning Narrow One-Hidden-Layer ReLU Networks Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, Raghu Meka
PDF
Limits of Model Selection Under Transfer Learning Steve Hanneke, Samory Kpotufe, Yasaman Mahdaviyeh
PDF
Linearization Algorithms for Fully Composite Optimization Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi, Nicolas Flammarion
PDF
List Online Classification Shay Moran, Ohad Sharon, Iska Tsubari, Sivan Yosebashvili
PDF
Local Glivenko-Cantelli Doron Cohen, Aryeh Kontorovich
PDF
Local Risk Bounds for Statistical Aggregation Jaouad Mourtada, Tomas Vaškevičius, Nikita Zhivotovskiy
PDF
Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models Yuchen Wu, Kangjie Zhou
PDF
Minimax Instrumental Variable Regression and $l_2$ Convergence Guarantees Without Identification or Closedness Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, Masatoshi Uehara
PDF
Minimax Optimal Testing by Classification Patrik R. Gerber, Yanjun Han, Yury Polyanskiy
PDF
Minimizing Dynamic Regret on Geodesic Metric Spaces Zihao Hu, Guanghui Wang, Jacob D. Abernethy
PDF
Moments, Random Walks, and Limits for Spectrum Approximation Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
PDF
Multiclass Online Learning and Uniform Convergence Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, Ambuj Tewari
PDF
Multitask Learning via Shared Features: Algorithms and Hardness Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia Zakynthinou
PDF
Near Optimal Heteroscedastic Regression with Symbiotic Learning Aniket Das, Dheeraj M. Nagaraj, Praneeth Netrapalli, Dheeraj Baby
PDF
Near-Optimal Fitting of Ellipsoids to Random Points Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein
PDF
Non-Asymptotic Convergence Bounds for Sinkhorn Iterates and Their Gradients: A Coupling Approach. Giacomo Greco, Maxence Noble, Giovanni Conforti, Alain Durmus
PDF
On a Class of Gibbs Sampling over Networks Bo Yuan, Jiaojiao Fan, Jiaming Liang, Andre Wibisono, Yongxin Chen
PDF
On Classification-Calibration of Gamma-Phi Losses Yutong Wang, Clayton Scott
PDF
On Testing and Learning Quantum Junta Channels Zongbo Bao, Penghui Yao
PDF
On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring Dean Foster, Dylan J. Foster, Noah Golowich, Alexander Rakhlin
PDF
On the Existence of a Complexity in Fixed Budget Bandit Identification Rémy Degenne
PDF
On the Lower Bound of Minimizing Polyak-Łojasiewicz Functions Pengyun Yue, Cong Fang, Zhouchen Lin
PDF
Online Learning and Solving Infinite Games with an ERM Oracle Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell K. Fishelson
PDF
Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence Ruichen Jiang, Qiujiang Jin, Aryan Mokhtari
PDF
Online Learning in Dynamically Changing Environments Changlong Wu, Ananth Grama, Wojciech Szpankowski
PDF
Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback Ziwei Guan, Yi Zhou, Yingbin Liang
PDF
Online Reinforcement Learning in Stochastic Continuous-Time Systems Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh
PDF
Open Problem: Is There a First-Order Method That Only Converges to Local Minimax Optima? Jiseok Chae, Kyuwon Kim, Donghwan Kim
PDF
Open Problem: Learning Sparse Linear Concepts by Priming the Features Manfred K. Warmuth, Ehsan Amid
PDF
Open Problem: Log(n) Factor in "Local Glivenko-Cantelli" Doron Cohen, Aryeh Kontorovich
PDF
Open Problem: Polynomial Linearly-Convergent Method for G-Convex Optimization? Christopher Criscitiello, David Martínez-Rubio, Nicolas Boumal
PDF
Open Problem: The Sample Complexity of Multi-Distribution Learning for VC Classes Pranjal Awasthi, Nika Haghtalab, Eric Zhao
PDF
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran
PDF
Optimal Scoring Rules for Multi-Dimensional Effort Jason D. Hartline, Liren Shan, Yingkai Li, Yifan Wu
PDF
Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making Adam Block, Max Simchowitz, Alexander Rakhlin
PDF
Orthogonal Directions Constrained Gradient Method: From Non-Linear Equality Constraints to Stiefel Manifold Sholom Schechtman, Daniil Tiapkin, Michael Muehlebach, Éric Moulines
PDF
Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron Weihang Xu, Simon Du
PDF
PAC Verification of Statistical Algorithms Saachi Mutreja, Jonathan Shafer
PDF
Precise Asymptotic Analysis of Deep Random Feature Models David Bosch, Ashkan Panahi, Babak Hassibi
PDF
Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations Oren Mangoubi, Nisheeth K. Vishnoi
PDF
Private Online Prediction from Experts: Separations and Faster Rates Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar
PDF
Projection-Free Online Exp-Concave Optimization Dan Garber, Ben Kretzu
PDF
Proper Losses, Moduli of Convexity, and Surrogate Regret Bounds Han Bao
PDF
Provable Benefits of Representational Transfer in Reinforcement Learning Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, Xuezhou Zhang
PDF
Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass Is Pareto-Optimal Moïse Blanchard, Junhui Zhang, Patrick Jaillet
PDF
Quantum Channel Certification with Incoherent Measurements Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir
PDF
Quasi-Newton Steps for Efficient Online Exp-Concave Optimization Zakaria Mhammedi, Khashayar Gatmiry
PDF
Reaching Kesten-Stigum Threshold in the Stochastic Block Model Under Node Corruptions Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, David Steurer
PDF
Repeated Bilateral Trade Against a Smoothed Adversary Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi
PDF
Resolving the Mixing Time of the Langevin Algorithm to Its Stationary Distribution for Log-Concave Sampling Jason Altschuler, Kunal Talwar
PDF
Self-Directed Linear Classification Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
PDF
Semi-Random Sparse Recovery in Nearly-Linear Time Jonathan Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian
PDF
SGD Learning on Neural Networks: Leap Complexity and Saddle-to-Saddle Dynamics Emmanuel Abbe, Enric Boix Adserà, Theodor Misiakiewicz
PDF
Sharp Analysis of EM for Learning Mixtures of Pairwise Differences Abhishek Dhawan, Cheng Mao, Ashwin Pananjady
PDF
Sharp Thresholds in Inference of Planted Subgraphs Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik
PDF
Sharper Model-Free Reinforcement Learning for Average-Reward Markov Decision Processes Zihan Zhang, Qiaomin Xie
PDF
Shortest Program Interpolation Learning Naren Sarayu Manoj, Nathan Srebro
PDF
Simple Binary Hypothesis Testing Under Local Differential Privacy and Communication Constraints Ankit Pensia, Amir Reza Asadi, Varun Jog, Po-Ling Loh
PDF
Sparse PCA Beyond Covariance Thresholding Gleb Novikov
PDF
Sparsity-Aware Generalization Theory for Deep Neural Networks Ramchandran Muthukumar, Jeremias Sulam
PDF
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
PDF
Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems Yunwen Lei
PDF
Statistical and Computational Limits for Tensor-on-Tensor Association Detection Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru Zhang
PDF
Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression Gabriel Arpino, Ramji Venkataramanan
PDF
STay-on-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis, Emmanouil Zampetakis
PDF
Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective Max Simchowitz, Abhishek Gupta, Kaiqing Zhang
PDF
Testing of Index-Invariant Properties in the Huge Object Model Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
PDF
The $k$-Cap Process on Geometric Random Graphs Mirabel E. Reid, Santosh S. Vempala
PDF
The Aggregation–Heterogeneity Trade-Off in Federated Learning Xuyang Zhao, Huiyuan Wang, Wei Lin
PDF
The Complexity of Markov Equilibrium in Stochastic Games Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang
PDF
The Computational Complexity of Finding Stationary Points in Non-Convex Optimization Alexandros Hollender, Emmanouil Zampetakis
PDF
The Expressive Power of Tuning Only the Normalization Layers Angeliki Giannou, Shashank Rajput, Dimitris Papailiopoulos
PDF
The Implicit Bias of Batch Normalization in Linear Models and Two-Layer Linear Convolutional Neural Networks Yuan Cao, Difan Zou, Yuanzhi Li, Quanquan Gu
PDF
The One-Inclusion Graph Algorithm Is Not Always Optimal Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy
PDF
The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning Adam Block, Yury Polyanskiy
PDF
Ticketed Learning–Unlearning Schemes Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, Chiyuan Zhang
PDF
Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures Wai Ming Tai, Bryon Aragam
PDF
Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient Dylan J. Foster, Noah Golowich, Yanjun Han
PDF
Tighter PAC-Bayes Bounds Through Coin-Betting Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij, Francesco Orabona
PDF
Toward L_∞Recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields Kefan Dong, Tengyu Ma
PDF
Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality Alireza Mousavi-Hosseini, Tyler K. Farghly, Ye He, Krishna Balasubramanian, Murat A. Erdogdu
PDF
U-Calibration: Forecasting for an Unknown Agent Bobby Kleinberg, Renato Paes Leme, Jon Schneider, Yifeng Teng
PDF
Uniqueness of BP Fixed Point for the Potts Model and Applications to Community Detection Yuzhou Gu, Yury Polyanskiy
PDF
Universal Rates for Multiclass Learning Steve Hanneke, Shay Moran, Qian Zhang
PDF
Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
PDF
Utilising the CLT Structure in Stochastic Gradient Based Sampling : Improved Analysis and Faster Algorithms Aniket Das, Dheeraj M. Nagaraj, Anant Raj
PDF
Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, Quanquan Gu
PDF
VO$Q$L: Towards Optimal Regret in Model-Free RL with Nonlinear Function Approximation Alekh Agarwal, Yujia Jin, Tong Zhang
PDF
Weak Recovery Threshold for the Hypergraph Stochastic Block Model Yuzhou Gu, Yury Polyanskiy
PDF
Zeroth-Order Optimization with Weak Dimension Dependency Pengyun Yue, Long Yang, Cong Fang, Zhouchen Lin
PDF