150813 research outputs found
Sort by
Equilibria, Efficiency, and Inequality in Network Formation for Hiring and Opportunity
No full textEC ’24, July 8–11, 2024, New Haven, CT, USAProfessional networks --- the social networks among people in a given line of work --- can serve as a conduit for job prospects and other opportunities. Here we propose a model for the formation of such networks and the transfer of opportunities within them. In our theoretical model, individuals strategically connect with others to maximize the probability that they receive opportunities from them. We explore how professional networks balance connectivity, where connections facilitate opportunity transfers to those who did not get them from outside sources, and congestion, where some individuals receive too many opportunities from their connections and waste some of them.
We show that strategic individuals are over-connected at equilibrium relative to a social optimum, leading to a price of anarchy for which we derive nearly tight asymptotic bounds. We also show that, at equilibrium, individuals form connections to those who provide similar benefit to them as they provide to others. Thus, our model provides a microfoundation in professional networking contexts for the fundamental sociological principle of homophily, that "similarity breeds connection" [McPherson et al., 2001], which in our setting is realized as a form of status homophily based on alignment in individual benefit. We further explore how, even if individuals are a priori equally likely to receive opportunities from outside sources, equilibria can be unequal, and we provide nearly tight bounds on how unequal they can be. Finally, we explore the ability for online platforms to intervene to improve social welfare and show that natural heuristics may result in adverse effects at equilibrium. Our simple model allows for a surprisingly rich analysis of coordination problems in professional networks and suggests many directions for further exploration
“Biopolitics from below?” — Lessons of Emergent Urban Governance Trend Under Covid-19 in China
No full textThis thesis interrogates COVID-19 emergent urban governance trends in China in response to the COVID-19 crisis, with a particular focus on the use of the narratives of epidemic and state emergency, as well as the governance strategies during the pandemic and in the socalled post-COVID era. More importantly, this thesis intends to investigate people’s responses towards emergency policies—the compliances and creative strategies that people have adopted to demonstrate their resistance. Using a combination of ethnographic data and archival research, this thesis covers five major themes: a) the impacts that different outbreak narratives perpetuated on the Internet; b) left-wing scholars’ view (or hope) for the rise of socialism and how the Chinese state has used the socialist narrative to build up its international image; c) the strong comeback of capitalist practices the pandemic exacerbated the precariousness of work; d) how the pandemic has been used as a justification to impose panoptic surveillance and control on Chinese citizens and asked for absolute obedience towards government policies, as well as how the formulaic practices dominated the post-COVID landscape; and finally, e) people’s response and sentiments to government policies such as lockdowns and social distancing displayed on social media platforms. It concludes by arguing that even in an autocratic state with increasingly tightened control justified by the epidemic, people are not passive recipients of such policies. They have come up with creative strategies to express their resistance and exhibit negotiation with the policies. It further argues that in China, COVID-19 has aroused a new wave of active civil participation, for citizens to discuss politics openly, starting from pandemic related topics to the freedom of speech at large. Complicating what Panagiotis Sotiris terms biopolitics from below, it suggests that the creative posts on social media platforms are a savvy means of claiming back our bodies.M.C.P
First and last as superlatives of before and after
No full textFirst and last have been variously described as ordinals, superlatives, or both. These descriptions are generally not accompanied by extensive argumentation, and those who label first and last as superlatives do not present and argue for a particular decomposition. Thus, first and last’s status as ordinals vs. superlatives and their internal composition remain open issues. In this paper, I argue that first and last are superlatives, in particular the superlative forms of before and after. To argue that first and last are superlatives, I show that they pattern like superlatives and unlike ordinals (second, third, etc.) with respect to plurality, modifier choice, “modal superlatives” with possible, and the ordinal superlative construction. I next argue that the relations between before and first and between after and last show themselves overtly in many languages and in English paraphrases; furthermore, first and last semantically differ in ways that before and after have also been noted to differ. While I acknowledge one observation that prima facie counterexemplifies these claims, I argue that it constitutes a genuine counterexample only if one formalizes my decomposition of first/last using a standard Heimian (Heim in Notes on superlatives. Manuscript, MIT (1999)) entry for -est. The counterexample, which concerns the “upstairs de dicto” reading of superlatives, ceases to be an issue if one treats before and after as simplex and formalizes my decomposition using a Containment Hypothesis-inspired semantics (Bobaljik in Universals in comparative morphology: Suppletion, superlatives, and the structure of words, MIT Press, Cambridge, 2012) for -est
A physics-inspired approach to the understanding of molecular representations and models
No full textThe story of machine learning in general, and its application to molecular design in particular, has been a tale of evolving representations of data. Understanding the implications of the use of a particular representation – including the existence of so-called ‘activity cliffs’ for cheminformatics models – is the key to their successful use for molecular discovery. In this work we present a physics-inspired methodology which exploits analogies between model response surfaces and energy landscapes to richly describe the relationship between the representation and the model. From these similarities, a metric emerges which is analogous to the commonly used frustration metric from the chemical physics community. This new property shows state-of-the-art prediction of model error, whilst belonging to a novel class of roughness measure that extends beyond the known data allowing the trivial identification of activity cliffs even in the absence of related training or evaluation data
SySTeC: A Symmetric Sparse Tensor Compiler
No full textCGO ’25, March 01–05, 2025, Las Vegas, NV, USASymmetric and sparse tensors arise naturally in many domains including linear algebra, statistics, physics, chemistry, and graph theory. Symmetric tensors are equal to their transposes, so in the n-dimensional case we can save up to a factor of n! by avoiding redundant operations. Sparse tensors, on the other hand, are mostly zero, and we can save asymptotically by processing only nonzeros. Unfortunately, specializing for both symmetry and sparsity at the same time is uniquely challenging. Optimizing for symmetry requires consideration of n! transpositions of a triangular kernel, which can be complex and error prone. Considering multiple transposed iteration orders and triangular loop bounds also complicates iteration through intricate sparse tensor formats. Additionally, since each combination of symmetry and sparse tensor formats requires a specialized implementation, this leads to a combinatorial number of cases. A compiler is needed, but existing compilers cannot take advantage of both symmetry and sparsity within the same kernel. In this paper, we describe the first compiler which can automatically generate symmetry-aware code for sparse or structured tensor kernels. We introduce a taxonomy for symmetry in tensor kernels, and show how to target each kind of symmetry. Our implementation demonstrates significant speedups ranging from 1.36x for SSYMV to 30.4x for a 5-dimensional MTTKRP over the non-symmetric state of the art
One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares
No full textWhile deep neural networks are capable of achieving state-of-the-art performance in various domains, their training typically requires iterating for many passes over the dataset. However, due to computational and memory constraints and potential privacy concerns, storing and accessing all the data is impractical in many real-world scenarios where the data arrives in a stream. In this thesis, we investigate the problem of one-pass learning, in which a model is trained on sequentially arriving data without retraining on previous datapoints. Motivated by the increasing use of overparameterized models, we develop Orthogonal Recursive Fitting (ORFit), an algorithm for one-pass learning which seeks to perfectly fit every new datapoint while changing the parameters in a direction that causes the least change to the predictions on previous datapoints. By doing so, we bridge two seemingly distinct algorithms in adaptive filtering and machine learning, namely the recursive least-squares (RLS) algorithm and orthogonal gradient descent (OGD). Our algorithm uses the memory efficiently by exploiting the structure of the streaming data via an incremental principal component analysis (IPCA). Further, we show that, for overparameterized linear models, the parameter vector obtained by our algorithm is what stochastic gradient descent (SGD) would converge to in the standard multi-pass setting. Finally, we generalize the results to the nonlinear setting for highly overparameterized models, relevant for deep learning. Our experiments show the effectiveness of the proposed method compared to the baselines.S.M
Metrology of Individual Small Viruses
No full textViruses come in various shapes and sizes, and understanding their morphology is central to understanding their activity and function. The need for fast recognition and real‐time fingerprinting methods for pathogenic viruses is a critical bottleneck in implementing many diagnostic and therapeutic techniques. In this work, nanopore tomography (NT) is implemented for fast measurements of the characteristic dimensions of viruses and the optimal operating conditions are explored. Using a small filamentous bacteriophage as a model, it is demonstrated that NT can detect geometrical features in a few‐nanometer regime, with high throughput and accuracy, in aqueous conditions. The instrumental parameters are optimized to obtain virus diameter measurements that are robust to the uncertainties of the external parameters. Furthermore, NT is critically compared to various single‐particle imaging techniques, with a particular emphasis on emerging helium ion microscopy (HIM). It is shown that, with proper operating procedures, HIM can reach a nanometer‐scale resolution in viral metrology, while retaining a high throughput second only to NT. The high throughput of both techniques can foster sufficient statistics for a precise exploration of viral heterogeneity
Computer-aided multi-objective optimization in small molecule discovery
No full textMolecular discovery is a multi-objective optimization problem that requires identifying a molecule or set of molecules that balance multiple, often competing, properties. Multi-objective molecular design is commonly addressed by combining properties of interest into a single objective function using scalarization, which imposes assumptions about relative importance and uncovers little about the trade-offs between objectives. In contrast to scalarization, Pareto optimization does not require knowledge of relative importance and reveals the trade-offs between objectives. However, it introduces additional considerations in algorithm design. In this review, we describe pool-based and de novo generative approaches to multi-objective molecular discovery with a focus on Pareto optimization algorithms. We show how pool-based molecular discovery is a relatively direct extension of multi-objective Bayesian optimization and how the plethora of different generative models extend from single-objective to multi-objective optimization in similar ways using non-dominated sorting in the reward function (reinforcement learning) or to select molecules for retraining (distribution learning) or propagation (genetic algorithms). Finally, we discuss some remaining challenges and opportunities in the field, emphasizing the opportunity to adopt Bayesian optimization techniques into multi-objective de novo design
Noisy-channel language comprehension in aphasia: A Bayesian mixture modeling approach
No full textIndividuals with “agrammatic” receptive aphasia have long been known to rely on semantic plausibility rather than syntactic cues when interpreting sentences. In contrast to early interpretations of this pattern as indicative of a deficit in syntactic knowledge, a recent proposal views agrammatic comprehension as a case of “noisy-channel” language processing with an increased expectation of noise in the input relative to healthy adults. Here, we investigate the nature of the noise model in aphasia and whether it is adapted to the statistics of the environment. We first replicate findings that a) healthy adults (N = 40) make inferences about the intended meaning of a sentence by weighing the prior probability of an intended sentence against the likelihood of a noise corruption and b) their estimate of the probability of noise increases when there are more errors in the input (manipulated via exposure sentences). We then extend prior findings that adults with chronic post-stroke aphasia (N = 28) and healthy age-matched adults (N = 19) similarly engage in noisy-channel inference during comprehension. We use a hierarchical latent mixture modeling approach to account for the fact that rates of guessing are likely to differ between healthy controls and individuals with aphasia and capture individual differences in the tendency to make inferences. We show that individuals with aphasia are more likely than healthy controls to draw noisy-channel inferences when interpreting semantically implausible sentences, even when group differences in the tendency to guess are accounted for. While healthy adults rapidly adapt their inference rates to an increase in noise in their input, whether individuals with aphasia do the same remains equivocal. Further investigation of comprehension through a noisy-channel lens holds promise for a parsimonious understanding of language processing in aphasia and may suggest potential avenues for treatment
Lower bounds for learning quantum states with single-copy measurements
No full textWe study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d-dimensional state. We first revisit known lower bounds [23] on quantum tomography with accuracy ϵ in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ2-divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2) and Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case.
In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ2-divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp (O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal