COLT A*

171 papers

YearTitle / Authors
2024(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits.
Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, Alberto Maria Metelli
2024A Non-Adaptive Algorithm for the Quantitative Group Testing Problem.
Mahdi Soleymani, Tara Javidi
2024A Theory of Interpretable Approximations.
Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen
2024A Unified Characterization of Private Learnability via Graph Theory.
Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
2024A faster and simpler algorithm for learning shallow networks.
Sitan Chen, Shyam Narayanan
2024A non-backtracking method for long matrix and tensor completion.
Ludovic Stephan, Yizhe Zhu
2024Accelerated Parameter-Free Stochastic Optimization.
Itai Kreisler, Maor Ivgi, Oliver Hinder, Yair Carmon
2024Active Learning with Simple Questions.
Vasilis Kontonis, Mingchen Ma, Christos Tzamos
2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds.
Shinji Ito, Taira Tsuchiya, Junya Honda
2024Adversarial Online Learning with Temporal Feedback Graphs.
Khashayar Gatmiry, Jon Schneider
2024Adversarially-Robust Inference on Trees via Belief Propagation.
Samuel B. Hopkins, Anqi Li
2024Agnostic Active Learning of Single Index Models with Linear Sample Complexity.
Aarshvi Gajjar, Wai Ming Tai, Xingyu Xu, Chinmay Hegde, Christopher Musco, Yi Li
2024Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space.
Yiheng Jiang, Sinho Chewi, Aram-Alexandre Pooladian
2024An information-theoretic lower bound in time-uniform estimation.
John C. Duchi, Saminul Haque
2024Apple Tasting: Combinatorial Dimensions and Minimax Rates.
Vinod Raman, Unique Subedi, Ananth Raman, Ambuj Tewari
2024Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics.
Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang
2024Better-than-KL PAC-Bayes Bounds.
Ilja Kuzborskij, Kwang-Sung Jun, Yulian Wu, Kyoungseok Jang, Francesco Orabona
2024Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation.
Shivam Gupta, Samuel B. Hopkins, Eric C. Price
2024Black-Box k-to-1-PCA Reductions: Theory and Applications.
Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, Kevin Tian
2024Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization.
Jiancong Xiao, Ruoyu Sun, Qi Long, Weijie Su
2024Choosing the p in Lp Loss: Adaptive Rates for Symmetric Mean Estimation.
Yu-Chun Kao, Min Xu, Cun-Hui Zhang
2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization.
Arun Jambulapati, Aaron Sidford, Kevin Tian
2024Community detection in the hypergraph stochastic block model and reconstruction on hypertrees.
Yuzhou Gu, Aaradhya Pandey
2024Computation-information gap in high-dimensional clustering.
Bertrand Even, Christophe Giraud, Nicolas Verzelen
2024Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression.
Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel
2024Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract).
Alex Damian, Loucas Pillaud-Vivien, Jason D. Lee, Joan Bruna
2024Contraction of Markovian Operators in Orlicz Spaces and Error Bounds for Markov Chain Monte Carlo (Extended Abstract).
Amedeo Roberto Esposito, Marco Mondelli
2024Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion.
Jianhao Ma, Salar Fattahi
2024Convergence of Kinetic Langevin Monte Carlo on Lie groups.
Lingkai Kong, Molei Tao
2024Correlated Binomial Process.
Moïse Blanchard, Doron Cohen, Aryeh Kontorovich
2024Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract.
Xifan Yu, Ilias Zadik, Peiyuan Zhang
2024Depth Separation in Norm-Bounded Infinite-Width Neural Networks.
Suzanna Parkinson, Greg Ongie, Rebecca Willett, Ohad Shamir, Nathan Srebro
2024Detection of L
Kiril Bangachev, Guy Bresler
2024Dimension-free Structured Covariance Estimation.
Nikita Puchkin, Maxim V. Rakhuba
2024Dual VC Dimension Obstructs Sample Compression by Embeddings.
Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff
2024Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation Extended Abstract.
Ziao Wang, Weina Wang, Lele Wang
2024Efficient Algorithms for Learning Monophonic Halfspaces in Graphs.
Marco Bressan, Emmanuel Esposito, Maximilian Thiessen
2024Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials.
Ilias Diakonikolas, Daniel M. Kane
2024Errors are Robustly Tamed in Cumulative Knowledge Processes.
Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
2024Exact Mean Square Linear Stability Analysis for SGD.
Rotem Mulayoff, Tomer Michaeli
2024Fast parallel sampling under isoperimetry.
Nima Anari, Sinho Chewi, Thuy-Duong Vuong
2024Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm.
Vishwak Srinivasan, Andre Wibisono, Ashia C. Wilson
2024Fast two-time-scale stochastic gradient method with applications in reinforcement learning.
Sihan Zeng, Thinh T. Doan
2024Fast, blind, and accurate: Tuning-free sparse regression with global linear convergence.
Claudio Mayrink Verdun, Oleh Melnyk, Felix Krahmer, Peter Jung
2024Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo.
Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, Tong Zhang
2024Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract).
Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
2024Finding Super-spreaders in Network Cascades.
Elchanan Mossel, Anirudh Sridhar
2024Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions.
Yilong Qin, Andrej Risteski
2024Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds.
Jongyeong Lee, Junya Honda, Shinji Ito, Min-hwan Oh
2024Fundamental Limits of Non-Linear Low-Rank Matrix Estimation.
Pierre Mergny, Justin Ko, Florent Krzakala, Lenka Zdeborová
2024Gap-Free Clustering: Sensitivity and Robustness of SDP.
Matthew Zurek, Yudong Chen
2024Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling.
Yunbum Kook, Santosh S. Vempala
2024Harmonics of Learning: Universal Fourier Features Emerge in Invariant Networks.
Giovanni Luca Marchetti, Christopher J. Hillar, Danica Kragic, Sophia Sanborn
2024Identification of mixtures of discrete product distributions in near-optimal sample and time complexity.
Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
2024Improved Hardness Results for Learning Intersections of Halfspaces.
Stefan Tiegel
2024Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability.
Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, Eric Moulines
2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs.
Dong Huang, Xianwen Song, Pengkun Yang
2024Information-theoretic generalization bounds for learning from quantum data.
Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian
2024Inherent limitations of dimensions for characterizing learnability of distribution classes.
Tosca Lechner, Shai Ben-David
2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract.
Gavin Brown, Jonathan Hayase, Samuel B. Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, Adam Smith
2024Is Efficient PAC Learning Possible with an Oracle That Responds "Yes" or "No"?
Constantinos Daskalakis, Noah Golowich
2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency.
Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, Bin Yu
2024Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps.
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
2024Learnability Gaps of Strategic Classification.
Lee Cohen, Yishay Mansour, Shay Moran, Han Shao
2024Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds.
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
2024Learning Neural Networks with Sparse Activations.
Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka
2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations.
Kazusato Oko, Yujin Song, Taiji Suzuki, Denny Wu
2024Limits of Approximating the Median Treatment Effect.
Raghavendra Addanki, Siddharth Bhandari
2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions.
Noah Golowich, Ankur Moitra
2024Linear bandits with polylogarithmic minimax regret.
Josep Lumbreras, Marco Tomamichel
2024List Sample Compression and Uniform Convergence.
Steve Hanneke, Shay Moran, Tom Waknine
2024Low-degree phase transitions for detecting a planted clique in sublinear time.
Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
2024Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries.
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2024Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
2024Metalearning with Very Few Samples Per Task.
Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, Jonathan R. Ullman
2024Metric Clustering and MST with Strong and Weak Distance Oracles.
MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, Chen Wang
2024Minimax Linear Regression under the Quantile Risk.
Ayoub El Hanchi, Chris J. Maddison, Murat A. Erdogdu
2024Minimax-optimal reward-agnostic exploration in reinforcement learning.
Gen Li, Yuling Yan, Yuxin Chen, Jianqing Fan
2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems extended abstract.
Tomás González, Cristóbal Guzmán, Courtney Paquette
2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning.
Philip Amortila, Tongyi Cao, Akshay Krishnamurthy
2024Mode Estimation with Partial Feedback.
Charles Arnal, Vivien Cabannes, Vianney Perchet
2024Multiple-output composite quantile regression through an optimal transport lens.
Xuzhi Yang, Tengyao Wang
2024Near-Optimal Learning and Planning in Separated Latent MDPs.
Fan Chen, Constantinos Daskalakis, Noah Golowich, Alexander Rakhlin
2024Nearly Optimal Regret for Decentralized Online Convex Optimization.
Yuanyu Wan, Tong Wei, Mingli Song, Lijun Zhang
2024New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions.
Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng
2024Non-Clashing Teaching Maps for Balls in Graphs.
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel
2024Nonlinear spiked covariance matrices and signal propagation in deep neural networks.
Zhichao Wang, Denny Wu, Zhou Fan
2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data.
Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, Chen-Yu Wei
2024Omnipredictors for regression and the approximate rank of convex functions.
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, Mihir Singhal
2024On Computationally Efficient Multi-Class Calibration.
Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum
2024On Convex Optimization with Semi-Sensitive Features.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
2024On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.
Lesi Chen, Jing Xu, Jingzhao Zhang
2024On sampling diluted Spin-Glasses using Glauber Dynamics.
Charilaos Efthymiou, Kostas Zampetakis
2024On the Computability of Robust PAC Learning.
Pascale Gourdeau, Tosca Lechner, Ruth Urner
2024On the Distance from Calibration in Sequential Prediction.
Mingda Qiao, Letian Zheng
2024On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective.
Daniil Dmitriev, Kristóf Szabó, Amartya Sanyal
2024On the Performance of Empirical Risk Minimization with Smoothed Data.
Adam Block, Alexander Rakhlin, Abhishek Shetty
2024On the sample complexity of parameter estimation in logistic regression with normal design.
Daniel Hsu, Arya Mazumdar
2024Online Learning with Set-valued Feedback.
Vinod Raman, Unique Subedi, Ambuj Tewari
2024Online Newton Method for Bandit Convex Optimisation Extended Abstract.
Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, Jack J. Mayo
2024Online Policy Optimization in Unknown Nonlinear Systems.
Yiheng Lin, James A. Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, Adam Wierman
2024Online Stackelberg Optimization via Nonlinear Control.
William Brown, Christos H. Papadimitriou, Tim Roughgarden
2024Online Structured Prediction with Fenchel-Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss.
Shinsaku Sakaue, Han Bao, Taira Tsuchiya, Taihei Oki
2024Open Problem: Anytime Convergence Rate of Gradient Descent.
Guy Kornowski, Ohad Shamir
2024Open Problem: Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization.
Xinyi Chen, Elad Hazan
2024Open Problem: Can Local Regularization Learn All Multiclass Problems?
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
2024Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy.
Bingshan Hu, Nishant A. Mehta
2024Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning.
Sattar Vakili
2024Open Problem: Tight Characterization of Instance-Optimal Identity Testing.
Clément L. Canonne
2024Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?
Achraf Azize, Debabrota Basu
2024Open problem: Convergence of single-timescale mean-field Langevin descent-ascent for two-player zero-sum games.
Guillaume Wang, Lénaïc Chizat
2024Open problem: Direct Sums in Learning Theory.
Steve Hanneke, Shay Moran, Tom Waknine
2024Optimal Multi-Distribution Learning.
Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, Jason D. Lee
2024Optimal score estimation via empirical Bayes smoothing.
Andre Wibisono, Yihong Wu, Kaylee Yingxi Yang
2024Optimistic Information Directed Sampling.
Gergely Neu, Matteo Papini, Ludovic Schwartz
2024Optimistic Rates for Learning from Label Proportions.
Gene Li, Lin Chen, Adel Javanmard, Vahab Mirrokni
2024Oracle-Efficient Hybrid Online Learning with Unknown Distribution.
Changlong Wu, Jin Sima, Wojciech Szpankowski
2024Physics-informed machine learning as a kernel method.
Nathan Doumèche, Francis R. Bach, Gérard Biau, Claire Boyer
2024Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes.
Yanjun Han, Tianze Jiang, Yihong Wu
2024Preface.
2024Principal eigenstate classical shadows.
Daniel Grier, Hakop Pashayan, Luke Schaeffer
2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs.
Davide Maran, Alberto Maria Metelli, Matteo Papini, Marcello Restelli
2024Provable Advantage in Quantum PAC Learning.
Wilfred Salmon, Sergii Strelchuk, Tom Gur
2024Pruning is Optimal for Learning Sparse Features in High-Dimensions.
Nuri Mert Vural, Murat A. Erdogdu
2024Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract).
Han Huang, Pakawut Jiradilok, Elchanan Mossel
2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximation (Extended Abstract).
Yan Dai, Qiwen Cui, Simon S. Du
2024Regularization and Optimal Multiclass Learning.
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
2024Risk-Sensitive Online Algorithms (Extended Abstract).
Nicolas Christianson, Bo Sun, Steven H. Low, Adam Wierman
2024Robust Distribution Learning with Local and Global Adversarial Corruptions (extended abstract).
Sloan Nietert, Ziv Goldfeld, Soroosh Shafiee
2024Safe Linear Bandits over Unknown Polytopes.
Aditya Gangrade, Tianrui Chen, Venkatesh Saligrama
2024Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity.
Alireza Fathollah Pour, Hassan Ashtiani, Shahab Asoodeh
2024Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier.
Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala
2024Sampling from the Mean-Field Stationary Distribution.
Yunbum Kook, Matthew Shunshi Zhang, Sinho Chewi, Murat A. Erdogdu, Mufan (Bill) Li
2024Scale-free Adversarial Reinforcement Learning.
Mingyu Chen, Xuezhou Zhang
2024Second Order Methods for Bandit Optimization and Control.
Arun Suggala, Y. Jennifer Sun, Praneeth Netrapalli, Elad Hazan
2024Settling the sample complexity of online reinforcement learning.
Zihan Zhang, Yuxin Chen, Jason D. Lee, Simon S. Du
2024Simple online learning with consistent oracle.
Alexander Kozachinskiy, Tomasz Steifer
2024Smaller Confidence Intervals From IPW Estimators via Data-Dependent Coarsening (Extended Abstract).
Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis
2024Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes.
Naty Peter, Eliad Tsfadia, Jonathan R. Ullman
2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension.
Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos
2024Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise.
Matthew Joseph, Alexander Yu
2024Spatial properties of Bayesian unsupervised trees.
Linxi Liu, Li Ma
2024Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing (Extended Abstract).
Yihan Zhang, Hong Chang Ji, Ramji Venkataramanan, Marco Mondelli
2024Statistical Query Lower Bounds for Learning Truncated Gaussians.
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2024Statistical curriculum learning: An elimination algorithm achieving an oracle risk.
Omer Cohen, Ron Meir, Nir Weinberger
2024Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework.
Hengquan Guo, Xin Liu
2024Superconstant Inapproximability of Decision Tree Learning.
Caleb Koch, Carmen Strassle, Li-Yang Tan
2024Testable Learning of General Halfspaces with Adversarial Label Noise.
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Nikos Zarifis
2024Testable Learning with Distribution Shift.
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
2024The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits.
Sepehr Assadi, Chen Wang
2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication.
Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U. Stich, Ziheng Cheng, Nirmit Joshi, Nathan Srebro
2024The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations.
Quanquan C. Liu, Vaidehi Srinivas
2024The Price of Adaptivity in Stochastic Convex Optimization.
Yair Carmon, Oliver Hinder
2024The Real Price of Bandit Information in Multiclass Classification.
Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran
2024The SMART approach to instance-optimal online learning.
Siddhartha Banerjee, Alankrita Bhatt, Christina Lee Yu
2024The Sample Complexity of Simple Binary Hypothesis Testing.
Ankit Pensia, Varun S. Jog, Po-Ling Loh
2024The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement.
Steve Hanneke
2024The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada.
Shipra Agrawal, Aaron Roth
2024The complexity of approximate (coarse) correlated equilibrium for incomplete information games.
Binghui Peng, Aviad Rubinstein
2024The power of an adversary in Glauber dynamics.
Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon
2024The role of randomness in quantum state certification with unentangled measurements.
Yuhan Liu, Jayadev Acharya
2024The sample complexity of multi-distribution learning.
Binghui Peng
2024Thresholds for Reconstruction of Random Hypergraphs From Graph Projections.
Guy Bresler, Chenghao Guo, Yury Polyanskiy
2024Top-K ranking with a monotone adversary.
Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma
2024Topological Expressivity of ReLU Neural Networks.
Ekin Ergen, Moritz Grillo
2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality (extended abstract).
Siyu Chen, Heejune Sheen, Tianhao Wang, Zhuoran Yang
2024Two fundamental limits for uncertainty quantification in predictive inference.
Felipe Areces, Chen Cheng, John C. Duchi, Kuditipudi Rohith
2024Undetectable Watermarks for Language Models.
Miranda Christ, Sam Gunn, Or Zamir
2024Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models.
Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser, Patrick Thiran
2024Universal Rates for Regression: Separations between Cut-Off and Absolute Loss.
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas
2024Universally Instance-Optimal Mechanisms for Private Statistical Estimation.
Hilal Asi, John C. Duchi, Saminul Haque, Zewei Li, Feng Ruan