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.
Optimal privacy-preserving ranking from noisy comparisons.
Optimizes identifying top-k items from comparisons with minimal comparisons.
A faster algorithm for ranking from pairwise comparisons.
There is increasing interest in learning algorithms that involve interaction between human and machine. Comparison-based queries are among the most natural ways to get feedback from humans. A challenge in designing comparison-based interactive learning algorithms is coping with noisy answers. The most common fix is to …
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…
Paper tackles noisy comparison oracle for robust clustering algorithms.
Test log-likelihood comparisons can be misleading.
We consider machine learning in a comparison-based setting where we are given a set of points in a metric space, but we have no access to the actual distances between the points. Instead, we can only ask an oracle whether the distance between two points and is smaller than the distance between the points an…
Active sampling algorithm improves accuracy of inferred scores from pairwise comparisons.
We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed "comparison graph" and every neighboring pair of items in this graph is compared times according to the Bradley-Terry-Luce model (where t…
Proposes a revenue function to evaluate dendrograms from comparisons.
The statistical comparison of multiple algorithms over multiple data sets is fundamental in machine learning. This is typically carried out by the Friedman test. When the Friedman test rejects the null hypothesis, multiple comparisons are carried out to establish which are the significant differences among algorithms. …
Benchmarked over 70 graph clustering algorithms.
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. In our algorithm, computation of function values or gradients is not required. Instead, pairwise comparison of function values is used. Our algorithm consists of two steps; one is the direction estimate step and the o…
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of objects can be identified by standard sorting methods using pairwise comparisons. We are interested in natural situations in which relationships among the o…
We study the active learning problem of top- ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top- items with high probability by adaptively querying sets for comparisons and observing the noisy output of the most preferred item from each comparison. To ac…
This paper optimizes the number of comparisons needed to find the best k items from pairwise comparisons.
We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksor…
A common problem in machine learning is to rank a set of n items based on pairwise comparisons. Here ranking refers to partitioning the items into sets of pre-specified sizes according to their scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defi…
Improves comparison of F-measures for imbalanced datasets.
New algorithm for identifying Condorcet team in noisy comparisons.
In this paper, we propose an active learning algorithm and models which can gradually learn individual's preference through pairwise comparisons. The active learning scheme aims at finding individual's most preferred choice with minimized number of pairwise comparisons. The pairwise comparisons are encoded into probabi…
In this paper, we compare the three most popular algorithms for hyperparameter optimization (Grid Search, Random Search, and Genetic Algorithm) and attempt to use them for neural architecture search (NAS). We use these algorithms for building a convolutional neural network (search architecture). Experimental results on…
Binary feedback outperforms ordinal comparisons in ranking recovery.
New oracle uses uncertainty for active classification with noisy feedback.
The dueling bandit problem is a variation of the classical multi-armed bandit in which the allowable actions are noisy comparisons between pairs of arms. This paper focuses on a new approach for finding the "best" arm according to the Borda criterion using noisy comparisons. We prove that in the absence of structural a…
This work benchmarks MARL algorithms in cooperative tasks.
Comparison Lift uses bandit algorithms to optimize online ad testing.
We analyze training dynamics in Gaussian mixture models using a comparison theorem.
FedML aims to improve FL research by providing a library and benchmark.
AdaStop improves statistical testing for Deep RL algorithm comparisons.
New methods rank players using covariates and comparisons, outperforming existing algorithms.
With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose …
New depth function for partial orders helps compare machine learning algorithms.
We describe a seriation algorithm for ranking a set of items given pairwise comparisons between these items. Intuitively, the algorithm assigns similar rankings to items that compare similarly with all others. It does so by constructing a similarity matrix from pairwise comparisons, using seriation methods to reorder t…
The question of aggregating pair-wise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In mo…
This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in w…
New algorithm learns human preferences from few comparisons efficiently.
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
We study the -armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower bound that is based on the information divergence. An algorithm that is inspired by the Deterministic…
We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking …
This paper presents a detailed comparison of a recently proposed algorithm for optimizing decision trees, tree alternating optimization (TAO), with other popular, established algorithms. We compare their performance on a number of classification and regression datasets of various complexity, different size and dimensio…
Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top items from noisy pairwise comparisons. In our setting, we are non-actively given pairwise comparisons between each pair of items, where each comparison has noi…
New algorithm ranks players from partial comparisons with optimal rate.
Improves Active Learning fairness and comparability across domains.
In this paper, we study a popular method for inference of the Bradley-Terry model parameters, namely the MM algorithm, for maximum likelihood estimation and maximum a posteriori probability estimation. This class of models includes the Bradley-Terry model of paired comparisons, the Rao-Kupper model of paired comparison…
Active learning improves ordering of items with contextual attributes.
This paper proposes a new method for solving the well-known rank aggregation problem from pairwise comparisons using the method of low-rank matrix completion. The partial and noisy data of pairwise comparisons is transformed into a matrix form. We then use tools from matrix completion, which has served as a major compo…