Adversarial robust learning improved for transductive setting.
problem Adversarial robust learning in transductive setting.
method Simple transductive learner for bounded VC dimension classes.
result Robust error rate linear in VC dimension, adaptive to perturbation complexity.
In this paper we introduce the transductive linear bandit problem: given a set of measurement vectors X⊂Rd, a set of items Z⊂Rd, a fixed confidence δ, and an unknown vector θ∗∈Rd, the goal is to infer $\text{argmax}_{z\in \mathcal{Z}} z^\t…
Standard methods in supervised learning separate training and prediction: the model is fit independently of any test points it may encounter. However, can knowledge of the next test point x⋆ be exploited to improve prediction accuracy? We address this question in the context of linear prediction, show…
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.
Improved bounds for unbounded losses using transductive priors.
problem Sequential regression and classification with unbounded losses.
method Exponential weights algorithm with transductive priors.
result Statistical bounds independent of design vectors and optimal solution norm.
Proposes a transductive matrix completion method with calibration for multi-task learning.
problem Improving multi-task learning with multiple related data sources.
method Transductive matrix completion with calibration constraint.
result The proposed algorithm recovers incomplete feature and target matrices with improved results.
Paper proposes PSIPS for identifying Pareto set with correlated objectives.
problem Identifying the best answer among items with multiple conflicting metrics.
method Posterior sampling in stopping and sampling rules for structure and correlation.
result PSIPS is asymptotically optimal and demonstrates good empirical performance.
Transductive learning considers a training set of m labeled samples and a test set of u unlabeled samples, with the goal of best labeling that particular test set. Conversely, inductive learning considers a training set of m labeled samples drawn iid from P(X,Y), with the goal of best labeling any future sample…
The paper finds a fundamental trade-off between confidence and efficiency in transductive conformal prediction.
problem The challenge is to balance confidence and efficiency in predicting multiple data points.
method The authors derive a strict finite-sample bound and introduce a practical algorithm to approach this bound.
result Any non-trivial confidence level leads to exponential growth in prediction set size, with a linear scaling in the number of samples.
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.
Multi-group learners suffer a penalty in transductive learning.
problem The penalty on multi-group learners in transductive learning.
method Analyzing the relationship between the number of groups and the error rate.
result The penalty can increase linearly with the number of groups, up to the square-root of the sample size.
New method TLC improves transductive learning bounds.
problem Sharp generalization bounds for transductive learning.
method Transductive Local Complexity (TLC) framework.
result Nearly sharp bounds consistent with inductive results.
Transductive learning considers situations when a learner observes m labelled training points and u unlabelled test points with the final goal of giving correct answers for the test points. This paper introduces a new complexity measure for transductive learning called Permutational Rademacher Complexity (PRC) and …
We show two novel concentration inequalities for suprema of empirical processes when sampling without replacement, which both take the variance of the functions into account. While these inequalities may potentially have broad applications in learning theory in general, we exemplify their significance by studying the t…
Improved few-shot learning with LSSVM and transductive modules.
problem Few-shot learning with limited data and samples.
method Introducing LSSVM as a base learner and transductive modules to enhance classification accuracy.
result FSLSTM achieves state-of-the-art performance on miniImageNet and CIFAR-FS benchmarks.
IDS algorithm optimizes sequential decisions in various monitoring settings.
problem Optimizing sequential decisions in complex monitoring scenarios.
method Information-directed sampling (IDS) algorithm for linear partial monitoring.
result IDS achieves nearly worst-case rate optimality in finite-action games.
Most traditional online learning algorithms are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, tailored for transductive settings, which combines "random playout" and randomized rounding of loss subgradients. As an applic…
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher…
New method improves transductive learning predictions with multiplicative oracle inequalities.
problem Improving transductive learning predictions with known covariates.
method Median of Level-Set Aggregation (MLSA) for transductive LOO prediction.
result Proved multiplicative oracle inequality for LOO error.
TIM maximizes mutual information for few-shot learning, outperforming state-of-the-art methods.
problem Few-shot learning with limited labeled data.
method Transductive Information Maximization (TIM) with alternating-direction solver.
result Significant improvement in accuracy across various datasets and networks.
Graph neural networks generalize well under certain conditions, explained by learning theory.
problem Understanding why graph neural networks generalize well in transductive inference.
method Analysis of transductive Rademacher complexity to explain generalization properties of graph convolutional networks.
result Transductive Rademacher complexity can explain the generalization of graph convolutional networks for node classification in stochastic block models.
We consider using an ensemble of binary classifiers for transductive prediction, when unlabeled test data are known in advance. We derive minimax optimal rules for confidence-rated prediction in this setting. By using PAC-Bayes analysis on these rules, we obtain data-dependent performance guarantees without distributio…
New bounds improve graph node classification using optimal transport.
problem Improving transductive generalization bounds for graph node classification.
method Representation-based generalization bounds via optimal transport, expressed in terms of Wasserstein distances.
result Strong correlation between derived bounds and empirical generalization in graph node classification.
Study shows transductive learning is equivalent to PAC learning for most natural loss functions.
problem Understanding the relationship between transductive and PAC learning models.
method Extending existing results and developing new techniques to analyze the equivalence of the two models.
result Transductive learning is essentially equivalent to PAC learning for realizable learning with most natural loss functions.
New method uses graph-based interpolation for few-shot classification.
problem Learning models with limited labeled examples.
method Graph-based feature vector interpolation for transductive learning.
result Significant gains in few-shot classification compared to other methods.
A new method for few-shot learning using Laplacian regularization.
problem Few-shot learning with limited labeled data.
method Transductive Laplacian-regularized inference for feature embeddings.
result Our method outperforms state-of-the-art methods across various benchmarks.
Local regularization fails in transductive learning for some multiclass problems.
problem Whether local regularization can learn all transductive multiclass problems.
method Provided a negative answer by exhibiting a specific multiclass problem.
result Local regularization cannot learn all transductive multiclass problems.
Unsupervised domain adaptation (UDA) amounts to assigning class labels to the unlabeled instances of a dataset from a target domain, using labeled instances of a dataset from a related source domain. In this paper, we propose to cast this problem in a game-theoretic setting as a non-cooperative game and introduce a ful…
Combines Xgboost and transductive SVM for semi-supervised learning.
problem Improving semi-supervised learning performance with heterogeneous tabular data.
method Proposes an optimization-based ensemble method to adaptively combine Xgboost and transductive SVM.
result Significantly improves classification accuracy over state-of-the-art methods.
Extractive compression is a challenging natural language processing problem. This work contributes by formulating neural extractive compression as a parse tree transduction problem, rather than a sequence transduction task. Motivated by this, we introduce a deep neural model for learning structure-to-substructure tree …
Study on tradeoffs between mistakes and ERM oracle calls in online and transductive learning.
problem Analyzing online and transductive learning with limited ERM and weak consistency oracle access.
method Proves lower bounds and upper bounds on mistakes and oracle calls, considering realizable and agnostic cases.
result Achieves optimal mistake bounds with weak consistency queries for certain concept classes.
A novel estimator for linear coefficients in semiparametric models without assuming model structure.
problem Estimating nuisances in semiparametric models without knowing the underlying structure.
method Proposes a novel estimator and a method called TAME for debiasing and improving on double machine learning.
result Establishes a new estimator with improved error rate compared to double machine learning.
New algorithm tackles multiclass transductive online learning with unbounded labels.
problem Characterizing optimal mistake bound for unbounded label spaces.
method Introducing new combinatorial dimensions (Level-constrained Littlestone and Branching dimensions) to characterize online learnability.
result Established trichotomy of possible minimax rates for unbounded label spaces: Θ(T), Θ(logT), or Θ(1). New algorithm identifies best arm in semiparametric bandits with near optimal efficiency.
problem Fixed-confidence Best Arm Identification in semiparametric bandits with unknown baseline shift.
method Phase-elimination algorithm based on orthogonalized regression design.
result Nearly optimal high-probability sample-complexity upper bound established.
Proposes a framework for compositional generalization in language models.
problem Lack of compositional generalization in neural networks compared to humans.
method Introduces Generalized Grammar Rules (GGRs) for transduction tasks, formalizing symmetry-based constraints.
result Framework enables models to generalize compositionally, similar to human learning.
Many machine learning tasks can be expressed as the transformation---or \emph{transduction}---of input sequences into output sequences: speech recognition, machine translation, protein secondary structure prediction and text-to-speech to name but a few. One of the key challenges in sequence transduction is learning to …
Enhances few-shot image classification using unlabelled examples.
problem Few-shot image classification with limited labeled data.
method Transductive meta-learning combining soft k-means clustering and neural feature extractor.
result State-of-the-art performance on Meta-Dataset, mini-ImageNet, and tiered-ImageNet benchmarks.
New methods learn from single graphs, improving transductive node classification.
problem Statistical foundations of transductive learning for single graphs.
method Developed new concentration-of-measure tools for large graphs.
result Achieved optimal nonparametric rate of N−1/2 for single graph learning. Meta-learning framework improves model performance on few-shot classification tasks.
problem Improving model performance on few-shot classification tasks.
method Empirical Bayes formulation with synthetic gradients for transductive meta-learning.
result Meta-learning framework outperforms previous state-of-the-art methods on benchmarks.
GCL-LRR improves node classification in noisy graphs.
problem Noise in real-world graph data impairs GNNs' effectiveness.
method Two-stage transductive learning with low-rank regularization and attention.
result Improved node classification performance in noisy graphs.
The paper surveys recent extensions of the Long-Short Term Memory networks to handle tree structures from the perspective of learning non-trivial forms of isomorph structured transductions. It provides a discussion of modern TreeLSTM models, showing the effect of the bias induced by the direction of tree processing. An…
Node Masking improves GNNs' scalability and generalization.
problem Improving GNNs' ability to handle arbitrary graphs.
method Introducing Node Masking to enhance GNNs' performance.
result Node Masking enables GNNs to generalize and scale better.
Algorithm predicts with optimal loss by abstaining from uncertain test examples.
problem Predicting with training data not matching test data.
method Transductive abstention algorithm using labeled and unlabeled test examples.
result Optimal prediction loss guarantees with additional term for abstaining cost.
Optimizes pure exploration in linear bandits with a new algorithm.
problem Best-arm identification in linear stochastic bandits.
method Developed the first asymptotically optimal algorithm for fixed-confidence pure exploration in linear bandits.
result Avoids the pitfall of a simple but difficult instance and bypasses the need to solve an optimal design problem.
PAC learning simplified as bipartite matching.
problem Efficiently solving PAC learning problems.
method Transductive learning and one-inclusion graphs.
result PAC learning can be reduced to bipartite matching.
We present transductive Boltzmann machines (TBMs), which firstly achieve transductive learning of the Gibbs distribution. While exact learning of the Gibbs distribution is impossible by the family of existing Boltzmann machines due to combinatorial explosion of the sample space, TBMs overcome the problem by adaptively …
Supervised learning with large scale labeled datasets and deep layered models has made a paradigm shift in diverse areas in learning and recognition. However, this approach still suffers generalization issues under the presence of a domain shift between the training and the test data distribution. In this regard, unsup…
Training-free GNNs use labels as features to improve node classification.
problem Improving graph neural networks for transductive node classification.
method Advocates labels as features, designs training-free GNNs based on this.
result Training-free GNNs outperform traditional GNNs in node classification.