Machine Learning

New submissions

• New submissions
• Cross-lists
• Replacements

New submissions for Fri, 3 May 24

[1]  arXiv:2405.01015 [pdf, other]

Title: Network reconstruction via the minimum description length principle

Authors: Tiago P. Peixoto

Comments: 17 pages, 10 figures

Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Social and Information Networks (cs.SI); Data Analysis, Statistics and Probability (physics.data-an); Populations and Evolution (q-bio.PE)

A fundamental problem associated with the task of network reconstruction from dynamical or behavioral data consists in determining the most appropriate model complexity in a manner that prevents overfitting, and produces an inferred network with a statistically justifiable number of edges. The status quo in this context is based on $L_{1}$ regularization combined with cross-validation. As we demonstrate, besides its high computational cost, this commonplace approach unnecessarily ties the promotion of sparsity with weight "shrinkage". This combination forces a trade-off between the bias introduced by shrinkage and the network sparsity, which often results in substantial overfitting even after cross-validation. In this work, we propose an alternative nonparametric regularization scheme based on hierarchical Bayesian inference and weight quantization, which does not rely on weight shrinkage to promote sparsity. Our approach follows the minimum description length (MDL) principle, and uncovers the weight distribution that allows for the most compression of the data, thus avoiding overfitting without requiring cross-validation. The latter property renders our approach substantially faster to employ, as it requires a single fit to the complete data. As a result, we have a principled and efficient inference scheme that can be used with a large variety of generative models, without requiring the number of edges to be known in advance. We also demonstrate that our scheme yields systematically increased accuracy in the reconstruction of both artificial and empirical networks. We highlight the use of our method with the reconstruction of interaction networks between microbial communities from large-scale abundance samples involving in the order of $10^{4}$ to $10^{5}$ species, and demonstrate how the inferred model can be used to predict the outcome of interventions in the system.

[2]  arXiv:2405.01124 [pdf, other]

Title: Investigating Self-Supervised Image Denoising with Denaturation

Authors: Hiroki Waida, Kimihiro Yamazaki, Atsushi Tokuhisa, Mutsuyo Wada, Yuichiro Wada

Subjects: Machine Learning (stat.ML); Computer Vision and Pattern Recognition (cs.CV); Machine Learning (cs.LG); Image and Video Processing (eess.IV); Statistics Theory (math.ST)

Self-supervised learning for image denoising problems in the presence of denaturation for noisy data is a crucial approach in machine learning. However, theoretical understanding of the performance of the approach that uses denatured data is lacking. To provide better understanding of the approach, in this paper, we analyze a self-supervised denoising algorithm that uses denatured data in depth through theoretical analysis and numerical experiments. Through the theoretical analysis, we discuss that the algorithm finds desired solutions to the optimization problem with the population risk, while the guarantee for the empirical risk depends on the hardness of the denoising task in terms of denaturation levels. We also conduct several experiments to investigate the performance of an extended algorithm in practice. The results indicate that the algorithm training with denatured images works, and the empirical performance aligns with the theoretical results. These results suggest several insights for further improvement of self-supervised image denoising that uses denatured data in future directions.

[3]  arXiv:2405.01404 [pdf, other]

Title: Random Pareto front surfaces

Authors: Ben Tu, Nikolas Kantas, Robert M. Lee, Behrang Shafei

Comments: The code is available at: this https URL

Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC); Methodology (stat.ME)

The Pareto front of a set of vectors is the subset which is comprised solely of all of the best trade-off points. By interpolating this subset, we obtain the optimal trade-off surface. In this work, we prove a very useful result which states that all Pareto front surfaces can be explicitly parametrised using polar coordinates. In particular, our polar parametrisation result tells us that we can fully characterise any Pareto front surface using the length function, which is a scalar-valued function that returns the projected length along any positive radial direction. Consequently, by exploiting this representation, we show how it is possible to generalise many useful concepts from linear algebra, probability and statistics, and decision theory to function over the space of Pareto front surfaces. Notably, we focus our attention on the stochastic setting where the Pareto front surface itself is a stochastic process. Among other things, we showcase how it is possible to define and estimate many statistical quantities of interest such as the expectation, covariance and quantile of any Pareto front surface distribution. As a motivating example, we investigate how these statistics can be used within a design of experiments setting, where the goal is to both infer and use the Pareto front surface distribution in order to make effective decisions. Besides this, we also illustrate how these Pareto front ideas can be used within the context of extreme value theory. Finally, as a numerical example, we applied some of our new methodology on a real-world air pollution data set.

