Chain-of-thought (CoT) reasoning applies to complex tasks with multiple intermediate steps, a key feature of large language models. Recent studies have revealed CoT as a composition of in-context filtering and learning. This paper proposes a unified framework for CoT optimization that exploits the nested problem structure to formulate training as multilevel optimization. Each intermediate reasoning step is a distinct optimization level. We develop an epigraph-based multilevel optimization (EMO) method to iteratively find the optimal solution for this class of problems. Experiments using GPT-2 show that the proposed EMO achieves the lowest generalization errors across all intermediate steps compared to state-of-the-art, highlighting the importance of nested optimization approaches for CoT reasoning.

Global climate change is redefining our understanding of how diseases spread. In Sri Lanka, vector-borne diseases such as dengue fever historically surged during the monsoon seasons when temperatures were high enough for mosquito eggs to hatch. Unfortunately, due to rising temperatures and more erratic rainfall patterns, mosquito eggs can now hatch year-round making outbreaks increasingly unpredictable, leading to an alarming rise in hospitalizations and deaths. More data is needed to adapt our response to these diseases in an increasingly warmer world. In the contemporary landscape, a wealth of disease information is available, yet accessibility remains limited due to unstructured data formats such as PDFs. Therefore, converting unstructured disease reports into structured formats is necessary for effectively leveraging data. This paper introduces a comprehensive framework for collecting unstructured disease reports and transforming them into analyzable formats. By creating separate models tailored to each data format, we can ensure accuracy compared to general models. These straightforward models enhance accessibility and empower other researchers to use our tools. The returned structured data can then be harnessed for analysis, statistical purposes, and informing evidence-based public health interventions, thus facilitating more informed decision-making in healthcare. We deploy this framework to produce geospatial data for Sri Lanka and Brazil for many different conditions and align these data with satellite environmental data, providing for the first time a structured, aligned powerful dataset for disease modeling.

The global expansion of the dengue belt, driven by climate change and increased urbanization, has led to a significant rise in dengue cases worldwide (1). Early warning systems (EWS) coupled with prompt public health response mechanisms are crucial in mitigating dengue-related morbidity and mortality globally. In Sri Lanka, dengue transmission occurs year-round with two peaks correlating to the southwest monsoon from May to September and the northeast monsoon from October to January (2). The presence of multiple dengue virus serotypes (DENV1–4) complicates epidemiological patterns, as sequential infections with different serotypes can increase the risk of severe disease manifestations detected by surveillance systems (3). Understanding and integrating these virological dynamics, vector dynamics, and real-time surveillance data are essential for developing effective EWS and targeted public health interventions. We propose the use of Graph Neural Networks (GNNs) as an EWS. Using Earth observational data from NASA’s global satellites and dengue incidence data from Sri Lanka’s Ministry of Health, we developed traditional and graph-based EWS to forecast dengue cases across Sri Lanka’s 25 districts between 2013 and 2022. We demonstrate empirically that GNNs incorporating spatiotemporal relations significantly outperform traditional EWS models such as Autoregressive Integrated Moving Average (ARIMA), Random Forest, and Long Short-Term Memory (LSTM). Our source code is available on GitHub.

Differential privacy (DP) is a key tool in privacy-preserving data analysis. Yet it remains challenging for non-privacy-experts to prove the DP of their algorithms. We propose a methodology for domain experts with limited data privacy background to empirically estimate the privacy of an arbitrary mechanism. Our Eureka moment is a new link— which we prove—between the problems of DP parameter-estimation and Bayes optimal classifiers in ML, which we believe can be of independent interest. Our estimator uses this link to achieve two desirable properties: (1) black-box, i.e., it does not require knowledge of the underlying mechanism, and (2) it has a theoretically-proven accuracy, depending on the underlying classifier used, allowing plug-and-play use of different classifiers.More concretely, motivated by the impossibility of the above task for unrestricted input domains (which we prove), we introduce a natural, application-inspired relaxation of DP which we term relative DP. Intuitively, relative DP defines a mechanism's privacy relative to an input set$\mathcal{T}$, circumventing the above impossibility when $\mathcal{T}$ is finite. Importantly, it preserves the key intuitive privacy guarantee of DP while enjoying a number of desirable DP properties—scalability, composition, and robustness to post-processing. We then devise a black-box poly-time (ε, δ)-relative DP estimator for any poly-size $\mathcal{T}$— the first privacy estimator to support mechanisms with large output spaces while having tight accuracy bounds. As a result of independent interest, we generalize our theory to develop the first Distributional Differential Privacy (DDP) estimator.We benchmark our estimator in a proof-of-concept implementation. First, using kNN as the classifier we show that our method (1) produces a tight, analytically computed (ε,δ)-DP trade-off of low-dimensional Laplace and Gaussian mechanisms—the first to do so, (2) accurately estimates the privacy spectrum of DDP mechanisms, and (3) can verify a DP mechanism's implementations, e.g., Sparse Vector Technique, Noisy Histogram, and Noisy max. Our implementation and experiments demonstrate the potential of our framework, and highlight its computational bottlenecks in estimating DP, e.g., in terms of the size of δ and the data dimensionality. Our second, neural-network-based instantiation makes a first step in showing that our method can be extended to mechanisms with high-dimensional outputs.

We present efficient algorithms to learn the parameters governing the dynamics of networked agents, given equilibrium steady state data. A key feature of our methods is the ability to learn without seeing the dynamics, using only the steady states. A key to the efficiency of our approach is the use of mean-field approximations to tune the parameters within a nonlinear least squares (NLS) framework. Our results on real networks demonstrate the accuracy of our approach in two ways. Using the learned parameters, we can: (i) Recover more accurate estimates of the true steady states when the observed steady states are noisy. (ii) Predict evolution to new equilibrium steady states after perturbations to the network topology.

Treatment interventions are usually targeted to improve a specific outcome on as elected group of patients who are eligible to receive the treatment. The success of such treatments is determined by the post-intervention treatment effect on the population under consideration. There are cases when the treatment group contains multiple categories of eligible populations, with various effects, especially when the study’s criteria are loosely defined. I n such s tudies (non-targeted trials) non-eligible subjects may be treated, producing heterogeneous treatment effects within the treated group. Inferring the effectiveness of the treatment under this scenario is difficult since the average treatment effect on the treated is a combination of multiple effect levels. This can bias the resulting conclusion of the causal studies. We propose an end-to-end framework based on matching and unsupervised clustering for extracting population sub-groups based on their effect levels. We demonstrate our methods on a real-world healthcare application, highlighting the value of subpopulation analysis for recovering multiple effect groups.

