Linear and convex aggregation of density estimators

We study the problem of finding the best linear and convex combination of M estimators of a density with respect to the mean squared risk. We suggest aggregation procedures and we prove sharp oracle inequalities for their risks, i.e., oracle inequalities with leading constant 1. We also obtain lower bounds showing that these procedures attain optimal rates of aggregation. As an example, we consider aggregation of multivariate kernel density estimators with different bandwidths. We show that linear and convex aggregates mimic the kernel oracles in asymptotically exact sense. We prove that, for Pinsker’s kernel, the proposed aggregates are sharp asymptotically minimax simultaneously over a large scale of Sobolev classes of densities. Finally, we provide simulations demonstrating performance of the convex aggregation procedure.      

Multi-self-similar Markov processes on ℝ<Subscript>+</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> and their Lamperti representations

 A classical result, due to Lamperti, establishes a one-to-one correspondence between a class of strictly positive Markov processes that are self-similar, and the class of one-dimensional Lévy processes. This correspondence is obtained by suitably time-changing the exponential of the Lévy process. In this paper we generalise Lamperti's result to processes in n dimensions. For the representation we obtain, it is essential that the same time-change be applied to all coordinates of the processes involved. Also for the statement of the main result we need the proper concept of self-similarity in higher dimensions, referred to as multi-self-similarity in the paper. The special case where the Lévy process ξ is standard Brownian motion in n dimensions is studied in detail. There are also specific comments on the case where ξ is an n-dimensional compound Poisson process with drift. Finally, we present some results concerning moment sequences, obtained by studying the multi-self-similar processes that correspond to n-dimensional subordinators. Received: 22 August 2002 / Revised version: 10 February 2003 Published online: 15 April 2003 RID="*" ID="*" MaPhySto – Centre for Mathematical Physics and Stochastics, funded by a grant from the Danish National Research Foundation Mathematics Subject Classification (2000): 60G18, 60G51, 60J25, 60J60, 60J75 Key words or phrases: Lévy process – Self-similarity – Time-change – Exponential functional – Brownian motion – Bessel process – Piecewise deterministic Markov process – Moment sequence     

Sharp adaptation for inverse problems with random noise

 We consider a heteroscedastic sequence space setup with polynomially increasing variances of observations that allows to treat a number of inverse problems, in particular multivariate ones. We propose an adaptive estimator that attains simultaneously exact asymptotic minimax constants on every ellipsoid of functions within a wide scale (that includes ellipoids with polynomially and exponentially decreasing axes) and, at the same time, satisfies asymptotically exact oracle inequalities within any class of linear estimates having monotone non-increasing weights. The construction of the estimator is based on a properly penalized blockwise Stein's rule, with weakly geometically increasing blocks. As an application, we construct sharp adaptive estimators in the problems of deconvolution and tomography. Received: 19 January 2000 / Revised version: 30 April 2001 / Published online: 14 June 2002     

Convergence rate analysis of iteractive algorithms for solving variational inequality problems

 We present a unified convergence rate analysis of iterative methods for solving the variational inequality problem. Our results are based on certain error bounds; they subsume and extend the linear and sublinear rates of convergence established in several previous studies. We also derive a new error bound for $\gamma$-strictly monotone variational inequalities. The class of algorithms covered by our analysis in fairly broad. It includes some classical methods for variational inequalities, e.g., the extragradient, matrix splitting, and proximal point methods. For these methods, our analysis gives estimates not only for linear convergence (which had been studied extensively), but also sublinear, depending on the properties of the solution. In addition, our framework includes a number of algorithms to which previous studies are not applicable, such as the infeasible projection methods, a separation-projection method, (inexact) hybrid proximal point methods, and some splitting techniques. Finally, our analysis covers certain feasible descent methods of optimization, for which similar convergence rate estimates have been recently obtained by Luo [14]. Received: April 17, 2001 / Accepted: December 10, 2002 Published online: April 10, 2003 RID="⋆" ID="⋆" Research of the author is partially supported by CNPq Grant 200734/95–6, by PRONEX-Optimization, and by FAPERJ. Key Words. Variational inequality – error bound – rate of convergence Mathematics Subject Classification (2000): 90C30, 90C33, 65K05     