Cross-lists for Fri, 3 May 24

[4]  arXiv:2405.00742 (cross-list from cs.CR) [pdf, other]

Title: Federated Graph Learning for EV Charging Demand Forecasting with Personalization Against Cyberattacks

Authors: Yi Li, Renyou Xie, Chaojie Li, Yi Wang, Zhaoyang Dong

Comments: 11 pages,4 figures

Subjects: Cryptography and Security (cs.CR); Machine Learning (cs.LG); Machine Learning (stat.ML)

Mitigating cybersecurity risk in electric vehicle (EV) charging demand forecasting plays a crucial role in the safe operation of collective EV chargings, the stability of the power grid, and the cost-effective infrastructure expansion. However, existing methods either suffer from the data privacy issue and the susceptibility to cyberattacks or fail to consider the spatial correlation among different stations. To address these challenges, a federated graph learning approach involving multiple charging stations is proposed to collaboratively train a more generalized deep learning model for demand forecasting while capturing spatial correlations among various stations and enhancing robustness against potential attacks. Firstly, for better model performance, a Graph Neural Network (GNN) model is leveraged to characterize the geographic correlation among different charging stations in a federated manner. Secondly, to ensure robustness and deal with the data heterogeneity in a federated setting, a message passing that utilizes a global attention mechanism to aggregate personalized models for each client is proposed. Thirdly, by concerning cyberattacks, a special credit-based function is designed to mitigate potential threats from malicious clients or unwanted attacks. Extensive experiments on a public EV charging dataset are conducted using various deep learning techniques and federated learning methods to demonstrate the prediction accuracy and robustness of the proposed approach.

[5]  arXiv:2405.00781 (cross-list from quant-ph) [pdf, other]

Title: A Review of Barren Plateaus in Variational Quantum Computing

Authors: Martin Larocca, Supanut Thanasilp, Samson Wang, Kunal Sharma, Jacob Biamonte, Patrick J. Coles, Lukasz Cincio, Jarrod R. McClean, Zoë Holmes, M. Cerezo

Comments: 21 pages, 10 boxes

Subjects: Quantum Physics (quant-ph); Machine Learning (cs.LG); Machine Learning (stat.ML)

Variational quantum computing offers a flexible computational paradigm with applications in diverse areas. However, a key obstacle to realizing their potential is the Barren Plateau (BP) phenomenon. When a model exhibits a BP, its parameter optimization landscape becomes exponentially flat and featureless as the problem size increases. Importantly, all the moving pieces of an algorithm -- choices of ansatz, initial state, observable, loss function and hardware noise -- can lead to BPs when ill-suited. Due to the significant impact of BPs on trainability, researchers have dedicated considerable effort to develop theoretical and heuristic methods to understand and mitigate their effects. As a result, the study of BPs has become a thriving area of research, influencing and cross-fertilizing other fields such as quantum optimal control, tensor networks, and learning theory. This article provides a comprehensive review of the current understanding of the BP phenomenon.

[6]  arXiv:2405.00792 (cross-list from cs.LG) [pdf, other]

Title: Error Exponent in Agnostic PAC Learning

Authors: Adi Hendel, Meir Feder

Comments: paper with appendix to accepted ISIT2024 paper with the same name

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

Statistical learning theory and the Probably Approximately Correct (PAC) criterion are the common approach to mathematical learning theory. PAC is widely used to analyze learning problems and algorithms, and have been studied thoroughly. Uniform worst case bounds on the convergence rate have been well established using, e.g., VC theory or Radamacher complexity. However, in a typical scenario the performance could be much better. In this paper, we consider PAC learning using a somewhat different tradeoff, the error exponent - a well established analysis method in Information Theory - which describes the exponential behavior of the probability that the risk will exceed a certain threshold as function of the sample size. We focus on binary classification and find, under some stability assumptions, an improved distribution dependent error exponent for a wide range of problems, establishing the exponential behavior of the PAC error probability in agnostic learning. Interestingly, under these assumptions, agnostic learning may have the same error exponent as realizable learning. The error exponent criterion can be applied to analyze knowledge distillation, a problem that so far lacks a theoretical analysis.

