158 research outputs found
Confusion Matrix Design for Downstream Decision-Making (Extended Abstract)
No full textWe initiate the study of confusion matrix design. In this problem, an algorithm designer needs to generate a machine learning model (for a classification task from contexts to labels) which makes predictions for a population of downstream decision makers. The prediction accuracy of the machine learning model is characterized by its confusion matrix, which is a stochastic matrix where each entry encodes the probability of predicting the true label to another label. Each downstream decision maker faces a separate optimization task and will decide his binary action based on his own context, realized prediction given his context, and the confusion matrix selected by the algorithm designer. Decision makers are heterogeneous, as they may hold different contexts. Both the decision makers and the algorithm designer will obtain utilities that are determined by the actions the decision makers take, and their true labels. The goal of the algorithm designer is to design a public confusion matrix that is used for all decision makers subject to some feasibility constraints in order to maximize her net utility. We consider a general class of net utility functions, which could be a combination of both decision makers' utilities and the algorithm designer’s utility. Classic outcome-independent utility and utilitarian/Nash/egalitarian social welfare are all special cases of our net utility formulation.
We study the above problem through an information design framework, where we view training machine learning model as designing an information structure (signaling scheme) subject to some specific constraints motivated by the machine learning literature. By building the connection to the public persuasion with heterogeneous priors, we design convex programming-based algorithms that compute the optimal confusion matrix subject to (i) post-processing constraints and (ii) receiver operating characteristic (ROC) constraints in polynomial time, respectively. Besides the computational results, we also obtain analytical structural results and numerical results for the special cases of outcome-independent utility and social-aware utility, by utilizing the convex programming-based characterization of the optimal confusion matrix
Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)
No full textIn several applications of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems, where online vertices arrive in K batches. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratios known for the online variant of these problems [Mehta et al., 2007; Aggarwal et al., 2011].
Our main technique is using a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage (by solving the stage’s convex program). We further show a matching upper-bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios
Revelation gap for pricing from samples
No full textThis paper considers prior-independent mechanism design, in which a single mechanism is designed to achieve approximately optimal performance on every prior distribution from a given class. Most results in this literature focus on mechanisms with truthtelling equilibria, a.k.a., truthful mechanisms. Feng and Hartline [FOCS 2018] introduce the revelation gap to quantify the loss of the restriction to truthful mechanisms. We solve a main open question left in Feng and Hartline [FOCS 2018]; namely, we identify a non-trivial revelation gap for revenue maximization. Our analysis focuses on the canonical problem of selling a single item to a single agent with only access to a single sample from the agent's valuation distribution. We identify the sample-bid mechanism (a simple non-truthful mechanism) and upper-bound its prior-independent approximation ratio by 1.835 (resp. 1.296) for regular (resp. MHR) distributions. We further prove that no truthful mechanism can achieve prior-independent approximation ratio better than 1.957 (resp. 1.543) for regular (resp. MHR) distributions. Thus, a non-trivial revelation gap is shown as the sample-bid mechanism outperforms the optimal prior-independent truthful mechanism. On the hardness side, we prove that no (possibly non-truthful) mechanism can achieve prior-independent approximation ratio better than 1.073 even for uniform distributions.</p
Studies of dynamics of infectious diseases using mathematical models
No full textThis thesis centers on the study of transmission dynamics of infectious diseases using mathematical models. It includes two main topics. The first one concerns the evolutionary dynamics of the human-schistosome-snail system. The second topic is on the evaluation of disease control strategies for directly transmitted infections such as influenza and SARS. The models attempt to answer specific biological questions that are of interest to biologists and policy-makers for public health. The model for human-schistosomesnail interactions is used to study questions including the impact of drug-treatment of human hosts and drug-resistance of parasites within human hosts as well as the role of parasite virulence on the the evolutionary dynamics of intermediate snail hosts. The models for directly transmitted diseases are employed to generate helpful information that can assist policy-makers in disease control and intervention. More specifically, for the human-schistosome-snail system, our model includes two snail host types and a single parasite strain. An age-structure of human hosts is also considered to reflect the age-dependent transmission rate and age-targeted drugtreatment rate. We consider various biological factors that may affect the evolutionary dynamics of host-parasite interactions. By assuming various trade-offs between parasite drug-resistance and the associated fitness cost and between snail resistance to the parasite and the associated cost in reproduction, we investigate the roles of drug-treatment rate, drug-resistance level, and parasite virulence on the evolutionary outcomes of the host-parasite system. Many existing epidemiological models have assumed that disease stages have exponentially distributed durations. However, models that use the exponential distribution assumption (EDA) may generate biased and even misleading results in some cases. This discrepancy is particularly damaging if the models are employed to assist policy-makers in disease control and interventions. Particularly, health authorities must rely on quarantine, isolation and other non-pharmaceutical interventions to contain outbreaks of newly emerging human diseases. Models with the EDA are especially inappropriate for evaluating the effectiveness of these control strategies. This thesis includes studies of mathematical models that use more realistic assumptions on disease stage durations (with the exponential distribution as a special case). With biological parameters for SARS from the initial case series in Hong Kong and infection rates from hospitalizations in Singapore, we determined sensitivity of model results to control parameters, which allows us to compare the effectiveness of various control strategies
Study of meiotic chromosomal structure and molecular mechanisms of meiotic prophase I
No full textSubmission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2023-12-01The student, Yiding Xu, accepted the attached license on 2021-08-17 at 12:22.The student, Yiding Xu, submitted this Thesis for approval on 2021-08-17 at 12:36.This Thesis was approved for publication on 2021-08-20 at 13:14.DSpace SAF Submission Ingestion Package generated from Vireo submission #17111 on 2022-04-29 at 16:08:53Made available in DSpace on 2022-04-29T21:58:14Z (GMT). No. of bitstreams: 2
XU-THESIS-2021.pdf: 11057102 bytes, checksum: 9912821002458c7b8bb2962e1828f09c (MD5)
LICENSE.txt: 4206 bytes, checksum: b868ca5906b0d445a6fefff2e998f5a9 (MD5)
Previous issue date: 2021-08-20Embargo set by: Seth Robbins for item 123406
Lift date: 2024-04-29T21:58:46Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemAuthor requested closed access (OA after 2yrs) in Vireo ETD systemLimitedMeiosis is a specialized cell division that produces gametes (sperms and eggs) in sexually reproducing organisms. The prophase I of meiosis is a unique stage, during which pairing and recombination of homologous maternal and parental chromosomes occur. Programed DNA double-strand breaks (DSBs) are generated by SPO11 proteins at the beginning of meiosis. Homologous chromosomes (homologs) first become co-aligned, then, synapse via establishment of a protein complex called synaptonemal complex (SC). DSBs are repaired through homologous recombination (HR). During HR, DNA damage response proteins and other DNA repair proteins are recruited to meiotic DSB sites and results in either non-crossovers or crossovers. A mechanism called meiotic silencing of unsynapsed chromatin (MSUC) silences chromosomes that fail to pair with its homologous partners. A special example of MSUC is meiotic sex chromosome inactivation (MSCI), which specifically silences sex chromosomes in pachytene spermatocytes. During this process, sex chromosomes compact and form a transcriptionally silent nuclear territory named “sex body” or “XY body”. It is critical to understand the molecular and biophysical mechanisms underlying these meiotic events.
Liquid-liquid phase separation (LLPS) is a process by which a homogenous aqueous solution demixes into distinct phases. It has emerged as a unifying mechanism in the cell that governs the formation of membraneless organelles and biomolecular compartments. Recent work suggests that the formation of heterochromatin is also driven by LLPS through phase-separating protein HP1. Thus, LLPS is likely a universal mechanism for forming cellular condensates. LLPS has been hypothesized to drive the formation of the Barr body, the inactive X chromosome in female mammals. Here, we addressed the possibility that LLPS underlies the formation of the sex body in spermatocytes.
During premeiotic S phase, sister chromatids are formed and held together by cohesin complexes. During meiotic prophase I, chromosomes are organized into compacted loop arrays and exhibit dynamic architectures. Both imaging-based and sequencing-based techniques are developed to study chromosome organizations. Recent advances on chromatin conformation capture (3C)-based methods have shed a new light on the genome-wide chromatin interactions. The reorganization of chromatin architecture during meiotic prophase I has been described. Topologically associating domains (TADs), a typical organization feature of interphase chromosomes, are completely lost at pachytene stage, suggesting meiosis-specific cohesin complexes load onto DNA to form stable loop structures. Interactions between homologs during synapsis are also detected, revealing the juxtaposed arrays of chromatin loops. However, sister chromatids could not be distinguished in paired homologs by traditional Hi-C technique. The recent breakthrough in mitotic study introduced two Hi-C-based approaches that can discriminate the inter- and intra-sister-chromatid interactions in human cancer and yeast cells. It is worthy considering the applications of these methods in meiotic studies.
The focus of my thesis is to study the architecture of meiotic chromosomes and the underlying mechanisms of special events during meiotic prophase I. First, I described the work on developing a novel method to study the organization of meiotic chromatin. I demonstrated its feasibility by showing the results from three key steps of the method: the synchronization of spermatogenesis, in-vitro testis culture, and incorporating BrdU during testis culture. Further, I gathered evidence from the literature and hypothesized that LLPS is linked to MSCI and sex-body formation
An End-to-End Argument in Mechanism Design (Prior-Independent Auctions for Budgeted Agents)
No full textThis paper considers prior-independent mechanism design, namely identifying a single mechanism that has near optimal performance on every prior distribution. We show that mechanisms with truthtelling equilibria, a.k.a., revelation mechanisms, do not always give optimal prior-independent mechanisms and we define the revelation gap to quantify the non-optimality of revelation mechanisms. This study suggests that it is important to develop a theory for the design of non-revelation mechanisms. Our analysis focuses on welfare maximization by singleitem auctions for agents with budgets and a natural regularity assumption on their distribution of values. The all-pay auction (a non-revelation mechanism) is the Bayesian optimal mechanism; as it is prior-independent it is also the prior-independent optimal mechanism (a 1-approximation). We prove a lower bound on the prior-independent approximation of revelation mechanisms of 1.013 and that the clinching auction (a revelation mechanism) is a prior-independent ϵ ≠ 2.714 approximation. Thus the revelation gap for single-item welfare maximization with public budget agents is in [1.013, e]. Some of our analyses extend to the revenue objective, position environments, and irregular distributions.</p
Recommended from our members
Batching and Optimal Multi-stage Bipartite Allocations
No full textIn several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. As our base model, we consider K-stage variants of the classic vertex weighted bipartite b-matching in the adversarial setting, where online vertices arrive stage-wise and in K batches — in contrast to online arrival. Our main result for this problem is an optimal 1−(1−1/K)^K- competitive (fractional) matching algorithm, improving the classic (1 − 1/e) competitive ratio bound known for its online variant (Mehta et al., 2007; Aggarwal et al., 2011). We also extend this result to the rich model of multi-stage configuration allocation with free-disposals (Devanur et al., 2016), which is motivated by the display advertising application in the context of video streaming platforms. Our main technique at high-level is developing algorithmic tools to vary the trade-off between “greedy- ness” and “hedging” of the matching algorithm across stages. We rely on a particular family of convex- programming based matchings that distribute the demand in a specifically balanced way among supply in different stages, while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degrees to be used as strictly concave regularizers of the maximum weight matching linear program to form these convex programs. At each stage, our fractional multi-stage algorithm returns the corresponding regularized optimal solution as the matching of this stage (by solving the convex program). By providing structural decomposition of the underlying graph using the optimal solutions of these convex programs and recursively connecting the regularizers together, we develop a new multi-stage primal-dual framework to analyze the competitive ratio of this algorithm. We further show this algorithm is optimal competitive, even in the unweighted case, by providing an upper-bound instance in which no online algorithm obtains a competitive ratio better than 1−(1−1/K)^K. For the extension to multi-stage configuration allocation, we introduce a novel extension of our regularized convex program that provides separate regularization at different ”price levels”. Despite the lack of a relevant graph decomposition in this extension, in contrast to our base model, we show how we can directly use convex duality to set up a primal-dual analysis framework for our new algorithm.</p
Batching and Optimal Multistage Bipartite Allocations
No full textIn several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. As our base model, we consider K-stage variants of the classic vertex-weighted bipartite b-matching in the adversarial setting, where online vertices arrive stagewise and in K batches—in contrast to online arrival. Our main result for this problem is an optimal (1 — (1 — 1=K)K)-competitive (fractional) matching algorithm, improving the classic (1 — 1=e)-competitive ratio bound known for its online variant [Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Ad words and generalized online matching. J. ACM 54(5):22–es; Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1253–1264]. We also extend this result to the general problem of multistage configuration allocation with free disposals [Devanur NR, Huang Z, Korula N, Mirrokni VS, Yan Q (2016) Whole page optimization and submodular welfare maximization with online bidders. ACM Trans. Econom. Comput. 4(3):1–20], which is motivated by the display advertising application in the context of video streaming platforms. Our main technique at a high level is developing algorithmic tools to vary the trade-off between “greediness” and “hedging” of the matching algorithm across stages. We rely on a particular family of convex programming–based matchings that distribute the demand in a specifically balanced way among supply in different stages while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degrees to be used as strictly concave regularizers of the maximum weight–matching linear program to form these convex programs. At each stage, our fractional multistage algorithm returns the corresponding regularized optimal solution as the matching of this stage (by solving the convex program). By providing structural decomposition of the underlying graph using the optimal solutions of these convex programs and recursively connecting the regularizers together, we develop a new multistage primal-dual framework to analyze the competitive ratio of this algorithm. We further show this algorithm is optimal competitive, even in the unweighted case, by providing an upper bound instance in which no online algorithm obtains a competitive ratio better than (1 — (1 — 1=K)K). For the extension to multistage configuration allocation, we introduce a novel extension of our regularized convex program that provides separate regularization at different “price levels.” Despite the lack of a relevant graph decomposition in this extension, in contrast to our base model, we show how we can directly use convex duality to set up a primal-dual analysis framework for our new algorithm.</p
- …
