Aggregation via empirical risk minimization

Given a finite set F of estimators, the problem of aggregation is to construct a new estimator whose risk is as close as possible to the risk of the best estimator in F. It was conjectured that empirical minimization performed in the convex hull of F is an optimal aggregation method, but we show that this conjecture is false. Despite that, we prove that empirical minimization in the convex hull of a well chosen, empirically determined subset of F is an optimal aggregation method.     

Set estimation under convexity type assumptions

The problem of estimating a set S from a random sample of points taken within S is considered. It is assumed that S is r-convex, which means that a ball of radius r can go around from outside the set boundary. Under this assumption, the r-convex hull of the sample is a natural estimator of S. We obtain convergence rates for this estimator under both the distance in measure and the Hausdorff metric between sets. It is also proved that the boundary of the estimator consistently estimates the boundary of S, in Hausdorff's sense.     

Closed convex hulls,contents, and K‐spectral states

Our general result says that the closed convex hull of a set K consists of barycentres of probability contents (i.e., finitely additive set functions) on K. (Here K can be any nonempty subset of any nonempty compact convex set in any real or complex locally convex Hausdorff vector space.) In the equivalent setting of dual spaces, we give a very handy analytic criterion for a linear functional to be in the closed convex hull of a given nonempty point‐wise bounded set K of linear functionals (under some mild additional assumption). This is the notion of a K‐spectral state. Our criterion enhances the Abstract Bochner Theorem for unital commutative Banach *‐algebras (which easily follows from our result), in that it allows us to prescribe the set K on which a representing content should live. The content can be chosen to be a Radon measure if K is weak* compact. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Probabilities of hitting a convex hull

In this note, we consider the non-negative least-square method with a random matrix. This problem has connections with the probability that the origin is not in the convex hull of many random points. As related problems, suitable estimates are obtained as well on the probability that a small ball does not hit the convex hull.     

Asymptotic theory of simultaneous estimation of Poisson means

The Poisson distribution is often a good approximation to the underlying sampling distribution and is central to the study of categorical data. In this paper, we propose a new unified approach to an investigation of point properties of simultaneous estimations of Poisson population parameters with general quadratic loss functions. The main accent is made on the shrinkage estimation. We build a series of estimators that could be represented as a convex combination of linear statistics such as maximum likelihood estimator (benchmark estimator), restricted estimator, composite estimator, preliminary test estimator, shrinkage estimator, positive rule shrinkage estimator (James-Stein type estimator). All these estimators are represented in a general integrated estimation approach, which allows us to unify our investigation and order them with respect to the risk. A simulation study with numerical and graphical results is conducted to illustrate the properties of the investigated estimators.     

Minimal Time Functions and the Smallest Intersecting Ball Problem with Unbounded Dynamics

The smallest enclosing circle problem introduced in the nineteenth century by Sylvester asks for the circle of smallest radius enclosing a given set of finite points in the plane. An extension of this problem, called the smallest intersecting ball problem, was also considered recently: given a finite number of nonempty closed subsets of a normed space, find a ball with the smallest radius that intersects all of the sets. In this paper, we initiate the study of minimal time functions generated by unbounded dynamics and discuss their applications to further extensions of the smallest enclosing circle problem. This approach continues our effort in applying convex and nonsmooth analysis to the well-established field of facility location.     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.     

Local generalized quadratic distance metrics: application to the <Emphasis Type="Italic">k</Emphasis>-nearest neighbors classifier

Finding the set of nearest neighbors for a query point of interest appears in a variety of algorithms for machine learning and pattern recognition. Examples include k nearest neighbor classification, information retrieval, case-based reasoning, manifold learning, and nonlinear dimensionality reduction. In this work, we propose a new approach for determining a distance metric from the data for finding such neighboring points. For a query point of interest, our approach learns a generalized quadratic distance (GQD) metric based on the statistical properties in a “small” neighborhood for the point of interest. The locally learned GQD metric captures information such as the density, curvature, and the intrinsic dimensionality for the points falling in this particular neighborhood. Unfortunately, learning the GQD parameters under such a local learning mechanism is a challenging problem with a high computational overhead. To address these challenges, we estimate the GQD parameters using the minimum volume covering ellipsoid (MVCE) for a set of points. The advantage of the MVCE is two-fold. First, the MVCE together with the local learning approach approximate the functionality of a well known robust estimator for covariance matrices. Second, computing the MVCE is a convex optimization problem which, in addition to having a unique global solution, can be efficiently solved using a first order optimization algorithm. We validate our metric learning approach on a large variety of datasets and show that the proposed metric has promising results when compared with five algorithms from the literature for supervised metric learning.     

The embracing Voronoi diagram and closest embracing number