[7]  arXiv:2405.00837 (cross-list from cs.LG) [pdf, other]

Title: Locality Regularized Reconstruction: Structured Sparsity and Delaunay Triangulations

Authors: Marshall Mueller, James M. Murphy, Abiy Tasissa

Comments: 26 pages, 8 figures

Subjects: Machine Learning (cs.LG); Signal Processing (eess.SP); Optimization and Control (math.OC); Machine Learning (stat.ML)

Linear representation learning is widely studied due to its conceptual simplicity and empirical utility in tasks such as compression, classification, and feature extraction. Given a set of points $[\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n] = \mathbf{X} \in \mathbb{R}^{d \times n}$ and a vector $\mathbf{y} \in \mathbb{R}^d$, the goal is to find coefficients $\mathbf{w} \in \mathbb{R}^n$ so that $\mathbf{X} \mathbf{w} \approx \mathbf{y}$, subject to some desired structure on $\mathbf{w}$. In this work we seek $\mathbf{w}$ that forms a local reconstruction of $\mathbf{y}$ by solving a regularized least squares regression problem. We obtain local solutions through a locality function that promotes the use of columns of $\mathbf{X}$ that are close to $\mathbf{y}$ when used as a regularization term. We prove that, for all levels of regularization and under a mild condition that the columns of $\mathbf{X}$ have a unique Delaunay triangulation, the optimal coefficients' number of non-zero entries is upper bounded by $d+1$, thereby providing local sparse solutions when $d \ll n$. Under the same condition we also show that for any $\mathbf{y}$ contained in the convex hull of $\mathbf{X}$ there exists a regime of regularization parameter such that the optimal coefficients are supported on the vertices of the Delaunay simplex containing $\mathbf{y}$. This provides an interpretation of the sparsity as having structure obtained implicitly from the Delaunay triangulation of $\mathbf{X}$. We demonstrate that our locality regularized problem can be solved in comparable time to other methods that identify the containing Delaunay simplex.

[8]  arXiv:2405.00853 (cross-list from cs.LG) [pdf, ps, other]

Title: Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

