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

Gábor Lugosi

Gábor Lugosi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.STStatistics TheoryMachine Learningmath.PRDiscrete Mathematicsmath.COMethodologyNetworking and Internet ArchitectureInformation Theorymath.ITSocial and Information Networks

Catalog footprint

What is connected

24works
11topics
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

24 published item(s)

preprint2026arXiv

Testing properties of trees in graphical models with covariance queries

We consider the problem of testing properties of graphs underlying high-dimensional graphical models. We adopt the model of covariance queries introduced by Lugosi, Truszkowski, Velona, and Zwiernik (2021). We study the case when the underlying graph is a tree. The main results of the paper show that, while reconstructing the entire tree may be costly, certain global structural properties can be tested efficiently. In particular, we design randomized tests for global structural properties that use a sub-quadratic number of queries. We develop testing procedures for several fundamental properties, including the number of leaves, the maximum degree, the typical distance, and the diameter of the tree. For each property, we obtain explicit query complexity bounds that depend on the target threshold and tolerance parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Archaeology of random recursive dags and Cooper-Frieze random networks

We study the problem of finding the root vertex in large growing networks. We prove that it is possible to construct confidence sets of size independent of the number of vertices in the network that contain the root vertex with high probability in various models of random networks. The models include uniform random recursive dags and uniform Cooper-Frieze random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Generalization Bounds via Convex Analysis

Since the celebrated works of Russo and Zou (2016,2019) and Xu and Raginsky (2017), it has been well known that the generalization error of supervised learning algorithms can be bounded in terms of the mutual information between their input and the output, given that the loss of any fixed hypothesis has a subgaussian tail. In this work, we generalize this result beyond the standard choice of Shannon's mutual information to measure the dependence between the input and the output. Our main result shows that it is indeed possible to replace the mutual information by any strongly convex function of the joint input-output distribution, with the subgaussianity condition on the losses replaced by a bound on an appropriately chosen norm capturing the geometry of the dependence measure. This allows us to derive a range of generalization bounds that are either entirely new or strengthen previously known ones. Examples include bounds stated in terms of $p$-norm divergences and the Wasserstein-2 distance, which are respectively applicable for heavy-tailed loss distributions and highly smooth loss functions. Our analysis is entirely based on elementary tools from convex analysis by tracking the growth of a potential function associated with the dependence measure and the loss function.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Benign Overfitting in Linear Regression

The phenomenon of benign overfitting is one of the key mysteries uncovered by deep learning methodology: deep neural networks seem to predict well, even with a perfect fit to noisy training data. Motivated by this phenomenon, we consider when a perfect fit to training data in linear regression is compatible with accurate prediction. We give a characterization of linear regression problems for which the minimum norm interpolating prediction rule has near-optimal prediction accuracy. The characterization is in terms of two notions of the effective rank of the data covariance. It shows that overparameterization is essential for benign overfitting in this setting: the number of directions in parameter space that are unimportant for prediction must significantly exceed the sample size. By studying examples of data covariance properties that this characterization shows are required for benign overfitting, we find an important role for finite-dimensional data: the accuracy of the minimum norm interpolating prediction rule approaches the best possible accuracy for a much narrower range of properties of the data distribution when the data lies in an infinite dimensional space versus when the data lies in a finite dimensional space whose dimension grows faster than the sample size.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Noise sensitivity of the top eigenvector of a Wigner matrix

We investigate the noise sensitivity of the top eigenvector of a Wigner matrix in the following sense. Let $v$ be the top eigenvector of an $N\times N$ Wigner matrix. Suppose that $k$ randomly chosen entries of the matrix are resampled, resulting in another realization of the Wigner matrix with top eigenvector $v^{[k]}$. We prove that, with high probability, when $k \ll N^{5/3-o(1)}$, then $v$ and $v^{[k]}$ are almost collinear and when $k\gg N^{5/3}$, then $v^{[k]}$ is almost orthogonal to $v$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Detecting positive correlations in a multivariate sample

