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

Varun Jog

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

ResearcherUnclaimed source record
Information Theorymath.ITmath.PRmath.STStatistics TheoryMachine LearningSocial and Information NetworksDiscrete MathematicsApplicationseess.SPmath.COmath.GRmath.MGmath.OC

Catalog footprint

What is connected

9works
14topics
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

9 published item(s)

preprint2022arXiv

The Many Faces of Adversarial Risk

Adversarial risk quantifies the performance of classifiers on adversarially perturbed data. Numerous definitions of adversarial risk -- not all mathematically rigorous and differing subtly in the details -- have appeared in the literature. In this paper, we revisit these definitions, make them rigorous, and critically examine their similarities and differences. Our technical tools derive from optimal transport, robust statistics, functional analysis, and game theory. Our contributions include the following: generalizing Strassen's theorem to the unbalanced optimal transport setting with applications to adversarial classification with unequal priors; showing an equivalence between adversarial robustness and robust hypothesis testing with $\infty$-Wasserstein uncertainty sets; proving the existence of a pure Nash equilibrium in the two-player game between the adversary and the algorithm; and characterizing adversarial risk by the minimum Bayes error between a pair of distributions belonging to the $\infty$-Wasserstein uncertainty sets. Our results generalize and deepen recently discovered connections between optimal transport and adversarial robustness and reveal new connections to Choquet capacities and game theory.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Channels, Remote Estimation and Queueing Systems With A Utilization-Dependent Component: A Unifying Survey Of Recent Results

In this article, we survey the main models, techniques, concepts, and results centered on the design and performance evaluation of engineered systems that rely on a utilization-dependent component (UDC) whose operation may depend on its usage history or assigned workload. Specifically, we report on research themes concentrating on the characterization of the capacity of channels and the design with performance guarantees of remote estimation and queueing systems. Causes for the dependency of a UDC on past utilization include the use of replenishable energy sources to power the transmission of information among the sub-components of a networked system, and the assistance of a human operator for servicing a queue. Our analysis unveils the similarity of the UDC models typically adopted in each of the research themes, and it reveals the differences in the objectives and technical approaches employed. We also identify new challenges and future research directions inspired by the cross-pollination among the central concepts, techniques, and problem formulations of the research themes discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications

The $r$-parallel set of a measurable set $A \subseteq \mathbb R^d$ is the set of all points whose distance from $A$ is at most $r$. In this paper, we show that the surface area of an $r$-parallel set in $\mathbb R^d$ with volume at most $V$ is upper-bounded by $e^{Θ(d)}V/r$, whereas its Gaussian surface area is upper-bounded by $\max(e^{Θ(d)}, e^{Θ(d)}/r)$. We also derive a reverse form of the Brunn-Minkowski inequality for $r$-parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We apply our results to two problems in theoretical machine learning: (1) bounding the computational complexity of learning $r$-parallel sets under a Gaussian distribution; and (2) bounding the sample complexity of estimating robust risk, which is a notion of risk in the adversarial machine learning literature that is analogous to the Bayes risk in hypothesis testing.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process

We investigate centrality and root-inference properties in a class of growing random graphs known as sublinear preferential attachment trees. We show that a continuous time branching processes called the Crump-Mode-Jagers (CMJ) branching process is well-suited to analyze such random trees, and prove that almost surely, a unique terminal tree centroid emerges, having the property that it becomes more central than any other fixed vertex in the limit of the random growth process. Our result generalizes and extends previous work establishing persistent centrality in uniform and linear preferential attachment trees. We also show that centrality may be utilized to generate a finite-sized $1-ε$ confidence set for the root node, for any $ε> 0$ in a certain subclass of sublinear preferential attachment trees.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Geometric Analysis of the AWGN channel with a $(σ, ρ)$-Power Constraint

In this paper, we consider the AWGN channel with a power constraint called the $(σ, ρ)$-power constraint, which is motivated by energy harvesting communication systems. Given a codeword, the constraint imposes a limit of $σ+ k ρ$ on the total power of any $k\geq 1$ consecutive transmitted symbols. Such a channel has infinite memory and evaluating its exact capacity is a difficult task. Consequently, we establish an $n$-letter capacity expression and seek bounds for the same. We obtain a lower bound on capacity by considering the volume of ${\cal S}_n(σ, ρ) \subseteq \mathbb{R}^n$, which is the set of all length $n$ sequences satisfying the $(σ, ρ)$-power constraints. For a noise power of $ν$, we obtain an upper bound on capacity by considering the volume of ${\cal S}_n(σ, ρ) \oplus B_n(\sqrt{nν})$, which is the Minkowski sum of ${\cal S}_n(σ, ρ)$ and the $n$-dimensional Euclidean ball of radius $\sqrt{nν}$. We analyze this bound using a result from convex geometry known as Steiner's formula, which gives the volume of this Minkowski sum in terms of the intrinsic volumes of ${\cal S}_n(σ, ρ)$. We show that as the dimension $n$ increases, the logarithm of the sequence of intrinsic volumes of $\{{\cal S}_n(σ, ρ)\}$ converges to a limit function under an appropriate scaling. The upper bound on capacity is then expressed in terms of this limit function. We derive the asymptotic capacity in the low and high noise regime for the $(σ, ρ)$-power constrained AWGN channel, with strengthened results for the special case of $σ= 0$, which is the amplitude constrained AWGN channel.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence

