COLT 2024

169 papers

(ε, U)-Adaptive Regret Minimization in Heavy-Tailed Bandits Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, Alberto Maria Metelli

A Faster and Simpler Algorithm for Learning Shallow Networks Sitan Chen, Shyam Narayanan

A Non-Adaptive Algorithm for the Quantitative Group Testing Problem Mahdi Soleymani, Tara Javidi

A Non-Backtracking Method for Long Matrix and Tensor Completion Ludovic Stephan, Yizhe Zhu

A Theory of Interpretable Approximations Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen

A Unified Characterization of Private Learnability via Graph Theory Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff

Accelerated Parameter-Free Stochastic Optimization Itai Kreisler, Maor Ivgi, Oliver Hinder, Yair Carmon

Active Learning with Simple Questions Kontonis Vasilis, Ma Mingchen, Tzamos Christos

Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds Shinji Ito, Taira Tsuchiya, Junya Honda

Adversarial Online Learning with Temporal Feedback Graphs Khashayar Gatmiry, Jon Schneider

Adversarially-Robust Inference on Trees via Belief Propagation Samuel B. Hopkins, Anqui Li

Agnostic Active Learning of Single Index Models with Linear Sample Complexity Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco, Yi Li

Algorithms for Mean-Field Variational Inference via Polyhedral Optimization in the Wasserstein Space Yiheng Jiang, Sinho Chewi, Aram-Alexandre Pooladian

An Information-Theoretic Lower Bound in Time-Uniform Estimation John Duchi, Saminul Haque

Apple Tasting: Combinatorial Dimensions and Minimax Rates Vinod Raman, Unique Subedi, Ananth Raman, Ambuj Tewari

Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang

Better-than-KL PAC-Bayes Bounds Ilja Kuzborskij, Kwang-Sung Jun, Yulian Wu, Kyoungseok Jang, Francesco Orabona

Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation Shivam Gupta, Samuel Hopkins, Eric Price

Black-Box K-to-1-PCA Reductions: Theory and Applications Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, Kevin Tian

Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization Jiancong Xiao, Ruoyu Sun, Qi Long, Weijie Su

Choosing the P in Lp Loss: Adaptive Rates for Symmetric Mean Estimation Yu-Chun Kao, Min Xu, Cun-Hui Zhang

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization Arun Jambulapati, Aaron Sidford, Kevin Tian

Community Detection in the Hypergraph Stochastic Block Model and Reconstruction on Hypertrees Yuzhou Gu, Aaradhya Pandey

Computation-Information Gap in High-Dimensional Clustering Bertrand Even, Christophe Giraud, Nicolas Verzelen

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel

Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract) Alex Damian, Loucas Pillaud-Vivien, Jason Lee, Joan Bruna

Contraction of Markovian Operators in Orlicz Spaces and Error Bounds for Markov Chain Monte Carlo (Extended Abstract) Amedeo Roberto Esposito, Marco Mondelli

Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion Jianhao Ma, Salar Fattahi

Convergence of Kinetic Langevin Monte Carlo on Lie Groups Lingkai Kong, Molei Tao

Correlated Binomial Process Moïse Blanchard, Doron Cohen, Aryeh Kontorovich

Counting Stars Is Constant-Degree Optimal for Detecting Any Planted Subgraph: Extended Abstract Xifan Yu, Ilias Zadik, Peiyuan Zhang

Depth Separation in Norm-Bounded Infinite-Width Neural Networks Suzanna Parkinson, Greg Ongie, Rebecca Willett, Ohad Shamir, Nathan Srebro

Detection of $l_∞$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion Kiril Bangachev, Guy Bresler

Dimension-Free Structured Covariance Estimation Nikita Puchkin, Maxim Rakhuba

Dual VC Dimension Obstructs Sample Compression by Embeddings Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation Extended Abstract Ziao Wang, Weina Wang, Lele Wang

Efficient Algorithms for Learning Monophonic Halfspaces in Graphs Marco Bressan, Emmanuel Esposito, Maximilian Thiessen

Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials Ilias Diakonikolas, Daniel M. Kane

Errors Are Robustly Tamed in Cumulative Knowledge Processes Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan

