Bayes-optimal limits in PCA with structured noise are determined.
problem Analyzing statistical dependencies in measurement noise for high-dimensional inference.
method Study of spiked matrix model with low-order polynomial orthogonal noise, providing Bayes-optimal limits and proposing a novel AMP.
result A novel AMP algorithm reaches the information-theoretic limits for more general priors.
Bayes-optimal learning of deep random networks with Gaussian weights is studied.
problem Learning a target function corresponding to a deep, extensive-width, non-linear neural network with random Gaussian weights.
method Closed-form expressions for Bayes-optimal test error, ridge regression, kernel and random features regression are computed.
result Optimally regularized ridge regression and kernel regression achieve Bayes-optimal performances, while logistic loss yields a near-optimal test error for classification.
Study of Bayes optimal learning in high-dimensional linear regression with network side information.
problem Bayes optimal learning in high-dimensional linear regression with network side information.
method Introduce a Reg-Graph model and an iterative AMP algorithm for Bayes optimality under general conditions.
result Characterization of the limiting mutual information between latent signal and data observed.
Study exact limits of matrix reconstruction from noisy projections.
problem Reconstructing matrices from linear projections with high-dimensional data.
method Asymptotic analysis, universality properties, and generalized linear models.
result Exact asymptotic equations for optimal learning performance.
Crowdsourcing is a strategy to categorize data through the contribution of many individuals. A wide range of theoretical and algorithmic contributions are based on the model of Dawid and Skene [1]. Recently it was shown in [2,3] that, in certain regimes, belief propagation is asymptotically optimal for data generated f…
Bayes-optimal learning of a neural network with quadratic activations is achieved with GAMP-RIE.
problem Learning a neural network with quadratic activations from quadratic samples.
method Combining approximate message passing with rotationally invariant matrix denoising.
result Derives a closed-form expression for Bayes-optimal test error.
Paper establishes limits for accurately estimating low-rank matrices from noisy, non-linear data.
problem Estimating low-rank matrices from noisy, non-linear observations.
method Proves strong universality result with equivalent Gaussian model and effective prior parameters.
result Signal-to-noise ratio requirement grows as $N^{ rac 12 (1-1/k_F)}$ for accurate reconstruction.
This paper tackles fair Bayes-optimal classifiers under predictive parity, proving their limitations and proposing a new algorithm.
problem Ensuring fair Bayes-optimal classifiers under predictive parity, especially when group performance levels vary widely.
method Proving the limitations of fair Bayes-optimal classifiers under predictive parity and proposing a new adaptive thresholding algorithm, FairBayes-DPP.
result Fair Bayes-optimal classifiers under predictive parity may not hold if group performance levels vary widely, leading to within-group unfairness.
The study sets limits on how robust classifiers can be against adversarial attacks.
problem Understanding the limits of robustness in classification models against adversarial attacks.
method Utilized optimal transport theory to derive variational formulae and explicit lower-bounds on Bayes-optimal error.
result Explicit lower-bounds on the Bayes-optimal error for distance-based attacks, universal in geometry of class-conditional distributions.
New framework shows cross-attention improves multi-modal in-context learning.
problem Understanding multi-modal in-context learning in neural networks.
method Mathematical framework and linearized cross-attention mechanism.
result Cross-attention mechanism is provably optimal for multi-modal in-context learning.
We study the rates of convergence from empirical surrogate risk minimizers to the Bayes optimal classifier. Specifically, we introduce the notion of \emph{consistency intensity} to characterize a surrogate loss function and exploit this notion to obtain the rate of convergence from an empirical surrogate risk minimizer…
The paper tackles fair classification with multiple sensitive features.
problem Existing fair classification methods often consider a single sensitive feature, but in practice, individuals are defined by multiple sensitive features.
method Characterizes Bayes-optimal fair classifiers for multiple sensitive features under various fairness measures, proposing in-processing and post-processing algorithms.
result Bayes-optimal fair classifiers for multiple sensitive features are instance-dependent thresholding rules that rely on a weighted sum of group membership probabilities.
Unified framework for Bayes-optimal classifiers under group fairness.
problem Mitigating disparate impacts from algorithmic predictions in high-stakes decision-making.
method Unified framework based on Neyman-Pearson argument for deriving Bayes-optimal classifiers under group fairness constraints.
result Proposes FairBayes method that directly controls disparity and achieves optimal fairness-accuracy tradeoff.
Study shows how classifiers can approach Bayes error in high-dimensional settings.
problem Generalization error in high-dimensional perceptrons.
method Proved a formula for generalization error using convex optimization and observed that logistic and hinge regression can approach Bayes error closely.
result Logistic and hinge regression can approach Bayes-optimal generalization error closely in high-dimensional settings.
Regularization helps improve classification of noisy high-dimensional data.
problem Classifying high-dimensional noisy Gaussian mixture with limited oracle knowledge.
method Analysis of regularized convex classifiers including ridge, hinge, and logistic regression.
result Regularization can reach Bayes-optimal performance under certain conditions.
Sharp feature transitions revealed in extensive-width networks.
problem Learning hierarchical features from noisy queries in large networks.
method Information-theoretic analysis and heuristic decoupling argument.
result Sequential phase transitions in feature learnability and effective width.
ContraBAR uses contrastive learning to learn Bayes-optimal policies in RL.
problem Learning optimal policies for unknown tasks sampled from a known distribution.
method Proposes ContraBAR, a meta RL algorithm using contrastive predictive coding (CPC) for belief inference.
result ContraBAR achieves comparable performance to state-of-the-art methods and is computationally efficient.
Recent advances in Bayesian reinforcement learning (BRL) have shown that Bayes-optimality is theoretically achievable by modeling the environment's latent dynamics using Flat-Dirichlet-Multinomial (FDM) prior. In self-interested multi-agent environments, the transition dynamics are mainly controlled by the other agent'…
Bayes optimal algorithm under certain conditions doesn't achieve exponential simple regret.
problem Best arm identification with normal rewards over time.
method Fixed-budget best arm identification problem with rewards from normal distributions. Evaluates performance via simple regret.
result Bayes optimal algorithm does not yield exponential decrease in simple regret.
The study analyzes multi-class teacher-student perceptron performance and generalization errors.
problem Analyzing multi-class classification with the teacher-student perceptron.
method Deriving asymptotic expressions for Bayes-optimal and empirical risk minimization (ERM) generalization errors.
result Regularised cross-entropy minimization yields close-to-optimal accuracy for multi-class classification.
This study optimizes multi-modal learning thresholds and algorithms in high dimensions.
problem Optimizing multi-modal learning performance in high-dimensional data.
method Analytical quantification and derivation of AMP algorithm with state evolution analysis.
result Bayes-optimal performance and recovery thresholds derived for multi-modal data.
Study improves flow-based model training from few samples.
problem Training flow-based models from limited data.
method Sharp analysis of two-layer autoencoder with finite sample complexity.
result Generative flow approximates target density with rate Θ_n(1/n).
Optimal adaptive experiment for choosing best treatment with binary outcomes.
problem Choosing the best treatment from binary options in an adaptive experiment.
method Adaptive experiment with two phases: treatment allocation and choice. Neyman allocation method used.
result Neyman allocation is minimax and Bayes optimal, matching lower bounds for regret.
Unified approach for fair classification with overlapping groups.
problem Ensuring fairness across multiple overlapping groups in prediction problems.
method Probabilistic population analysis leading to Bayes-optimal classifier, unifying existing methods.
result Outperforms baselines in fairness-performance tradeoff on real datasets.
The paper proves statistical consistency and fairness guarantees for a plug-in algorithm.
problem Establishing statistical guarantees for fairness-aware binary classification.
method Proves statistical consistency and derives finite sample guarantees for the plug-in algorithm.
result The plug-in algorithm is statistically consistent and guarantees fairness and differential privacy.
Develops methods for fair classification under linear disparity constraints.
problem Disparate impacts of machine learning algorithms on protected groups.
method Bayes-optimal fair classification methods via pre-, in-, and post-processing.
result Explicit forms of Bayes-optimal fair classifiers under linear disparity measures.
Study optimizes best-arm identification with minimax and Bayes strategies.
problem Efficiently identifying the best arm in fixed-budget scenarios.
method Adaptive procedure with two stages: pilot phase and minimax game.
result Single strategy is asymptotically minimax and Bayes optimal.
Focal loss improves classification but not class-posterior probability estimation.
problem Improving class-posterior probability estimation from focal loss.
method Proved classification-calibration and derived a transformation to recover true class-posterior probabilities.
result A transformation of the confidence score from focal loss minimization allows recovery of true class-posterior probabilities.
Study on conditions for Bayes optimal classifier in adversarial robustness.
problem Existence of Bayes optimal classifier for adversarial robustness.
method General sufficient conditions for existence of Bayes optimal classifier.
result Guaranteed existence of Bayes optimal classifier under certain conditions.
We consider effort allocation in crowdsourcing, where we wish to assign labeling tasks to imperfect homogeneous crowd workers to maximize overall accuracy in a continuous-time Bayesian setting, subject to budget and time constraints. The Bayes-optimal policy for this problem is the solution to a partially observable Ma…
AIM models explain deep learning in attention layers, offering solvable insights.
problem Understanding how deep learning models learn in attention layers.
method Statistical mechanics and random matrix theory.
result Closed-form predictions for Bayes-optimal generalization error and gradient descent performance.
Memory-based models can learn to approximate Bayes-optimal predictors for non-stationary data.
problem Learning from non-stationary data with unobserved switching points.
method Memory-based neural models, including Transformers, LSTMs, and RNNs, trained to minimize log loss.
result Memory-based models can accurately approximate known Bayes-optimal algorithms and perform Bayesian inference over latent switching points.
New method quantifies uncertainty for near-optimal ML algorithms.
problem Uncertainty quantification for near-Bayes optimal ML algorithms.
method Developed a martingale posterior to recover Bayesian posterior from ML algorithms.
result Proved practical uncertainty quantification method applicable to general ML algorithms.
Since the discovery of adversarial examples - the ability to fool modern CNN classifiers with tiny perturbations of the input, there has been much discussion whether they are a "bug" that is specific to current neural architectures and training methods or an inevitable "feature" of high dimensional geometry. In this pa…
Paper studies how few pretraining tasks are needed for a linear model to solve new tasks.
problem How many pretraining tasks are needed for a linear model to solve new tasks?
method Pretrained a linear attention model for linear regression with a Gaussian prior.
result Effective pretraining requires a small number of independent tasks, and the model closely matches Bayes optimal.
In statistical learning for real-world large-scale data problems, one must often resort to "streaming" algorithms which operate sequentially on small batches of data. In this work, we present an analysis of the information-theoretic limits of mini-batch inference in the context of generalized linear models and low-rank…
Combines linear and spectral estimators for signal recovery in generalized linear models.
problem Signal recovery from generalized linear models with Gaussian sensing matrix.
method Optimal combination of a linear estimator and a spectral estimator using an AMP algorithm.
result Bayes-optimal combination of estimators improves signal recovery.
The paper explores robust classifiers for imbalanced Gaussian data.
problem Adversarial robustness in machine learning with imbalanced data.
method Developed exact and approximate Bayes-optimal robust classifiers for Gaussian classification problems.
result Revealed fundamental tradeoffs between standard and robust accuracy.
We consider compressed sensing formulated as a minimization problem of nonconvex sparse penalties, Smoothly Clipped Absolute deviation (SCAD) and Minimax Concave Penalty (MCP). The nonconvexity of these penalties is controlled by nonconvexity parameters, and L1 penalty is contained as a limit with respect to these para…
LDA-GO improves LDA for high-dimensional data via gradient optimization.
problem LDA struggles in high-dimensional settings due to unreliable covariance matrix estimation.
method LDA-GO learns a low-rank precision matrix via gradient optimization, automatically selecting between Gaussian likelihood and cross-entropy loss.
result LDA-GO outperforms other LDA variants in sparse-signal high-dimensional regimes.
Continuum transformers learn operators in context via gradient descent.
problem Generalizing transformers to handle infinite-dimensional inputs for in-context learning.
method Gradient descent in an operator RKHS, leveraging generalized representer theorems and gradient flows.
result Operator learned in context is Bayes Optimal Predictor in infinite depth limit.
SPRT-TANDEM improves sequential classification accuracy with fewer samples.
problem Efficiently classifying sequential data with high accuracy and low sampling cost.
method Deep neural network-based SPRT algorithm that estimates log-likelihood ratio of two hypotheses.
result SPRT-TANDEM achieves statistically significantly better classification accuracy than other classifiers with fewer samples.
Paper tackles regression with cost-based rejection, balancing prediction and rejection costs.
problem Regression with cost-based rejection, balancing prediction and rejection costs in a continuous target space.
method Formulated expected risk, derived Bayes optimal solution, proposed surrogate loss function.
result Bayes optimal solution can be recovered by the proposed surrogate loss function.
In many applications of black-box optimization, one can evaluate multiple points simultaneously, e.g. when evaluating the performances of several different neural network architectures in a parallel computing environment. In this paper, we develop a novel batch Bayesian optimization algorithm --- the parallel knowledge…
Paper solves Bayesian bandit problem with continuous-time limit and approximate policy.
problem Finding optimal policy in Bayesian bandit problems with large horizons.
method Reformulates Bayesian bandit problem as continuous Hamilton-Jacobi-Bellman (HJB) equation and proposes approximate Bayes-optimal policy.
result Approximate Bayes-optimal policy for large horizons with constant computational cost.
This paper introduces SS-MAMP to address convergence issues in AMP algorithms.
problem Convergence issues in AMP algorithms for signal reconstruction.
method Proposes SS-MAMP algorithm framework for right-unitarily invariant sensing matrices and Lipschitz-continuous local processors.
result Covariance matrices of SS-MAMP are L-banded and convergent, ensuring optimal convergence.
Adaptive classifier optimizes high-dimensional data with spiked covariance structure.
problem Classification of high-dimensional data with spiked covariance structure.
method Adaptive classifier that whitens data, screens features, and applies Fisher linear discriminant.
result The classifier is Bayes optimal under certain conditions and performs well on real and synthetic data.
Meta-learning method improves PU classification performance.
problem Improving binary classifiers from PU data in unseen tasks.
method Adapts model to PU data using related tasks and neural networks.
result Proposed method outperforms existing methods on synthetic and real-world datasets.