On logarithmic Sobolev inequalities for continuous time random walks on graphs

We establish modified logarithmic Sobolev inequalities for the path distributions of some continuous time random walks on graphs, including the simple examples of the discrete cube and the lattice ZZ ^d . Our approach is based on the Malliavin calculus on Poisson spaces developed by J. Picard and stochastic calculus. The inequalities we prove are well adapted to describe the tail behaviour of various functionals such as the graph distance in this setting. Received: 6 April 1998 / Revised version: 15 March 1999 / Published on line: 14 February 2000     

Multifractal products of cylindrical pulses

 New multiplicative and statistically self-similar measures μ are defined on ℝ as limits of measure-valued martingales. Those martingales are constructed by multiplying random functions attached to the points of a statistically self-similar Poisson point process defined in a strip of the plane. Several fundamental problems are solved, including the non-degeneracy and the multifractal analysis of μ. On a bounded interval, the positive and negative moments of diverge under broad conditions. First received: 14 September 1999 / Resubmited: 27 June 2001 / Revised version: 30 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2002): 28A80, 60G18, 60G44, 60G55, 60G57 Key words or phrases: Random measures – Multifractal analysis – Continuous time martingales – Statistically self-similar Poisson point processes     

On the infinite divisibility of squared Gaussian processes

 We show that fractional Brownian motions with index in (0,1] satisfy a remarkable property: their squares are infinitely divisible. We also prove that a large class of Gaussian processes are sharing this property. This property then allows the construction of two-parameters families of processes having the additivity property of the squared Bessel processes. Received: 1 April 2002 / Revised version: 7 September 2002 / Published online: 19 December 2002 Mathematics Subject Classification (2000): 60E07, 60G15, 60J25, 60J55 Key words or phrases: Gaussian processes – Infinite divisibility – Markov processes     

Generalized mirror averaging and <Emphasis Type="Italic">D</Emphasis>-convex aggregation

We study the problem of aggregation of estimators. Given a collection of M different estimators, we construct a new estimator, called aggregate, which is nearly as good as the best linear combination over an l ₁-ball of ℝ^M of the initial estimators. The aggregate is obtained by a particular version of the mirror averaging algorithm. We show that our aggregation procedure statisfies sharp oracle inequalities under general assumptions. Then we apply these results to a new aggregation problem: D-convex aggregation. Finally we implement our procedure in a Gaussian regression model with random design and we prove its optimality in a minimax sense up to a logarithmic factor.      

The principle of penalized empirical risk in severely ill-posed problems

We study a standard method of regularization by projections of the linear inverse problem Y=Ax+, where is a white Gaussian noise, and A is a known compact operator. It is assumed that the eigenvalues of AA^* converge to zero with exponential decay. Such behavior of the spectrum is typical for inverse problems related to elliptic differential operators. As model example we consider recovering of unknown boundary conditions in the Dirichlet problem for the Laplace equation on the unit disk. By using the singular value decomposition of A, we construct a projection estimator of x. The bandwidth of this estimator is chosen by a data-driven procedure based on the principle of minimization of penalized empirical risk. We provide non–asymptotic upper bounds for the mean square risk of this method and we show, in particular, that this approach gives asymptotically minimax estimators in our model example.Mathematics Subject Classification (2000):Primary 62G05, 62G20; secondary 62C20     

Generalized qd algorithm and Markov–Bernstein inequalities for Jacobi weight

The Markov–Bernstein inequalities for the Jacobi measure remained to be studied in detail. Indeed the tools used for obtaining lower and upper bounds of the constant which appear in these inequalities, did not work, since it is linked with the smallest eigenvalue of a five diagonal positive definite symmetric matrix. The aim of this paper is to generalize the qd algorithm for positive definite symmetric band matrices and to give the mean to expand the determinant of a five diagonal symmetric matrix. After that these new tools are applied to the problem to produce effective lower and upper bounds of the Markov–Bernstein constant in the Jacobi case. In the last part we com pare, in the particular case of the Gegenbauer measure, the lower and upper bounds which can be deduced from this paper, with those given in Draux and Elhami (Comput J Appl Math 106:203–243, 1999) and Draux (Numer Algor 24:31–58, 2000).      

Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

