New bounds on machine learning model generalization error moments.
problem Understanding the performance of machine learning models.
method Information-theoretic bounds on the moments of the generalization error of learning algorithms.
result Proposed bounds on generalization error moments and their high-probability bounds.
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 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.
New framework connects online learning to statistical learning for better generalization bounds.
problem Deriving generalization bounds for statistical learning algorithms.
method Constructing an online learning game and showing a connection to statistical learning.
result Established a connection between online and statistical learning, leading to new generalization bounds.
This paper improves meta-learning by developing new PAC-Bayes bounds.
problem Meta-learning generalization gap across multiple tasks.
method Upper bounding convex functions linking environment and task-level losses.
result New PAC-Bayes bounds for meta-learning with improved algorithms.
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.
New bounds estimate learning algorithm performance using prediction information.
problem Estimating the performance of black-box learning algorithms.
method Information-theoretic bounds based on prediction information.
result Improved bounds applicable to deterministic algorithms and easier to estimate.
New PAC-Bayesian bounds for multi-view learning using Rényi divergence.
problem Applying PAC-Bayesian theory to multi-view learning.
method Introducing novel PAC-Bayesian bounds based on Rényi divergence for multi-view learning.
result Efficient optimization algorithms that align with theoretical bounds.
New tighter bounds for learning algorithms from Steinke & Zakynthinou's supersample setting.
problem Improving generalization bounds for machine learning algorithms.
method Information-theoretic approach using projected loss and Rademacher sequence.
result The new bounds are tighter than previous information-theoretic bounds.
Improved mistake bounds for transductive online learning.
problem Quantifying the power of unlabeled data in online learning.
method Proving lower and upper bounds on transductive mistake bounds.
result Exponential improvement in mistake bounds for transductive learning.
Establishes upper bounds on generalization error in active learning.
problem Improving query algorithms in active learning.
method Derives upper bounds on generalization error using informativeness and representativeness query strategies.
result Validates the use of regularization techniques to ensure bounds' validity.
New algorithm reduces online learning regret for bounded recall games.
problem Reducing regret in online learning with limited past information.
method Constructing a stationary bounded-recall algorithm with O ( 1 / M ) O(1/\sqrt{M}) O ( 1/ M ) regret. result Any low regret bounded-recall algorithm must be aware of past losses' order.
Paper derives PAC-Bayesian bounds for LTI systems learning from empirical data.
problem Characterizing predictive power of LTI systems learned from data.
method PAC-Bayesian bounds for LTI stochastic dynamical systems with inputs.
result Finite-sample error bounds for learning algorithms of LTI systems.
The paper introduces gapped scale-sensitive dimensions to improve learning rate bounds.
problem Improving lower bounds on rates of convergence in statistical and online learning.
method Introducing and analyzing gapped scale-sensitive dimensions for function classes.
result Gapped dimensions lead to stronger lower bounds on offset Rademacher averages.
Develops bounds for deep learning risk via Hilbert coresets.
problem Risk estimation for complex deep learning models.
method Hilbert coreset approach for transductive risk bounds.
result Effective and meaningful bounds for deep neural networks.
New bounds on IDS for RL show how to balance computation and learning efficiency.
problem Understanding and optimizing information-directed sampling (IDS) for reinforcement learning.
method Developed novel information-theoretic tools to bound information ratio and cumulative information gain.
result Derived prior-free Bayesian regret bounds for IDS in tabular finite-horizon MDPs and improved computational efficiency.
New PAC bound for meta-learning improves generalization guarantees.
problem Provide strong generalization guarantees in meta-learning.
method PAC-Bayes and uniform stability frameworks applied to gradient-based meta-learning.
result Derives a tighter PAC bound for gradient-based meta-learning.
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…
Q-learning for average cost MDPs gets a concentration bound.
problem Finding bounds for Q-learning in average cost MDPs.
method Derives a concentration bound using shortest path problem equivalence.
result Numerical comparison with relative value iteration shows the bound's effectiveness.
The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.
problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.
method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.
result The proposed bounds match theoretical lower bounds up to a logarithmic term.
New margin-based learning guarantees improve generalization bounds.
problem Improving generalization bounds for machine learning models.
method Relative deviation margin bounds using empirical margin loss and Rademacher complexity.
result Distribution-dependent generalization bounds for unbounded loss functions.
New method improves understanding of machine learning model performance.
problem Understanding how well machine learning models generalize from training data to unseen data.
method Auxiliary Distribution Method to derive new generalization error bounds.
result Upper bounds on generalization errors are tighter and more applicable.
Unified framework for learning flexible probabilistic programs using DPP and PAC-Bayes bounds.
problem Learning and generalizing from complex probabilistic models.
method Unified DPP representation and PAC-Bayes bounds for stochastic programs.
result Improved performance and generalization prediction using flexible DPP model representations and learned complexity measures.
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least d Ω ( 1 / ε ) d^{Ω(1/ε)} d Ω ( 1/ ε ) for learning mixtures of bounded covariance Gaussians. New analysis improves generalization bounds for meta-learning.
problem Improving generalization in meta-learning algorithms.
method Information-theoretic analysis of MAML and its stochastic variant.
result Data-dependent generalization bound is tighter and non-vacuous.
The paper establishes risk bounds for PU learning with label noise.
problem Finding a classifier in PU learning with label noise.
method Establishes risk bounds under the assumption of label selection randomness.
result Proves that the upper bound on minimax risk is almost optimal.
New bounds predict deep learning generalization better than existing methods.
problem Predicting generalization errors for deep learning models.
method Function-based PAC-Bayesian bounds that meet multiple desiderata.
result The new bound performs significantly better than existing parameter-based PAC-Bayes bounds.
Paper improves generalization bounds for multi-kernel learning with mixed datasets.
problem Improving generalization for multi-kernel learning with mixed Markov chain datasets.
method Developed novel generalization bounds with O ( log m ) O(\sqrt{\log m}) O ( log m ) and O ( 1 / n ) O(1/\sqrt{n}) O ( 1/ n ) dependencies. result Added terms compensate for dependency among samples in mixed datasets.
New SVM margin bound improves generalization in machine learning.
problem Improving SVM margin bounds for better generalization.
method Stable sample compression schemes to derive new data-dependent generalization bounds.
result Proves a new optimal SVM margin bound with a log factor improvement.
The paper bounds generalization error for iterative learning with bounded updates.
problem Generalization error of iterative learning algorithms with bounded updates for non-convex loss functions.
method Information-theoretic techniques, reformulating mutual information as update uncertainty, variance decomposition.
result Improved generalization error bounds for iterative learning algorithms with bounded updates.
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.
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…
A new stopping criterion for active learning based on deterministic generalization bounds.
problem Determining the optimal stopping point for active learning when data acquisition is costly.
method The proposed stopping criterion is based on the difference in expected generalization errors and hypothesis testing, derived from PAC-Bayesian theory.
result The proposed stopping criterion effectively stops active learning by combining an upper bound with a statistical test.
The paper improves deep learning generalization bounds using PAC-Bayes compression.
problem Improving generalization bounds for deep neural networks.
method Quantizing neural network parameters in a linear subspace to develop tight generalization bounds.
result Large models can be compressed significantly, explaining Occam's razor.
Unified learning bound for covariate and concept shifts.
problem Generalization under distribution shift in machine learning.
method Support-agnostic definitions of covariate and concept shifts using entropic optimal transport, leading to a unified error bound applicable to various loss functions and label spaces.
result Development of estimators for shifts with concentration guarantees and the DataShifts algorithm for quantifying and estimating the error bound.
The paper establishes bounds for transductive learning using information theory.
problem Transductive learning generalization gap control.
method Information theory, PAC-Bayes, mutual information, conditional mutual information, different information measures.
result Established transductive information-theoretic and PAC-Bayesian bounds.
Paper develops bounds for stochastic approximation with averaging.
problem Establish high-probability bounds for averaged stochastic approximation.
method Develops a general framework for non-asymptotic concentration bounds.
result Derives sharp bounds for averaged iterates and tightens existing results.
Proves SQ lower bounds for learning two-hidden-layer neural networks.
problem Learning two-hidden-layer ReLU networks with Gaussian inputs.
method Refined lifting procedure to reduce Boolean PAC learning to Gaussian.
result Superpolynomial SQ lower bounds for Gaussian inputs.
New reinforcement learning bound improves generalization for sequential data.
problem Challenges in obtaining generalization guarantees for reinforcement learning due to sequential data.
method PAC-Bayesian reinforcement learning with consideration of Markov dependencies and mixing time.
result Demonstrated practical utility through PB-SAC, providing meaningful confidence certificates.
Paper tightens privacy and generalization bounds for iterative learning.
problem Balancing privacy and generalization in iterative learning algorithms.
method Established alignment between generalization and privacy, derived composition theorems for iterative algorithms.
result Generalization bounds for iterative learning algorithms are strictly tighter than existing works.
This paper bounds meta-generalization gap using information theory.
problem Improving sample efficiency for new tasks in meta-learning.
method Information-theoretic upper bounds on meta-generalization gap for two meta-learning classes.
result Novel ITMI bounds for noisy iterative algorithms.
Investigates tight PAC-Bayes bounds for small datasets.
problem Tightening PAC-Bayes bounds for small data.
method Generic PAC-Bayes theorem, meta-learning, synthetic tasks.
result PAC-Bayes bounds are competitive with Chernoff bounds but not as tight.
Optimal SQ bounds for learning binary product distributions and Ising models.
problem Learning binary product distributions and Ising models robustly.
method Statistical Query (SQ) lower bounds for robust learning.
result Optimal SQ lower bounds match known algorithm error guarantees.
Ahpatron improves online kernel learning with tighter mistake bounds.
problem Improving mistake bounds in online kernel learning with budget constraints.
method Introducing Ahpatron, a new model that uses an aggressive updating rule and a budget maintenance mechanism to approximate AVP.
result Ahpatron achieves tighter mistake bounds compared to previous models.
This work bounds classification error in machine learning for low Bayes error conditions.
problem Understanding the error mismatch between Bayes error and model-based classification error.
method Applying classification error bounds to study the relationship with Kullback-Leibler divergence and proposing a linear approximation for low Bayes error conditions.
result A linear approximation of the classification error bound for low Bayes error conditions is proposed.
New algorithms minimize PAC-Bayesian C-Bound for majority voting, leading to scalable and accurate predictors.
problem Improving majority vote classifiers using PAC-Bayesian bounds.
method Directly optimizing PAC-Bayesian guarantees on the C-Bound with gradient descent.
result Self-bounding majority vote learning algorithms with scalable and accurate predictors.
This paper improves Q-learning bounds using reference-advantage decomposition.
problem Improving Q-learning bounds in MDPs with positive suboptimality gaps.
method Develops a novel error decomposition framework to prove gap-dependent regret bounds.
result Establishes logarithmic gap-dependent regret bounds for Q-learning.
Paper improves worst-case regret bounds for RLSVI in reinforcement learning.
problem Minimizing regret in reinforcement learning with randomized value functions.
method Introduces a clipping variant of Thompson Sampling for RLSVI.
result Achieves a i l d e O ( H 2 S A T ) ilde{\mathrm{O}}(H^2S\sqrt{AT}) i l d e O ( H 2 S A T ) worst-case regret bound.