An Inscribing Model for Random Polytopes

For convex bodies K with boundary in ℝ ^d , we explore random polytopes with vertices chosen along the boundary of K. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem. The research of V.H. Vu was done under the support of A. Sloan Fellowship and an NSF Career Grant. The research of L. Wu is done while the author was at University of California San Diego.     

Multivariate Normal Approximation for Functionals of Random Polytopes

Journal of Theoretical Probability - Consider the random polytope that is given by the convex hull of a Poisson point process on a smooth convex body in $$\mathbb {R}^d$$ . We prove central limit...     

Banach-Mazur Distances and Projections on Random Subgaussian Polytopes

We consider polytopes in that are generated by N vectors in whose coordinates are independent subgaussian random variables. (A particular case of such polytopes are symmetric random polytopes generated by N independent vertices of the unit cube.) We show that for a random pair of such polytopes the Banach-Mazur distance between them is essentially of a maximal order n. This result is an analogue of the well-known Gluskin's result for spherical vectors. We also study the norms of projections on such polytopes and prove an analogue of Gluskin's and Szarek's results on basis constants. The proofs are based on a version of "small ball" estimates for linear images of random subgaussian vectors.     

Error Bounds: Necessary and Sufficient Conditions

The paper presents a general classification scheme of necessary and sufficient criteria for the error bound property incorporating the existing conditions. Several derivative-like objects both from the primal as well as from the dual space are used to characterize the error bound property of extended-real-valued functions on a Banach space.     

Risk Bounds for Random Regression Graphs

We consider the regression problem and describe an algorithm approximating the regression function by estimators piecewise constant on the elements of an adaptive partition. The partitions are iteratively constructed by suitable random merges and splits, using cuts of arbitrary geometry. We give a risk bound under the assumption that a "weak learning hypothesis" holds, and characterize this hypothesis in terms of a suitable RKHS. Two examples illustrate the general results in two particularly interesting cases.     

Sufficient Conditions for Error Bounds and Applications

Our aim in this paper is to present sufficient conditions for error bounds in terms of Fréchet and limiting Fréchet subdifferentials in general Banach spaces. This allows us to develop sufficient conditions in terms of the approximate subdifferential for systems of the form (x, y) C × D, g(x, y, u) = 0, where g takes values in an infinite-dimensional space and u plays the role of a parameter. This symmetric structure offers us the choice of imposing conditions either on C or D. We use these results to prove the nonemptiness and weak-star compactness of Fritz–John and Karush–Kuhn–Tucker multiplier sets, to establish the Lipschitz continuity of the value function and to compute its subdifferential and finally to obtain results on local controllability in control problems of nonconvex unbounded differential inclusions.     

Equivalent Conditions for Local Error Bounds

In this paper we present two classes of equivalent conditions for local error bounds in finite dimensional spaces. We formulate conditions of the first class by using subderivatives, subdifferentials and strong slopes for nearby points outside the referenced set, and show that these conditions actually characterize a uniform version of the local error bound property. We demonstrate this uniformity for the max function of a finite collection of smooth functions, and as a consequence we show that quasinormality constraint qualifications guarantee the existence of local error bounds. We further present the second class of equivalent conditions for local error bounds by using the various limits defined on the boundary of the referenced set. In presenting these conditions, we exploit the variational geometry of the referenced set in a systematic way and unify some existing results in the literature.     

Error Bounds for Nonnegative Dynamic Models

The extension of Markov reward models to dynamic models with nonnegative matrices is motivated by practical applications, such as economic input–output, employment, or population models. This paper studies the generalization of error bound theorems for Markov reward structures to dynamic reward structures with arbitrary nonnegative matrices. Both irreducible and reducible matrices are covered. In addition, results for the stochastic case are unified and extended. First, generalized expressions are derived for average reward functions. The special normalization case is distinguished and is shown to be transformable into the stochastic case. Its interpretation is of interest in itself. Next, error bound results are studied. Under a general normalization condition, it is shown that the results for the stochastic case can be extended. Both the average case and the transient case are included. A random walk-type example is included to illustrate the results.     

Improved Error Bounds for Lattice Rules

We establish results on the worst-case errors that can be achieved by well-chosen lattice rules for standard classes of multivariate periodic functions. These theorems improve or generalize earlier results of this type.     

Error Bounds for Exponential Operator Splittings

