Página 1 dos resultados de 115 itens digitais encontrados em 0.001 segundos

Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints

Nguyen, Nam; Needell, Deanna; Woolf, Tina
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/06/2014
Relevância na Pesquisa
16.59%
Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and covariance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which align with the theoretical analysis and demonstrate these improvements in several different settings.

Estimation of a k-monotone density, part 1: characterizations consistency, and minimax lower bounds

Balabdaoui, Fadoua; Wellner, Jon A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/09/2005
Relevância na Pesquisa
16.59%
Shape constrained densities are encountered in many nonparametric estimation problems. The classes of monotone or convex (and monotone) densities can be viewed as special cases of the classes of k-monotone densities. A density g is said to be k-monotone if its successive derivatives up to order k-2 are alternately negative or positive, with the k-2 derivative convex (or concave) according as k is even (or odd) respectively. g is simply nonincreasing if k=1. These classes of shape constrained densities bridge the gap between the classes of monotone (1-monotone) and convex decreasing (2-monotone) densities for which asymptotic results are known, and the class of completely monotone densities with k infinite. In this series of four papers we consider both (nonparametric) Maximum Likelihood estimators and Least Squares estimators of a k-monotone density. In this first part (part 1), we prove existence of the estimators and give characterizations. We also establish consistency properties, and show that the estimators are splines of order k (degree k-1) with simple knots. We further provide asymptotic minimax risk lower bounds for estimating a k-monotone density g_0 (x_0) and its derivatives g_0^{(j)}(x_0), for j=1, ..., k-1, at a fixed point x_0 under the assumption that the k-th derivative of g_0 at x_0 is non-zero.; Comment: 60 pages. Submitted to Annals of Statistics. See also http://www.stat.washington.edu/www/research/reports/2004/tr459.pdf http://www.stat.washington.edu/jaw/RESEARCH/PAPERS/available.html

Estimation of a $k$-monotone density: limit distribution theory and the spline connection

Balabdaoui, Fadoua; Wellner, Jon A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We study the asymptotic behavior of the Maximum Likelihood and Least Squares Estimators of a $k$-monotone density $g_0$ at a fixed point $x_0$ when $k>2$. We find that the $j$th derivative of the estimators at $x_0$ converges at the rate $n^{-(k-j)/(2k+1)}$ for $j=0,...,k-1$. The limiting distribution depends on an almost surely uniquely defined stochastic process $H_k$ that stays above (below) the $k$-fold integral of Brownian motion plus a deterministic drift when $k$ is even (odd). Both the MLE and LSE are known to be splines of degree $k-1$ with simple knots. Establishing the order of the random gap $\tau_n^+-\tau_n^-$, where $\tau_n^{\pm}$ denote two successive knots, is a key ingredient of the proof of the main results. We show that this ``gap problem'' can be solved if a conjecture about the upper bound on the error in a particular Hermite interpolation via odd-degree splines holds.; Comment: Published in at http://dx.doi.org/10.1214/009053607000000262 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Catastrophe Management and Inter-Reserve Distance for Marine Reserve Networks

Wagner, Liam; Ross, Joshua; Possingham, Hugh
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We consider the optimal spacing between marine reserves for maximising the viability of a species occupying a reserve network. The closer the networks are placed together, the higher the probability of colonisation of an empty reserve by an occupied reserve, thus increasing population viability. However, the closer the networks are placed together, the higher the probability that a catastrophe will cause extinction of the species in both reserves, thus decreasing population viability. Using a simple discrete-time Markov chain model for the presence or absence of the species in each reserve we determine the distance between the two reserves which provides the optimal trade-off between these processes, resulting in maximum viability of the species.; Comment: 12 pages and 9 figures

Utility Maximization with a Stochastic Clock and an Unbounded Random Endowment

Zitkovic, Gordan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/03/2005
Relevância na Pesquisa
16.59%
We introduce a linear space of finitely additive measures to treat the problem of optimal expected utility from consumption under a stochastic clock and an unbounded random endowment process. In this way we establish existence and uniqueness for a large class of utility-maximization problems including the classical ones of terminal wealth or consumption, as well as the problems that depend on a random time horizon or multiple consumption instances. As an example we explicitly treat the problem of maximizing the logarithmic utility of a consumption stream, where the local time of an Ornstein-Uhlenbeck process acts as a stochastic clock.; Comment: Published at http://dx.doi.org/10.1214/105051604000000738 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Intersection probabilities for a chordal SLE path and a semicircle

Alberts, Tom; Kozdron, Michael J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We derive a number of estimates for the probability that a chordal SLE path in the upper half plane H intersects a semicircle centred on the real line. We prove that if 00 of radius rx, 00. For 4

Free-Knot Spline Approximation of Stochastic Processes

Creutzig, J.; Mueller-Gronbach, T.; Ritter, K.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/12/2006
Relevância na Pesquisa
16.59%
We study optimal approximation of stochastic processes by polynomial splines with free knots. The number of free knots is either a priori fixed or may depend on the particular trajectory. For the $s$-fold integrated Wiener process as well as for scalar diffusion processes we determine the asymptotic behavior of the average $L_p$-distance to the splines spaces, as the (expected) number $k$ of free knots tends to infinity.; Comment: 23 pages