Complex care management (CCM) or hot spotting programs identify and manage high-need/high-cost patients, improving long-term health quality and medical costs. Typically, physicians refer patients to CCM. Despite strict guidelines to ensure that eligible patients are placed in appropriate programs, such a provider-based approach is limited by provider-capacity and the narrow view of a patient that a provider sees. We propose an ML workflow to augment the provider-based approach, that can flag patients who are suited to CCM. Our predictor uses a global view of a patient’s entire history across multiple providers and time to identify high-risk individuals from among all the individuals in a matter of seconds. On a monthly basis, we evaluate our predictions against physician referrals. In the test dataset, 41% of the top-500 highest risk individuals found by our model were referred to CCM by a physician at some point in the 6-month window following our prediction (top-500 is a parameter that can be set to match the CCM program’s capacity). Of those who were not referred in the 6-month window, 30% were referred at some time in their trajectory. The remaining false positives had a greater than 95% similarity when compared to true positive physician referrals in terms of cost profiles (both prior to referral and after referral) and patient profile. This remarkable similarity suggests that our machine learning predictor can identify new candidates for complex care management and/or predict referrals before a physician has an opportunity to do so.

GraphQL is a query language for APIs and a runtime for executing those queries, fetching the requested data from existing microservices, REST APIs, databases, or other sources. Its expressiveness and its flexibility have made it an attractive candidate for API providers in many industries, especially through the web. A major drawback to blindly servicing a client’s query in GraphQL is that the cost of a query can be unexpectedly large, creating computation and resource overload for the provider, and API rate-limit overages and infrastructure overload for the client. To mitigate these drawbacks, it is necessary to efficiently estimate the cost of a query before executing it. Estimating query cost is challenging, because GraphQL queries have a nested structure, GraphQL APIs follow different design conventions, and the underlying data sources are hidden. Estimates based on worst-case static query analysis have had limited success because they tend to grossly overestimate cost. We propose a machine-learning approach to efficiently and accurately estimate the query cost. We also demonstrate the power of this approach by testing it on query-response data from publicly available commercial APIs. Our framework is efficient and predicts query costs with high accuracy, consistently outperforming the static analysis by a large margin.

We study nonlinear dynamics on complex networks. Each vertex i has a state xi which evolves according to a networked dynamics to a steady-state xi*. We develop fundamental tools to learn the true steady-state of a small part of the network, without knowing the full network. A naive approach and the current state-of-the-art is to follow the dynamics of the observed partial network to local equilibrium. This dramatically fails to extract the true steady state. We use a mean-field approach to map the dynamics of the unseen part of the network to a single node, which allows us to recover accurate estimates of steady-state on as few as 5 observed vertices in domains ranging from ecology to social networks to gene regulation. Incomplete networks are the norm in practice, and we offer new ways to think about nonlinear dynamics when only sparse information is available.

Inferring topological characteristics of complex networks from observed data is critical to understand the dynamical behavior of networked systems, ranging from the Internet and the World Wide Web to biological networks and social networks. Prior studies usually focus on the structure-based estimation to infer network sizes, degree distributions, average degrees, and more. Little effort attempted to estimate the specific degree of each vertex from a sampled induced graph, which prevents us from measuring the lethality of nodes in protein networks and influencers in social networks. The current approaches dramatically fail for a tiny sampled induced graph and require a specific sampling method and a large sample size. These approaches neglect information of the vertex state, representing the dynamical behavior of the networked system, such as the biomass of species or expression of a gene, which is useful for degree estimation. We fill this gap by developing a framework to infer individual vertex degrees using both information of the sampled topology and vertex state. We combine the mean-field theory with combinatorial optimization to learn vertex degrees. Experimental results on real networks with a variety of dynamics demonstrate that our framework can produce reliable degree estimates and dramatically improve existing link prediction methods by replacing the sampled degrees with our estimated degrees.

We define the intrinsic scale at which a network begins to reveal its identity as the scale at which subgraphs in the network (created by a random walk) are distinguishable from similar sized subgraphs in a perturbed copy of the network. We conduct an extensive study of intrinsic scale for several networks, ranging from structured (e.g. road networks) to ad-hoc and unstructured (e.g. crowd sourced information networks), to biological. We find: (a) The intrinsic scale is surprisingly small (7-20 vertices), even though the networks are many orders of magnitude larger. (b) The intrinsic scale quantifies "structure" in a network - networks which are explicitly constructed for specific tasks have smaller intrinsic scale. (c) The structure at different scales can be fragile (easy to disrupt) or robust.

We examine a machine learning approach for deriving insights from observational healthcare data in order to improve public health. Our goal is to simultaneously identify patient subpopulations with differing health risks and find the distinct risk factors or determinants associated with each subpopulation. Here, we develop a supervised Gaussian Mixture Model (GMM) approach for subpopulation modeling that combines GMMs with L1-logistic regression. We demonstrate the approach on an analysis of high cost drivers of Medicaid expenditures for inpatient stays associated with Newborn, Pregnancy, and Circulatory Systems diagnostic categories. These conditions were chosen because they had the highest total inpatient expenditures in New York State (NYS) in 2016. When compared with state-of-the-art learning methods (random forests, boosting, deep learning), our approach provides comparable prediction performance but also extracts insightful explanations of the subpopulation structure and risk factors within each subpopulation. Sequentially applying unsupervised learning methods and then applying logistic regression fails to yield equally meaningful results: the unsupervised subpopulations are homogeneous and moderately predictable, while some of our subpopulations are highly predictable with easy-to-identify drivers of cost. Focusing on newborns, we unveil subpopulations indicative of the landscape of healthcare in NYS: about 90% of the discharges are healthy New York City babies and about 1% are costly complex cases. Subpopulations indicate regional disparities: for example newborns from Central, Southern and Western NY are of higher risk for high-cost stays associated with substance abuse. The results indicate the promise of the approach for future population health studies based on electronic health care records.

Direct democracy, where each voter casts one vote, fails when the average voter competence falls below 50%. This happens in noisy settings when voters have limited information. Representative democracy, where voters choose representatives to vote, can be an elixir in both these situations. We introduce a mathematical model for studying representative democracy, in particular understanding the parameters of a representative democracy that gives maximum decision making capability. Our main result states that under general and natural conditions, for fixed voting cost, the optimal number of representatives is linear; for polynomial cost, the optimal number of representatives is logarithmic.

This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that element-wise sparsifies the data, retaining only a few of its entries. Our new algorithm independently samples the data using probabilities that depend on both squares ($\ell_2$ sampling) and absolute values ($\ell_1$ sampling) of the entries. We prove that this hybrid algorithm ($i$) achieves a near-PCA reconstruction of the data, and ($ii$) recovers sparse principal components of the data, from a sketch formed by a sublinear sample size. Hybrid-($\ell_1,\ell_2$) inherits the $\ell_2$-ability to sample the important elements, as well as the regularization properties of $\ell_1$ sampling, and maintains strictly better quality than either $\ell_1$ or $\ell_2$ on their own. Extensive experimental results on synthetic, image, text, biological, and financial data show that not only are we able to recover PCA and sparse PCA from incomplete data, but we can speed up such computations significantly using our sparse sketch .

We study a natural problem: Given a small piece of a large parent network, is it possible to identify the parent network? We approach this problem from two perspectives. First, using several “sophisticated” or “classical” network features that have been developed over decades of social network study. These features measure aggregate properties of the network and have been found to take on distinctive values for different types of network, at the large scale. By using these classical features within a standard machine learning framework, we show that one can identify large parent networks from small (even 8-node) subgraphs. Second, we present a novel adjacency matrix embedding technique which converts the small piece of the network into an image and, within a deep learning framework, we are able to obtain prediction accuracies upward of 80%, which is comparable to or slightly better than the performance from classical features. Our approach provides a new tool for topology-based prediction which may be of interest in other network settings. Our approach is plug and play, and can be used by non-domain experts. It is an appealing alternative to the often arduous task of creating domain specific features using domain expertise.

Principal components analysis~(PCA) is the optimal linear encoder of data. Sparse linear encoders (e.g., sparse PCA) produce more interpretable features that can promote better generalization. (\rn{1}) Given a level of sparsity, what is the best approximation to PCA? (\rn{2}) Are there efficient algorithms which can achieve this optimal combinatorial tradeoff? We answer both questions by providing the first polynomial-time algorithms to construct \emph{optimal} sparse linear auto-encoders; additionally, we demonstrate the performance of our algorithms on real data.

We provide fast algorithms for overconstrained $\ell_p$ regression and related problems: for an $n\times d$ input matrix $A$ and vector $b\in\mathbb{R}^n$, in $O(nd\log n)$ time we reduce the problem $\min_{x\in\mathbb{R}^d} \|Ax-b\|_p$ to the same problem with input matrix $\tilde A$ of dimension $s \times d$ and corresponding $\tilde b$ of dimension $s\times 1$. Here, $\tilde A$ and $\tilde b$ are a coreset for the problem, consisting of sampled and rescaled rows of $A$ and $b$; and $s$ is independent of $n$ and polynomial in $d$. Our results improve on the best previous algorithms when $n\gg d$ for all $p\in [1,\infty)$ except $p=2$; in particular, they improve the $O(nd^{1.376+})$ running time of Sohler and Woodruff [Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 755--764 ] for $p=1$, which uses asymptotically fast matrix multiplication, and the $O(nd^5\log n)$ time of Dasgupta et al. [SIAM J. Comput., 38 (2009), pp. 2060--2078] for general $p$, which uses ellipsoidal rounding. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general $\ell_p$ problems. To complement this theory, we provide a detailed empirical evaluation of implementations of our algorithms for $p=1$, comparing them with several related algorithms. Among other things, our empirical results clearly show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for $\ell_p$ spaces and, for $p=1$, a fast subspace embedding of independent interest that we call the Fast Cauchy transform: a distribution over matrices $\Pi: \mathbb{R}^n\mapsto \mathbb{R}^{O(d\log d)}$, found obliviously to $A$, that approximately preserves the $\ell_1$ norms, that is, with large probability, simultaneously for all $x$, $\|Ax\|_1 \approx \|\Pi Ax\|_1$, with distortion $O(d^{2+\eta} )$, for an arbitrarily small constant $\eta>0$; and, moreover, $\Pi A$ can be computed in $O(nd\log d)$ time. The techniques underlying our Fast Cauchy transform include Fast Johnson--Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.

Our reliance on networked, collectively built information is a vulnerability when the quality or reliability of this information is poor. Wikipedia, one such collectively built information source, is often our first stop for information on all kinds of topics; its quality has stood up to many tests, and it prides itself on having a “neutral point of view.” Enforcement of neutrality is in the hands of comparatively few, powerful administrators. In this article, we document that a surprisingly large number of editors change their behavior and begin focusing more on a particular controversial topic once they are promoted to administrator status. The conscious and unconscious biases of these few, but powerful, administrators may be shaping the information on many of the most sensitive topics on Wikipedia; some may even be explicitly infiltrating the ranks of administrators in order to promote their own points of view. In addition, we ask whether administrators who change their behavior in this suspicious manner can be identified in advance. Neither prior history nor vote counts during an administrator’s election are useful in doing so, but we find that an alternative measure, which gives more weight to influential voters, can successfully reject these suspicious candidates. This second result has important implications for how we harness collective intelligence: even if wisdom exists in a collective opinion (like a vote), that signal can be lost unless we carefully distinguish the true expert voter from the noisy or manipulative voter.

We give two provably accurate feature-selection techniques for the linear SVM. The algorithms run in deterministic and randomized time respectively. Our algorithms can be used in an unsupervised or supervised setting. The supervised approach is based on sampling features from support vectors. We prove that the margin in the feature space is preserved to within ε-relative error of the margin in the full feature space in the worst-case. In the unsupervised setting, we also provide worst-case guarantees of the radius of the minimum enclosing ball, thereby ensuring comparable generalization as in the full feature space and resolving an open problem posed in Dasgupta et al. We present extensive experiments on real-world datasets to support our theory and to demonstrate that our methods are competitive and often better than prior state-of-the-art, for which there are no known provable guarantees.

We study the relationship between the level of chatter on a social medium (like Twitter) and the level of the observed actions related to the chatter. For example, in a disaster, how does relief-donation chatter on Twitter correlate with the dollar amount received? One hypothesis is that a fraction of those who act will also tweet about it, which implies linear scaling, action ∝ chatter. On the other hand, if there is a contagion effect (those who tweet about donation incite others to donate) and these incited donors tend to be "quiet" and not broadcast their actions, then we expect superlinear scaling,

We study how well one can recover sparse principal componentsof a data matrix using a sketch formed from a few of its elements. We show that for a wide class of optimization problems,if the sketch is close (in the spectral norm) to the original datamatrix, then one can recover a near optimal solution to the optimizationproblem by using the sketch. In particular, we use this approach toobtain sparse principal components and show that for \math{m} data pointsin \math{n} dimensions,\math{O(\epsilon^{-2}\tilde k\max{m,n})} elements gives an\math{\epsilon}-additive approximation to the sparse PCA problem(\math{\tilde k} is the stable rank of the data matrix).We demonstrate our algorithms extensivelyon image, text, biological and financial data.The results show that not only are we able to recover the sparse PCAs from the incomplete data, but by using our sparse sketch, the running timedrops by a factor of five or more.

Selecting a good column (or row) subset of massive data matrices has found many applications in data analysis and machine learning. We propose a new adaptive sampling algorithm that can be used to improve any relative-error column selection algorithm. Our algorithm delivers a tighter theoretical bound on the approximation error which we also demonstrate empirically using two well known relative-error column subset selection algorithms. Our experimental results on synthetic and real-world data show that our algorithm outperforms non-adaptive sampling as well as prior adaptive sampling approaches.