Error bounds for the Strang splitting in the presence of unbounded operators are derived in a general setting and are applied to evolutionary Schrödinger equations and their pseudo-spectral space discretization.     

On Error Bounds for Quasinormal Programs

The Mangasarian-Fromovitz constraint qualification is a central concept within the theory of constraint qualifications in nonlinear optimization. Nevertheless there are problems where this condition does not hold though other constraint qualifications can be fulfilled. One of such constraint qualifications is the so-called quasinormality by Hestenes. The well known error bound property (R-regularity) can also play the role of a general constraint qualification providing the existence of Lagrange multipliers. In this note we investigate the relation between some constraint qualifications and prove that quasinormality implies the error bound property, while the reciprocal is not true.     

Random Function Iterations for Consistent Stochastic Feasibility

We study the convergence of iterated random functions for stochastic feasibility in the consistent case (in the sense of Butnariu and Flåm [Numer. Funct. Anal. Optimiz., 1995]) in several different settings, under decreasingly restrictive regularity assumptions of the fixed point mappings. The iterations are Markov chains and, for the purposes of this study, convergence is understood in very restrictive terms. We show that sufficient conditions for geometric (linear) convergence in expectation of stochastic projection algorithms presented in Nedi? [Math. Program, 2011], are in fact necessary for geometric (linear) convergence in expectation more generally of iterated random functions.     

Computable Error Bounds for Semidefinite Programming

We study computability and applicability of error bounds for a given semidefinite pro-gramming problem under the assumption that the recession function associated with the constraint system satisfies the Slater condition. Specifically, we give computable error bounds for the distances between feasible sets, optimal objective values, and optimal solution sets in terms of an upper bound for the condition number of a constraint system, a Lipschitz constant of the objective function, and the size of perturbation. Moreover, we are able to obtain an exact penalty function for semidefinite programming along with a lower bound for penalty parameters. We also apply the results to a class of statistical problems.     

Finite-Data Error Bounds for Koopman-Based Prediction and Control

Journal of Nonlinear Science - This paper presents symmetry reduction for material stochastic Lagrangian systems with advected quantities whose configuration space is a Lie group. Such variational...     

Error Bounds for Polynomial Evaluation and Complex Arithmetic

Explicit and computable strict bounds of a posteriori type areconstructed for the evaluation of a polynomial and its derivativesby nested multiplication, using floating-point arithmetic. Thepolynomial may be real or complex, and may contain errors inits coefficients and argument. Some new error bounds for arithmetic operations with complexnumbers are included.     

Error Bounds and Stopping Rules for Extrapolation Methods

In this paper, we present two different types of error boundsfor the approximation of functions by extrapolation methods(also called elimination methods). First, we give some a prioritype bounds; by means of these, one can, before starting theextrapolation process, estimate the errors of the extrapolatedvalues. Next, we present the so-called stopping rules; thesecan be used to decide during the process if the desired accuracyhas already been reached. Using the same techniques as for deducingthe error bounds, we then give criteria which help to predictthe form of the resulting error curves. It turns out that theseare in many cases monotone functions. Finally, two numericalexamples illustrate the results of this paper.     

Error Bounds for Approximation with Neural Networks

In this paper we prove convergence rates for the problem of approximating functions f by neural networks and similar constructions. We show that the rates are the better the smoother the activation functions are, provided that f satisfies an integral representation. We give error bounds not only in Hilbert spaces but also in general Sobolev spaces W^m, r(Ω). Finally, we apply our results to a class of perceptrons and present a sufficient smoothness condition on f guaranteeing the integral representation.     

Improved Error Bounds for a Chebysheff-Halley-Type Method

Using the majorant method we find sufficient conditions for the convergence of a Chebysheff-Halley-type method in a Banach space. Our results improve all our previous results as well as those of others.     

A Posteriori Error Bounds for Gaussian Elimination

Explicit bounds are constructed for the error in the solutionof a system of linear algebraic equations obtained by Gaussianelimination using floating-point arithmetic. The bounds takeaccount of inherent errors in the data and all abbreviations(choppings or roundings) introduced during the process of solution.The bounds are strict and agree with the estimate for the maximumerror obtained by linearized perturbation theory. The formulationof the bounds avoids the need for specially directed roundingprocedures in the hardware or software; in consequence the boundscan be evaluated on most existing computers. The cost of computingthe bounds is comparable with the cost of computing the originalsolution.