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.
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.
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.
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.
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.
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.
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.
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.
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.
Study high-dimensional logistic regression with missing data, providing exact error characterizations.
problem High-dimensional logistic regression with missing or corrupted covariates.
method Exact characterizations of prediction and estimation errors under independence and moment conditions.
result Characterizations are universal and hold for various imputation strategies.
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.
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.
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.
New bounds show robust models can generalize well, contrary to prior theories.
problem Existing robustness-based error bounds are vacuous for the best classifier.
method Developed novel bounds that converge to the true error of the best classifier.
result New bounds converge to the true error of the best classifier, improving generalization.
We analyse the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix …
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.
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…
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.
We analyze the problem of learning a single user's preferences in an active learning setting, sequentially and adaptively querying the user over a finite time horizon. Learning is conducted via choice-based queries, where the user selects her preferred option among a small subset of offered alternatives. These queries …
Minimizes indecisions in selective classification to control misclassification rates.
problem Controlling misclassification rates in high-risk scenarios.
method Using indecisions to control misclassification rates, even below Bayes optimal.
result Control of misclassification rates to any user-specified level, even below Bayes optimal.
Optimal graph classification uses message-passing neural networks.
problem Node classification on sparse graphs with fixed feature dimensions.
method Asymptotic local Bayes optimality, message-passing graph neural networks.
result Optimal message-passing architecture interpolates between MLP and convolution.
New algorithm for signal estimation in noisy matrix models.
problem Signal estimation in rectangular spiked matrix models with rotationally invariant noise.
method Orthogonal Approximate Message Passing (OAMP) algorithm for signal estimation.
result Optimal OAMP algorithm minimizes mean-squared error and achieves Bayes-optimal performance.
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.
Self-training improves weak classifiers in mixture models.
problem Improving weak classifiers in mixture models.
method Iterative self-training algorithm using pseudolabels and unlabeled data.
result Self-training converts weak learners to strong learners in mixture models.
Bottlenecks of binary classification from positive and unlabeled data (PU classification) are the requirements that given unlabeled patterns are drawn from the test marginal distribution, and the penalty of the false positive error is identical to the false negative error. However, such requirements are often not fulfi…
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.
This paper introduces a set of algorithms for Monte-Carlo Bayesian reinforcement learning. Firstly, Monte-Carlo estimation of upper bounds on the Bayes-optimal value function is employed to construct an optimistic policy. Secondly, gradient-based algorithms for approximate upper and lower bounds are introduced. Finally…
Bad models can teach well by replicating noise.
problem Overparameterized models can replicate noise in training data.
method Knowledge distillation from noisy samplers.
result Distillation from samplers approximates Bayes optimal classifier.
Bayes-optimal classifiers are robust to adversarial attacks, unlike CNNs trained on the same data.
problem The vulnerability of modern CNN classifiers to adversarial examples.
method Constructing realistic image datasets and deriving analytic conditions for Bayes-optimal classifiers.
result Bayes-optimal classifiers are robust to adversarial attacks, unlike CNNs trained on the same data.
We address the problem of learning to benchmark the best achievable classifier performance. In this problem the objective is to establish statistically consistent estimates of the Bayes misclassification error rate without having to learn a Bayes-optimal classifier. Our learning to benchmark framework improves on previ…
This paper improves binary classification methods beyond accuracy, especially in imbalanced datasets.
problem Binary classification performance metrics often fail to reflect real-world consequences, especially in imbalanced datasets.
method Derives a generalized Bayes-optimal classifier from accuracy to any performance metric, removing assumptions and providing finite-sample statistical guarantees.
result Optimal classification performance depends on class imbalance properties, providing new insights and guarantees.
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.
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.
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.
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 integrating multivariate normals and computing classification measures.
problem Computing performance of multivariate normal models is challenging due to lack of general analytical expressions.
method Mathematical results and open-source software for integrating and analyzing multivariate normal distributions.
result Provides tools for calculating classification errors, discriminability, and reliability.
In this work we show that, using the eigen-decomposition of the adjacency matrix, we can consistently estimate latent positions for random dot product graphs provided the latent positions are i.i.d. from some distribution. If class labels are observed for a number of vertices tending to infinity, then we show that the …
Algorithm learns decision trees from noisy data.
problem Learning stochastic decision trees from corrupted samples.
method Quasipolynomial-time algorithm for adversarial noise.
result Returns a hypothesis with error within 2η+ε of optimal. 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.
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.
This study connects prevalence and machine learning for diagnostic testing.
problem Uncertainty quantification in machine learning for diagnostic tests.
method Developed a numerical homotopy algorithm to estimate classification boundaries and quantify uncertainty.
result The proposed method stabilizes uncertainty quantification in machine learning for diagnostic tests.
This work addresses privacy in Bayesian estimation, achieving near-optimal error rates.
problem Preserving privacy in Bayesian estimation while maintaining optimal estimation accuracy.
method Developed efficient algorithms for Gaussian mean estimation and linear regression with near-optimal error rates, leveraging sum-of-squares techniques.
result Achieved near-optimal mean-squared error rates for Bayesian mean estimation and linear regression, with computational-statistical gaps.
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 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…
New tests for binary classification regression functions without distribution assumptions.
problem Testing regression functions in binary classification without distributional assumptions.
method Conditional kernel mean embeddings and resampling-based framework.
result Distribution-free hypothesis tests with exact type I error control.
Researchers compute Bayes error for classification models using normalizing flows.
problem Evaluating the inherent difficulty of classification problems.
method Invertible transformations and Gaussian base distributions to compute Bayes error.
result State-of-the-art models can achieve near-optimal accuracy but not always.