New binary classification techniques help multiclass classification by aggregating proper learners.
problem Multiclass classification faces a properness barrier that prevents optimal learning by proper learners.
method Aggregations of proper binary learners, generalized to multiclass settings, achieve optimal sample complexity.
result Optimal binary learners can achieve sample complexity $O\left(\frac{d_G + \ln(1 / δ)}ε
ight)$ for classes with finite Graph dimension dG. Proper learning is possible with labeled data, but unlabeled data can improve performance.
problem Problems that can only be learned improperly, like multiclass classification.
method Distributional regularization and worst-case performance evaluation.
result Proper learnability is possible under certain conditions involving unlabeled data.
Study shows improper learning can outperform proper learning in misspecified models.
problem Misspecification in probabilistic prediction models.
method Investigates the performance of proper and improper learning strategies in misspecified models.
result Improper learning can achieve lower regret compared to proper learning, especially in high-dimensional settings.
New findings show second-order scoring rules can't accurately represent epistemic uncertainty.
problem Lack of epistemic uncertainty representation in second-order learners.
method Generalised second-order scoring rules introduced to prove theoretical limitations.
result No loss function incentivizes second-order learners to accurately represent epistemic uncertainty.
First proper learning algorithm for Gaussian halfspaces with matching sample and computational complexity.
problem Agnostically learning halfspaces under Gaussian distribution.
method First proper learning algorithm with matching sample and computational complexity.
result First proper learning algorithm for agnostically learning halfspaces under Gaussian distribution with matching sample and computational complexity.
New algorithms improve agnostic learning for triangles and polygons, reducing time complexity.
problem Efficient agnostic learning for geometric concept classes.
method Data structures and algorithms from computational geometry, probabilistic combinatorics.
result Optimal time complexity improvements for agnostic learning of triangles and polygons.
Defines computable learning for binary classification over metric spaces.
problem Defines computable PAC learning for binary classification over computable metric spaces.
method Provides sufficient conditions for ERM learners to be computable and bounds the strong Weihrauch degree of an ERM learner.
result Gives a hypothesis class that does not admit any proper computable PAC learner with computable sample function.
New insights into learning from only positive examples.
problem Characterizing proper learning from positive-only samples.
method Introducing a new combinatorial condition for proper positive-only learning.
result Proper positive-only learning is characterized by finite VC dimension and uniform exterior separability.
We study the problem of {\em properly} learning large margin halfspaces in the agnostic PAC model. In more detail, we study the complexity of properly learning d-dimensional halfspaces on the unit ball within misclassification error α⋅OPTγ+ε, where OPTγ is the optimal γ-margin error r…
New framework models echo chamber learning, proving tight bounds on algorithm performance.
problem Echo chambers in machine learning where systems learn from self-annotated data.
method Online Learning in the Replay Setting, Extended Threshold dimension, closure-based learner.
result Proves tight bounds on algorithm performance against replay adversaries.
The paper introduces new measures for quantifying uncertainty in machine learning.
problem Uncertainty representation and quantification in machine learning.
method Proper scoring rules for aleatoric and epistemic uncertainty quantification.
result Established a natural bridge between credal set and second-order distribution representations of uncertainty.
New algorithms achieve near-optimal cumulative loss in nonparametric online learning and games.
problem Fast rates of convergence in nonparametric online regression and classification.
method Randomized proper learning algorithms, hierarchical aggregation, multi-scale extension, stability proof.
result Achieved near-optimal cumulative loss bounds for real-valued and binary games.
How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension d? Previous works have shown that even for d=1 the amount of information may be unbounded (tend to ∞ with the universe size). Can it be that all concepts in the class require leaking a large amount of inform…
Study adversarial perturbations in classification, analyzing learning and certification.
problem Formal study of classification under adversarial perturbations from both learner and third-party perspectives.
method PAC-type semi-supervised learning framework, black-box certification under limited query budget, adversary analysis.
result Existence of a polynomial query complexity adversary implies the existence of a sample efficient robust learner.
Paper characterizes classes for which optimal sample complexity can be achieved by proper learning algorithms.
problem Characterizing classes for which optimal sample complexity can be achieved by proper learning algorithms.
method Identifying dual Helly number and its relation to proper learning algorithms.
result Optimal sample complexity can be achieved by proper learning algorithms for classes with bounded dual Helly number.
Study assesses hyperparameter tuning for causal inference with DML.
problem Optimizing hyperparameters for causal inference with DML.
method Empirical simulation study using DML approach.
result Hyperparameter tuning crucial for causal estimation with DML.
Conventional learning with expert advice methods assumes a learner is always receiving the outcome (e.g., class labels) of every incoming training instance at the end of each trial. In real applications, acquiring the outcome from oracle can be costly or time consuming. In this paper, we address a new problem of active…
Nowadays model uncertainty has become one of the most important problems in both academia and industry. In this paper, we mainly consider the scenario in which we have a common model set used for model averaging instead of selecting a single final model via a model selection procedure to account for this model's uncert…
While statistical learning methods have proved powerful tools for predictive modeling, the black-box nature of the models they produce can severely limit their interpretability and the ability to conduct formal inference. However, the natural structure of ensemble learners like bagged trees and random forests has been …
Efficient algorithms for monophonic halfspaces in graphs simplify learning and compression.
problem Learning and compressing monophonic halfspaces in graphs.
method 2-satisfiability based decomposition theorem, efficient algorithms for various learning problems.
result Achieved efficient and nearly optimal algorithms for various learning problems.
Bounds on Littlestone dimension for private learning and online prediction.
problem Understanding the Littlestone dimension of composed classes for private learning.
method Deriving bounds on Littlestone dimension and transforming private learners.
result Improved bounds on sample complexity for private learning.
This work describes simple and efficient algorithms for interactively learning non-binary concepts in the learning from random counter-examples (LRC) model. Here, learning takes place from random counter-examples that the learner receives in response to their proper equivalence queries. In this context, the learning ti…
Optimal algorithm converts weak to strong learner with less data.
problem Constructing a strong learner from a weak learner with minimal data.
method New algorithm that uses less training data than AdaBoost.
result Optimal sample complexity for converting weak to strong learner.
Inverse reinforcement learning (IRL) enables an agent to learn complex behavior by observing demonstrations from a (near-)optimal policy. The typical assumption is that the learner's goal is to match the teacher's demonstrated behavior. In this paper, we consider the setting where the learner has its own preferences th…
Meta clustering categorizes learners for collaborative learning.
problem Filtering out unqualified collaborators in collaborative learning.
method Select-Exchange-Cluster (SEC) method to classify learners by their supervised functions.
result SEC can cluster learners into accurate collaboration sets and enhance single-learner performance.
New meta-learners estimate time-varying treatment effects without model assumptions.
problem Estimating treatment effects over time in personalized medicine.
method Model-agnostic meta-learners for weighted pseudo-outcome regressions.
result Comprehensive theoretical analysis and practical insights for choosing meta-learners.
New survival learners estimate heterogeneous treatment effects from time-to-event data.
problem Estimating HTEs from time-to-event data with censoring outcomes.
method Orthogonal survival learners with theoretical guarantees and custom weighting functions.
result Orthogonal survival learners provide robust and model-agnostic HTE estimation.
Proposes a method to integrate learner models robustly against misspecifications.
problem Misspecifications in learner models and parameter sharing patterns degrade prediction accuracy.
method Sequentially incorporates additional learners based on user-specified parameter sharing patterns.
result Data-adaptively selects the most suitable way of parameter sharing to enhance predictive performance.
VTIRT speeds up IRT inference for dynamic learner proficiency.
problem Expensive and slow inference algorithms for dynamic IRT models.
method Variational Temporal IRT (VTIRT) for fast, accurate inference.
result Orders of magnitude speedup in inference runtime with accurate results.
Method selects the best deep learner for time-series prediction using Bayesian networks.
problem Selecting the most effective deep learning model for time-series prediction.
method Bayesian network selects deep learners based on input variables and cluster training data.
result Threshold value determines which deep learners predict time-series data robustly.
One of the most ambitious use cases of computer-assisted learning is to build a recommendation system for lifelong learning. Most recommender algorithms exploit similarities between content and users, overseeing the necessity to leverage sensible learning trajectories for the learner. Lifelong learning thus presents un…
In this paper, we make an important step towards the black-box machine teaching by considering the cross-space machine teaching, where the teacher and the learner use different feature representations and the teacher can not fully observe the learner's model. In such scenario, we study how the teacher is still able to …
pystacked combines machine learning models for improved predictions.
problem Improving machine learning model performance through stacking.
method Stacked generalization using Python's scikit-learn with various base learners.
result Enhanced predictive models through combining multiple machine learning algorithms.
MTL2L learns to adapt optimisation rules for unseen data.
problem Learners need to adapt to unseen data domains.
method Introduces MTL2L, a context-aware neural optimiser.
result MTL2L can adapt optimisation rules for unseen data.
Teaches sequential learners with changing inner states to improve future performance.
problem Teaching sequential learners with evolving inner states.
method Introduces an optimal control approach for multi-agent learning.
result Optimal control approach improves future performance of learners.
Theorem ensures superior learning outcomes for authorized learners with quantum label encoding.
problem Ensuring data security for authorized learners in machine learning.
method Quantum label encoding and PAC learning framework.
result Authorized learners achieve superior learning outcomes while eavesdroppers do not.
Meta-learners improve causal effect estimation in small samples.
problem Estimating causal effects using machine learning methods.
method Sample-splitting and cross-fitting to reduce overfitting bias.
result Meta-learners' performance depends on sample size and estimation procedure.
The paper presents a method for personalized exercise recommendations that improves learner skill gain.
problem Adapting to individual needs in large, diverse groups of learners in digital environments.
method Contextual Thompson Sampling to select exercises that advance learner skill.
result The method recommends exercises associated with greater skill improvement and adapts to learner differences.
sGBM speeds up gradient boosting by parallelizing and adapting base learners.
problem Infeasibility of parallelizing GBM training and sub-optimal performance in online settings.
method Integrates multiple differentiable base learners, jointly optimizing them with linear speed-up.
result sGBM achieves higher time efficiency and better accuracy than traditional GBM.
Deep reinforcement learning algorithms have been successfully applied to a range of challenging control tasks. However, these methods typically struggle with achieving effective exploration and are extremely sensitive to the choice of hyperparameters. One reason is that most approaches use a noisy version of their oper…
New LT-O-learners improve HLTE estimation with low overlap.
problem Challenges in estimating heterogeneous long-term treatment effects due to limited overlap.
method Introduces LT-O-learners that use custom overlap weights to downweight low-overlap samples.
result LT-O-learners provide robust HLTE estimates with lower variance in low-overlap regimes.
New concept of proper-calibeating extends classic calibrated forecasts to proper scoring rules.
problem Defining and extending calibrated forecasts to proper scoring rules.
method Extending the concepts of calibrated and calibeating forecasts to proper scoring rules and proving their properties.
result Proper-calibration always implies calibration, but proper-calibeating does not necessarily imply calibeating.
Paper introduces GDR-learners for estimating potential outcomes from observational data.
problem Lack of theoretical property of general Neyman-orthogonality in deep generative models.
method Develops flexible GDR-learners based on various deep generative models.
result GDR-learners possess quasi-oracle efficiency and rate double robustness, asymptotically optimal.
An algorithm learns from multiple models to match an oracle's risk.
problem Learning from multiple noisy models to estimate a target parameter.
method Elimination rounds algorithm for adaptive learning.
result Risk of weak-oracle learner matches that of an oracle in multiple source case.
LARP filters data to protect model performance across various learners.
problem Protecting model accuracy in public datasets with diverse learners.
method Formalizes and analyzes LARP, a robust data prefiltering method.
result LARP provides guarantees on worst-case loss over a set of learners, with some performance trade-off.
In this paper, we consider the problem of machine teaching, the inverse problem of machine learning. Different from traditional machine teaching which views the learners as batch algorithms, we study a new paradigm where the learner uses an iterative algorithm and a teacher can feed examples sequentially and intelligen…
Machine teaching addresses the problem of finding the best training data that can guide a learning algorithm to a target model with minimal effort. In conventional settings, a teacher provides data that are consistent with the true data distribution. However, for sequential learners which actively choose their queries,…
Data-driven model selection reduces regret in sequential decisions.
problem Optimizing model selection in stochastic environments with bandit feedback.
method Data-driven regret balancing for model selection.
result Meta-learner selects the best base learner based on actual realized regret.