Exact Mean Square Linear Stability Analysis for SGD Rotem Mulayoff, Tomer Michaeli

Fast Parallel Sampling Under Isoperimetry Nima Anari, Sinho Chewi, Thuy-Duong Vuong

Fast Sampling from Constrained Spaces Using the Metropolis-Adjusted Mirror Langevin Algorithm Vishwak Srinivasan, Andre Wibisono, Ashia Wilson

Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning Sihan Zeng, Thinh Doan

Fast, Blind, and Accurate: Tuning-Free Sparse Regression with Global Linear Convergence Claudio Mayrink Verdun, Oleh Melnyk, Felix Krahmer, Peter Jung

Faster Sampling Without Isoperimetry via Diffusion-Based Monte Carlo Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, Tong Zhang

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract) Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh

Finding Super-Spreaders in Network Cascades Elchanan Mossel, Anirudh Sridhar

Fit like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions Yilong Qin, Andrej Risteski

Follow-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

Fundamental Limits of Non-Linear Low-Rank Matrix Estimation Pierre Mergny, Justin Ko, Florent Krzakala, Lenka Zdeborová

Gap-Free Clustering: Sensitivity and Robustness of SDP Matthew Zurek, Yudong Chen

Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling Yunbum Kook, Santosh S. Vempala

Harmonics of Learning: Universal Fourier Features Emerge in Invariant Networks Giovanni Luca Marchetti, Christopher J Hillar, Danica Kragic, Sophia Sanborn

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

Improved Hardness Results for Learning Intersections of Halfspaces Stefan Tiegel

Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, Eric Moulines

Information-Theoretic Generalization Bounds for Learning from Quantum Data Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian

Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs Dong Huang, Xianwen Song, Pengkun Yang

Inherent Limitations of Dimensions for Characterizing Learnability of Distribution Classes Tosca Lechner, Shai Ben-David

Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares Extended Abstract Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C Perdomo, Adam Smith

Is Efficient PAC Learning Possible with an Oracle That Responds "Yes" or "No"? Constantinos Daskalakis, Noah Golowich

Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, Bin Yu

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Learnability Gaps of Strategic Classification Lee Cohen, Yishay Mansour, Shay Moran, Han Shao

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Learning Neural Networks with Sparse Activations Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka

Learning Sum of Diverse Features: Computational Hardness and Efficient Gradient-Based Training for Ridge Combinations Kazusato Oko, Yujin Song, Taiji Suzuki, Denny Wu

Limits of Approximating the Median Treatment Effect Raghavendra Addanki, Siddharth Bhandari

Linear Bandits with Polylogarithmic Minimax Regret Josep Lumbreras, Marco Tomamichel

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions Noah Golowich, Ankur Moitra

List Sample Compression and Uniform Convergence Steve Hanneke, Shay Moran, Waknine Tom

Low-Degree Phase Transitions for Detecting a Planted Clique in Sublinear Time Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein

Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

Majority-of-Three: The Simplest Optimal Learner? Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy

Metalearning with Very Few Samples per Task Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, Jonathan Ullman

Metric Clustering and MST with Strong and Weak Distance Oracles MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, Chen Wang

Minimax Linear Regression Under the Quantile Risk Ayoub El Hanchi, Chris Maddison, Murat Erdogdu

Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning Gen Li, Yuling Yan, Yuxin Chen, Jianqing Fan

Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems Extended Abstract Tomas Gonzalez, Cristobal Guzman, Courtney Paquette

Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning Philip Amortila, Tongyi Cao, Akshay Krishnamurthy

Mode Estimation with Partial Feedback Charles Arnal, Vivien Cabannes, Vianney Perchet

Multiple-Output Composite Quantile Regression Through an Optimal Transport Lens Xuzhi Yang, Tengyao Wang

Near-Optimal Learning and Planning in Separated Latent MDPs Fan Chen, Constantinos Daskalakis, Noah Golowich, Alexander Rakhlin

Nearly Optimal Regret for Decentralized Online Convex Optimization Yuanyu Wan, Tong Wei, Mingli Song, Lijun Zhang

New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions Yuqian Cheng, Daniel Kane, Zheng Zhicheng

Non-Clashing Teaching Maps for Balls in Graphs Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel

Nonlinear Spiked Covariance Matrices and Signal Propagation in Deep Neural Networks Zhichao Wang, Denny Wu, Zhou Fan

Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, Chen-Yu Wei

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

On Convex Optimization with Semi-Sensitive Features Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang

On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis Lesi Chen, Jing Xu, Jingzhao Zhang

On Sampling Diluted Spin-Glasses Using Glauber Dynamics Charilaos Efthymiou, Kostas Zampetakis

On the Computability of Robust PAC Learning Pascale Gourdeau, Lechner. Tosca, Ruth Urner

On the Distance from Calibration in Sequential Prediction Mingda Qiao, Letian Zheng

On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective Daniil Dmitriev, Kristóf Szabó, Amartya Sanyal

On the Performance of Empirical Risk Minimization with Smoothed Data Adam Block, Alexander Rakhlin, Abhishek Shetty

On the Sample Complexity of Parameter Estimation in Logistic Regression with Normal Design Daniel Hsu, Arya Mazumdar

Online Learning with Set-Valued Feedback Vinod Raman, Unique Subedi, Ambuj Tewari

Online Newton Method for Bandit Convex Optimisation Extended Abstract Hidde Fokkema, Dirk Hoeven, Tor Lattimore, Jack J. Mayo

Online Policy Optimization in Unknown Nonlinear Systems Yiheng Lin, James A. Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, Adam Wierman

Online Stackelberg Optimization via Nonlinear Control William Brown, Christos Papadimitriou, Tim Roughgarden

Online 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

Open Problem: Anytime Convergence Rate of Gradient Descent Guy Kornowski, Ohad Shamir

Open Problem: Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization Xinyi Chen, Elad Hazan

Open Problem: Can Local Regularization Learn All Multiclass Problems? Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng

Open Problem: Convergence of Single-Timescale Mean-Field Langevin Descent-Ascent for Two-Player Zero-Sum Games Guillaume Wang, Lénaïc Chizat

Open Problem: Direct Sums in Learning Theory Steve Hanneke, Shay Moran, Waknine Tom

Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy Bingshan Hu, Nishant A. Mehta

Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning Sattar Vakili

Open Problem: Tight Characterization of Instance-Optimal Identity Testing Clément Canonne

Open Problem: What Is the Complexity of Joint Differential Privacy in Linear Contextual Bandits? Achraf Azize, Debabrota Basu

Optimal Multi-Distribution Learning Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S Du, Jason D Lee

Optimal Score Estimation via Empirical Bayes Smoothing Andre Wibisono, Yihong Wu, Kaylee Yingxi Yang

Optimistic Information Directed Sampling Gergely Neu, Matteo Papini, Ludovic Schwartz

Optimistic Rates for Learning from Label Proportions Gene Li, Lin Chen, Adel Javanmard, Vahab Mirrokni

Oracle-Efficient Hybrid Online Learning with Unknown Distribution Changlong Wu, Jin Sima, Wojciech Szpankowski

Physics-Informed Machine Learning as a Kernel Method Nathan Doumèche, Francis Bach, Gérard Biau, Claire Boyer

Prediction from Compression for Models with Infinite Memory, with Applications to Hidden Markov and Renewal Processes Yanjun Han, Tianze Jiang, Yihong Wu

Principal Eigenstate Classical Shadows Daniel Grier, Hakop Pashayan, Luke Schaeffer

Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs Davide Maran, Alberto Maria Metelli, Matteo Papini, Marcello Restelli

Provable Advantage in Quantum PAC Learning Wilfred Salmon, Sergii Strelchuk, Tom Gur

Pruning Is Optimal for Learning Sparse Features in High-Dimensions Nuri Mert Vural, Murat A Erdogdu

Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract) Han Huang, Pakawut Jiradilok, Elchanan Mossel

Refined Sample Complexity for Markov Games with Independent Linear Function Approximation (Extended Abstract) Yan Dai, Qiwen Cui, Simon S. Du

Regularization and Optimal Multiclass Learning Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng

Risk-Sensitive Online Algorithms (Extended Abstract) Nicolas Christianson, Bo Sun, Steven Low, Adam Wierman

Robust Distribution Learning with Local and Global Adversarial Corruptions (extended Abstract) Sloan Nietert, Ziv Goldfeld, Soroosh Shafiee