We consider the problem of testing whether a correlation matrix of a multivariate normal population is the identity matrix. We focus on sparse classes of alternatives where only a few entries are nonzero and, in fact, positive. We derive a general lower bound applicable to various classes and study the performance of some near-optimal tests. We pay special attention to computational feasibility and construct near-optimal tests that can be computed efficiently. Finally, we apply our results to prove new lower bounds for the clique number of high-dimensional random geometric graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Empirical risk minimization for heavy-tailed losses

The purpose of this paper is to discuss empirical risk minimization when the losses are not necessarily bounded and may have a distribution with heavy tails. In such situations, usual empirical averages may fail to provide reliable estimates and empirical risk minimization may provide large excess risk. However, some robust mean estimators proposed in the literature may be used to replace empirical means. In this paper, we investigate empirical risk minimization based on a robust estimate proposed by Catoni. We develop performance bounds based on chaining arguments tailored to Catoni's mean estimator.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Finding Adam in random growing trees

We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of $K$ vertices, such that, with probability at least $1-ε$, the first vertex is in this set. We show that for any $ε$, there exist such algorithms with $K$ independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of $K$ as a function of $ε$. In the uniform attachment case we show that the optimal $K$ is subpolynomial in $1/ε$, and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best $K$ is polynomial in $1/ε$. We conclude the paper with several open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the measure of Voronoi cells