Authors: Marco Bressan, Emmanuel Esposito, Maximilian Thiessen

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices that are convex in a certain abstract sense. Monophonic halfspaces, and related notions such as geodesic halfspaces,have recently attracted interest, and several connections have been drawn between their properties(e.g., their VC dimension) and the structure of the underlying graph $G$. We prove several novel results for learning monophonic halfspaces in the supervised, online, and active settings. Our main result is that a monophonic halfspace can be learned with near-optimal passive sample complexity in time polynomial in $n = |V(G)|$. This requires us to devise a polynomial-time algorithm for consistent hypothesis checking, based on several structural insights on monophonic halfspaces and on a reduction to $2$-satisfiability. We prove similar results for the online and active settings. We also show that the concept class can be enumerated with delay $\operatorname{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\operatorname{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (Gonz\'alez et al., 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).

[9]  arXiv:2405.00914 (cross-list from math.OC) [pdf, other]

Title: Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

Authors: Chris Junchi Li

Comments: arXiv admin note: text overlap with arXiv:2307.00126

Subjects: Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)

This paper presents a new algorithm member for accelerating first-order methods for bilevel optimization, namely the \emph{(Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation}, abbreviated as \texttt{(P)RAF${}^2$BA}. The algorithm leverages \emph{fully} first-order oracles and seeks approximate stationary points in nonconvex-strongly-convex bilevel optimization, enhancing oracle complexity for efficient optimization. Theoretical guarantees for finding approximate first-order stationary points and second-order stationary points at the state-of-the-art query complexities are established, showcasing their effectiveness in solving complex optimization tasks. Empirical studies for real-world problems are provided to further validate the outperformance of our proposed algorithms. The significance of \texttt{(P)RAF${}^2$BA} in optimizing nonconvex-strongly-convex bilevel optimization problems is underscored by its state-of-the-art convergence rates and computational efficiency.

[10]  arXiv:2405.00937 (cross-list from cs.LG) [pdf, ps, other]

Title: New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering

Authors: Sanjoy Dasgupta, Eduardo Laber

Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)

Linkage methods are among the most popular algorithms for hierarchical clustering. Despite their relevance the current knowledge regarding the quality of the clustering produced by these methods is limited. Here, we improve the currently available bounds on the maximum diameter of the clustering obtained by complete-link for metric spaces.
One of our new bounds, in contrast to the existing ones, allows us to separate complete-link from single-link in terms of approximation for the diameter, which corroborates the common perception that the former is more suitable than the latter when the goal is producing compact clusters.
We also show that our techniques can be employed to derive upper bounds on the cohesion of a class of linkage methods that includes the quite popular average-link.

[11]  arXiv:2405.00950 (cross-list from cs.LG) [pdf, other]

Title: Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback

Authors: Guojun Xiong, Jian Li

Comments: Accepted by ICML 2024

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

Restless multi-armed bandits (RMAB) play a central role in modeling sequential decision making problems under an instantaneous activation constraint that at most B arms can be activated at any decision epoch. Each restless arm is endowed with a state that evolves independently according to a Markov decision process regardless of being activated or not. In this paper, we consider the task of learning in episodic RMAB with unknown transition functions and adversarial rewards, which can change arbitrarily across episodes. Further, we consider a challenging but natural bandit feedback setting that only adversarial rewards of activated arms are revealed to the decision maker (DM). The goal of the DM is to maximize its total adversarial rewards during the learning process while the instantaneous activation constraint must be satisfied in each decision epoch. We develop a novel reinforcement learning algorithm with two key contributors: a novel biased adversarial reward estimator to deal with bandit feedback and unknown transitions, and a low-complexity index policy to satisfy the instantaneous activation constraint. We show $\tilde{\mathcal{O}}(H\sqrt{T})$ regret bound for our algorithm, where $T$ is the number of episodes and $H$ is the episode length. To our best knowledge, this is the first algorithm to ensure $\tilde{\mathcal{O}}(\sqrt{T})$ regret for adversarial RMAB in our considered challenging settings.

[12]  arXiv:2405.01010 (cross-list from cs.LG) [pdf, other]

Title: Efficient and Adaptive Posterior Sampling Algorithms for Bandits

Authors: Bingshan Hu, Zhiming Huang, Tianyue H. Zhang, Mathias Lécuyer, Nidhi Hegde

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when $T \le 288 e^{64}$, we derive a more practical bound that tightens the coefficient of the leading term %from $288 e^{64}$ to $1270$. Additionally, motivated by large-scale real-world applications that require scalability, adaptive computational resource allocation, and a balance in utility and computation, we propose two parameterized Thompson Sampling-based algorithms: Thompson Sampling with Model Aggregation (TS-MA-$\alpha$) and Thompson Sampling with Timestamp Duelling (TS-TD-$\alpha$), where $\alpha \in [0,1]$ controls the trade-off between utility and computation. Both algorithms achieve $O \left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bound, where $K$ is the number of arms, $T$ is the finite learning horizon, and $\Delta$ denotes the single round performance loss when pulling a sub-optimal arm.

[13]  arXiv:2405.01031 (cross-list from cs.LG) [pdf, other]

Title: The Privacy Power of Correlated Noise in Decentralized Learning

Authors: Youssef Allouah, Anastasia Koloskova, Aymane El Firdoussi, Martin Jaggi, Rachid Guerraoui

Comments: Accepted as conference paper at ICML 2024

Subjects: Machine Learning (cs.LG); Cryptography and Security (cs.CR); Distributed, Parallel, and Cluster Computing (cs.DC); Optimization and Control (math.OC); Machine Learning (stat.ML)

Decentralized learning is appealing as it enables the scalable usage of large amounts of distributed data and resources (without resorting to any central entity), while promoting privacy since every user minimizes the direct exposure of their data. Yet, without additional precautions, curious users can still leverage models obtained from their peers to violate privacy. In this paper, we propose Decor, a variant of decentralized SGD with differential privacy (DP) guarantees. Essentially, in Decor, users securely exchange randomness seeds in one communication round to generate pairwise-canceling correlated Gaussian noises, which are injected to protect local models at every communication round. We theoretically and empirically show that, for arbitrary connected graphs, Decor matches the central DP optimal privacy-utility trade-off. We do so under SecLDP, our new relaxation of local DP, which protects all user communications against an external eavesdropper and curious users, assuming that every pair of connected users shares a secret, i.e., an information hidden to all others. The main theoretical challenge is to control the accumulation of non-canceling correlated noise due to network sparsity. We also propose a companion SecLDP privacy accountant for public use.

[14]  arXiv:2405.01157 (cross-list from cs.LG) [pdf, other]

Title: Tabular and Deep Reinforcement Learning for Gittins Index

Authors: Harshit Dhankar, Kshitij Mishra, Tejas Bodas

Subjects: Machine Learning (cs.LG); Performance (cs.PF); Machine Learning (stat.ML)

In the realm of multi-arm bandit problems, the Gittins index policy is known to be optimal in maximizing the expected total discounted reward obtained from pulling the Markovian arms. In most realistic scenarios however, the Markovian state transition probabilities are unknown and therefore the Gittins indices cannot be computed. One can then resort to reinforcement learning (RL) algorithms that explore the state space to learn these indices while exploiting to maximize the reward collected. In this work, we propose tabular (QGI) and Deep RL (DGN) algorithms for learning the Gittins index that are based on the retirement formulation for the multi-arm bandit problem. When compared with existing RL algorithms that learn the Gittins index, our algorithms have a lower run time, require less storage space (small Q-table size in QGI and smaller replay buffer in DGN), and illustrate better empirical convergence to the Gittins index. This makes our algorithm well suited for problems with large state spaces and is a viable alternative to existing methods. As a key application, we demonstrate the use of our algorithms in minimizing the mean flowtime in a job scheduling problem when jobs are available in batches and have an unknown service time distribution. \

[15]  arXiv:2405.01196 (cross-list from cs.LG) [pdf, other]

Title: Decoupling Feature Extraction and Classification Layers for Calibrated Neural Networks

Authors: Mikkel Jordahn, Pablo Olmos

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

Deep Neural Networks (DNN) have shown great promise in many classification applications, yet are widely known to have poorly calibrated predictions when they are over-parametrized. Improving DNN calibration without comprising on model accuracy is of extreme importance and interest in safety critical applications such as in the health-care sector. In this work, we show that decoupling the training of feature extraction layers and classification layers in over-parametrized DNN architectures such as Wide Residual Networks (WRN) and Visual Transformers (ViT) significantly improves model calibration whilst retaining accuracy, and at a low training cost. In addition, we show that placing a Gaussian prior on the last hidden layer outputs of a DNN, and training the model variationally in the classification training stage, even further improves calibration. We illustrate these methods improve calibration across ViT and WRN architectures for several image classification benchmark datasets.

[16]  arXiv:2405.01251 (cross-list from cs.LG) [pdf, other]

Title: Revisiting semi-supervised training objectives for differentiable particle filters

Authors: Jiaxi Li, John-Joseph Brady, Xiongjie Chen, Yunpeng Li

Comments: 5 pages, 2 figures

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

Differentiable particle filters combine the flexibility of neural networks with the probabilistic nature of sequential Monte Carlo methods. However, traditional approaches rely on the availability of labelled data, i.e., the ground truth latent state information, which is often difficult to obtain in real-world applications. This paper compares the effectiveness of two semi-supervised training objectives for differentiable particle filters. We present results in two simulated environments where labelled data are scarce.

[17]  arXiv:2405.01281 (cross-list from stat.ME) [pdf, ps, other]

Title: Demistifying Inference after Adaptive Experiments

Authors: Aurélien Bibaut, Nathan Kallus

Subjects: Methodology (stat.ME); Econometrics (econ.EM); Statistics Theory (math.ST); Machine Learning (stat.ML)

Adaptive experiments such as multi-arm bandits adapt the treatment-allocation policy and/or the decision to stop the experiment to the data observed so far. This has the potential to improve outcomes for study participants within the experiment, to improve the chance of identifying best treatments after the experiment, and to avoid wasting data. Seen as an experiment (rather than just a continually optimizing system) it is still desirable to draw statistical inferences with frequentist guarantees. The concentration inequalities and union bounds that generally underlie adaptive experimentation algorithms can yield overly conservative inferences, but at the same time the asymptotic normality we would usually appeal to in non-adaptive settings can be imperiled by adaptivity. In this article we aim to explain why, how, and when adaptivity is in fact an issue for inference and, when it is, understand the various ways to fix it: reweighting to stabilize variances and recover asymptotic normality, always-valid inference based on joint normality of an asymptotic limiting sequence, and characterizing and inverting the non-normal distributions induced by adaptivity.

[18]  arXiv:2405.01304 (cross-list from math.ST) [pdf, ps, other]

Title: Misclassification bounds for PAC-Bayesian sparse deep learning

Authors: The Tien Mai

Comments: arXiv admin note: text overlap with arXiv:1908.04847 by other authors

Subjects: Statistics Theory (math.ST); Machine Learning (stat.ML)

Recently, there has been a significant focus on exploring the theoretical aspects of deep learning, especially regarding its performance in classification tasks. Bayesian deep learning has emerged as a unified probabilistic framework, seeking to integrate deep learning with Bayesian methodologies seamlessly. However, there exists a gap in the theoretical understanding of Bayesian approaches in deep learning for classification. This study presents an attempt to bridge that gap. By leveraging PAC-Bayes bounds techniques, we present theoretical results on the prediction or misclassification error of a probabilistic approach utilizing Spike-and-Slab priors for sparse deep learning in classification. We establish non-asymptotic results for the prediction error. Additionally, we demonstrate that, by considering different architectures, our results can achieve minimax optimal rates in both low and high-dimensional settings, up to a logarithmic factor. Moreover, our additional logarithmic term yields slight improvements over previous works. Additionally, we propose and analyze an automated model selection approach aimed at optimally choosing a network architecture with guaranteed optimality.

[19]  arXiv:2405.01365 (cross-list from cs.LG) [pdf, other]

Title: Dynamic Online Ensembles of Basis Expansions

Authors: Daniel Waxman, Petar M. Djurić

Comments: 34 pages, 14 figures. Accepted to Transactions on Machine Learning Research (TMLR)

Journal-ref: Transactions on Machine Learning Research (TMLR), 2024

Subjects: Machine Learning (cs.LG); Signal Processing (eess.SP); Machine Learning (stat.ML)

Practical Bayesian learning often requires (1) online inference, (2) dynamic models, and (3) ensembling over multiple different models. Recent advances have shown how to use random feature approximations to achieve scalable, online ensembling of Gaussian processes with desirable theoretical properties and fruitful applications. One key to these methods' success is the inclusion of a random walk on the model parameters, which makes models dynamic. We show that these methods can be generalized easily to any basis expansion model and that using alternative basis expansions, such as Hilbert space Gaussian processes, often results in better performance. To simplify the process of choosing a specific basis expansion, our method's generality also allows the ensembling of several entirely different models, for example, a Gaussian process and polynomial regression. Finally, we propose a novel method to ensemble static and dynamic models together.

[20]  arXiv:2405.01425 (cross-list from cs.DS) [pdf, other]

Title: In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

Authors: Yunbum Kook, Santosh S. Vempala, Matthew S. Zhang

Comments: 32 pages

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)

We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in R\'enyi divergence (which implies TV, $\mathcal{W}_2$, KL, $\chi^2$). The proof departs from known approaches for polytime algorithms for the problem -- we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density.

[21]  arXiv:2405.01484 (cross-list from cs.HC) [pdf, other]

Title: Designing Algorithmic Recommendations to Achieve Human-AI Complementarity

Authors: Bryce McLaughlin, Jann Spiess

Subjects: Human-Computer Interaction (cs.HC); Machine Learning (cs.LG); Econometrics (econ.EM); Machine Learning (stat.ML)

Algorithms frequently assist, rather than replace, human decision-makers. However, the design and analysis of algorithms often focus on predicting outcomes and do not explicitly model their effect on human decisions. This discrepancy between the design and role of algorithmic assistants becomes of particular concern in light of empirical evidence that suggests that algorithmic assistants again and again fail to improve human decisions. In this article, we formalize the design of recommendation algorithms that assist human decision-makers without making restrictive ex-ante assumptions about how recommendations affect decisions. We formulate an algorithmic-design problem that leverages the potential-outcomes framework from causal inference to model the effect of recommendations on a human decision-maker's binary treatment choice. Within this model, we introduce a monotonicity assumption that leads to an intuitive classification of human responses to the algorithm. Under this monotonicity assumption, we can express the human's response to algorithmic recommendations in terms of their compliance with the algorithm and the decision they would take if the algorithm sends no recommendation. We showcase the utility of our framework using an online experiment that simulates a hiring task. We argue that our approach explains the relative performance of different recommendation algorithms in the experiment, and can help design solutions that realize human-AI complementarity.

[22]  arXiv:2405.01488 (cross-list from cs.LG) [pdf, other]

Title: Digital Twin Generators for Disease Modeling

Authors: Nameyeh Alam, Jake Basilico, Daniele Bertolini, Satish Casie Chetty, Heather D'Angelo, Ryan Douglas, Charles K. Fisher, Franklin Fuller, Melissa Gomes, Rishabh Gupta, Alex Lang, Anton Loukianov, Rachel Mak-McCully, Cary Murray, Hanalei Pham, Susanna Qiao, Elena Ryapolova-Webb, Aaron Smith, Dimitri Theoharatos, Anil Tolwani, Eric W. Tramel, Anna Vidovszky, Judy Viduya, Jonathan R. Walsh

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

A patient's digital twin is a computational model that describes the evolution of their health over time. Digital twins have the potential to revolutionize medicine by enabling individual-level computer simulations of human health, which can be used to conduct more efficient clinical trials or to recommend personalized treatment options. Due to the overwhelming complexity of human biology, machine learning approaches that leverage large datasets of historical patients' longitudinal health records to generate patients' digital twins are more tractable than potential mechanistic models. In this manuscript, we describe a neural network architecture that can learn conditional generative models of clinical trajectories, which we call Digital Twin Generators (DTGs), that can create digital twins of individual patients. We show that the same neural network architecture can be trained to generate accurate digital twins for patients across 13 different indications simply by changing the training set and tuning hyperparameters. By introducing a general purpose architecture, we aim to unlock the ability to scale machine learning approaches to larger datasets and across more indications so that a digital twin could be created for any patient in the world.

[23]  arXiv:2405.01507 (cross-list from cs.LG) [pdf, other]

Title: Accelerating Convergence in Bayesian Few-Shot Classification

Authors: Tianjun Ke, Haoqun Cao, Feng Zhou

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

Bayesian few-shot classification has been a focal point in the field of few-shot learning. This paper seamlessly integrates mirror descent-based variational inference into Gaussian process-based few-shot classification, addressing the challenge of non-conjugate inference. By leveraging non-Euclidean geometry, mirror descent achieves accelerated convergence by providing the steepest descent direction along the corresponding manifold. It also exhibits the parameterization invariance property concerning the variational distribution. Experimental results demonstrate competitive classification accuracy, improved uncertainty quantification, and faster convergence compared to baseline models. Additionally, we investigate the impact of hyperparameters and components. Code is publicly available at https://github.com/keanson/MD-BSFC.

Replacements for Fri, 3 May 24

[24]  arXiv:2305.19001 (replaced) [pdf, other]

Title: High-probability sample complexities for policy evaluation with linear function approximation

Authors: Gen Li, Weichen Wu, Yuejie Chi, Cong Ma, Alessandro Rinaldo, Yuting Wei

Comments: The first two authors contributed equally; paper accepted to IEEE Transactions on Information Theory

Subjects: Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG); Optimization and Control (math.OC); Statistics Theory (math.ST)