Safe Linear Bandits over Unknown Polytopes Aditya Gangrade, Tianrui Chen, Venkatesh Saligrama

Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity Alireza F. Pour, Hassan Ashtiani, Shahab Asoodeh

Sampling from the Mean-Field Stationary Distribution Yunbum Kook, Matthew S. Zhang, Sinho Chewi, Murat A. Erdogdu, Mufan Li

Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala

Scale-Free Adversarial Reinforcement Learning Mingyu Chen, Xuezhou Zhang

Second Order Methods for Bandit Optimization and Control Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, Elad Hazan

Settling the Sample Complexity of Online Reinforcement Learning Zihan Zhang, Yuxin Chen, Jason D Lee, Simon S Du

Simple Online Learning with Consistent Oracle Alexander Kozachinskiy, Tomasz Steifer

Smaller Confidence Intervals from IPW Estimators via Data-Dependent Coarsening (Extended Abstract) Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis

Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes Naty Peter, Eliad Tsfadia, Jonathan Ullman

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos

Some Constructions of Private, Efficient, and Optimal $k$-Norm and Elliptic Gaussian Noise Matthew Joseph, Alexander Yu

Spatial Properties of Bayesian Unsupervised Trees Linxi Liu, Li Ma

Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing (Extended Abstract) Yihan Zhang, Hong Chang Ji, Ramji Venkataramanan, Marco Mondelli

Statistical Curriculum Learning: An Elimination Algorithm Achieving an Oracle Risk Omer Cohen, Ron Meir, Nir Weinberger

Statistical Query Lower Bounds for Learning Truncated Gaussians Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis

Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework Hengquan Guo, Xin Liu

Superconstant Inapproximability of Decision Tree Learning Caleb Koch, Carmen Strassle, Li-Yang Tan

Testable Learning of General Halfspaces with Adversarial Label Noise Ilias Diakonikolas, Daniel Kane, Sihan Liu, Nikos Zarifis

Testable Learning with Distribution Shift Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

The Best Arm Evades: Near-Optimal Multi-Pass Streaming Lower Bounds for Pure Exploration in Multi-Armed Bandits Sepehr Assadi, Chen Wang

The Complexity of Approximate (coarse) Correlated Equilibrium for Incomplete Information Games Binghui Peng, Aviad Rubinstein

The 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

The Power of an Adversary in Glauber Dynamics Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon

The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations Quanquan C. Liu, Vaidehi Srinivas

The Price of Adaptivity in Stochastic Convex Optimization Yair Carmon, Oliver Hinder

The Real Price of Bandit Information in Multiclass Classification Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran

The Role of Randomness in Quantum State Certification with Unentangled Measurements Yuhan Liu, Jayadev Acharya

The Sample Complexity of Multi-Distribution Learning Binghui Peng

The Sample Complexity of Simple Binary Hypothesis Testing Ankit Pensia, Varun Jog, Po-Ling Loh

The SMART Approach to Instance-Optimal Online Learning Siddhartha Banerjee, Alankrita Bhatt, Christina Lee Yu

The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement Steve Hanneke

Thresholds for Reconstruction of Random Hypergraphs from Graph Projections Guy Bresler, Chenghao Guo, Yury Polyanskiy

Top-$k$ Ranking with a Monotone Adversary Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma

Topological Expressivity of ReLU Neural Networks Ekin Ergen, Moritz Grillo

Training Dynamics of Multi-Head SoftMax Attention for In-Context Learning: Emergence, Convergence, and Optimality (extended Abstract) Chen Siyu, Sheen Heejune, Wang Tianhao, Yang Zhuoran

Two Fundamental Limits for Uncertainty Quantification in Predictive Inference Felipe Areces, Chen Cheng, John Duchi, Kuditipudi Rohith

Undetectable Watermarks for Language Models Miranda Christ, Sam Gunn, Or Zamir

Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser, Patrick Thiran

Universal Rates for Regression: Separations Between Cut-Off and Absolute Loss Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas

Universally Instance-Optimal Mechanisms for Private Statistical Estimation Hilal Asi, John C. Duchi, Saminul Haque, Zewei Li, Feng Ruan