A regularized risk minimization procedure for regression function estimation is introduced that achieves near optimal accuracy and confidence under general conditions, including heavy-tailed predictor and response variables. The procedure is based on median-of-means tournaments, introduced by the authors in [8]. It is …
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,695 papers · 148 categories
Trend · papers per month
48 results for “tournament procedure”
Breaks the hardness conjecture for batch RL with a novel tournament-based approach.
problem Sample-efficient reinforcement learning from exploratory data.
method BVFT algorithm using pairwise comparison and state-action partition.
result Solves the learning problem in a setting previously thought impossible.
Proposes a flexible tournament design combining knockout and round-robin.
problem Designing a tournament that eliminates participants linearly.
method Combines knockout and round-robin structures for flexible elimination.
result Flexible tournament design can eliminate participants linearly.
Classifies intrinsically linked tournaments by their score sequences.
problem Classifying intrinsically linked tournaments using their score sequences.
method Examining the score sequences of tournaments and identifying linkless sequences.
result The vast majority of score sequences for 8-vertex tournaments are linkless.
We explore a new way to evaluate generative models using insights from evaluation of competitive games between human players. We show experimentally that tournaments between generators and discriminators provide an effective way to evaluate generative models. We introduce two methods for summarizing tournament outcomes…
A directed graph is if every embedding of that graph contains a non-split link , where each component of is a consistently oriented cycle in . A is a directed graph where each pair of vertices is connected by exactly one directed edge. We consider intr…
Extracts StarCraft II tournament data for AI and ML studies.
problem Lack of accessible esports data for scientific use.
method Gathered and processed StarCraft II tournament replays using an API parser library.
result The largest publicly available StarCraft II esports dataset.
Reply to Tetlock et al. on tail risk and probability gap.
problem Expert judgment fails to account for tail risk.
method Comparison of forecasting tournaments and extreme value theory.
result Greater gap between tail expectation and probability properties.
This paper extends Median-of-Means to new learning problems involving pairwise comparisons.
problem Learning from pairwise comparisons in machine learning.
method Segmenting data into blocks, comparing pairs of decision rules, and declaring the winner based on majority performance.
result The Median-of-Means approach maintains robustness and performance under various sampling schemes.
We propose a novel ranking model that combines the Bradley-Terry-Luce probability model with a nonnegative matrix factorization framework to model and uncover the presence of latent variables that influence the performance of top tennis players. We derive an efficient, provably convergent, and numerically stable majori…
The paper tackles optimal level set estimation in crowdsourcing and tournaments.
problem Deciphering small entries in a partially observed matrix of expert correctness.
method Constructs an efficient polynomial-time algorithm for recovering level sets up to a precision.
result The algorithm is minimax optimal for the classification problem, contrasting with existing literature.
New method estimates optimizer for convex stochastic problems.
problem Estimating optimizer for convex stochastic optimization problems.
method Median-of-means tournament procedure for heavy-tailed data.
result Optimal statistical performance in heavy tailed situations.
Elo ratings learn model parameters quickly using Markov chains.
problem Ranking players in online settings.
method Bradley--Terry--Luce model and Markov chain theory.
result Elo learns model parameters at a competitive rate.
Tournament Leave-pair-out Cross-validation for Receiver Operating Characteristic (ROC) Analysisstat.ML
Receiver operating characteristic (ROC) analysis is widely used for evaluating diagnostic systems. Recent studies have shown that estimating an area under ROC curve (AUC) with standard cross-validation methods suffers from a large bias. The leave-pair-out (LPO) cross-validation has been shown to correct this bias. Howe…
The small-ball method was introduced as a way of obtaining a high probability, isomorphic lower bound on the quadratic empirical process, under weak assumptions on the indexing class. The key assumption was that class members satisfy a uniform small-ball estimate: that for given const…
Introducing ReQuEST: an Open Platform for Reproducible and Quality-Efficient Systems-ML Tournamentsstat.ML
Co-designing efficient machine learning based systems across the whole hardware/software stack to trade off speed, accuracy, energy and costs is becoming extremely complex and time consuming. Researchers often struggle to evaluate and compare different published works across rapidly evolving software frameworks, hetero…
We are interested in parallelizing the Least Angle Regression (LARS) algorithm for fitting linear regression models to high-dimensional data. We consider two parallel and communication avoiding versions of the basic LARS algorithm. The two algorithms have different asymptotic costs and practical performance. One offers…
New method improves stock return prediction in non-stationary markets.
problem Tackles the challenge of predicting stock returns in non-stationary environments.
method Jointly optimizes model class and training window size using a tournament procedure.
result Consistently outperforms standard benchmarks by 14-23% in out-of-sample .
New algorithms for model selection in off-policy evaluation of reinforcement learning.
problem Hyperparameter tuning for off-policy evaluation methods in reinforcement learning.
method Developed new model-free and model-based selectors with theoretical guarantees and a new experimental protocol.
result New model-free selector, LSTD-Tournament, demonstrates promising empirical performance.
Directed graphs occur throughout statistical modeling of networks, and exchangeability is a natural assumption when the ordering of vertices does not matter. There is a deep structural theory for exchangeable undirected graphs, which extends to the directed case via measurable objects known as digraphons. Using digraph…
In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function's parameters for computer chess. Our results show that using an appropriate mentor, we can evolve a program that is on par with top tournament-playing chess programs, outperforming a two-time World Computer Chess …
The paper derives upper bounds on the MLE error for BTL model under general graphs.
problem Estimating the MLE of BTL model parameters with -loss under general graphs.
method Novel upper bounds on estimation error dependent on algebraic connectivity and graph topology.
result Upper bounds on error are sharp and match minimax lower bounds under certain graph topologies.
The paper studies dynamic ranking and translation synchronization from evolving pairwise comparison graphs.
problem Dynamic pairwise comparison graphs in evolving environments.
method Proposes estimators based on smoothness-penalized least squares and projection onto low frequency eigenspace.
result Finite sample bounds for the estimation error, proving consistency of the proposed methods.
In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function's parameters for computer chess. Our results show that using an appropriate expert (or mentor), we can evolve a program that is on par with top tournament-playing chess programs, outperforming a two-time World Com…
A method for dynamic ranking using BTL model and nearest neighbor rank centrality.
problem Aggregating evolving pairwise comparisons to recover item strengths over time.
method Adapting Rank Centrality method to handle dynamic pairwise outcomes.
result Consistency of the method in estimating latent strengths over time.
Bayesian model infers strengths from noisy tennis match outcomes.
problem Ranking tennis players from match outcomes.
method Bayesian approach to infer unobserved strengths and mapping function.
result Bayesian approach robust to different model specifications.
Recently we proposed a general, ensemble-based feature engineering wrapper (FEW) that was paired with a number of machine learning methods to solve regression problems. Here, we adapt FEW for supervised classification and perform a thorough analysis of fitness and survival methods within this framework. Our tests demon…
Fantasy Premier League (FPL) performance predictors tend to base their algorithms purely on historical statistical data. The main problems with this approach is that external factors such as injuries, managerial decisions and other tournament match statistics can never be factored into the final predictions. In this pa…
Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We…
A number of applications (e.g., AI bot tournaments, sports, peer grading, crowdsourcing) use pairwise comparison data and the Bradley-Terry-Luce (BTL) model to evaluate a given collection of items (e.g., bots, teams, students, search results). Past work has shown that under the BTL model, the widely-used maximum-likeli…
Tennis is a popular sport worldwide, boasting millions of fans and numerous national and international tournaments. Like many sports, tennis has benefitted from the popularity of rigorous record-keeping of game and player information, as well as the growth of machine learning methods for use in sports analytics. Of par…
Optimizes decision-making in dueling bandits with contextual features.
problem Identifying the best arm in dueling bandits with contextual features.
method Develops algorithms for minimizing regret in stochastic contextual dueling bandits.
result Proves optimal regret bounds for contextual dueling bandits.
Recent progress in artificial intelligence through reinforcement learning (RL) has shown great success on increasingly complex single-agent environments and two-player turn-based games. However, the real-world contains multiple agents, each learning and acting independently to cooperate and compete with other agents, a…
This paper tackles bandit optimization with a new pairwise comparison oracle for unknown strongly concave functions.
problem Maximizing an unknown strongly concave function over T periods with a biased pairwise comparison oracle.
method Introduced a discretization technique and local polynomial approximation to relate the problem to linear bandits. Developed a tournament successive elimination technique to localize the discretized cell and run LinUCB algorithm on cells.
result Established optimal regret bounds and improved state-of-the-art results in operations management problems.
Item response theory (IRT) models are widely used in psychometrics and educational measurement, being deployed in many high stakes tests such as the GRE aptitude test. IRT has largely focused on estimation of a single latent trait (e.g. ability) that remains static through the collection of item responses. However, in …
We study learning problems involving arbitrary classes of functions , distributions and targets . Because proper learning procedures, i.e., procedures that are only allowed to select functions in , tend to perform poorly unless the problem satisfies some additional structural property (e.g., that is co…
The need for parameter estimation with massive datasets has reinvigorated interest in stochastic optimization and iterative estimation procedures. Stochastic approximations are at the forefront of this recent development as they yield procedures that are simple, general, and fast. However, standard stochastic approxima…
We describe a procedure which verifies that a group given by generators and relators is word-hyperbolic. This procedure always works with a group which is word-hyperbolic, provided there is sufficient memory and time devoted to the problem. If the group is not word-hyperbolic, the procedure continues indefinitely. We a…
Myopic procedures are shown to be asymptotically optimal in ranking and selection problems.
problem Selecting the best design from a set with unknown mean performance.
method Myopic procedures that iteratively improve an approximation of the objective measure.
result Myopic procedures satisfy optimality conditions of ranking and selection problems.
Several authors have pointed out the connection between Barbilian's metric introduced in 1934 and the recent study of Apollonian metrics. We provide examples of various distances that can be obtained by Barbilian's metrization procedure and we discuss the relation between this metrization procedure and important Rieman…
Biclustering, the process of simultaneously clustering the rows and columns of a data matrix, is a popular and effective tool for finding structure in a high-dimensional dataset. Many biclustering procedures appear to work well in practice, but most do not have associated consistency guarantees. To address this shortco…
Chemical plants are complex and dynamical systems consisting of many components for manipulation and sensing, whose state transitions depend on various factors such as time, disturbance, and operation procedures. For the purpose of supporting human operators of chemical plants, we are developing an AI system that can s…
ARK improves knockoffs robustness to feature distribution misspecification.
problem Robustness of knockoffs inference to misspecified feature distributions.
method Coupling approximate knockoffs with model-X knockoffs to achieve FDR and FWER control.
result The approximate knockoffs procedure can control FDR and FWER asymptotically.
A new procedure, called DDa-procedure, is developed to solve the problem of classifying d-dimensional objects into q >= 2 classes. The procedure is completely nonparametric; it uses q-dimensional depth plots and a very efficient algorithm for discrimination analysis in the depth space [0,1]^q. Specifically, the depth i…
Investigation of the market graph attracts a growing attention in market network analysis. One of the important problem connected with market graph is to identify it from observations. Traditional way for the market graph identification is to use a simple procedure based on statistical estimations of Pearson correlatio…
A new method calibrates forecasts without sacrificing expertise.
problem Forecasters' calibration scores can be manipulated to appear expert.
method Deterministic and stochastic online procedures to calibrate forecasts.
result Calibration can be achieved without losing expertise.
Procedure groups nonparametric regression curves automatically.
problem Determining groups of nonparametric regression curves when curves are numerous.
method Automatic selection of group number through testing procedure.
result Groups of nonparametric regression curves exist in tunnel geometry.
We model the quantities appearing in Internal Revenue Service (IRS) tax guidance for calculating the health insurance premium tax credit created by the Patient Protection and Affordable Care Act, also called Obamacare. We ask the question of whether there is a procedure, computable by hand, which can calculate the appr…