BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Roberto I. Oliveira appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We present an alternative proof of Sanov's theorem for Polish spaces in the weak topology that follows via discretization arguments. We combine the simpler version of Sanov's Theorem for discrete finite spaces and well chosen finite discretizations of the Polish space. The main tool in our proof is an explicit control on the rate of convergence for the approximated measures.
We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted $n$-sized label-feature sample of at most $εn$ arbitrary outliers. We wish to estimate a $p$-dimensional parameter $b^*$ given such sample of a label-feature pair $(y,x)$ satisfying $y=\langle x,b^*\rangle+ξ$ with heavy-tailed $(x,ξ)$. We only assume $x$ is $L^4-L^2$ hypercontractive with constant $L>0$ and has covariance matrix $Σ$ with minimum eigenvalue $1/μ^2>0$ and bounded condition number $κ>0$. The noise $ξ$ can be arbitrarily dependent on $x$ and nonsymmetric as long as $ξx$ has finite covariance matrix $Ξ$. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on $(Σ,Ξ)$ nor the operator norm of $Ξ$. With probability at least $1-δ$, our proposed estimator attains the statistical rate $μ^2\VertΞ\Vert^{1/2}(\frac{p}{n}+\frac{\log(1/δ)}{n}+ε)^{1/2}$ and breakdown-point $ε\lesssim\frac{1}{L^4κ^2}$, both optimal in the $\ell_2$-norm, assuming the near-optimal minimum sample size $L^4κ^2(p\log p + \log(1/δ))\lesssim n$, up to a log factor. To the best of our knowledge, this is the first computationally tractable algorithm satisfying simultaneously all the mentioned properties. Our estimator is based on a two-stage Multiplicative Weight Update algorithm. The first stage estimates a descent direction $\hat v$ with respect to the (unknown) pre-conditioned inner product $\langleΣ(\cdot),\cdot\rangle$. The second stage estimate the descent direction $Σ\hat v$ with respect to the (known) inner product $\langle\cdot,\cdot\rangle$, without knowing nor estimating $Σ$.
We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are "sub-Gaussian"~even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to have been considered before in the non-asymptotic literature. Our proofs combine different ideas of potential independent interest: an adaptation of Talagrand's "generic chaining"~bound for sub-Gaussian processes; "localization"~ideas from the Statistical Learning literature; and the use of standard conditions in Optimization (metric regularity, Slater-type conditions) to control fluctuations of the feasible set.
We prove limit theorems for systems of interacting diffusions on sparse graphs. For example, we deduce a hydrodynamic limit and the propagation of chaos property for the stochastic Kuramoto model with interactions determined by Erdős-Rényi graphs with constant mean degree. The limiting object is related to a potentially infinite system of SDEs defined over a Galton-Watson tree. Our theorems apply more generally, when the sequence of graphs ("decorated" with edge and vertex parameters) converges in the local weak sense. Our main technical result is a locality estimate bounding the influence of far-away diffusions on one another. We also numerically explore the emergence of synchronization phenomena on Galton-Watson random trees, observing rich phase transitions from synchronized to desynchronized activity among nodes at different distances from the root.
The Holme-Kim random graph processes is a variant of the Barabasi-Albert scale-free graph that was designed to exhibit clustering. In this paper we show that whether the model does indeed exhibit clustering depends on how we define the clustering coefficient. In fact, we find that local clustering coefficient remains typically positive whereas global clustering tends to 0 at a slow rate. These and other results are proven via martingale techniques, such as Freedman's concentration inequality combined with a bootstrapping argument.
We study the problem of estimating the mean of a multivariatedistribution based on independent samples. The main result is the proof of existence of an estimator with a non-asymptotic sub-Gaussian performance for all distributions satisfying some mild moment assumptions.
We study a variable length Markov chain model associated with a group of stationary processes that share the same context tree but each process has potentially different conditional probabilities. We propose a new model selection and estimation method which is computationally efficient. We develop oracle and adaptivity inequalities, as well as model selection properties, that hold under continuity of the transition probabilities and polynomial $β$-mixing. In particular, model misspecification is allowed. These results are applied to interesting families of processes. For Markov processes, we obtain uniform rate of convergence for the estimation error of transition probabilities as well as perfect model selection results. For chains of infinite order with complete connections, we obtain explicit uniform rates of convergence on the estimation of conditional probabilities, which have an explicit dependence on the processes' continuity rates. Similar guarantees are also derived for renewal processes. Our results are shown to be applicable to discrete stochastic dynamic programming problems and to dynamic discrete choice models. We also apply our estimator to a linguistic study, based on recent work, by Galves et al (2012), of the rhythmic differences between Brazilian and European Portuguese.
Let $P$ be the transition matrix of a finite, irreducible and reversible Markov chain. We say the continuous time Markov chain $X$ has transition matrix $P$ and speed $λ$ if it jumps at rate $λ$ according to the matrix $P$. Fix $λ_X,λ_Y,λ_Z\geq 0$, then let $X,Y$ and $Z$ be independent Markov chains with transition matrix $P$ and speeds $λ_X,λ_Y$ and $λ_Z$ respectively, all started from the stationary distribution. What is the chance that $X$ and $Y$ meet before either of them collides with $Z$? For each choice of $λ_X,λ_Y$ and $λ_Z$ with $\max(λ_X,λ_Y)>0$, we prove a lower bound for this probability which is uniform over all transitive, irreducible and reversible chains. In the case that $λ_X=λ_Y=1$ and $λ_Z=0$ we prove a strengthening of our main theorem using a martingale argument. We provide an example showing the transitivity assumption cannot be removed for general $λ_X,λ_Y$ and $λ_Z$.
We discuss the possibilities and limitations of estimating the mean of a real-valued random variable from independent and identically distributed observations from a non-asymptotic point of view. In particular, we define estimators with a sub-Gaussian behavior even for certain heavy-tailed distributions. We also prove various impossibility results for mean estimators.
We study the relation between the performance of the randomized rumor spreading (push model) in a d-regular graph G and the performance of the same algorithm in the percolated graph G_p. We show that if the push model successfully broadcast the rumor within T rounds in the graph G then only (1 + ε)T rounds are needed to spread the rumor in the graph G_p when T = o(pd).