Search

An important challenge in robust machine learning is when training data is provided by strategic sources who may intentionally report erroneous data for their own benefit. A line of work at the intersection of machine learning and mechanism design aims to deter strategic agents from reporting erroneous training data by designing learning algorithms that are strategyproof. Strategyproofness is a strong and desirable property, but it comes at a cost in the approximation ratio of even simple risk minimization problems. In this paper, we study strategyproof regression and classification problems in a model with advice. This model is part of a recent line on mechanism design with advice where the goal is to achieve both an improved approximation ratio when the advice is correct (consistency) and a bounded approximation ratio when the advice is incorrect (robustness). We provide the first non-trivial consistency-robustness tradeoffs for strategyproof regression and classification, which hold for simple yet interesting classes of functions. For classes of constant functions, we give a deterministic and strategyproof mechanism that is, for any $\gamma \in (0, 2]$, $1+\gamma$ consistent and $1 + 4/\gamma$ robust and provide a lower bound that shows that this tradeoff is optimal. We extend this mechanism and its guarantees to homogeneous linear regression over $\mathbb{R}$. In the binary classification problem of selecting from three or more labelings, we present strong impossibility results for both deterministic and randomized mechanism. Finally, we provide deterministic and randomized mechanisms for selecting from two labelings.

In several clinical areas, traditional clinical trials often use a responder outcome, a composite endpoint that involves dichotomising a continuous measure. An augmented binary method that improves power whilst retaining the original responder endpoint has previously been proposed. The method leverages information from the the undichotomised component to improve power. We extend this method for basket trials, which are gaining popularity in many clinical areas. For clinical areas where response outcomes are used, we propose the new Augmented Binary method for BAsket trials (ABBA) enhances efficiency by borrowing information on the treatment effect between subtrials. The method is developed within a latent variable framework using a Bayesian hierarchical modelling approach. We investigate the properties of the proposed methodology by analysing point estimates and credible intervals in various simulation scenarios, comparing them to the standard analysis for basket trials that assumes binary outcome. Our method results in a reduction of 95% high density interval of the posterior distribution of the log odds ratio and an increase in power when the treatment effect is consistent across subtrials. We illustrate our approach using real data from two clinical trials in rheumatology., Comment: 20 pages, 6 tables, 2 figures

We look at simple groups associated primarily with the general theory of Moufang buildings, and to analyze their relation to stability theory in the model theoretic sense. As it becomes quite technical in the details, a lengthy introduction surveys the developments at a less detailed level. The text, beginning from the second section, first deals with some model theoretic algebra of fields, followed by an extended study of three associated families of simple groups coming from the theory of Tits buildings, Moufang polygons, and Timmesfeld's theory of exotic analogs of SL_2. The field theoretic part is fundamental ({\S}2). The rest of the paper relates this to group theoretic constructions, with two sections surveying the consequences for the original Tits and Timmesfeld theory before concentrating on the more exotic groups associated with Moufang polygons. A good deal of the group theoretical material is expository, aimed to make the relevant structural information meaningful to those coming from the direction of model theory.

Aiming to overcome some of the limitations of worst-case analysis, the recently proposed framework of "algorithms with predictions" allows algorithms to be augmented with a (possibly erroneous) machine-learned prediction that they can use as a guide. In this framework, the goal is to obtain improved guarantees when the prediction is correct, which is called \emph{consistency}, while simultaneously guaranteeing some worst-case bounds even when the prediction is arbitrarily wrong, which is called \emph{robustness}. The vast majority of the work on this framework has focused on a refined analysis of online algorithms augmented with predictions regarding the future input. A subsequent line of work has also successfully adapted this framework to mechanism design, where the prediction is regarding the private information of strategic agents. In this paper, we initiate the study of online mechanism design with predictions, which combines the challenges of online algorithms with predictions and mechanism design with predictions. We consider the well-studied problem of designing a revenue-maximizing auction to sell a single item to strategic bidders who arrive and depart over time, each with an unknown, private, value for the item. We study the learning-augmented version of this problem where the auction designer is given a prediction regarding the maximum value over all agents. Our main result is a strategyproof mechanism whose revenue guarantees are $\alpha$-consistent with respect to the highest value and $(1-\alpha^2)/4$-robust with respect to the second-highest value, for $\alpha \in [0,1]$. We show that this tradeoff is optimal within a broad and natural family of auctions, meaning that any $\alpha$-consistent mechanism in that family has robustness at most $(1-\alpha^2)/4$. Finally, we extend our mechanism to also achieve expected revenues proportional to the prediction quality., Comment: 25 pages, 1 figure

Introduction: Even in effectively conducted randomised trials, the probability of a successful study remains relatively low. With recent advances in the next-generation sequencing technologies, there is a rapidly growing number of high-dimensional data, including genetic, molecular and phenotypic information, that have improved our understanding of driver genes, drug targets, and drug mechanisms of action. The leveraging of high-dimensional data holds promise for increased success of clinical trials. Methods: We provide an overview of methods for utilising high-dimensional data in clinical trials. We also investigate the use of these methods in practice through a review of recently published randomised clinical trials that utilise high-dimensional genetic data. The review includes articles that were published between 2019 and 2021, identified through the PubMed database. Results: Out of 174 screened articles, 100 (57.5%) were randomised clinical trials that collected high-dimensional data. The most common clinical area was oncology (30%), followed by chronic diseases (28%), nutrition and ageing (18%) and cardiovascular diseases (7%). The most common types of data analysed were gene expression data (70%), followed by DNA data (21%). The most common method of analysis (36.3%) was univariable analysis. Articles that described multivariable analyses used standard statistical methods. Most of the clinical trials had two arms. Discussion: New methodological approaches are required for more efficient analysis of the increasing amount of high-dimensional data collected in randomised clinical trials. We highlight the limitations and barriers to the current use of high-dimensional data in trials, and suggest potential avenues for improvement and future work., Comment: 17 pages, 3 figures, 2 tables

We propose a Cross-validated ADaptive ENrichment design (CADEN) in which a trial population is enriched with a subpopulation of patients who are predicted to benefit from the treatment more than an average patient (the sensitive group). This subpopulation is found using a risk score constructed from the baseline (potentially high-dimensional) information about patients. The design incorporates an early stopping rule for futility. Simulation studies are used to assess the properties of CADEN against the original (non-enrichment) cross-validated risk scores (CVRS) design that constructs a risk score at the end of the trial. We show that when there exists a sensitive group of patients, CADEN achieves a higher power and a reduction in the expected sample size, in comparison to the CVRS design. We illustrate the application of the design in two real clinical trials. We conclude that the new design offers improved statistical efficiency in comparison to the existing non-enrichment method, as well as increased benefit to patients. The method has been implemented in an R package caden., Comment: 1 figure

We give a bibliography of works relating to homogeneous structures in the sense of Fra\"iss\'e, and related topics, mainly through 2016, with some narrow updating through 2021. We first give a list arranged by topics, with references to the main bibliogrphay, which follows., Comment: 67 pages. V2, reformatted and corrected. Source included

We study Ramsey expansions of certain homogeneous 3-hypertournaments. We show that they exhibit an interesting behaviour and, in one case, they seem not to submit to current gold-standard methods for obtaining Ramsey expansions. This makes these examples very interesting from the point of view of structural Ramsey theory as there is a large demand for novel examples., Comment: Extended abstract accepted to EUROCOMB 2021

Suppose we are given a system of coupled oscillators on an unknown graph along with the trajectory of the system during some period. Can we predict whether the system will eventually synchronize? Even with a known underlying graph structure, this is an important yet analytically intractable question in general. In this work, we take an alternative approach to the synchronization prediction problem by viewing it as a classification problem based on the fact that any given system will eventually synchronize or converge to a non-synchronizing limit cycle. By only using some basic statistics of the underlying graphs such as edge density and diameter, our method can achieve perfect accuracy when there is a significant difference in the topology of the underlying graphs between the synchronizing and the non-synchronizing examples. However, in the problem setting where these graph statistics cannot distinguish the two classes very well (e.g., when the graphs are generated from the same random graph model), we find that pairing a few iterations of the initial dynamics along with the graph statistics as the input to our classification algorithms can lead to significant improvement in accuracy; far exceeding what is known by the classical oscillator theory. More surprisingly, we find that in almost all such settings, dropping out the basic graph statistics and training our algorithms with only initial dynamics achieves nearly the same accuracy. We demonstrate our method on three models of continuous and discrete coupled oscillators -- the Kuramoto model, Firefly Cellular Automata, and Greenberg-Hastings model. Finally, we also propose an "ensemble prediction" algorithm that successfully scales our method to large graphs by training on dynamics observed from multiple random subgraphs., Comment: 22 pages, 13 figures, 3 tables

The existing cross-validated risk scores (CVRS) design has been proposed for developing and testing the efficacy of a treatment in a high-efficacy patient group (the sensitive group) using high-dimensional data (such as genetic data). The design is based on computing a risk score for each patient and dividing them into clusters using a non-parametric clustering procedure. In some settings it is desirable to consider the trade-off between two outcomes, such as efficacy and toxicity, or cost and effectiveness. With this motivation, we extend the CVRS design (CVRS2) to consider two outcomes. The design employs bivariate risk scores that are divided into clusters. We assess the properties of the CVRS2 using simulated data and illustrate its application on a randomised psychiatry trial. We show that CVRS2 is able to reliably identify the sensitive group (the group for which the new treatment provides benefit on both outcomes) in the simulated data. We apply the CVRS2 design to a psychology clinical trial that had offender status and substance use status as two outcomes and collected a large number of baseline covariates. The CVRS2 design yields a significant treatment effect for both outcomes, while the CVRS approach identified a significant effect for the offender status only after pre-filtering the covariates., Comment: 30 pages, 3 figures, 3 tables