A point q is embraced by a set of points S if q is interior to the convex hull of S [8]. In some illumination applications where points of S are lights and q is a point to be illuminated, the embracing concept is related to a good illumination [4, 6], also known as the ∆-guarding [12] and the well-covering [10]. In this paper, we are not only interested in convex dependency (which is actually the embracing notion) but also in proximity. Suppose that the sites of S are lights or antennas with limited range; due to their limited power, they cover a disk of a given radius r centered at the sites of S. Only the points lying in such disks are illuminated. If we want to embrace the point q with the minimum range r, we need to know which is the closest light s _q to q such that q lies in the convex hull formed by s _q and the lights of S closer to q than s _q . This subset of S related to point q is called the closest embracing set for q in relation to S and its cardinality is the closest embracing number of q. By assigning every point q in the convex hull of S to its closest embracing site s _q , we obtain a partition of the convex hull that we call the embracing Voronoi diagram of S. This paper proves some properties of the embracing Voronoi diagrams and describes algorithms to compute such diagrams, as well as the levels in which the convex hull is decomposed regarding the closest embracing number.     

On the spectral function of the Poisson–Voronoi cells

Denote by (t)=∑_n1e^−λ_nt, t>0, the spectral function related to the Dirichlet Laplacian for the typical cell of a standard Poisson–Voronoi tessellation in . We show that the expectation E(t), t>0, is a functional of the convex hull of a standard d-dimensional Brownian bridge. This enables us to study the asymptotic behaviour of E(t), when t→0⁺,+∞. In particular, we prove that the law of the first eigenvalue λ₁ of satisfies the asymptotic relation lnP{λ₁t}−2^dω_dj_(d−2)/2^d·t^−d/2 when t→0⁺, where ω_d and j_(d−2)/2 are respectively the Lebesgue measure of the unit ball in and the first zero of the Bessel function J_(d−2)/2.     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

Approximate convex hull of affine iterated function system attractors

In this paper, we present an algorithm to construct an approximate convex hull of the attractors of an affine iterated function system (IFS). We construct a sequence of convex hull approximations for any required precision using the self-similarity property of the attractor in order to optimize calculations. Due to the affine properties of IFS transformations, the number of points considered in the construction is reduced. The time complexity of our algorithm is a linear function of the number of iterations and the number of points in the output approximate convex hull. The number of iterations and the execution time increases logarithmically with increasing accuracy. In addition, we introduce a method to simplify the approximate convex hull without loss of accuracy.     

On convergence of the modified Newton’s method under Hölder continuous Fréchet derivative

In this paper, the upper and lower estimates of the radius of the convergence ball of the modified Newton’s method in Banach space are provided under the hypotheses that the Fréchet derivative of the nonlinear operator are center Hölder continuous for the initial point and the solution of the operator. The error analysis is given which matches the convergence order of the modified Newton’s method. The uniqueness ball of solution is also established. Numerical examples for validating the results are also provided, including a two point boundary value problem.     

Using Interval Arithmetic for Determining the Structure of Convex Hulls

We discuss the use of interval arithmetic in the computation of the convex hull of n points in D dimensions. Convex hull algorithms rely on simple geometric tests, such as “does some point p lie in a certain half-space or affine subspace?” to determine the structure of the hull. These tests in turn can be carried out by solving appropriate (not necessarily square) linear systems. If interval-based methods are used for the solution of these systems then the correct hull can be obtained at lower cost than with exact arithmetic. In addition, interval-based methods can determine the topological structure of the convex hull even if the position of the points is not known exactly. In the present paper we compare various interval linear solvers with respect to their ability to handle close-to-pathological situations. This property determines how often interval arithmetic cannot provide the required information and therefore some computations must be redone with exact arithmetic.     

Extreme values for characteristic radii of a Poisson-Voronoi Tessellation

A homogeneous Poisson-Voronoi tessellation of intensity γ is observed in a convex body W. We associate to each cell of the tessellation two characteristic radii: the inradius, i.e. the radius of the largest ball centered at the nucleus and included in the cell, and the circumscribed radius, i.e. the radius of the smallest ball centered at the nucleus and containing the cell. We investigate the maximum and minimum of these two radii over all cells with nucleus in W. We prove that when \(\gamma \rightarrow \infty \) , these four quantities converge to Gumbel or Weibull distributions up to a rescaling. Moreover, the contribution of boundary cells is shown to be negligible. Such approach is motivated by the analysis of the global regularity of the tessellation. In particular, consequences of our study include the convergence to the simplex shape of the cell with smallest circumscribed radius and an upper-bound for the Hausdorff distance between W and its so-called Poisson-Voronoi approximation.     

On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.     

On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables

In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially generated using a convexification scheme such as the Reformulation-Linearization Technique (RLT) or lift-and-project process, which yields valid inequalities that are reusable in the subsequent subproblems by updating the values of the first-stage variables. A branch-and-bound algorithm is designed based on a hyperrectangular partitioning process, using the established property that any resulting lower bounding Benders' master problem defined over a hyperrectangle yields the same objective value as the original stochastic program over that region if the first-stage variable solution is an extreme point of the defining hyperrectangle or the second-stage solution satisfies the binary restrictions. We prove that this algorithm converges to a global optimal solution. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach.     

Run time estimation of the spectral radius of Jacobians

It is useful for ordinary differential equation (ODE) solvers to include an estimator of the spectral radius of the Jacobian matrix of the system of ODE's, since this determines the numerical stability of the method. Hence a knowledge of spectral radius enables the run time selection of a more efficient integrator. Some techniques for estimating spectral radius are described and compared. They include methods suitable for use with any ODE solvers, but which require additional computation. Other methods are described which are suitable with Runge-Kutta or Rosenbrock methods, and which require little extra computation.