We develop a fast algorithm for computing the “SVD-truncated” regularized solution to the least-squares problem: minx∥Ax - b∥2. Let Akof rank k be the best rank k matrix computed via the SVD of A. Then, the SVD-truncated regularized solution is: xk= Ak†b. If A is m × n, then, it takes O(mnmin{m, n}) time to compute xkusing the SVD of A. We give an approximation algorithm for xkwhich constructs a rank k approximation Ãkand computes x̃k= Ãk†in roughly O(nnz(A)k log n) time. Our algorithm uses a randomized variant of the subspace iteration method. We show that, with high probability: ∥Ax̃k- b∥2≈ ∥Axk- b∥2and ∥xk- x̃k∥2≈ 0.

We consider low-rank reconstruction of a matrix using a subset of its columns and present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our results are (i) the use of fast approximate SVD-like decompositions for column-based matrix reconstruction, and (ii) two deterministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse representation theorem for decompositions of the identity that appeared in [J. D. Batson, D. A. Spielman, and N. Srivastava, Twice-Ramanujan sparsifiers, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 2009, pp. 255--262].

Let X be a data matrix of rank ρ, whose rows represent n points in d -dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique that is precomputed and can be applied to any input matrix X . We prove that, with high probability, the margin and minimum enclosing ball in the feature space are preserved to within ϵ-relative error, ensuring comparable generalization as in the original space in the case of classification. For regression, we show that the margin is preserved to ϵ-relative error with high probability. We present extensive experiments with real and synthetic data to support our theory.

We describe the design of Instructor Rating Markets (IRMs) where human participants interact through intelligent automated market-makers in order to provide dynamic collective feedback to instructors on the progress of their classes. The markets are among the first to enable the empirical study of prediction markets where traders can affect the very outcomes they are trading on. More than 200 students across the Rensselaer campus participated in markets for ten classes in the Fall 2010 semester. In this paper, we describe how we designed these markets in order to elicit useful information, and analyze data from the deployment. We show that market prices convey useful information on future instructor ratings and contain significantly more information than do past ratings. The bulk of useful information contained in the price of a particular class is provided by students who are in that class, showing that the markets are serving to disseminate insider information. At the same time, we find little evidence of attempted manipulation by raters. The markets are also a laboratory for comparing different market designs and the resulting price dynamics, and we show how they can be used to compare market making algorithms.

Let X be a data matrix of rank ρ, representing n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique which is precomputed and can be applied to any input matrix X. We prove that, with high probability, the margin and minimum enclosing ball in the feature space are preserved to within ε-relative error, ensuring comparable generalization as in the original space. We present extensive experiments with real and synthetic data to support our theory.

We examine whether the prominence of individuals in different social networks is determined by their position in their local network or by how the community to which they belong relates to other communities. To this end, we introduce two new measures of centrality, both based on communities in the network: local and community centrality. Community centrality is a novel concept that we introduce to describe how central one's community is within the whole network. We introduce an algorithm to estimate the distance between communities and use it to find the centrality of communities. Using data from several social networks, we show that community centrality is able to capture the importance of communities in the whole network. We then conduct a detailed study of different social networks and determine how various global measures of prominence relate to structural centrality measures. Our measures deconstruct global centrality along local and community dimensions. In some cases, prominence is determined almost exclusively by local information, while in others a mix of local and community centrality matters. Our methodology is a step toward understanding of the processes that contribute to an actor's prominence in a network.

Our reliance on networked, collectively built information is a vulnerability when the quality or reliability of this information is poor. Wikipedia, one such collectively built information source, is often our first stop for information on all kinds of topics; its quality has stood up to many tests, and it prides itself on having a "Neutral Point of View". Enforcement of neutrality is in the hands of comparatively few, powerful administrators. We find a surprisingly large number of editors who change their behavior and begin focusing more on a particular controversial topic once they are promoted to administrator status. The conscious and unconscious biases of these few, but powerful, administrators may be shaping the information on many of the most sensitive topics on Wikipedia; some may even be explicitly infiltrating the ranks of administrators in order to promote their own points of view. Neither prior history nor vote counts during an administrator's election can identify those editors most likely to change their behavior in this suspicious manner. We find that an alternative measure, which gives more weight to influential voters, can successfully reject these suspicious candidates. This has important implications for how we harness collective intelligence: even if wisdom exists in a collective opinion (like a vote), that signal can be lost unless we carefully distinguish the true expert voter from the noisy or manipulative voter.

We provide fast algorithms for overconstrained ℓp regression and related problems: for an n × d input matrix A and vector b ∊ ℝn, in O(nd log n) time we reduce the problem minx ∊ ℝd ‖Ax − b‖p to the same problem with input matrix A of dimension s × d and corresponding b of dimension s × 1. Here, Ã and are a coreset for the problem, consisting of sampled and rescaled rows of A and b; and s is independent of n and polynomial in d. Our results improve on the best previous algorithms when n ≫ d, for all p ∊ [1, ∞) except p = 2; in particular, they improve the O(nd1.376+) running time of Sohler and Woodruff (STOC, 2011) for p = 1, that uses asymptotically fast matrix multiplication, and the O(nd5 log n) time of Dasgupta et al. (SICOMP, 2009) for general p, that uses ellipsoidal rounding. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general ℓp problems. To complement this theory, we provide a detailed empirical evaluation of implementations of our algorithms for p = 1, comparing them with several related algorithms. Among other things, our empirical results clearly show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for ℓp spaces and, for p = 1, a fast subspace embedding of independent interest that we call the Fast Cauchy Transform: a matrix Π : ℝn → ℝO(d log d), found obliviously to A, that approximately preserves the ℓ1 norms: that is, ‖Ax‖1 ≈ ‖ΠAx‖1, for all x, with distortion O(d2 + η log d), for an arbitrarily small constant η > 0; and, moreover, ΠA can be computed in O(nd log d) time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.