[25]  arXiv:2310.05921 (replaced) [pdf, other]

Title: Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions

Authors: Jordan Lekeufack, Anastasios N. Angelopoulos, Andrea Bajcsy, Michael I. Jordan, Jitendra Malik

Comments: 8 pages, 5 figures

Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Robotics (cs.RO); Methodology (stat.ME)

[26]  arXiv:2401.15502 (replaced) [pdf, other]

Title: Differentially private Bayesian tests

Authors: Abhisek Chakraborty, Saptati Datta

Subjects: Machine Learning (stat.ML); Cryptography and Security (cs.CR); Machine Learning (cs.LG)

[27]  arXiv:2402.03008 (replaced) [pdf, other]

Title: Diffusive Gibbs Sampling

Authors: Wenlin Chen, Mingtian Zhang, Brooks Paige, José Miguel Hernández-Lobato, David Barber

Comments: Accepted for publication at ICML 2024. Code available: this https URL

Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Computation (stat.CO)

[28]  arXiv:2403.15527 (replaced) [pdf, other]

Title: Conformal online model aggregation

Authors: Matteo Gasparin, Aaditya Ramdas

Comments: 22 pages, 12 figures. arXiv admin note: text overlap with arXiv:2401.09379

Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG)

[29]  arXiv:2404.10727 (replaced) [pdf, other]

Title: How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model

Authors: Umberto Tomasini, Matthieu Wyart

Comments: 9 pages, 6 figures

Subjects: Machine Learning (stat.ML); Disordered Systems and Neural Networks (cond-mat.dis-nn); Machine Learning (cs.LG)

[30]  arXiv:2205.11787 (replaced) [pdf, other]

Title: Quadratic models for understanding catapult dynamics of neural networks

Authors: Libin Zhu, Chaoyue Liu, Adityanarayanan Radhakrishnan, Mikhail Belkin

Comments: accepted in ICLR 2024; changed the title

Subjects: Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)

[31]  arXiv:2212.09201 (replaced) [pdf, other]

Title: Spectral Regularized Kernel Two-Sample Tests

Authors: Omar Hagrass, Bharath K. Sriperumbudur, Bing Li

Comments: 75 pages, to be published in the Annals of Statistics

Subjects: Statistics Theory (math.ST); Machine Learning (cs.LG); Machine Learning (stat.ML)

[32]  arXiv:2303.11786 (replaced) [pdf, other]

Title: Skeleton Regression: A Graph-Based Approach to Estimation with Manifold Structure

Authors: Zeyu Wei, Yen-Chi Chen

Subjects: Machine Learning (cs.LG); Methodology (stat.ME); Machine Learning (stat.ML)

