We consider a binary crowdsourcing problem in which independent tasks, such as fake-news detection or binary classification tasks, are assigned to$n$imperfect agents, each of which may misclassify/mislabel the tasks with some unknown probability. We revisit a result in [1], presented at NeurIPS 2017, regarding a lower bound for the minimax error of this problem, and then investigate a more general lower bound under a broader parameter set. We demonstrate that for any estimator using a sufficiently large number of independent observations$T$of the labeling results, the probability of having an estimation error of at least$1 / \sqrt{T}$is bounded away from zero by a constant that depends on a structural feature of the parameter set. Additionally, we derive a local version of this result, which essentially asserts that for any$r$-ball around any parameter point and any estimator based on$T \geq 4 / r^{2}$samples, there always exists a point in that ball that cannot be estimated accurately to within$o(1 / \sqrt{T})$.

We formulate the problem of fake news detection using distributed inexpert agents. We consider the source for news/statements as a binary source (to model true vs. false statements). Upon observing news, each agent labels the news as true or false, which equals the validity of the statement with some probability depending on the reliability of the agent. In other words, each agent is viewed as a Binary Symmetric Channel (BSC) that misclassifies each statement with some error probability. For an algorithm that estimates the validity by thresholding a linear combination of the individual agents’ labels, we characterize the optimal weights and threshold to minimize the probability of error. We establish an upper bound on this probability of error as well as the naive majority rule.

The cost of sequencing the genome is dropping at a much faster rate compared to assembling and finishing the genome. The use of lightly sampled genomes (genome-skims) could be transformative for genomic ecology, and results using k-mers have shown the advantage of this approach in identification and phylogenetic placement of eukaryotic species. Here, we revisit the basic question of estimating genomic parameters such as genome length, coverage, and repeat structure, focusing specifically on estimating the k-mer repeat spectrum. We show using a mix of theoretical and empirical analysis that there are fundamental limitations to estimating the k-mer spectra due to ill-conditioned systems, and that has implications for other genomic parameters. We get around this problem using a novel constrained optimization approach (Spline Linear Programming), where the constraints are learned empirically. On reads simulated at 1X coverage from 66 genomes, our method, REPeat SPECTra Estimation (RESPECT), had 2.2% error in length estimation compared to 27% error previously achieved. In shotgun sequenced read samples with contaminants, RESPECT length estimates had median error 4%, in contrast to other methods that had median error 80%. Together, the results suggest that low-pass genomic sequencing can yield reliable estimates of the length and repeat content of the genome. The RESPECT software will be publicly available at https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_shahab-2Dsarmashghi_RESPECT.git&d=DwIGAw&c=-35OiAkTchMrZOngvJPOeA&r=ZozViWvD1E8PorCkfwYKYQMVKFoEcqLFm4Tg49XnPcA&m=f-xS8GMHKckknkc7Xpp8FJYw_ltUwz5frOw1a5pJ81EpdTOK8xhbYmrN4ZxniM96&s=717o8hLR1JmHFpRPSWG6xdUQTikyUjicjkipjFsKG4w&e=.

As most users do not precisely know the structure and/or the content of databases, their queries do not exactly reflect their information needs. The database management system (DBMS) may interact with users and use their feedback on the returned results to learn the information needs behind their queries. Current query interfaces assume that users do not learn and modify the way they express their information needs in the form of queries during their interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS and their learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do not modify their strategies, they cannot discover the information needs behind users’ queries effectively. We model the interaction between the user and the DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in the form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users’ strategies and proves that it improves the effectiveness of answering queries, stochastically speaking. We propose two efficient implementations of this method over large relational databases. Our extensive empirical studies over real-world query workloads indicate that our algorithms are efficient and effective.

A constant-rate multi-mode system is a hybrid system that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent constant rates. We introduce and study a stochastic extension of a constant-rate multi-mode system where the dynamics is specified by mode-dependent compactly supported probability distributions over a set of constant rate vectors. The almost-sure reachability problem for stochastic multi-mode systems is to decide whether for all ε > 0 and for all pairs of start and target states in a path-connected and bounded safety set there exists a control strategy that almost-surely steers the system from the start state to the ε-neighborhood of the target state without leaving the safety set. We prove a necessary and sufficient condition to decide almost-sure reachability and, using this condition, we show that almost-sure reachability can be decided in polynomial time. Our algorithm can be used as a path-following algorithm in combination with off-the-shelf path-planning algorithms to make a robot with noisy low-level controllers follow a path with arbitrary precision.

Most users do not know the structure and content of databases or concepts such as schema or formal query languages sufficiently well to express their information needs precisely in form of queries. They may convey their intents via usable but inherently ambiguous query interfaces, such as keyword or natural language queries, which are open to numerous interpretations. Thus, it is very challenging for a database management system (DBMS) to understand and satisfy the intents behind these queries. A useful source of information to decode the intent behind a query is the user feedback on the returned results, which may come in various ways, such as click-through information. To use this information, DBMS has to establish a trade-off between showing strongly reinforced answers, i.e., exploitation, and exploring never-before-shown or rarely shown answers to solicit user feedback on them, i.e. exploration. A DBMS that returns only positively reinforced results may always return a small subset of all relevant answers to a query. On the other hand, if a DBMS shows too many unseen answers to the user, it may discourage and disengage users as many such answers may not be relevant to the query. Moreover, users may learn more about the structure and content of the database and how to express intents as they submit queries and observe the returned results. Thus, they may modify the way they express intents over the course of their interactions with the DBMS.

As many users do not precisely know the structure and/or the content of databases, their queries do not exactly reflect their information needs. The database management systems (DBMS) may interact with users and leverage their feedback on the returned results to learn the information needs behind users' queries. Current query interfaces assume that users follow a fixed strategy of expressing their information needs, that is, the likelihood by which a user submits a query to express an information need remains unchanged during her interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS. We also show that users' learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do not modify their strategies, they cannot discover the information needs behind users' queries effectively. We model the interaction between users and DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users' strategies and prove that it improves the effectiveness of answering queries stochastically speaking. We analyze the challenges of efficient implementation of this method over large-scale relational databases and propose two efficient adaptations of this algorithm over large-scale relational databases. Our extensive empirical studies over real-world query workloads and large-scale relational databases indicate that our algorithms are efficient. Our empirical results also show that our proposed learning mechanism is more effective than the state-of-the-art query answering method.

In networked systems comprised of many agents, it is often required to reach a common operating point of all agents, termed the network consensus. We consider two iterative methods for reaching a ranking (ordering) consensus over a voter network, where the initial preference of every voter is of the form of a full ranking of candidates. The voters are allowed, one at a time and based on some random scheme, to change their votes to bring them “closer” to the opinions of selected subsets of peers. The first consensus method is based on changing votes one adjacent swap at a time; the second method is based on changing votes via averaging with the votes of peers, potentially leading to many adjacent swaps at a given time. For the first model, we characterize convergence points and conditions for convergence. For the second model, we prove convergence to a global ranking and derive the rate of convergence to this consensus.