We derive sharp thresholds for exact recovery of communities in a weighted stochastic block model, where observations are collected in the form of a weighted adjacency matrix, and the weight of each edge is generated independently from a distribution determined by the community membership of its endpoints. Our main result, characterizing the precise boundary between success and failure of maximum likelihood estimation when edge weights are drawn from discrete distributions, involves the Renyi divergence of order $\frac{1}{2}$ between the distributions of within-community and between-community edges. When the Renyi divergence is above a certain threshold, meaning the edge distributions are sufficiently separated, maximum likelihood succeeds with probability tending to 1; when the Renyi divergence is below the threshold, maximum likelihood fails with probability bounded away from 0. In the language of graphical channels, the Renyi divergence pinpoints the information-theoretic capacity of discrete graphical channels with binary inputs. Our results generalize previously established thresholds derived specifically for unweighted block models, and support an important natural intuition relating the intrinsic hardness of community estimation to the problem of edge classification. Along the way, we establish a general relationship between the Renyi divergence and the probability of success of the maximum likelihood estimator for arbitrary edge weight distributions. Finally, we discuss consequences of our bounds for the related problems of censored block models and submatrix localization, which may be seen as special cases of the framework developed in our paper.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On model misspecification and KL separation for Gaussian graphical models

We establish bounds on the KL divergence between two multivariate Gaussian distributions in terms of the Hamming distance between the edge sets of the corresponding graphical models. We show that the KL divergence is bounded below by a constant when the graphs differ by at least one edge; this is essentially the tightest possible bound, since classes of graphs exist for which the edge discrepancy increases but the KL divergence remains bounded above by a constant. As a natural corollary to our KL lower bound, we also establish a sample size requirement for correct model selection via maximum likelihood estimation. Our results rigorize the notion that it is essential to estimate the edge structure of a Gaussian graphical model accurately in order to approximate the true distribution to close precision.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Persistence of centrality in random growing trees

We investigate properties of node centrality in random growing tree models. We focus on a measure of centrality that computes the maximum subtree size of the tree rooted at each node, with the most central node being the tree centroid. For random trees grown according to a preferential attachment model, a uniform attachment model, or a diffusion processes over a regular tree, we prove that a single node persists as the tree centroid after a finite number of steps, with probability 1. Furthermore, this persistence property generalizes to the top $K \ge 1$ nodes with respect to the same centrality measure. We also establish necessary and sufficient conditions for the size of an initial seed graph required to ensure persistence of a particular node with probability $1-ε$, as a function of $ε$: In the case of preferential and uniform attachment models, we derive bounds for the size of an initial hub constructed around the special node. In the case of a diffusion process over a regular tree, we derive bounds for the radius of an initial ball centered around the special node. Our necessary and sufficient conditions match up to constant factors for preferential attachment and diffusion tree models.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Entropy Power Inequality and Mrs. Gerber's Lemma for Abelian Groups of Order 2^n

Shannon's Entropy Power Inequality can be viewed as characterizing the minimum differential entropy achievable by the sum of two independent random variables with fixed differential entropies. The entropy power inequality has played a key role in resolving a number of problems in information theory. It is therefore interesting to examine the existence of a similar inequality for discrete random variables. In this paper we obtain an entropy power inequality for random variables taking values in an abelian group of order 2^n, i.e. for such a group G we explicitly characterize the function f_G(x,y) giving the minimum entropy of the sum of two independent G-valued random variables with respective entropies x and y. Random variables achieving the extremum in this inequality are thus the analogs of Gaussians in this case, and these are also determined. It turns out that f_G(x,y) is convex in x for fixed y and, by symmetry, convex in y for fixed x. This is a generalization to abelian groups of order 2^n of the result known as Mrs. Gerber's Lemma.

0 citations0 reviewsNo code linkedOpen access