Exact order of Hoffman’s error bounds for elliptic quadratic inequalities derived from vector-valued Chebyshev approximation

In this paper, we introduce the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities. Elliptic quadratic inequalities are closely related to Chebyshev approximation of vector-valued functions (including complex-valued functions). The set of Chebyshev approximations of a vector-valued function defined on a finite set is shown to be Hausdorff strongly unique of order exactly 2 ^s for some nonnegative integer s. As a consequence, the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities is exactly 2 ^-s for some nonnegative integer s. The integer s, called the order of deficiency (which is computable), quantifies how much the Abadie constraint qualification is violated by the elliptic quadratic inequalities. Received: April 15, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

Some nonlinear dynamic inequalities on time scales

The aim of this paper is to investigate some nonlinear dynamic inequalities on time scales, which provide explicit bounds on unknown functions. The inequalities given here unify and extend some inequalities in (B G Pachpatte, On some new inequalities related to a certain inequality arising in the theory of differential equation, J. Math. Anal. Appl. 251 (2000) 736–751).     

Renormalization and homogenization of fractional diffusion equations with random data

 This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple stochastic integral representations. Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002 Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60 Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler function – Stable distributions – Bessel potential – Riesz potential     

On lower bounds of moderate large deviations of tests and estimators

New lower bounds for probabilities of large deviations of tests and estimators are proposed. These bounds cover the cases of moderate and Cramér-type large deviations. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 216, 1994, pp. 52–61. Translated by the author.     

On the central limit theorem for the stationary Poisson process of compact sets

Stochastic geometry models based on a stationary Poisson point process of compact subsets of the Euclidean space are examined. Random measures on ?^d, derived from these processes using Hausdorff and projection measures are studied. The central limit theorem is formulated in a way which enables comparison of the various estimators of the intensity of the produced random measures. Approximate confidence intervals for the intensity are constructed. Their use is demonstrated in an example of length intensity estimation for the segment processes. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Oracle convergence rate of posterior under projection prior and Bayesian model selection

We apply the Bayes approach to the problem of projection estimation of a signal observed in the Gaussian white noise model and we study the rate at which the posterior distribution concentrates about the true signal from the space ℓ₂ as the information in observations tends to infinity. A benchmark is the rate of a so-called oracle projection risk, i.e., the smallest risk of an unknown true signal over all projection estimators. Under an appropriate hierarchical prior, we study the performance of the resulting (appropriately adjusted by the empirical Bayes approach) posterior distribution and establish that the posterior concentrates about the true signal with the oracle projection convergence rate. We also construct a Bayes estimator based on the posterior and show that it satisfies an oracle inequality. The results are nonasymptotic and uniform over ℓ₂. Another important feature of our approach is that our results on the oracle projection posterior rate are always stronger than any result about posterior convergence with the minimax rate over all nonparametric classes for which the corresponding projection oracle estimator is minimax over this class. We also study implications for the model selection problem, namely, we propose a Bayes model selector and assess its quality in terms of the so-called false selection probability.     

On domination of tail probabilities of (super)martingales: Explicit bounds

Let X be a random variable with survival function G(x)=ℙ{X≥x}. Let α > 0. Consider a transform, say T _α, of survival functions G↦T _α G defined by

Mingling: mixed-integer rounding with bounds

Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs. When used as cutting planes, MIR inequalities are very effective for mixed-integer programming problems with unbounded integer variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information into MIR. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets with bounded variables. We show that facets of mixed-integer knapsack sets derived earlier by superadditive lifting techniques can be obtained by the mingling procedure. In particular, the mingling inequalities developed in this paper subsume the continuous cover and reverse continuous cover inequalities of Marchand and Wolsey (Math Program 85:15–33, 1999) as well as the continuous integer knapsack cover and pack inequalities of Atamtürk (Math Program 98:145–175, 2003; Ann Oper Res 139:21–38, 2005). In addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Günlük (Math Program 105:29–53, 2006) under some conditions.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05