Gábor Lugosi

We consider the problem of structure recovery in a graphical model of a tree where some variables are latent. Specifically, we focus on the Gaussian case, which can be reformulated as a well-studied problem: recovering a semi-labeled tree from a distance metric. We introduce randomized procedures that achieve query complexity of optimal order. Additionally, we provide statistical analysis for scenarios where the tree distances are noisy. The Gaussian setting can be extended to other situations, including the binary case and non-paranormal distributions.

A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertices. In such graphs, paths with increasing time-stamps indicate the propagation of information. We determine a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. The results reveal that temporal connectivity appears at a significantly larger edge density than simple connectivity of the underlying random geometric graph. This is in contrast with Erdős–Rényi random graphs in which the thresholds for temporal connectivity and simple connectivity are of the same order of magnitude. Our results hold for a family of ‘soft’ random geometric graphs as well as the standard random geometric graph.

We study a random recursive tree model featuring complete redirection called the random friend tree and introduced by Saramäki and Kaski (2004). Vertices are attached sequentially, one by one, by selecting an existing target vertex and connecting to one of its neighbours (or friends), chosen uniformly at random. This model has interesting emergent properties, such as a highly skewed degree sequence. In contrast to the preferential attachment model, these emergent phenomena stem from a local rather than a global attachment mechanism. The structure of the resulting tree is also strikingly different from both the preferential attachment tree and the uniform random recursive tree: every edge is incident to a macro‐hub of asymptotically linear degree, and with high probability all but at most vertices in a tree of size are leaves. We prove various results on the neighbourhood of fixed vertices and edges, and we study macroscopic properties such as the diameter and the degree distribution, providing insights into the overall structure of the tree. We also present a number of open questions on this model and related models.

Motivated by the study of random temporal networks, we introduce a class of random trees that we coin uniform temporal trees . A uniform temporal tree is obtained by assigning independent uniform labels to the edges of a rooted complete infinite ‐ary tree and keeping only those vertices for which the path from the root to the vertex has decreasing edge labels. The ‐percolated uniform temporal tree, denoted by , is obtained similarly, with the additional constraint that the edge labels on each path are all below . We study several properties of these trees, including their size, height, the typical depth of a vertex, and degree distribution. In particular, we establish a limit law for the size of which states that converges in distribution to an random variable as . For the height , we prove that converges to in probability. Uniform temporal trees show some remarkable similarities to uniform random recursive trees.

A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertices. In such graphs, paths with increasing time stamps indicate the propagation of information. We determine a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. The results reveal that temporal connectivity appears at a significantly larger edge density than simple connectivity of the underlying random geometric graph. This is in contrast with Erdős-Rényi random graphs in which the thresholds for temporal connectivity and simple connectivity are of the same order of magnitude. Our results hold for a family of "soft" random geometric graphs as well as the standard random geometric graph.

We consider a repeated newsvendor problem in which the inventory manager has no prior information about the demand and can access only censored/sales data. In analogy to multiarmed bandit problems, the manager needs to simultaneously “explore” and “exploit” with inventory decisions in order to minimize the cumulative cost. Our goal is to understand the hardness of the problem disentangled from any probabilistic assumptions on the demand sequence—importantly, independence or time stationarity—and, correspondingly, to develop policies that perform well with respect to the regret criterion. We design a cost estimator that is tailored to the special structure of the censoring problem, and we show that, if coupled with the classic exponentially weighted forecaster, it achieves optimal scaling of the expected regret (up to logarithmic factors) with respect to both the number of time periods and available actions. This result also leads to two important insights: the benefit from “information stalking” as well as the cost of censoring are both negligible, at least in terms of the regret. We demonstrate the flexibility of our technique by combining it with the fixed share forecaster to provide strong guarantees in terms of tracking regret, a powerful notion of regret that uses a large class of time-varying action sequences as benchmark. Numerical experiments suggest that the resulting policy outperforms existing policies (that are tailored to or facilitated by time stationarity) on nonstationary demand models with time-varying noise, trend, and seasonality components. Finally, we consider the “combinatorial” version of the repeated newsvendor problem, that is, single-warehouse, multiretailer inventory management of a perishable product. We extend the proposed approach so that, again, it achieves near-optimal performance in terms of the regret. Funding: G. Lugosi was supported by the Spanish Ministry of Economy, Industry and Competitiveness [Grant MTM2015-67304-P (AEI/FEDER, UE)]. M. G. Markakis was supported by the Spanish Ministry of Economy and Competitiveness [Grant ECO2016-75905-R (AEI/FEDER, UE)] and a Juan de la Cierva fellowship as well as the Spanish Ministry of Science and Innovation through a Ramón y Cajal fellowship. G. Neu was supported by the UPFellows Fellowship (Marie Curie COFUND program) [Grant 600387]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoo.2022.0017 .