[33]  arXiv:2303.15121 (replaced) [pdf, ps, other]

Title: Learning linear dynamical systems under convex constraints

Authors: Hemant Tyagi, Denis Efimov

Comments: 29 pages; added Example 4 (Lipschitz regression), Corollary 4 and Remark 2; corrected minor typos

Subjects: Statistics Theory (math.ST); Systems and Control (eess.SY); Optimization and Control (math.OC); Machine Learning (stat.ML)

[34]  arXiv:2306.06545 (replaced) [pdf, other]

Title: A Probabilistic Framework for Modular Continual Learning

Authors: Lazar Valkov, Akash Srivastava, Swarat Chaudhuri, Charles Sutton

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

[35]  arXiv:2309.01837 (replaced) [pdf, other]

Title: Delegating Data Collection in Decentralized Machine Learning

Authors: Nivasini Ananthakrishnan, Stephen Bates, Michael I. Jordan, Nika Haghtalab

Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)

[36]  arXiv:2310.02246 (replaced) [pdf, other]

Title: Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances

Authors: Mikhail Khodak, Edmond Chow, Maria-Florina Balcan, Ameet Talwalkar

Comments: ICLR 2024 Spotlight

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Numerical Analysis (math.NA); Machine Learning (stat.ML)

[37]  arXiv:2312.16427 (replaced) [pdf, other]

