A-kNN improves kNN's ability to classify unknown instances.
problem kNN's inability to predict unknown instances.
method Developed Advanced kNN (A-kNN) algorithm.
result A-kNN significantly improves accuracy in classifying unknown instances.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “unknown instances”
We study learning latent models with multi-instance weak supervision.
problem Learning latent models with multi-instance weak supervision.
method Formulated as multi-instance Partial Label Learning (multi-instance PLL), proposed a necessary and sufficient condition for learnability, derived Rademacher-style error bounds.
result First theoretical study of multi-instance PLL with unknown transition function, aligns with empirical results but highlights scalability issues.
We propose a new problem formulation which is similar to, but more informative than, the binary multiple-instance learning problem. In this setting, we are given groups of instances (described by feature vectors) along with estimates of the fraction of positively-labeled instances per group. The task is to learn an ins…
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of .
MetaCaDI learns causal graphs and unknown interventions from few data instances.
problem Discovering causal mechanisms in systems with high data costs and unknown interventions.
method MetaCaDI is a Bayesian meta-learning framework that optimizes for rapid adaptation to new intervention targets.
result MetaCaDI significantly outperforms state-of-the-art methods in causal graph recovery and intervention target prediction.
Paper tackles open set domain adaptation by detecting unknown classes.
problem Adapting to target domains with unknown classes when label spaces partially overlap.
method Instance-level reweighting strategy combined with Extreme Value Theory for unknown class detection.
result Proposed method outperforms state-of-the-art models on conventional datasets.
One of the key challenges of performing label prediction over a data stream concerns with the emergence of instances belonging to unobserved class labels over time. Previously, this problem has been addressed by detecting such instances and using them for appropriate classifier adaptation. The fundamental aspect of a n…
Study on reward poisoning attacks on CMAB, revealing attackability depends on adversary's knowledge.
problem Reward poisoning attacks on Combinatorial Multi-Armed Bandits (CMAB).
method Provided a sufficient and necessary condition for attackability, devised an attack algorithm.
result Attackability of CMAB depends on adversary's knowledge of the bandit instance.
MetaTS learns to explore better by meta-learning prior from bandit instances.
problem Efficient exploration in bandit problems.
method MetaThompson Sampling (MetaTS) that meta-learns the prior from bandit instances.
result MetaTS quickly adapts to unknown prior and achieves better exploration.
\textit{Multiple Instance Learning} (MIL) is concerned with learning from bags of instances, where only bag labels are given and instance labels are unknown. Existent approaches in this field were mainly designed for the bag-level label prediction (predict labels for bags) but not the instance-level (predict labels for…
New method tackles unknown unknowns in machine learning.
problem Unknown classes in training data misperceived as other labels.
method Exploratory machine learning with rejection model, feature exploration, and model cascade.
result The method discovers potentially hidden classes and improves model performance.
Open set recognition problems exist in many domains. For example in security, new malware classes emerge regularly; therefore malware classification systems need to identify instances from unknown classes in addition to discriminating between known classes. In this paper we present a neural network based representation…
In open set recognition (OSR), almost all existing methods are designed specially for recognizing individual instances, even these instances are collectively coming in batch. Recognizers in decision either reject or categorize them to some known class using empirically-set threshold. Thus the decision threshold plays a…
A method uses confidence scores to handle noisy labels for each instance.
problem Learning with noisy labels where each instance's label can randomly change.
method Introduces confidence-scored instance-dependent noise (CSIDN) to estimate transition distributions for each instance.
result Demonstrates the utility and effectiveness of CSIDN through experiments with synthetic and real-world noise.
In this paper, we consider a novel machine learning problem, that is, learning a classifier from noisy label distributions. In this problem, each instance with a feature vector belongs to at least one group. Then, instead of the true label of each instance, we observe the label distribution of the instances associated …
Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resourc…
This work learns exploration policies for unknown distributions using samples and policy gradients.
problem Learning exploration policies for unknown distributions in Bayesian bandits.
method Meta-learning approach parameterizing policies in a differentiable way and optimizing them with policy gradients.
result Effective gradient estimators and variance reduction techniques are derived.
Algorithm reduces regret in multi-player bandits with unknown collision rewards.
problem Reducing regret in multi-player multi-armed bandits with unknown collision rewards.
method Proposes an algorithm that combines a modified successive elimination strategy with a communication protocol to estimate suboptimality gaps and coordinate among players.
result Achieves logarithmic regret for the problem when collision reward is unknown.
In this work, we consider a manufactory process which can be described by a multiple-instance logistic regression model. In order to compute the maximum likelihood estimation of the unknown coefficient, an expectation-maximization algorithm is proposed, and the proposed modeling approach can be extended to identify the…
The paper sets bounds on how much regret is unavoidable in adaptive LQR with unknown B-matrix.
problem Understanding the limits of adaptive LQR with unknown B-matrix.
method Local asymptotic minimax regret lower bounds using van Trees' inequality and Bellman error representation.
result Logarithmic regret is impossible if the parametrization induces an uninformative optimal policy.
Many active learning methods belong to the retraining-based approaches, which select one unlabeled instance, add it to the training set with its possible labels, retrain the classification model, and evaluate the criteria that we base our selection on. However, since the true label of the selected instance is unknown, …
In the classical best arm identification (Best--Arm) problem, we are given stochastic bandit arms, each associated with a reward distribution with an unknown mean. We would like to identify the arm with the largest mean with probability at least , using as few samples as possible. Understanding the sample c…
In the Best--Arm problem, we are given stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample…
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
New algorithm reduces prediction error in online learning without knowing base measure.
problem Smoothed online learning without knowledge of base measure.
method R-Cover algorithm based on recursive coverings.
result First algorithm to guarantee sublinear regret for agnostic smoothed online learning without prior knowledge of base measure.
Private KL distribution estimation improved with instance-optimality.
problem Minimizing KL divergence between true and estimated distributions.
method Construct minimax optimal private estimators, then focus on instance-optimality.
result Achieved instance-optimality up to constant factors for KL estimation.
Safe linear bandits over unknown polytopes avoid safety violations and suboptimal actions.
problem Online approach to linear programming with unknown constraints and risks.
method Doubly-optimistic strategy (DOSS) for safe linear bandits over polytopes.
result DOSS achieves tight bounds on efficacy regret and safety violations.
We consider the problem where an agent wants to find a hidden object that is randomly located in some vertex of a directed acyclic graph (DAG) according to a fixed but possibly unknown distribution. The agent can only examine vertices whose in-neighbors have already been examined. In this paper, we address a learning s…
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.
We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a r…
Optimizes budgeted evaluations of LLMs by allocating queries to judges efficiently.
problem Evaluating LLMs with heterogeneous judges and varying costs and reliability.
method Formalizes and analyzes budgeted heteroskedastic multi-judge estimation, proposing EST-IVWE for practical implementation.
result EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget and is instance-optimal.
Paper tackles anomaly detection in restless Markov arms with unknown TPMs.
problem Detecting an anomalous arm in a multi-armed bandit with unknown transition probability matrices.
method Developed a policy based on the principle of certainty equivalence, achieving the lower bound arbitrarily closely under specific assumptions.
result Achieved the lower bound on expected time required to find the odd arm index, demonstrating the policy's effectiveness.
New algorithm reduces regret for kernelized bandits by adapting to specific problem instances.
problem Efficiently learning the optimizer of an unknown function in RKHS with noisy oracle.
method Instance-dependent regret analysis and a new minimax near-optimal algorithm.
result New algorithm achieves better performance on specific problem instances.
Many objects in the real world are difficult to describe by a single numerical vector of a fixed length, whereas describing them by a set of vectors is more natural. Therefore, Multiple instance learning (MIL) techniques have been constantly gaining on importance throughout last years. MIL formalism represents each obj…
New algorithm detects changes quickly without knowing parameters, near optimally.
problem Quickest change detection with unknown parameters.
method Leverages theoretical asymptotic properties to derive a scalable approximate algorithm with near optimal performance.
result Detects changes in constant complexity with near optimal performance.
Optimal best-arm identification with known number of optimal arms.
problem Identifying the best arm in a multi-armed bandit with multiple optimal arms under fixed confidence.
method Deriving a new information-theoretic lower bound and proposing a modified stopping rule.
result Achieving asymptotic instance-optimality with a new lower bound and new stopping rule.
Adversarial online multi-task RL with task separation.
problem Minimize regret in an adversarial online multi-task setting with unknown MDPs.
method Prove minimax and instance-specific lower bounds, develop a clustering algorithm with optimal sample complexity and regret.
result Tight sample complexity and regret bounds for adversarial online multi-task RL.
Low-dimensional embedding, manifold learning, clustering, classification, and anomaly detection are among the most important problems in machine learning. The existing methods usually consider the case when each instance has a fixed, finite-dimensional feature representation. Here we consider a different setting. We as…
Restless bandit problems are instances of non-stationary multi-armed bandits. These problems have been studied well from the optimization perspective, where the goal is to efficiently find a near-optimal policy when system parameters are known. However, very few papers adopt a learning perspective, where the parameters…
New trade-off found in bandit problems with unknown range.
problem Stochastic bandit problems with unknown range.
method Exhibit a strategy achieving new trade-off between distribution-dependent and distribution-free regret bounds.
result Achieves the rates for regret indicated by the new trade-off.
Bayesian neural networks' performance varies with prior choice, affecting their ability to identify unknowns.
problem The impact of prior choice on Bayesian neural networks' ability to identify unknowns.
method Evaluation of different prior distributions on classification tasks using BNNs and NNs with Monte Carlo dropout.
result Prior choice significantly impacts BNNs' ability to identify unknowns, affecting true and false positive rates.
Online learning makes sequence of decisions with partial data arrival where next movement of data is unknown. In this paper, we have presented a new technique as multiple times weight updating that update the weight iteratively forsame instance. The proposed technique analyzed with popular state-of-art algorithms from …
Study contextual online pricing with biased offline data, achieving optimal regret bounds.
problem Contextual online pricing with biased offline data.
method Identify to measure data bias, use OFU policy and robust variant for unknown bias.
result Achieve minimax-optimal regret bounds for contextual pricing.
Estimates shared parameters across related learning problems using robust statistics and LASSO.
problem Simultaneously learning related but heterogeneous problems like store demand or patient risk.
method Two-stage multitask learning estimator combining robust statistics and LASSO regression.
result Improved sample complexity bounds for multitask learning, especially beneficial for 'data-poor' instances.
Raiders of the Lost Architecture: Kernels for Bayesian Optimization in Conditional Parameter Spacesstat.ML
In practical Bayesian optimization, we must often search over structures with differing numbers of parameters. For instance, we may wish to search over neural network architectures with an unknown number of layers. To relate performance data gathered for different architectures, we define a new kernel for conditional p…
Improves classifier accuracy in ambiguous data settings.
problem Training classifiers with partially labeled data.
method Incremental pruning of candidate labels using conformal prediction.
result Significantly improves test set accuracies of PLL classifiers.
Hyperbolic conservation laws posed on manifolds arise in many applications to geophysical flows and general relativity. Recent work by the author and his collaborators attempts to set the foundations for a study of weak solutions defined on Riemannian or Lorentzian manifolds and includes an investigation of the existen…
At present, object recognition studies are mostly conducted in a closed lab setting with classes in test phase typically in training phase. However, real-world problem is far more challenging because: i) new classes unseen in the training phase can appear when predicting; ii) discriminative features need to evolve when…