We study the (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low-order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results.

We study feature selection for k-means clustering. Although the literature contains many methods with good empirical performance, algorithms with provable theoretical behavior have only recently been developed. Unfortunately, these algorithms are randomized and fail with, say, a constant probability. We present the first deterministic feature selection algorithm for k-means clustering with relative error guarantees. At the heart of our algorithm lies a deterministic method for decompositions of the identity and a structural result which quantifies some of the tradeoffs in dimensionality reduction.

We present a new algorithm called iHypR for computing prominence of actors in social networks of collaborations. Our algorithm builds on the assumption that prominent actors collaborate on prominent objects, and prominent objects are naturally grouped into prominent clusters or groups (hyperedges in a graph). iHypR makes use of the relationships between actors, objects, and hyperedges to compute a global prominence score for the actors in the network. We do not assume the hyperedges are given in advance. Hyperedges computed by our method can perform as well or even better than “true” hyperedges. Our algorithm is customized for networks of collaborations, but it is generally applicable without further tuning. We show, through extensive experimentation with three real-life data sets and multiple external measures of prominence, that our algorithm outperforms existing well-known algorithms. Our work is the first to offer such an extensive evaluation. We show that unlike most existing algorithms, the performance is robust across multiple measures of performance. Further, we give a detailed study of the sensitivity of our algorithm to different data sets and the design choices within the algorithm that a user may wish to change. Our article illustrates the various trade-offs that must be considered in computing prominence in collaborative social networks.

Discussion based websites like Epinions.com and Slashdot.com allow users to identify both friends and foes. Such networks are called Signed Social Networks and mining communities of like-minded users from these networks has potential value. We extend existing community detection algorithms that work only on unsigned networks to be applicable to signed networks. In particular, we develop a spectral approach augmented with iterative optimization. We use our algorithms to study both communities and structural balance. Our results indicate that modularity based communities are distinct from structurally balanced communities.

We present a two step procedure to identify long lasting communities, or evolutions, in social networks. First, we use axiomatic foundations to `rigorously' establish shorter, strongly-connected evolutions. In the second step, we use heuristics to combine these shorter evolutions to form longer evolutions. We apply the procedure on data generated from two networks - the DBLP co-authorship database and Live Journal blog data. We visually validate our algorithms by examining the topic evolution of the associated documents. Our results demonstrate that our algorithms, based solely on structural properties of the data (who interacts with whom), are able to track thematic trends in the literature. We then use a machine learning framework to identify the structural features of the early stages of a community's evolution are most useful for predicting the lifetime of the community. We find that (in order) size, intensity and stability are the most important features.

We present novel indexing and searching schemes for semantic graphs based on the notion of the i.degrees of a node. The i.degrees allow searches performed on the graph to use “type” and connection information, rather than textual labels, to identify nodes. We aim to identify a network graph (fragment) within a large semantic graph (database). A fragment may represent incomplete information that a researcher has collected on a sub-network of interest. While textual labels might be available, they are highly unreliable, and cannot be used for identification of hidden networks. Since this problem comes from the classically NP-hard problem of identifying isomorphic subgraphs, our algorithms are heuristic.

Ensuring sufficient liquidity is one of the key challenges for designers of prediction markets. Variants of the logarithmic market scoring rule (LMSR) have emerged as the standard. LMSR market makers are loss-making in general and need to be subsidized. Proposed variants, including liquidity sensitive market makers, suffer from an inability to react rapidly to jumps in population beliefs. In this paper we propose a Bayesian Market Maker for binary outcome (or continuous 0-1) markets that learns from the informational content of trades. By sacrificing the guarantee of bounded loss, the Bayesian Market Maker can simultaneously offer: (1) significantly lower expected loss at the same level of liquidity, and, (2) rapid convergence when there is a jump in the underlying true value of the security. We present extensive evaluations of the algorithm in experiments with intelligent trading agents and in human subject experiments. Our investigation also elucidates some general properties of market makers in prediction markets. In particular, there is an inherent tradeoff between adaptability to market shocks and convergence during market equilibrium.

In recent years, new studies concentrating on analyzing user personality and finding credible content in social media have become quite popular. Most such work augments features from textual content with features representing the user's social ties and the tie strength. Social ties are crucial in understanding the network the people are a part of. However, textual content is extremely useful in understanding topics discussed and the personality of the individual. We bring a new dimension to this type of analysis with methods to compute the type of ties individuals have and the strength of the ties in each dimension. We present a new genre of behavioral features that are able to capture the "function" of a specific relationship without the help of textual features. Our novel features are based on the statistical properties of communication patterns between individuals such as reciprocity, assortativity, attention and latency. We introduce a new methodology for determining how such features can be compared to textual features, and show, using Twitter data, that our features can be used to capture contextual information present in textual features very accurately. Conversely, we also demonstrate how textual features can be used to determine social attributes related to an individual.

Collaborative media such as wikis have become enormously successful venues for information creation. Articles accrue information through the asynchronous editing of users who arrive both seeking information and possibly able to contribute information. Most articles stabilize to high-quality, trusted sources of information representing the collective wisdom of all the users who edited the article. We propose a model for information growth which relies on two main observations: (i) as an article’s quality improves, it attracts visitors at a faster rate (a rich-get-richer phenomenon); and, simultaneously, (ii) the chances that a new visitor will improve the article drops (there is only so much that can be said about a particular topic). Our model is able to reproduce many features of the edit dynamics observed on Wikipedia; in particular, it captures the observed rise in the edit rate, followed by 1/ t decay. Despite differences in the media, we also document similar features in the comment rates for a segment of the LiveJournal blogosphere.

We consider low-rank reconstruction of a matrix using a subset of its columns and we present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our results are: (i) the use of fast approximate SVD-like decompositions for column-based matrix reconstruction, and (ii) two deterministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse representation theorem for decompositions of the identity that appeared in [1].

Principal Components Analysis~(PCA) is often used as a feature extraction procedure. Given a matrix $X \in \mathbb{R}^{n \times d}$, whose rows represent $n$ data points with respect to $d$ features, the top $k$ right singular vectors of $X$ (the so-called \textit{eigenfeatures}), are arbitrary linear combinations of all available features. The eigenfeatures are very useful in data analysis, including the regularization of linear regression. Enforcing sparsity on the eigenfeatures, i.e., forcing them to be linear combinations of only a \textit{small} number of actual features (as opposed to all available features), can promote better generalization error and improve the interpretability of the eigenfeatures. We present deterministic and randomized algorithms that construct such sparse eigenfeatures while \emph{provably} achieving in-sample performance comparable to regularized linear regression. Our algorithms are relatively simple and practically efficient, and we demonstrate their performance on several data sets.

IAM ABOUT to start my second year of service as the Editor-in-Chief (EiC) of the IEEE TRANSACTIONS ON NEURAL NETWORKS (TNN). Needless to say, my first year as the EiC has been full of excitement and challenges. Transitioning this position from my predecessor to me went very smoothly during the months of September 2009 to January 2010. During the past year, we have accumulated 50+ Associate Editors (AEs) handling roughly 600 new submissions (not counting resubmissions and revised submissions). With the help of these AEs and my predecessor, I was quickly able to learn to do my job, and as such, the transition had very few glitches. The easy part of my job is checking whether a submission is in compliance with our guidelines and where it is within the scope of the TRANSACTIONS, before it is assigned to an AE for handling. The difficult part of my job has been dealing with some papers with three or more reviewers, all of whom agreed to review them but for some reason failed to respond to repeated automatic-review reminders. AEs handling these papers have to take several extra steps to remind reviewers through phone calls or e-mails, look for replacement reviewers, or review the papers themselves. Most authors have been appreciative of the work of the AEs and reviewers, and they accept our decisions without a problem. The backlog of papers has been kept short over the last year. We have maintained an organized printing and paperacceptance schedule, with papers typically printed in the journal within 2‐3 months of acceptance. Our page budget has been kept constant in the past few years (roughly 2060 pages per year), and we expect to hold the same page count for next year.

Computational science is placing new demands on optimization algorithms as the size of data sets and the computational complexity of scientific models continue to increase. As these complex models have many local minima, evolutionary algorithms (EAs) are very useful for quickly finding optimal solutions in these challenging search spaces. In addition to the complex search spaces involved, calculating the objective function can be extremely demanding computationally. Because of this, distributed computation is a necessity. In order to address these computational demands, top-end distributed computing systems are surpassing hundreds of thousands of computing hosts; and as in the case of Internet based volunteer computing systems, they can also be highly heterogeneous and faulty. This work examines asynchronous strategies for distributed EAs using simulated computing environments. Results show that asynchronous EAs can scale to hundreds of thousands of computing hosts while being highly resilient to heterogeneous and faulty computing environments, something not possible for traditional distributed EAs which require synchronization. While the simulation not only provides insight as to how asynchronous EAs perform on distributed computing environments with different latencies and heterogeneity, it also serves as a sanity check because live distributed systems require problems with high computation to communication ratios and traditional benchmark problems cannot be used for meaningful analysis due to their short computation times.

Trust is an important yet complex and little understood aspect of the dyadic relationship between two entities. Trust plays an important role in the formation of coalitions in social networks and in determining how high value of information flows through the network. We present algorithmically quantifiable measures of trust based on communication behavior. We propose that trust results in likely communication behaviors which are statistically different from random communications; detecting these trust-like behaviors allows us to develop a quantitative measure of who trusts whom in the network. We develop algorithms to efficiently compute such behavioral trust and validate these measures on the Twitter network.

We define a data dependent permutation complexity for a hypothesis set \math{\hset}, which is similar to a Rademacher complexity or maximum discrepancy. The permutation complexity is based like the maximum discrepancy on (dependent) sampling. We prove a uniform bound on the generalization error, as well as a concentration result which means that the permutation estimate can be efficiently estimated.

We give a permutation approach to validation (estimation of out-sample error). One typical use of validation is model selection. We establish the legitimacy of the proposed permutation complexity by proving a uniform bound on the out-sample error, similar to a VC-style bound. We extensively demonstrate this approach experimentally on synthetic data, standard data sets from the UCI-repository, and a novel diffusion data set. The out-of-sample error estimates are comparable to cross validation (CV); yet, the method is more efficient and robust, being less susceptible to overfitting during model selection.

Wikis and blogs have become enormously successful media for collaborative information creation. Articles and posts accrue information through the asynchronous editing of users who arrive both seeking information and possibly able to contribute information. Most articles stabilize to high quality, trusted sources of information representing the collective wisdom of all the users who edited the article. We propose a model for information growth which relies on two main observations: (i) as an article's quality improves, it attracts visitors at a faster rate (a rich get richer phenomenon); and, simultaneously, (ii) the chances that a new visitor will improve the article drops (there is only so much that can be said about a particular topic). Our model is able to reproduce many features of the edit dynamics observed on Wikipedia and on blogs collected from LiveJournal; in particular, it captures the observed rise in the edit rate, followed by 1/t decay.

We study information diffusion in real-life and synthetic dynamic networks, using well known threshold and cascade models of diffusion. Our test-bed is the communication network of the LiveJournal Blogosphere. We observe that the dynamic and static versions of the Blogograph, yield very different behaviors of the diffusion. It was earlier discovered that the communication dynamics of the Blogograph is quite high - over 60% of the links each week were not present in the previous week, though the size of the node set is relatively stable. Our models of the Blogograph evolution reproduce general stable statistics of the real-life Blogograph. We discover that the diffusion footprint on our models closely approximate the diffusion footprint of the real-life dynamic network.

Volunteer computing grids offer significant computing power at relatively low cost to researchers, while at the same time generating public interest in different scientific projects. However, in order to be used effectively, their heterogeneity, volatility and restrictive computing models must be overcome. As these computing grids are open, incorrect or malicious results must also be handled. This paper examines extending the BOINC volunteer computing framework to allow for asynchronous global optimization as applied to scientific computing problems. The asynchronous optimization method used is resilient to faults and the heterogeneous nature of volunteer computing grids, while allowing scalability to tens of thousands of hosts. A work verification strategy that does not require the validation of every result is presented. This is shown to be able to effectively reduce the need for verification done to less than 30% of the reported results, without degrading the performance of the asynchronous search methods. An asynchronous version of particle swarm optimization (APSO) is presented and com- pared to previously used asynchronous genetic search (AGS) using the MilkyWay@Home BOINC computing project. Both search methods are shown to scale to MilkyWay@Home's current user base, over 75,000 heterogeneous and volatile hosts, something not possible for traditional optimization methods. APSO is shown to provide faster convergence to optimal results while being less sensitive to its search parameters. The verification strategy presented is shown to be effective for both AGS and APSO.

Accent identification has grown over the past decade. There has been decent success when a priori knowledge about the accents is available. A typical approach entails detection of certain syllables and phonemes, which in turn requires phoneme-based models. Recently, Gaussian Mixture Models (GMMs) have been used as an unsupervised alternative to these phoneme-based models, but they have had limited success unless they used a priori knowledge. We studied extensions of the GMMs using ensemble learning (i. e. bagging and Boosting).

This work experimentally examines different notions of stability of the behavior of individuals and groups in a network of blogs. Our experiments are conducted on data collected from LiveJournal. All stability notions aim to locate stable behavior within an individual's area, which is defined in a variety of manners. Our experiments confirm an earlier observation of the highly dynamic nature of the network. Roughly 70% of the communication of a typical week was not observed in the previous week. Depending on the definition of stability and area used, we find small, but highly stable, sets of individuals with stable behavior in the network.

In this work, we present the software library graphOnt. The purpose of this library is to automate the process of dynamically extracting ldquointerestingrdquo graphs from semantic networks. Instructions on the extraction are fed into the library via an ontological language specification custom built for this application. A set of SPARQL queries are used to define vertices and edges in the constructed graph. Extracted graphs are returned using the JUNG framework, which offers many algorithmic and visualization options. This work allows a set of individuals analyzing the same semantic network to extract and analyze dynamically created graphs using sophisticated, specific algorithmic tools without needing to manually construct classical graphs from the data.

In this paper, we present a novel model for the evolution dynamics of social networks which supports public communication (communication which is visible to all members of the network). Though our model is general, it is particularly applicable to blog-networks, which is the domain we use for testing. We use a directed graph, the blogograph, to represent the communication activity in the Blogosphere. Our model is based on three fundamental principles for describing evolution dynamics in social networks.

We study the profit-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. The sequential decision problem is hard to solve because the state space is a function. We demonstrate that the belief state is well approximated by a Gaussian distribution. We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the first optimal sequential market-making algorithm in an established model. The algorithm leads to a surprising insight: an optimal monopolist can provide more liquidity than perfectly competitive market-makers in periods of extreme uncertainty, because a monopolist is willing to absorb initial losses in order to learn a new valuation rapidly so she can extract higher profits later.

We present a machine learning approach to discover the agent dynamics that drives the evolution of the social groups in a community. We set up the problem by introducing an agent-based hidden Markov model for the agent dynamics: an agent's actions are determined by micro-laws. Nonetheless, We learn the agent dynamics from the observed communications without knowing state transitions. Our approach is to identify the appropriate micro-laws corresponding to an identification of the appropriate parameters in the model. The model identification problem is then formulated as a mixed optimization problem. To solve the problem, we develop a multistage learning process for determining the group structure, the group evolution, and the micro-laws of a community based on the observed set of communications among actors, without knowing the semantic contents. Finally, to test the quality of our approximations and the feasibility of the approach, we present the results of extensive experiments on synthetic data as well as the results on real communities, such as Enron email and Movie newsgroups. Insight into agent dynamics helps us understand the driving forces behind social evolution.

We present a modeling laboratory, Virtual Laboratory for the Simulation and Analysis of Social Group Evolution (ViSAGE), that views the organization of human communities and the experience of individuals in a community as contingent upon on the dynamic properties, or micro-laws , of social groups. The laboratory facilitates the theorization and validation of these properties through an iterative research processes that involves (1) forward simulation experiments, which are used to formalize dynamic group properties, (2) reverse engineering from real data on how the parameters are distributed among individual actors in the community, and (3) grounded research, such as participant observation, that follows specific activities of real actors in a community and determines if, or how well, the micro-laws describe the way choices are made in real world, local settings. In this article we report on the design of ViSAGE. We first give some background to the model. Next we detail each component. We then describe a set of simulation experiments that we used to further design and clarify ViSAGE as a tool for studying emergent properties/phenomena in social networks.

We address the sensor selection problem which arises in tracking and localization applications. In sensor selection, the goal is to select a small number of sensors whose measurements provide a good estimate of a target's state (such as location). We focus on the bounded uncertainty sensing model where the target is a point in thed-dimensional Euclidean space. Each sensor measurement corresponds to a convex polyhedral subset of the space. The measurements are merged by intersecting corresponding sets. We show that, on the plane, four sensors are sufficient (and sometimes necessary) to obtain an estimate whose area is at most twice the area of the best possible estimate (obtained by intersecting all measurements). We also extend this result to arbitrary dimensions and show that a constant number of sensors suffice for a constant factor approximation in arbitrary dimensions. Both constants depend on the dimensionality of the space but are independent of the total number of sensors in the network.

In the oblivious path selection problem, each packet in the network independently chooses a path, which is an important property if the routing algorithm is to be independent of the traffic distribution. The quality of the paths is determined by the congestion, C, the maximum number of paths crossing an edge, and the dilation, D, the maximum path length. So far, the oblivious algorithms studied in the literature have focused on minimizing the congestion while ignoring the dilation. An open problem is to give algorithms for networks in which C and D can be controlled simultaneously. Here, we solve this problem for the d-dimensional mesh. We present an oblivious algorithm for which C and D are both within O(d2) of the optimal. The algorithm uses randomization and we show that the number of random bits required per packet is within O(d) of the minimum number of random bits required by any algorithm that obtains the same congestion. For a fixed d, our algorithm is asymptotically optimal.

This paper presents GMLE1, a generic and distributed framework for maximum likelihood evaluation. GMLE is currently being applied to astroinformatics for determining the shape of star streams in the Milky Way galaxy, and to particle physics in a search for theory-predicted but yet unobserved sub-atomic particles. GMLE is designed to enable parallel and distributed executions on platforms ranging from supercomputers and high-performance homogeneous computing clusters to more heterogeneous Grid and Internet computing environments. GMLE's modular implementation seperates concerns of developers into the distributed evaluation frameworks, scientific models, and search methods, which interact through a simple API. This allows us to compare the benefits and drawbacks of different scientific models using different search methods on different computing environments. We describe and compare the performance of two implementations of the GMLE framework: an MPI version that more effectively uses homogeneous environments such as IBM's BlueGene, and a SALSA version that more easily accommodates heterogeneous environments such as the Rensselaer Grid. We have shown GMLE to scale well in terms of computation as well as communication over a wide range of environments. We expect that scientific computing frameworks, such as GMLE, will help bridge the gap between scientists needing to analyze ever larger amounts of data and ever more complex distributed computing environments.

The power of social values that helps to surreptitiously shape or formulate our behavior patterns is not only inevitable, but also influential as the directions of our decision making can never seem to escape the impact of this hidden agent. Therefore, the search of such power agent can be validated through a machine learning approach that enables us to discover the agent dynamics in which drives the evolution of the social groups in a community. By doing so, we set up the problem by introducing a parameterized probabilistic model for the agent dynamics: the acts of an agent are determined by micro-laws with unknown parameters. Our approach is to identify the appropriate parameters in the model. To solve the problem, we develop heuristic expectation-maximization style algorithms for determining the micro-laws of a community based on either observed communication links between actors, or the observed evolution of social groups. We present the learning results from the synthetic data as well as the findings on real communities, e.g., Enron email and movie newsgroups.

We present an extended version of a software system SIGHTS (statistical identification of groups hidden in time and space), which can be used for the discovery, analysis, and knowledge visualization of social coalitions in communication networks such as Blog-networks. The evolution of social groups reflects information flow and social dynamics in social networks. Our system discovers such groups by analyzing communication patterns. The goal of SIGHTS is to be an assistant to an analyst in identifying relevant information. The functionality of SIGHTS includes: discovery of coalitions (clusters) and their leaders; finding hidden groups using communication persistence techniques; discovering hidden groups in communication streams; matching topics of the blogs and detecting sentiments; tracking the evolution of clusters; visualization of collections of individual clusters.

A packet-switching algorithm specifies the actions of the nodes in order to deliver packets in the network. A packet-switching algorithm is universal if it applies to any network topology and for any batch communication problem on the network. A long-standing open problem has concerned the existence of a universal packet-switching algorithm with near-optimal performance guarantees for the class of bufferless networks where the buffer size for packets in transit is zero. We give a positive answer to this question. In particular, we give a universal bufferless algorithm which is within a polylogarithmic factor from optimal for arbitrary batch problems: ${\cal T}=O\left({\cal T}^*\cdot \log^3(n+N)\right)$, where ${\cal T}$ is the packet delivery time of our algorithm, ${\cal T}^*$ is the optimal delivery time, n is the size of the network, and N is the number of packets. At the heart of our result is a new deterministic technique for constructing a universal bufferless algorithm by emulating a store-and-forward algorithm on a transformation of the network. The main idea is to replace packet buffering in the transformed network with packet circulation in regions of the original network. The cost of the emulation on the packet delivery time is proportional to the buffer sizes used by the store-and-forward algorithm. We obtain the advertised result by using a store-and-forward algorithm with logarithmic sized buffers. The resulting bufferless algorithm is constructive and can be implemented in a distributed way.

Boosting is a meta-learning algorithm which takes as input a set of classifiers and combines these classifiers to obtain a better classifier. We consider the combinatorial problem of efficiently and optimally boosting a pair of classifiers by reducing this problem to that of constructing the optimal linear separator for two sets of points in two dimensions. Specifically, let each point x element of R be assigned a weight W(x) > 0, where the weighting function can be an arbitrary positive function. We give efficient (low-order polynomial time) algorithms for constructing an optimal linear "separator" l defined as follows. Let Q be the set of points misclassified by l. Then, the weight of Q, defined as the sum of the weights of the points in Q, is minimized. If W(z) = 1 for all points, then the resulting separator minimizes (exactly) the misclassification error. Without an increase in computational complexity, our algorithm can be extended to output the leave-one-out error, an unbiased estimate of the expected performance of the resulting boosted classifier.

This paper focuses on the principled study of distance reconstruction for distance-based node localization. We address an important issue in node localization by showing that a highly incomplete set of inter-node distance measurements obtained in ad-hoc node deployments carries sufficient information for the accurate reconstruction of the missing distances, even in the presence of noise and sensor node failures. We provide an efficient and provably accurate algorithm for this reconstruction, and we show that the resulting error is bounded, decreasing at a rate that is inversely proportional to radicn, the square root of the number of nodes in the region of deployment. Although this result is applicable to many localization schemes, in this paper we illustrate its use in conjunction with the popular multidimensional scaling algorithm. Our analysis reveals valuable insights and key factors to consider during the sensor network setup phase, to improve the quality of the position estimates

We study oblivious routing in which the packet paths are constructed independently of each other. We give a simple oblivious routing algorithm for geometric networks in which the nodes are embedded in the Euclidean plane. In our algorithm, a packet path is constructed by first choosing a random intermediate node in the space between the source and destination, and then the packet is sent to its destination through the intermediate node. We analyze the performance of the algorithm in terms of the stretch and congestion of the resulting paths. We show that the stretch is constant, and the congestion is near optimal when the network paths can be chosen to be close to the geodesic lines that connect the end points of the paths. We give applications of our general result to the mesh topology and uniformly distributed disc graphs. Previous oblivious routing algorithms with near optimal congestion use many intermediate nodes and do not control the stretch.

We present new families of lower bounds for the price of the American put option on a dividend paying stock when the stock follows a log normal process and the option can be exercised continuously to a finite horizon T. By put call parity, these bounds can be easily converted to bounds on the price of the American call option on a dividend paying stock. By numerically optimizing these bounds, we obtain tighter bounds on the option price. Our methodology simultaneously furnishes us with an (exponential) exercise strategy. We provide an extensive experimental computation, comparing with convergent binomial tree pricing methods. Our bounds deliver an accuracy comparable to a 2000 step binomial tree, with a computational cost comparable to a 400 step binomial tree.

The MDD is defined as the maximum loss incurred from peak to bottom during a specified period of time. It is often preferred over some of the other risk measures because of the tight relationship between large drawdowns and fund redemptions. Also, a large drawdown can even indicate the start of a deterioration of an otherwise successful trading system, for example due to a market regime switch. Overall, the MDD is a very important risk measure. To be able to use it more insightfully, its analytical properties have to be understood. As a step towards this direction, we have presented in this article some analytic results that we have developed. We hope more and more results will come out from the research community analyzing this important measure.

In this paper we consider two important topics: density estimation and random variate generation. We present a framework that is easily implemented using the familiar multilayer neural network. First, we develop two new methods for density estimation, a stochastic method and a related deterministic method. Both methods are based on approximating the distribution function, the density being obtained by differentiation. In the second part of the paper, we develop new random number generation methods. Our methods do not suffer from some of the restrictions of existing methods in that they can be used to generate numbers from any density provided that certain smoothness conditions are satisfied. One of our methods is based on an observed inverse relationship between the density estimation process and random number generation. We present two variants of this method, a stochastic, and a deterministic version. We propose a second method that is based on a novel control formulation of the problem, where a "controller network" is trained to shape a given density into the desired density. We justify the use of all the methods that we propose by providing theoretical convergence results. In particular, we prove that the L(infinity) convergence to the true density for both the density estimation and random variate generation techniques occurs at a rate O((log log N/N)((1-epsilon)/2)) where N is the number of data points and epsilon can be made arbitrarily small for sufficiently smooth target densities. This bound is very close to the optimally achievable convergence rate under similar smoothness conditions. Also, for comparison, the (2) root mean square (rms) convergence rate of a positive kernel density estimator is O(N(-2/5)) when the optimal kernel width is used. We present numerical simulations to illustrate the performance of the proposed density estimation and random variate generation methods. In addition, we present an extended introduction and bibliography that serves as an overview and reference for the practitioner.

There are several phases that an emerging field goes through before it reaches maturity, and computational finance is no exception. There is usually a trigger for the birth of the field. In our case, new techniques such as neural networks, significant progress in computing technology, and the need for results that rely on more realistic assumptions inspired new researchers to revisit the traditional problems of finance, problems that have often been tackled by introducing simplifying assumptions in the past. The result has been a wealth of new approaches to these time-honored problems, with significant improvements in many cases.

We provide a self contained introduction to the risk neutral or martingale approach to the pricing of financial derivatives, while assuming no financial background. This approach to pricing provides a rich source of problems ideally suited to the application of Monte Carlo methods, thus forming a bridge between computational finance and some of the well developed tools available to engineers and scientists. We illustrate the power of the martingale approach by using it to develop the price of the European call option using only elementary methods and briefly discuss the pricing of the American put option as well as interest rate derivatives.

No-free-lunch theorems have shown that learning algorithms cannot be universally good. We show that no free funch exists for noise prediction as well. We show that when the noise is additive and the prior over target functions is uniform, a prior on the noise distribution cannot be updated, in the Bayesian sense, from any finite data set. We emphasize the importance of a prior over the target function in order to justify superior performance for learning systems.

Consider an algorithm whose time to convergence is unknown (because of some random element in the algorithm, such as a random initial weight choice for neural network training). Consider the following strategy. Run the algorithm for a specific time T. If it has not converged by time T, cut the run short and rerun it from the start (repeat the same strategy for every run). This so-called restart mechanism has been proposed by Fahlman (1988) in the context of backpropagation training. It is advantageous in problems that are prone to local minima or when there is a large variability in convergence time from run to run, and may lead to a speed-up in such cases. In this article, we analyze theoretically the restart mechanism, and obtain conditions on the probability density of the convergence time for which restart will improve the expected convergence time. We also derive the optimal restart time. We apply the derived formulas to several cases, including steepest-descent algorithms.

We show that with a uniform prior on models having the same training error, early stopping at some fixed training error above the training error minimum results in an increase in the expected generalization error.

We report new results about the impact of noise on information processing with application to financial markets. These results quantify the trade-off between the amount of data and the noise level in the data. They also provide estimates for the performance of a learning system in terms of the noise level. We use these results to derive a method for detecting the change in market volatility from period to period. We successfully apply these results to the four major foreign exchange markets. The results hold for linear as well as nonlinear learning models and algorithms and for different noise models.