Title: Learning to Embed Time Series Patches Independently

Authors: Seunghan Lee, Taeyoung Park, Kibok Lee

Comments: ICLR 2024

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

[38]  arXiv:2401.01404 (replaced) [pdf, other]

Title: Scalable network reconstruction in subquadratic time

Authors: Tiago P. Peixoto

Comments: 12 pages, 7 figures

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Data Analysis, Statistics and Probability (physics.data-an); Computation (stat.CO); Machine Learning (stat.ML)

[39]  arXiv:2403.04764 (replaced) [pdf, other]

Title: TS-RSR: A provably efficient approach for batch bayesian optimization

Authors: Zhaolin Ren, Na Li

Comments: Revised presentation and organization of theoretical results

Subjects: Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)

[40]  arXiv:2404.13663 (replaced) [pdf, other]

Title: Cumulative Hazard Function Based Efficient Multivariate Temporal Point Process Learning

Authors: Bingqing Liu

Comments: 8 pages

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

[41]  arXiv:2404.16444 (replaced) [pdf, other]

Title: Automating the Discovery of Partial Differential Equations in Dynamical Systems

Authors: Weizhen Li, Rui Carvalho

Comments: 18 pages, 6 figures, 1 table

Subjects: Machine Learning (cs.LG); Dynamical Systems (math.DS); Applications (stat.AP); Machine Learning (stat.ML)

[42]  arXiv:2404.19756 (replaced) [pdf, other]

Title: KAN: Kolmogorov-Arnold Networks

Authors: Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruehle, James Halverson, Marin Soljačić, Thomas Y. Hou, Max Tegmark

Comments: 48 pages, 20 figures. Codes are available at this https URL

Subjects: Machine Learning (cs.LG); Disordered Systems and Neural Networks (cond-mat.dis-nn); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

• New submissions
• Cross-lists
• Replacements