Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
Random forest uses only triplet comparisons to learn from metric spaces.
problem Learning from metric spaces without direct access to data or distances.
method A novel random forest algorithm that uses only triplet comparisons.
result The proposed random forest is consistent and competitive with other methods.
New estimators show consistent estimation is possible with randomized item assignment.
problem Estimating underlying comparison probabilities from noisy pairwise comparisons.
method Study permutation-based models under strong stochastic transitivity, randomized item assignment.
result Rates of estimators are optimal for a large class of graphs.
Randomized Kaczmarz solves ranking from pairwise comparisons.
problem Inferring overall ranking from pairwise preference data.
method Randomized Kaczmarz method applied to noisy linear system.
result The method is convergent, has good empirical performance.
NetOTC compares and aligns directed or undirected networks via random walk transitions.
problem Comparing and aligning networks of different types and sizes.
method NetOTC uses a transport-based approach to find optimal transition couplings of random walks.
result NetOTC quantifies network differences and provides vertex and edge alignments.
This paper compares Grid Search, Random Search, and Genetic Algorithm for NAS.
problem Hyperparameter optimization for neural architecture search.
method Comparison of Grid Search, Random Search, and Genetic Algorithm.
result Genetic Algorithm outperforms Grid Search and Random Search in terms of accuracy and execution time.
Efficient clustering from random comparisons, achieving low error with minimal labeled data.
problem Clustering partially labeled data from random comparisons.
method Power iteration of the non-backtracking operator.
result Small error can be achieved from O(n) randomly chosen measurements. A comparison-based algorithm finds nearest neighbors in metric spaces.
problem Finding nearest neighbors without direct distance information.
method Recursive splitting using random pivot points to form a comparison tree.
result The height of the comparison tree is logarithmic in the number of points, leading to efficient search performance.
Sharp comparison for sub-Gaussian random variables in convex order.
problem Comparing sub-Gaussian random variables in convex order.
method Proving dominance using moment generating functions and convex functions.
result Sharp comparison established between specific sub-Gaussian random variables.
New curvature measure connects graph Laplacian to heat equation and random walks.
problem Understanding curvature in general graphs for random walk analysis.
method Extended Ollivier curvature definition, Laplacian representation, heat equation connection.
result Lower bound on Ollivier curvature equivalent to Lipschitz decay of heat equation solutions.
Paper compares different models for time-to-event analysis.
problem Comparing models for time-to-event analysis.
method Experimental comparison of semi-parametric, parametric, and machine learning models.
result Models' performance evaluated using concordance index.
The paper tackles estimating vectors from binary comparisons, providing bounds and adaptive strategies.
problem Estimating a vector from binary comparisons of preference.
method Theoretical bounds and adaptive strategies for estimating vectors from noisy and randomized comparisons.
result Stable embedding of the space of target vectors and significant gains from adaptive distribution changes.
New algorithm learns human preferences from few comparisons efficiently.
problem Learning human preferences from limited comparison feedback.
method Formulated as D-optimal design for Plackett-Luce model, solved using randomized Frank-Wolfe algorithm.
result Proposed algorithm efficiently solves D-optimal design problem for Plackett-Luce objective.
We study Gauss curvature for random Riemannian metrics on a compact surface, lying in a fixed conformal class; our questions are motivated by comparison geometry. Next, analogous questions are considered for the scalar curvature in dimension n>2, and for the Q-curvature of random Riemannian metrics.
Crowdsourcing platforms are now extensively used for conducting subjective pairwise comparison studies. In this setting, a pairwise comparison dataset is typically gathered via random sampling, either \emph{with} or \emph{without} replacement. In this paper, we use tools from random graph theory to analyze these two ra…
There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into ac…
Automates debiasing for large language model evaluations through Fisher random walk.
problem Rigorous and scalable evaluation of large language models.
method Semiparametric efficient estimator using Fisher random walk for weighted residual balancing.
result Efficient estimation of contextual preference scores for large language models.
Rank regression from pairwise comparisons requires many comparisons to accurately learn model parameters.
problem Learning model parameters for rank regression from noisy pairwise comparisons.
method Uniform random pairwise comparisons to estimate model parameters with a given accuracy.
result Learning model parameters requires a number of comparisons proportional to dNlog3N/ε2. Meta-algorithm for efficient reinforcement learning from human preferences.
problem Learning from human preference comparisons in Markov decision processes.
method Randomized exploration and experimental design for batch comparison queries.
result Meta-algorithm achieves both regret and last-iterate guarantees with minimal preference queries.
New model accounts for scale variation and noise in pairwise comparisons.
problem Nonreciprocal pairwise comparisons in decision analysis.
method Additive model with structured matrix and random perturbation.
result Explicit estimators and probability assessments of admissible ranking regions.
Unified view on random walk and Weisfeiler-Leman kernels, improving accuracy.
problem Improving graph kernel methods for better classification accuracy.
method Define and analyze walk-based node refinement methods, relate to Weisfeiler-Leman test, and introduce new walk-based kernels.
result Walk-based kernels are as expressive as Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison.
ROVAE uses noisy pairwise comparisons to disentangle factors in VAEs.
problem Disentangling factors in VAEs requires an inductive bias.
method Robust Ordinal VAE (ROVAE) incorporates noisy pairwise ordinal comparisons to disentangle factors.
result ROVAE outperforms existing methods and is more robust to noisy comparisons.
Logistic regression for brain imaging without p-values.
problem Computing the distribution of random field suprema is hard.
method Uses logistic regression for brain network classification.
result Performs classification at each edge level without preselected features.
New model captures intransitive preferences without concave likelihood.
problem Complex human choices not accounted for by traditional models.
method Inspired by Condorcet method, Majority Vote model using RUMs.
result Three-dimensional model can represent strong, long intransitive cycles.
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of n objects can be identified by standard sorting methods using nlog2n pairwise comparisons. We are interested in natural situations in which relationships among the o…
New random models improve clustering similarity assessment.
problem Improper random models affect clustering similarity assessments.
method Derived corrected Rand index and Mutual Information measures for varying cluster sizes.
result Random model choice drastically impacts clustering similarity rankings.
Paper proposes a new method to compare classifiers across multiple datasets.
problem Comparing classifiers over multiple datasets with multiple criteria.
method Adopting decision theory, the paper introduces generalized stochastic dominance for ranking classifiers.
result Generalized stochastic dominance can be used to rank classifiers and statistically tested.
We develop a new statistical test for comparing variables with varying scales.
problem Comparing variables with different scales in multidimensional spaces.
method Order based on expectations of random variables, generalized stochastic dominance (GSD) order, regularized statistical test, linear optimization, imprecise probability models.
result Validated through multidimensional data from various fields.
Alternative dynamic paired comparison model using Gaussian Processes.
problem Sports prediction and ranking players or teams.
method Dynamic paired comparison model with Gaussian Process priors, incorporating covariates, and efficient Bayesian inference.
result The GP model outperforms Elo and Glicko on log loss, especially with surface covariates.
XGBoost outperforms other boosting techniques in training speed and generalization performance.
problem Comparing XGBoost with other boosting techniques.
method Comprehensive comparison of XGBoost, random forests, and gradient boosting using tuned and default models.
result XGBoost is not always the best choice under all circumstances.
Paper tackles learning mixture of RUMs from partial data.
problem Learning a mixture of Random Utility Models (RUMs) from pairwise comparisons.
method PCA-based spectral clustering to reduce mixture to single component.
result Algorithm correctly clusters data from a mixture of RUMs with high probability.
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…
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…
The paper improves spectral ranking methods for diverse comparison graphs.
problem Estimating preference scores from multiway comparisons with heterogeneous sizes.
method Develops a two-step spectral method for estimating preference scores and their uncertainties.
result The two-step spectral method achieves the same asymptotic efficiency as the Maximum Likelihood Estimator (MLE).
Improves random survival forest model by weighted averaging.
problem Improving the performance of random survival forest.
method Modifies random forest by weighted averaging of trees, optimizing weights via quadratic optimization to maximize Harrell's C-index.
result The weighted random survival forest outperforms the original model in numerical examples.
Default settings impact machine learning performance; fair evaluation requires best-practice model selection.
problem The impact of default parameter settings on machine learning performance evaluation.
method Investigation of three key machine learning algorithms (SVM, RF, and Rotation Forest) using default settings and cross-validation.
result Rotation Forest outperforms SVM and RF on average.
We review statistical properties of models generated by the application of a (positive and negative order) fractional derivative operator to a standard random walk and show that the resulting stochastic walks display slowly-decaying autocorrelation functions. The relation between these correlated walks and the well-kno…
Analyzes various methods to compare portfolio performance, explaining why simple choices can outperform sophisticated ones.
problem Explains why simple portfolio choices can outperform more complex ones.
method Examines several comparison criteria for portfolios, including those on the market line and in the absence of a risk-free asset.
result Clarifies why some portfolios may seem to outperform others, providing theoretical insights.
In this paper we are concerned with backward stochastic differential equations with random default time and their applications to default risk. The equations are driven by Brownian motion as well as a mutually independent martingale appearing in a defaultable setting. We show that these equations have unique solutions …
Comparison Lift uses bandit algorithms to optimize online ad testing.
problem Optimizing online ad testing to maximize click-through rates.
method Bandit-based experimentation algorithm that adapts to test results.
result Ad click-through rates increased by 46% on average.
New random forest algorithm improves regression with missing data.
problem Regression with missing data values.
method New random forest algorithm compared to existing techniques.
result Improved performance in quadratic errors and bias compared to existing methods.
AdaStop improves statistical testing for Deep RL algorithm comparisons.
problem Statistical reproducibility issues in Deep RL.
method AdaStop, a new statistical test based on multiple group sequential tests.
result AdaStop ensures theoretically sound comparisons of Deep RL algorithms.
Partition functions arise in a variety of settings, including conditional random fields, logistic regression, and latent gaussian models. In this paper, we consider semistochastic quadratic bound (SQB) methods for maximum likelihood inference based on partition function optimization. Batch methods based on the quadrati…
Estimates user preferences from noisy paired comparisons.
problem Estimating user preferences from noisy paired comparisons.
method Greedy information maximization strategies.
result Superior preference estimation over state-of-the-art methods.
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…
A new method selects variables for random survival forests using maximally selected rank statistics.
problem Random survival forests can be biased in selecting variables, especially for non-linear effects.
method Use maximally selected rank statistics for variable selection in random survival forests, comparing on p-value scale.
result The new method outperforms other approaches in prediction performance and computational speed.
Study uses three sources to evaluate language models fairly.
problem Bias in offline model evaluation due to confounded model choice.
method Combines observational logs, randomized experiments, and simulators.
result Randomized experiment and simulator together recover causal model values.
A new method corrects flaws in comparing deep learning architectures.
problem Flaws in comparing deep learning architectures using best single model performance.
method Proposes Boo_n method to correct stochasticity in model performance.
result Corrects flaws in comparing deep learning architectures.