COLT 2024

170 papers

Principal eigenstate classical shadows

Daniel Grier, Hakop Pashayan, Luke Schaeffer

On the Computability of Robust PAC Learning

Pascale Gourdeau, Lechner. Tosca, Ruth Urner

Identification 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

Omnipredictors for regression and the approximate rank of convex functions

Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, Mihir Singhal

On Computationally Efficient Multi-Class Calibration

Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum

Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems extended abstract

Tomas Gonzalez, Cristóbal Guzmán, Courtney Paquette

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions

Noah Golowich, Ankur Moitra

On Convex Optimization with Semi-Sensitive Features

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka

(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits

Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, Alberto Maria Metelli

Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier

Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala

Safe Linear Bandits over Unknown Polytopes

Aditya Gangrade, Tianrui Chen, Venkatesh Saligrama

Agnostic Active Learning of Single Index Models with Linear Sample Complexity

Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco

Online Newton Method for Bandit Convex Optimisation Extended Abstract

Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, Jack J. Mayo

Computation-information gap in high-dimensional clustering

Bertrand Even, Christophe Giraud, Nicolas Verzelen

Contraction of Markovian Operators in Orlicz Spaces and Error Bounds for Markov Chain Monte Carlo (Extended Abstract)

Amedeo Roberto Esposito, Marco Mondelli

Topological Expressivity of ReLU Neural Networks

Ekin Ergen, Moritz Grillo

The Real Price of Bandit Information in Multiclass Classification

Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran

Minimax Linear Regression under the Quantile Risk

Ayoub El Hanchi, Chris Maddison, Murat Erdogdu

On sampling diluted Spin-Glasses using Glauber Dynamics

Charilaos Efthymiou, Kostas Zampetakis

An information-theoretic lower bound in time-uniform estimation

John Duchi, Saminul Haque

Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models

Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser, Patrick Thiran

Physics-informed machine learning as a kernel method

Nathan Doumèche, Francis Bach, Gérard Biau, Claire Boyer

On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

Daniil Dmitriev, Kristóf Szabó, Amartya Sanyal

Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials

Ilias Diakonikolas, Daniel M. Kane

Statistical Query Lower Bounds for Learning Truncated Gaussians

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis

Testable Learning of General Halfspaces with Adversarial Label Noise

Ilias Diakonikolas, Daniel Kane, Sihan Liu, Nikos Zarifis

Is Efficient PAC Learning Possible with an Oracle That Responds "Yes" or "No"?

Constantinos Daskalakis, Noah Golowich

Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract)

Alex Damian, Loucas Pillaud-Vivien, Jason Lee, Joan Bruna

Refined Sample Complexity for Markov Games with Independent Linear Function Approximation (Extended Abstract)

Yan Dai, Qiwen Cui, Simon S. Du

Learnability Gaps of Strategic Classification

Lee Cohen, Yishay Mansour, Shay Moran, Han Shao

Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries

Edith Cohen, Xin Lyu, Jelani Nelson, Tamas Sarlos, Uri Stemmer

Statistical curriculum learning: An elimination algorithm achieving an oracle risk

Omer Cohen, Ron Meir, Nir Weinberger

Risk-Sensitive Online Algorithms (Extended Abstract)

Nicolas Christianson, Bo Sun, Steven Low, Adam Wierman

Undetectable Watermarks for Language Models

Miranda Christ, Sam Gunn, Or Zamir

The power of an adversary in Glauber dynamics

Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon

Scale-free Adversarial Reinforcement Learning

Mingyu Chen, Xuezhou Zhang

Near-Optimal Learning and Planning in Separated Latent MDPs

Fan Chen, Constantinos Daskalakis, Noah Golowich, Alexander Rakhlin

A faster and simpler algorithm for learning shallow networks

Sitan Chen, Shyam Narayanan

On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis

Lesi Chen, Jing Xu, Jingzhao Zhang

Dual VC Dimension Obstructs Sample Compression by Embeddings

Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos

Non-Clashing Teaching Maps for Balls in Graphs

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel

Information-theoretic generalization bounds for learning from quantum data

Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian

The Price of Adaptivity in Stochastic Convex Optimization

Yair Carmon, Oliver Hinder

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression

Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel

Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract

Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu

Online Stackelberg Optimization via Nonlinear Control

William Brown, Christos Papadimitriou, Tim Roughgarden

Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

Marco Bressan, Emmanuel Esposito, Maximilian Thiessen

A Theory of Interpretable Approximations

Marco Bressan, Nicolò Cesa-bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran

Thresholds for Reconstruction of Random Hypergraphs From Graph Projections

Guy Bresler, Chenghao Guo, Yury Polyanskiy

Errors are Robustly Tamed in Cumulative Knowledge Processes

Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan

On the Performance of Empirical Risk Minimization with Smoothed Data

Adam Block, Alexander Rakhlin, Abhishek Shetty

Correlated Binomial Process

Moise Blanchard, Doron Cohen, Aryeh Kontorovich

Metric Clustering and MST with Strong and Weak Distance Oracles

Mohammadhossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, Chen Wang

Detection of $L_∞$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion

Kiril Bangachev, Guy Bresler

The SMART approach to instance-optimal online learning

Siddhartha Banerjee, Alankrita Bhatt, Christina Lee Yu

Learning Neural Networks with Sparse Activations

Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka

Universal Rates for Regression: Separations between Cut-Off and Absolute Loss

Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits

Sepehr Assadi, Chen Wang

Regularization and Optimal Multiclass Learning

Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng

Universally Instance-Optimal Mechanisms for Private Statistical Estimation

Hilal Asi, John C. Duchi, Saminul Haque, Zewei Li, Feng Ruan

Mode Estimation with Partial Feedback

Charles Arnal, Vivien Cabannes, Vianney Perchet

Two fundamental limits for uncertainty quantification in predictive inference

Felipe Areces, Chen Cheng, John Duchi, Kuditipudi Rohith

Fast parallel sampling under isoperimetry

Nima Anari, Sinho Chewi, Thuy-Duong Vuong

Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning

Philip Amortila, Tongyi Cao, Akshay Krishnamurthy

A Unified Characterization of Private Learnability via Graph Theory

Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff

Metalearning with Very Few Samples Per Task

Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro

Majority-of-Three: The Simplest Optimal Learner?

Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy

Limits of Approximating the Median Treatment Effect

Raghavendra Addanki, Siddharth Bhandari

Conference on Learning Theory 2024: Preface

Shipra Agrawal, Aaron Roth