$n$ independent random points drawn from a density $f$ in $R^d$ define a random Voronoi partition. We study the measure of a typical cell of the partition. We prove that the asymptotic distribution of the probability measure of the cell centered at a point $x \in R^d$ is independent of $x$ and the density $f$. We determine all moments of the asymptotic distribution and show that the distribution becomes more concentrated as $d$ becomes large. In particular, we show that the variance converges to zero exponentially fast in $d$. %We also study the measure of the largest cell of the partition. %{\red We also obtain a density-free bound for the rate of convergence of the diameter of a typical Voronoi cell.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Robust estimation of U-statistics

An important part of the legacy of Evarist Giné is his fundamental contributions to our understanding of $U$-statistics and $U$-processes. In this paper we discuss the estimation of the mean of multivariate functions in case of possibly heavy-tailed distributions. In such situations, reliable estimates of the mean cannot be obtained by usual $U$-statistics. We introduce a new estimator, based on the so-called median-of-means technique. We develop performance bounds for this new estimator that generalizes an estimate of Arcones and Giné (1993), showing that the new estimator performs, under minimal moment conditions, as well as classical $U$-statistics for bounded random variables. We discuss an application of this estimator to clustering.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Set estimation from reflected Brownian motion

We study the problem of estimating a compact set $S\subset \mathbb{R}^d$ from a trajectory of a reflected Brownian motion in $S$ with reflections on the boundary of $S$. We establish consistency and rates of convergence for various estimators of $S$ and its boundary. This problem has relevant applications in ecology in estimating the home range of an animal based on tracking data. There are a variety of studies on the habitat of animals that employ the notion of home range. This paper offers theoretical foundations for a new methodology that, under fairly unrestrictive shape assumptions, allows one to find flexible regions close to reality. The theoretical findings are illustrated on simulated and real data examples.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Connectivity of sparse Bluetooth networks

Consider a random geometric graph defined on $n$ vertices uniformly distributed in the $d$-dimensional unit torus. Two vertices are connected if their distance is less than a "visibility radius" $r_n$. We consider {\sl Bluetooth networks} that are locally sparsified random geometric graphs. Each vertex selects $c$ of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of $n^{-(1-δ)/d}$ for some $δ> 0$, then a constant value of $c$ is sufficient for the graph to be connected, with high probability. It suffices to take $c \ge \sqrt{(1+ε)/δ} + K$ for any positive $ε$ where $K$ is a constant depending on $d$ only. On the other hand, with $c\le \sqrt{(1-ε)/δ}$, the graph is disconnected, with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Prediction by Random-Walk Perturbation

We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(sqrt(n log N)) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(sqrt(n log N)) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Regret in Online Combinatorial Optimization

We address online linear optimization problems when the possible actions of the decision maker are represented by binary vectors. The regret of the decision maker is the difference between her realized loss and the best loss she would have achieved by picking, in hindsight, the best possible action. Our goal is to understand the magnitude of the best possible (minimax) regret. We study the problem under three different assumptions for the feedback the decision maker receives: full information, and the partial information models of the so-called "semi-bandit" and "bandit" problems. Combining the Mirror Descent algorithm and the INF (Implicitely Normalized Forecaster) strategy, we are able to prove optimal bounds for the semi-bandit case. We also recover the optimal bounds for the full information setting. In the bandit case we discuss existing results in light of a new lower bound, and suggest a conjecture on the optimal regret in that case. Finally we also prove that the standard exponentially weighted average forecaster is provably suboptimal in the setting of online combinatorial optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bandits with heavy tail

The stochastic multi-armed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper we examine the bandit problem under the weaker assumption that the distributions have moments of order 1+ε, for some $ε\in (0,1]$. Surprisingly, moments of order 2 (i.e., finite variance) are sufficient to obtain regret bounds of the same order as under sub-Gaussian reward distributions. In order to achieve such regret, we define sampling strategies based on refined estimators of the mean such as the truncated empirical mean, Catoni's M-estimator, and the median-of-means estimator. We also derive matching lower bounds that also show that the best achievable regret deteriorates when ε<1.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Detection of correlations

We consider the hypothesis testing problem of deciding whether an observed high-dimensional vector has independent normal components or, alternatively, if it has a small subset of correlated components. The correlated components may have a certain combinatorial structure known to the statistician. We establish upper and lower bounds for the worst-case (minimax) risk in terms of the size of the correlated subset, the level of correlation, and the structure of the class of possibly correlated sets. We show that some simple tests have near-optimal performance in many cases, while the generalized likelihood ratio test is suboptimal in some important cases.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Efficient Tracking of Large Classes of Experts

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different "base" expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular we provide a method that can transform any prediction algorithm $\A$ that is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency of $\A$ in the sense that it can be implemented with time and space complexity only $O(n^γ \ln n)$ times larger than that of $\A$, where $n$ is the time horizon and $γ\ge 0$ is a parameter of the algorithm. With $\A$ properly chosen, our algorithm achieves a regret bound of optimal order for $γ>0$, and only $O(\ln n)$ times larger than the optimal order for $γ=0$ for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimal $O(\ln n)$ regret rate with time complexity $O(n^{1+γ}\ln n)$ for any $γ\in (0,1)$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Connectivity threshold for Bluetooth graphs

We study the connectivity properties of random Bluetooth graphs that model certain "ad hoc" wireless networks. The graphs are obtained as "irrigation subgraphs" of the well-known random geometric graph model. There are two parameters that control the model: the radius $r$ that determines the "visible neighbors" of each node and the number of edges $c$ that each node is allowed to send to these. The randomness comes from the underlying distribution of data points in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters $r, c$ and completely characterize the connectivity threshold (in $c$) for values of $r$ close the critical value for connectivity in the underlying random geometric graph.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On combinatorial testing problems

We study a class of hypothesis testing problems in which, upon observing the realization of an $n$-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal distribution or, alternatively, whether there is a subset of the components belonging to a certain given class of sets whose elements have been ``contaminated,'' that is, have a mean different from zero. We establish some general conditions under which testing is possible and others under which testing is hopeless with a small risk. The combinatorial and geometric structure of the class of sets is shown to play a crucial role. The bounds are illustrated on various examples.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Ranking and empirical minimization of U-statistics

The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous statistical framework. The goal is to learn a ranking rule for deciding, among two instances, which one is "better," with minimum ranking risk. Since the natural estimates of the risk are of the form of a U-statistic, results of the theory of U-processes are required for investigating the consistency of empirical risk minimizers. We establish in particular a tail inequality for degenerate U-processes, and apply it for showing that fast rates of convergence may be achieved under specific noise assumptions, just like in classification. Convex risk minimization methods are also studied.

0 citations0 reviewsNo code linkedOpen access