New tighter confidence bounds for sequential kernel regression.
problem Quantifying uncertainty in sequential learning algorithms.
method Martingale tail inequalities and conic programming.
result New confidence bounds are tighter than existing ones.
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.
New algorithms improve machine learning performance with explicit regret bounds.
problem Improving machine learning performance with explicit regret bounds.
method Projection-based linear regression algorithms with a focus on modern machine-learning models and their algorithmic performance.
result Established a priori regret bounds with explicit λ-dependence.
In the field of reinforcement learning there has been recent progress towards safety and high-confidence bounds on policy performance. However, to our knowledge, no practical methods exist for determining high-confidence policy performance bounds in the inverse reinforcement learning setting---where the true reward fun…
New method estimates model performance bounds without ground truth labels.
problem Evaluation of weakly supervised models without direct access to ground truth labels.
method Formulates model evaluation as a partial identification problem and uses Fréchet bounds for performance estimation.
result Derives accurate and computationally efficient bounds for key metrics like accuracy, precision, recall, and F1-score.
Active learning algorithms propose which unlabeled objects should be queried for their labels to improve a predictive model the most. We study active learners that minimize generalization bounds and uncover relationships between these bounds that lead to an improved approach to active learning. In particular we show th…
Boosts Q-learning by using value function bounds.
problem Efficiently solving new tasks using past experience.
method Derives double-sided bounds on optimal value function and uses them to update Q-function.
result Boosted training performance through alternative Q-function update method.
Proposes a method to compute valid lower confidence bounds for multiple models selected based on their performance.
problem Model selection and evaluation in machine learning.
method Interprets model selection as a simultaneous inference problem, uses bootstrap tilting and maxT-type multiplicity correction.
result Yields valid lower confidence bounds that are at least as good as standard approaches and reliably reach nominal coverage probability.
The belief propagation (BP) algorithm is widely applied to perform approximate inference on arbitrary graphical models, in part due to its excellent empirical properties and performance. However, little is known theoretically about when this algorithm will perform well. Using recent analysis of convergence and stabilit…
New bound on machine learning model performance using Jensen-Shannon information.
problem Understanding the performance of machine learning models.
method Proposes a new information-theoretic bound on generalization error.
result Shows that the new bound can be tighter than mutual information-based bounds under certain conditions.
Survey and compare PAC-Bayes bounds for bandit problems.
problem Designing and evaluating bandit algorithms with strong performance guarantees.
method PAC-Bayes bounds applied to bandit problems.
result PAC-Bayes bounds useful for offline bandit algorithms, but loose for online algorithms.
New self-imitation learning method improves performance in continuous control tasks.
problem Improving off-policy learning in continuous control tasks.
method Proposes a n-step lower bound to generalize lower-bound Q-learning and introduces a new family of self-imitation learning algorithms.
result n-step lower bound Q-learning achieves a better trade-off between bias and contraction rate, leading to improved performance.
New findings show margins are not sufficient for explaining gradient boosting performance.
problem The inadequacy of margin explanations in explaining the performance of gradient boosting.
method Demonstrated and proved a stronger margin-based generalization bound for boosted classifiers.
result Proved a stronger margin-based generalization bound that explains the performance of modern gradient boosters.
The paper analyzes the generalizability of linear autoencoders and multivariate linear regression.
problem Limited theoretical understanding of linear autoencoders' performance.
method Proposes a PAC-Bayes bound for multivariate linear regression and shows LAEs as constrained models.
result The proposed PAC-Bayes bound is tight and correlates with practical metrics.
We consider the problem of dictionary learning under the assumption that the observed signals can be represented as sparse linear combinations of the columns of a single large dictionary matrix. In particular, we analyze the minimax risk of the dictionary learning problem which governs the mean squared error (MSE) perf…
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly with…
This paper presents eight PAC-Bayes bounds to analyze the generalization performance of multi-view classifiers. These bounds adopt data dependent Gaussian priors which emphasize classifiers with high view agreements. The center of the prior for the first two bounds is the origin, while the center of the prior for the t…
New computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
We study two time-scale linear stochastic approximation algorithms, which can be used to model well-known reinforcement learning algorithms such as GTD, GTD2, and TDC. We present finite-time performance bounds for the case where the learning rate is fixed. The key idea in obtaining these bounds is to use a Lyapunov fun…
Existing guarantees in terms of rigorous upper bounds on the generalization error for the original random forest algorithm, one of the most frequently used machine learning methods, are unsatisfying. We discuss and evaluate various PAC-Bayesian approaches to derive such bounds. The bounds do not require additional hold…
New algorithms for private GLM estimation with minimax lower bounds.
problem Privacy in generalized linear models.
method Differentially private algorithms using projected gradient descent.
result Nearly rate-optimal performance with privacy-constrained minimax lower bounds.
Meta-learning bounds derived using PAC-Bayes theory for improved generalization.
problem Uncertainty in generalization performance for meta-learning with new tasks.
method PAC-Bayes relative entropy bounds and empirical risk minimization (ERM) method.
result Competitive generalization performance and rapid convergence with data-dependent prior.
We obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used her…
New algorithm guarantees performance on noisy data.
problem Learning with noisy data and heavy-tailed distributions.
method Anytime online-to-batch conversion for smooth objectives.
result Stochastic gradient-based algorithm with sub-Gaussian error bounds.
HAMBO estimates policy performance by hallucinating worst-case trajectories, providing valid lower bounds.
problem Conservative off-policy evaluation of policies in real-world applications.
method HAMBO hallucinates worst-case trajectories based on learned model uncertainty.
result Valid lower bounds on policy performance, converging to true expected return under regular conditions.
One significant challenge to scaling entity resolution algorithms to massive datasets is understanding how performance changes after moving beyond the realm of small, manually labeled reference datasets. Unlike traditional machine learning tasks, when an entity resolution algorithm performs well on small hold-out datas…
The paper analyzes and proposes an algorithm for multi-modal nonlinear embeddings with theoretical performance bounds.
problem Generalizability of multi-modal nonlinear embeddings to unseen data.
method Theoretical analysis and a multi-modal nonlinear representation learning algorithm motivated by performance bounds.
result The proposed algorithm yields promising performance in multi-modal image classification and cross-modal image-text retrieval applications.
We propose a new PAC-Bayesian bound and a way of constructing a hypothesis space, so that the bound is convex in the posterior distribution and also convex in a trade-off parameter between empirical performance of the posterior distribution and its complexity. The complexity is measured by the Kullback-Leibler divergen…
Study bounds graph neural networks' over-parameterized error.
problem Understanding graph neural networks' performance in over-parameterized regimes.
method Developed mean-field regime bounds for graph convolutional and message passing neural networks.
result Established upper bounds with a convergence rate of O(1/n) for generalization error. Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong problem-dependent bounds could help illuminate the key features of what makes a RL problem hard and reduc…
Study reveals mutual information is crucial for understanding algorithm performance in stochastic convex optimization.
problem Uncertainty in capturing the exceptional performance of learning algorithms using existing information-theoretic generalization bounds.
method Examined the relationship between mutual information and generalization in stochastic convex optimization.
result Mutual information is necessary for true risk minimization in stochastic convex optimization, indicating existing bounds fall short.
Improved Bayesian optimisation method using randomised Gaussian process UCB.
problem Improving performance in Bayesian optimisation.
method Developed a modified Gaussian process upper confidence bound (GP-UCB) acquisition function.
result The method achieves better performance than GP-UCB in various problems.
LBQL improves Q-learning by using lookahead bounds for better performance.
problem Improving Q-learning in stochastic environments.
method LBQL uses lookahead bounds to construct dual penalties and track upper and lower bounds via stochastic approximation.
result LBQL converges faster and is more robust to hyperparameters than standard Q-learning.
This work introduces a new data-driven estimator for the Bayesian Cramér-Rao bound using score matching.
problem Benchmarking the performance of statistical estimators and providing a principled metric for system design and optimization.
method Score matching technique to estimate the Bayesian Cramér-Rao bound from training data.
result Developed novel non-asymptotic bounds on the score matching error and the Bayesian CRB estimator.
This paper optimizes MDP policies for efficient state aggregation.
problem Optimizing policies in aggregated Markov chains while preserving optimal performance.
method Homomorphic mappings to establish optimal policy equivalence and derive performance bounds.
result Developed HPG and EBHPG methods for efficient aggregation and policy optimization.
Recently, an extension of independent component analysis (ICA) from one to multiple datasets, termed independent vector analysis (IVA), has been the subject of significant research interest. IVA has also been shown to be a generalization of Hotelling's canonical correlation analysis. In this paper, we provide the ident…
Paper extends Bayesian Cramér-Rao bound with geometric considerations.
problem Estimation of covariance matrices with geometric structures.
method Intrinsic Bayesian Cramér-Rao bound with Riemannian geometry.
result Performance bounds for covariance matrix estimation.
New bounds for nearly-linear networks without training.
problem Generalization of neural networks close to linearity.
method Perturbation of linear networks to derive bounds.
result First non-vacuous bounds for neural nets.
Improved Gaussian process regression with tighter log marginal likelihood bounds.
problem Improving predictive performance in Gaussian process regression models.
method Lower bound on log marginal likelihood using conjugate gradients.
result Improved predictive performance compared to other conjugate gradient based approaches.
New bounds for quantum circuits depend on how data is encoded.
problem Lack of explicit dependence on data encoding in generalization bounds for PQCs.
method Derived generalization bounds that depend on data encoding strategies using Rademacher complexity and metric entropy.
result Optimal data-encoding strategies can be selected via structural risk minimization.
This work improves bounds on Bayesian coreset quality.
problem Limitations of existing theoretical analysis of Bayesian coresets.
method Develops general upper and lower bounds on KL divergence.
result Demonstrates flexibility of new theoretical bounds in various models.
Optimal simple regret bound for Gaussian Process bandits.
problem Sequential optimization of expensive-to-evaluate functions.
method Proved a bound on simple regret for pure exploration algorithms.
result Order optimal bound on simple regret for Gaussian Process bandits.
Spectral methods achieve near-optimal performance in orthogonal and permutation group synchronization.
problem Recovering group elements from pairwise measurements in computer vision.
method Spectral methods applied with the leave-one-out technique.
result Near-optimal performance bounds for orthogonal and permutation group synchronization established.
Paper develops PAC-Bayes bounds for unknown linear systems.
problem Learning controllers for unknown stochastic linear discrete-time systems.
method PAC-Bayes framework for data-dependent high probability bounds.
result Proposes efficient learning algorithms with theoretical guarantees.
New IDS algorithm refines parameter norm bounds for better bandit performance.
problem Frequentist IDS requires tight norm bounds, which are often unavailable in practice.
method Iteratively refines a high-probability upper bound on true parameter norm using data.
result Regret bounds independent of assumed parameter norm, outperforming state-of-the-art algorithms.
Improved graph neural network bounds using graph diffusion matrix.
problem Empirical performance of graph neural networks on real-world graphs.
method Unified model of graph neural networks, focusing on feature diffusion matrix stability.
result Generalization bounds scale with largest singular value of feature diffusion matrix, smaller than prior bounds.
Study provides bounds for estimating intrinsic dimension using Gaussian kernels.
problem Estimating intrinsic dimension from data.
method Finite-sample concentration and anti-concentration bounds for Gaussian kernel sums.
result Explicit dependence on sample size, bandwidth, and geometric parameters.
A new method to measure neural network expressiveness using tighter upper bounds.
problem Measuring the expressiveness of deep neural networks (DNNs).
method Proposes a new tighter upper bound for the number of linear regions in rectifier networks, using matrix computation.
result The proposed upper bound is tighter than existing ones and explains the performance improvements of skip connections and residual structures.