Expected Number of Slope Crossings of Certain Gaussian Random Polynomials

Rezakhah, S.; Shemehsavar, S.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 31/12/2006
Relevância na Pesquisa
16.59%
Let $Q_n(x)=\sum_{i=0}^{n} A_{i}x^{i}$ be a random polynomial where the coefficients $A_0,A_1,... $ form a sequence of centered Gaussian random variables. Moreover, assume that the increments $\Delta_j=A_j-A_{j-1}$, $j=0,1,2,...$ are independent, assuming $A_{-1}=0$. The coefficients can be considered as $n$ consecutive observations of a Brownian motion. We study the number of times that such a random polynomial crosses a line which is not necessarily parallel to the x-axis. More precisely we obtain the asymptotic behavior of the expected number of real roots of the equation $Q_n(x)=Kx$, for the cases that $K$ is any non-zero real constant $K=o(n^{1/4})$, and $K=o(n^{1/2})$ separately.; Comment: 11 pages

Limit theorems for stochastic approximation algorithms

Renlund, Henrik
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/02/2011
Relevância na Pesquisa
16.59%
We prove a central limit theorem applicable to one dimensional stochastic approximation algorithms that converge to a point where the error terms of the algorithm do not vanish. We show how this applies to a certain class of these algorithms that in particular covers a generalized P\'olya urn model, which is also discussed. In addition, we show how to scale these algorithms in some cases where we cannot determine the limiting distribution but expect it to be non-normal.

The Rademacher cotype of operators from $l_\infty^N$

Montgomery-Smith, Stephen J.; Talagrand, Michel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We show that for any operator $T:l_\infty^N\to Y$, where $Y$ is a Banach space, that its cotype 2 constant, $K_2(T)$, is related to its $(2,1)$-summing norm, $\pi_{2,1}(T)$, by $K_2(T) \le c \log\log N \pi_{2,1}(T) $. Thus, we can show that there is an operator $T:C(K)\to Y$ that has cotype 2, but is not 2-summing.

Asymptotic estimates on the von Neumann inequality for homogeneous polynomials

Galicer, Daniel; Muro, Santiago; Sevilla-Peris, Pablo
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
By the von Neumann inequality for homogeneous polynomials there exists a positive constant $C_{k,q}(n)$ such that for every $k$-homogeneous polynomial $p$ in $n$ variables and every $n$-tuple of commuting operators $(T_1, \dots, T_n)$ with $\sum_{i=1}^{n} \Vert T_{i} \Vert^{q} \leq 1$ we have \[ \|p(T_1, \dots, T_n)\|_{\mathcal L(\mathcal H)} \leq C_{k,q}(n) \; \sup\{ |p(z_1, \dots, z_n)| : \textstyle \sum_{i=1}^{n} \vert z_{i} \vert^{q} \leq 1 \}\,. \] For fixed $k$ and $q$, we study the asymptotic growth of the smallest constant $C_{k,q}(n)$ as $n$ (the number of variables/operators) tends to infinity. For $q = \infty$, we obtain the correct asymptotic behavior of this constant (answering a question posed by Dixon in the seventies). For $2 \leq q < \infty$ we improve some lower bounds given by Mantero and Tonge, and prove the asymptotic behavior up to a logarithmic factor. To achieve this we provide estimates of the norm of homogeneous unimodular Steiner polynomials, i.e. polynomials such that the multi-indices corresponding to the nonzero coefficients form partial Steiner systems.; Comment: 14 pages, Accepted in Journal f\"ur die reine und angewandte Mathematik (Crelle's Journal)

Logarithmic Coefficients and Multifractality of Whole-Plane SLE

Duplantier, Bertrand; Ho, Xuan Hieu; Le, Thanh Binh; Zinsmeister, Michel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/04/2015
Relevância na Pesquisa
16.59%
We consider the whole-plane SLE conformal map f from the unit disk to the slit plane, and show that its mixed moments, involving a power p of the derivative modulus |f'| and a power q of the map |f| itself, have closed forms along some integrability curves in the (p,q) moment plane, which depend continuously on the SLE parameter kappa. The generalization of this integrability property to the m-fold transform of f is also given. We define a generalized integral means spectrum corresponding to the singular behavior of the mixed moments above. The average generalized spectrum of whole-plane SLE takes four possible forms, separated by five phase transition lines in the moment plane, whereas the average generalized spectrum of the m-fold whole-plane SLE is directly obtained from a linear map acting in that plane. We also conjecture the form of the universal generalized integral means spectrum.; Comment: 44 pages, 17 figures

Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm

Needell, Deanna; Srebro, Nathan; Ward, Rachel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning $(L/\mu)^2$ (where $L$ is a bound on the smoothness and $\mu$ on the strong convexity) to a linear dependence on $L/\mu$. Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness, dominating previous results. We also discuss importance sampling for SGD more broadly and show how it can improve convergence also in other scenarios. Our results are based on a connection we make between SGD and the randomized Kaczmarz algorithm, which allows us to transfer ideas between the separate bodies of literature studying each of the two methods. In particular, we recast the randomized Kaczmarz algorithm as an instance of SGD, and apply our results to prove its exponential convergence, but to the solution of a weighted least squares problem rather than the original least squares problem. We then present a modified Kaczmarz algorithm with partially biased sampling which does converge to the original least squares solution with the same exponential convergence rate.; Comment: 22 pages...

Reflection positive stochastic processes indexed by Lie groups

Jorgensen, Palle E. T.; Neeb, Karl-Hermann; Olafsson, Gestur
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/10/2015
Relevância na Pesquisa
16.59%
In physics reflection positivity is a bridge between euclidean quantum theory and quantum field theory. In mathematics it is Cartan duality of symmetric Lie groups and unitary representations. In this discussion causality is represented by an involutive semigroup in $G$. We connect those ideas to stochastic processes indexed by a Lie group emphasizing Markov processes and measures on path spaces for topological groups. We also explain when Gaussian measures can be realized in the space of distribution vectors of a unitary representation.; Comment: 47 pages

Measure changes with extinction

Harris, Simon; Roberts, Matthew
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We consider a change of measure by a martingale $Z_t$ and clarify that in general $1/Z_t$ is only a supermartingale under the changed measure. We then give a necessary and sufficient condition for the event that the limit of the martingale is zero to coincide with the event that the martingale hits zero in finite time (up to a set of zero probability).; Comment: 6 pages; corrected typo, shortened proof of Theorem 6

Convergence in Density in Finite Time Windows and the Skorohod Representation

Thorisson, Hermann
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 31/08/2015
Relevância na Pesquisa
16.59%
According to the Dudley-Wichura extension of the Skorohod representation theorem, convergence in distribution to a limit in a separable set is equivalent to the existence of a coupling with elements converging a.s. in the metric. A density analogue of this theorem says that a sequence of probability densities on a general measurable space has a probability density as a pointwise lower limit if and only if there exists a coupling with elements converging a.s. in the discrete metric. In this paper the discrete-metric theorem is extended to stochastic processes considered in a widening time window. The extension is then used to prove the separability version of the Skorohod representation theorem.

On the Optimal Amount of Experimentation in Sequential Decision Problems

Rosenberg, Dinah; Solan, Eilon; Vieille, Nicolas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/07/2009
Relevância na Pesquisa
16.59%
We provide a tight bound on the amount of experimentation under the optimal strategy in sequential decision problems. We show the applicability of the result by providing a bound on the cut-off in a one-arm bandit problem.

Chains with unbounded variable length memory: perfect simulation and visible regeneration scheme

Gallo, Sandro
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.59%
We present a new perfect simulation algorithm for stationary chains having unbounded variable length memory. This is the class of infnite memory chains for which the family of transition probabilities is represented by a probabilistic context tree. We do not assume any continuity condition: our condition is expressed in terms of the structure of the context tree. More precisely, the length of the contexts is a deterministic function of the distance to the last occurrence of some determined string of symbols. It turns out that the resulting class of chains can be seen as a natural extension of the class of chains having a renewal string. In particular, our chains exhibit a visible regeneration scheme.; Comment: 27 pages, 10 figures, slight improvements of the results and simplification of the proof, simulations.

A Distributed Procedure for Computing Stochastic Expansions with Mathematica

Ladroue, Christophe; Papavasiliou, Anastasia
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/09/2010
Relevância na Pesquisa
16.59%
The solution of a (stochastic) differential equation can be locally approximated by a (stochastic) expansion. If the vector field of the differential equation is a polynomial, the corresponding expansion is a linear combination of iterated integrals of the drivers and can be calculated using Picard Iterations. However, such expansions grow exponentially fast in their number of terms, due to their specific algebra, rendering their practical use limited. We present a Mathematica procedure that addresses this issue by re-parametrising the polynomials and distributing the load in as small as possible parts that can be processed and manipulated independently, thus alleviating large memory requirements and being perfectly suited for parallelized computation. We also present an iterative implementation of the shuffle product (as opposed to a recursive one, more usually implemented) as well as a fast way for calculating the expectation of iterated Stratonovich integrals for Brownian Motion.; Comment: 15 pages, 2 figures. Submitted

A continuous time stochastic model for biological neural nets

Coregliano, Leonardo Nagami
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/07/2015
Relevância na Pesquisa
16.59%
We propose a new stochastic model for biological neural nets which is a continuous time version of the model proposed by Galves and L\"ocherbach in [A. Galves and E. L\"ocherbach, "Infinite systems of interacting chains with memory of variable length - a stochastic model for biological neural nets", J. Stat. Phys. 151 (2013), no. 5, 896-921]. We also show how to computationally simulate such model for easy neuron potential decays and probability functions and characterize when the model has a finite time of death almost surely.; Comment: 17 pages