BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

James Sharpnack

James Sharpnack appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Machine Learningmath.STStatistics TheoryMethodologyInformation Theorymath.ITArtificial Intelligence

Catalog footprint

What is connected

14works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2022arXiv

On $L_2$-consistency of nearest neighbor matching

Biased sampling and missing data complicates statistical problems ranging from causal inference to reinforcement learning. We often correct for biased sampling of summary statistics with matching methods and importance weighting. In this paper, we study nearest neighbor matching (NNM), which makes estimates of population quantities from biased samples by substituting unobserved variables with their nearest neighbors in the biased sample. We show that NNM is $L_2$-consistent in the absence of smoothness and boundedness assumptions in finite dimensions. We discuss applications of NNM, outline the barriers to generalizing this work to separable metric spaces, and compare this result to inverse probability weighting.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms

The stochastic contextual bandit problem, which models the trade-off between exploration and exploitation, has many real applications, including recommender systems, online advertising and clinical trials. As many other machine learning algorithms, contextual bandit algorithms often have one or more hyper-parameters. As an example, in most optimal stochastic contextual bandit algorithms, there is an unknown exploration parameter which controls the trade-off between exploration and exploitation. A proper choice of the hyper-parameters is essential for contextual bandit algorithms to perform well. However, it is infeasible to use offline tuning methods to select hyper-parameters in contextual bandit environment since there is no pre-collected dataset and the decisions have to be made in real time. To tackle this problem, we first propose a two-layer bandit structure for auto tuning the exploration parameter and further generalize it to the Syndicated Bandits framework which can learn multiple hyper-parameters dynamically in contextual bandit environment. We derive the regret bounds of our proposed Syndicated Bandits framework and show it can avoid its regret dependent exponentially in the number of hyper-parameters to be tuned. Moreover, it achieves optimal regret bounds under certain scenarios. Syndicated Bandits framework is general enough to handle the tuning tasks in many popular contextual bandit algorithms, such as LinUCB, LinTS, UCB-GLM, etc. Experiments on both synthetic and real datasets validate the effectiveness of our proposed framework.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Estimating Graphlet Statistics via Lifting

Exploratory analysis over network data is often limited by the ability to efficiently calculate graph statistics, which can provide a model-free understanding of the macroscopic properties of a network. We introduce a framework for estimating the graphlet count---the number of occurrences of a small subgraph motif (e.g. a wedge or a triangle) in the network. For massive graphs, where accessing the whole graph is not possible, the only viable algorithms are those that make a limited number of vertex neighborhood queries. We introduce a Monte Carlo sampling technique for graphlet counts, called {\em Lifting}, which can simultaneously sample all graphlets of size up to $k$ vertices for arbitrary $k$. This is the first graphlet sampling method that can provably sample every graphlet with positive probability and can sample graphlets of arbitrary size $k$. We outline variants of lifted graphlet counts, including the ordered, unordered, and shotgun estimators, random walk starts, and parallel vertex starts. We prove that our graphlet count updates are unbiased for the true graphlet count and have a controlled variance for all graphlets. We compare the experimental performance of lifted graphlet counts to the state-of-the art graphlet sampling procedures: Waddling and the pairwise subgraph random walk.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multiscale Non-stationary Stochastic Bandits

Classic contextual bandit algorithms for linear models, such as LinUCB, assume that the reward distribution for an arm is modeled by a stationary linear regression. When the linear regression model is non-stationary over time, the regret of LinUCB can scale linearly with time. In this paper, we propose a novel multiscale changepoint detection method for the non-stationary linear bandit problems, called Multiscale-LinUCB, which actively adapts to the changing environment. We also provide theoretical analysis of regret bound for Multiscale-LinUCB algorithm. Experimental results show that our proposed Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in non-stationary contextual environments.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximate Recovery in Changepoint Problems, from $\ell_2$ Estimation Error Rates

In the 1-dimensional multiple changepoint detection problem, we prove that any procedure with a fast enough $\ell_2$ error rate, in terms of its estimation of the underlying piecewise constant mean vector, automatically has an (approximate) changepoint screening property---specifically, each true jump in the underlying mean vector has an estimated jump nearby. We also show, again assuming only knowledge of the $\ell_2$ error rate, that a simple post-processing step can be used to eliminate spurious estimated changepoints, and thus delivers an (approximate) changepoint recovery property---specifically, in addition to the screening property described above, we are assured that each estimated jump has a true jump nearby. As a special case, we focus on the application of these results to the 1-dimensional fused lasso, i.e., 1-dimensional total variation denoising, and compare the implications with existing results from the literature. We also study extensions to related problems, such as changepoint detection over graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Trend Filtering on Graphs

We introduce a family of adaptive estimators on graphs, based on penalizing the $\ell_1$ norm of discrete graph differences. This generalizes the idea of trend filtering [Kim et al. (2009), Tibshirani (2014)], used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual $\ell_2$-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Detecting Anomalous Activity on Networks with the Graph Fourier Scan Statistic

We consider the problem of deciding, based on a single noisy measurement at each vertex of a given graph, whether the underlying unknown signal is constant over the graph or there exists a cluster of vertices with anomalous activation. This problem is relevant to several applications such as surveillance, disease outbreak detection, biomedical imaging, environmental monitoring, etc. Since the activations in these problems often tend to be localized to small groups of vertices in the graphs, we model such activity by a class of signals that are supported over a (possibly disconnected) cluster with low cut size relative to its size. We analyze the corresponding generalized likelihood ratio (GLR) statistics and relate it to the problem of finding a sparsest cut in the graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the graph Fourier scan statistic, and analyze its properties. We show how its performance as a testing procedure depends directly on the spectrum of the graph, and use this result to explicitly derive its asymptotic properties on a few significant graph topologies. Finally, we demonstrate theoretically and with simulations that the graph Fourier scan statistic can outperform naive testing procedures based on global averaging and vertex-wise thresholding. We also demonstrate the usefulness of the GFSS by analyzing groundwater Arsenic concentrations from a U.S. Geological Survey dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exact Asymptotics for the Scan Statistic and Fast Alternatives

We consider the problem of detecting a rectangle of activation in a grid of sensors in d-dimensions with noisy measurements. This has applications to massive surveillance projects and anomaly detection in large datasets in which one detects anomalously high measurements over rectangular regions, or more generally, blobs. Recently, the asymptotic distribution of a multiscale scan statistic was established in (Kabluchko, 2011) under the null hypothesis, using non-constant boundary crossing probabilities for locally-stationary Gaussian random fields derived in (Chan and Lai, 2006). Using a similar approach, we derive the exact asymptotic level and power of four variants of the scan statistic: an oracle scan that knows the dimensions of the activation rectangle; the multiscale scan statistic just mentioned; an adaptive variant; and an epsilon-net approximation to the latter, in the spirit of (Arias-Castro, 2005). This approximate scan runs in time near-linear in the size of the grid and achieves the same asymptotic power as the adaptive scan. We complement our theory with some numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Mean and variance estimation in high-dimensional heteroscedastic models with non-convex penalties

Despite its prevalence in statistical datasets, heteroscedasticity (non-constant sample variances) has been largely ignored in the high-dimensional statistics literature. Recently, studies have shown that the Lasso can accommodate heteroscedastic errors, with minor algorithmic modifications (Belloni et al., 2012; Gautier and Tsybakov, 2013). In this work, we study heteroscedastic regression with linear mean model and log-linear variances model with sparse high-dimensional parameters. In this work, we propose estimating variances in a post-Lasso fashion, which is followed by weighted-least squares mean estimation. These steps employ non-convex penalties as in Fan and Li (2001), which allows us to prove oracle properties for both post-Lasso variance and mean parameter estimates. We reinforce our theoretical findings with experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Recovering Graph-Structured Activations using Adaptive Compressive Measurements

We study the localization of a cluster of activated vertices in a graph, from adaptively designed compressive measurements. We propose a hierarchical partitioning of the graph that groups the activated vertices into few partitions, so that a top-down sensing procedure can identify these partitions, and hence the activations, using few measurements. By exploiting the cluster structure, we are able to provide localization guarantees at weaker signal to noise ratios than in the unstructured setting. We complement this performance guarantee with an information theoretic lower bound, providing a necessary signal-to-noise ratio for any algorithm to successfully localize the cluster. We verify our analysis with some simulations, demonstrating the practicality of our algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic

The detection of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. Beyond its wide applicability, graph structured anomaly detection serves as a case study in the difficulty of balancing computational complexity with statistical power. In this work, we develop from first principles the generalized likelihood ratio test for determining if there is a well connected region of activation over the vertices in the graph in Gaussian noise. Because this test is computationally infeasible, we provide a relaxation, called the Lovasz extended scan statistic (LESS) that uses submodularity to approximate the intractable generalized likelihood ratio. We demonstrate a connection between LESS and maximum a-posteriori inference in Markov random fields, which provides us with a poly-time algorithm for LESS. Using electrical network theory, we are able to control type 1 error for LESS and prove conditions under which LESS is risk consistent. Finally, we consider specific graph models, the torus, k-nearest neighbor graphs, and epsilon-random graphs. We show that on these graphs our results provide near-optimal performance by matching our results to known lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Changepoint Detection over Graphs with the Spectral Scan Statistic

We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two connected induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistics and relate it to the problem of finding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral scan statistic, and analyze its properties. We show how its performance as a testing procedure depends directly on the spectrum of the graph, and use this result to explicitly derive its asymptotic properties on few significant graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and $χ^2$ testing.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Detecting Activations over Graphs using Spanning Tree Wavelet Bases

We consider the detection of activations over graphs under Gaussian noise, where signals are piece-wise constant over the graph. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with proveable theoretical guarantees for general graph topologies. We cast this as a hypothesis testing problem, and first provide a universal necessary condition for asymptotic distinguishability of the null and alternative hypotheses. We then introduce the spanning tree wavelet basis over graphs, a localized basis that reflects the topology of the graph, and prove that for any spanning tree, this approach can distinguish null from alternative in a low signal-to-noise regime. Lastly, we improve on this result and show that using the uniform spanning tree in the basis construction yields a randomized test with stronger theoretical guarantees that in many cases matches our necessary conditions. Specifically, we obtain near-optimal performance in edge transitive graphs, $k$-nearest neighbor graphs, and $ε$-graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Variance function estimation in high-dimensions

We consider the high-dimensional heteroscedastic regression model, where the mean and the log variance are modeled as a linear combination of input variables. Existing literature on high-dimensional linear regres- sion models has largely ignored non-constant error variances, even though they commonly occur in a variety of applications ranging from biostatis- tics to finance. In this paper we study a class of non-convex penalized pseudolikelihood estimators for both the mean and variance parameters. We show that the Heteroscedastic Iterative Penalized Pseudolikelihood Optimizer (HIPPO) achieves the oracle property, that is, we prove that the rates of convergence are the same as if the true model was known. We demonstrate numerical properties of the procedure on a simulation study and real world data.

0 citations0 reviewsNo code linkedOpen access