An Algorithm for Nonlinear,Nonparametric Model Choice and Prediction

We introduce an algorithm which, in the context of nonlinear regression on vector-valued explanatory variables, aims to choose those combinations of vector components that provide best prediction. The algorithm is constructed specifically so that it devotes attention to components that might be of relatively little predictive value by themselves, and so might be ignored by more conventional methodology for model choice, but which, in combination with other difficult-to-find components, can be particularly beneficial for prediction. The design of the algorithm is also motivated by a desire to choose vector components that become redundant once appropriate combinations of other, more relevant components are selected. Our theoretical arguments show these goals are met in the sense that, with probability converging to 1 as sample size increases, the algorithm correctly determines a small, fixed number of variables on which the regression mean, g say, depends, even if dimension diverges to infinity much faster than n. Moreover, the estimated regression mean based on those variables approximates g with an error that, to first order, equals the error which would arise if we were told in advance the correct variables. In this sense, the estimator achieves oracle performance. Our numerical work indicates that the algorithm is suitable for very high dimensional problems, where it keeps computational labor in check by using a novel sequential argument, and also for more conventional prediction problems, where dimension is relatively low.     

Subregion-Adaptive Integration of Functions Having a Dominant Peak

Abstract

Many statistical multiple integration problems involve integrands that have a dominant peak. In applying numerical methods to solve these problems, statisticians have paid relatively little attention to existing quadrature methods and available software developed in the numerical analysis literature. One reason these methods have been largely overlooked, even though they are known to be more efficient than Monte Carlo for well-behaved problems of low dimensionality, may be that when applied naively they are poorly suited for peaked-integrand problems. In this article we use transformations based on “split t” distributions to allow the integrals to be efficiently computed using a subregion-adaptive numerical integration algorithm. Our split t distributions are modifications of those suggested by Geweke and may also be used to define Monte Carlo importance functions. We then compare our approach to Monte Carlo. In the several examples we examine here, we find subregion-adaptive integration to be substantially more efficient than importance sampling.     

Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue

We develop a strongly efficient rare-event simulation algorithm for computing the tail of the steady-state waiting time in a single server queue with regularly varying service times. Our algorithm is based on a state-dependent importance sampling strategy that is constructed so as to be straightforward to implement. The construction of the algorithm and its asymptotic optimality rely on a Lyapunov-type inequality that is used to bound the second moment of the estimator. The solution to the Lyapunov inequality is constructed using fluid heuristics. Our approach takes advantage of the regenerative ratio formula for the steady-state distribution—and does not use the first passage time representation that is particular to the delay in the G/G/1 queue. Hence, the strategy has the potential to be applied in more general queueing models.      

A general ratio estimator and its application in model based inference

A general ratio estimator of a population total is proposed as an approximation to the estimator introduced by Srivastava (1985,Bull. Internat. Statist. Inst.,51(10.3), 1–16). This estimator incorporates additional information gathered during the survey in a new way. Statistical properties of the general ratio estimator are given and its relationship to the estimator proposed by Srivastava is explored. A special kind of general ratio estimator is suggested and it turns out to be very efficient in a simulation study when compared to several other commonly used estimators.The work of this author was supported by AFOSR grant #830080.     

Asymptotic optimality of the generalized bayes estimator in multiparameter cases

The higher order asymptotic efficiency of the generalized Bayes estimator is discussed in multiparameter cases. For all symmetric loss functions, the generalized Bayes estimator is second order asymptotically efficient in the classA ₂ of the all second order asymptotically median unbiased (AMU) estimators and third order asymptotically efficient in the restricted classD of estimators.     

Torsion in the full orbifold <Emphasis Type="Italic">K</Emphasis>-theory of abelian symplectic quotients

Let (M, ω, Φ) be a Hamiltonian T-space and let H í T{H\subseteq T} be a closed Lie subtorus. Under some technical hypotheses on the moment map Φ, we prove that there is no additive torsion in the integral full orbifold K-theory of the orbifold symplectic quotient [M//H]. Our main technical tool is an extension to the case of moment map level sets the well-known result that components of the moment map of a Hamiltonian T-space M are Morse-Bott functions on M. As first applications, we conclude that a large class of symplectic toric orbifolds, as well as certain S ¹-quotients of GKM spaces, have integral full orbifold K-theory that is free of additive torsion. Finally, we introduce the notion of semilocally Delzant which allows us to formulate sufficient conditions under which the hypotheses of the main theorem hold. We illustrate our results using low-rank coadjoint orbits of type A and B.     

A projection method of estimation for a subfamily of exponential families

Summary This paper is concerned with estimation for a subfamily of exponential-type, which is a parametric model with sufficient statistics. The family is associated with a surface in the domain of a sufficient statistic. A new estimator, termed a projection estimator, is introduced. The key idea of its derivation is to look for a one-to-one transformation of the sufficient statistic so that the subfamily can be associated with a flat subset in the transformed domain. The estimator is defined by the orthogonal projection of the transformed statistic onto the flat surface. Here the orthogonality is introduced by the inverse of the estimated variance matrix of the statistic on the analogy of Mahalanobis's notion (1936,Proc. Nat. Inst. Sci. Ind.,2, 49–55). Thus the projection estimator has an explicit representation with no iterations. On the other hand, the MLE and classical estimators have to be sought as numerical solutions by some algorithm with a choice of an initial value and a stopping rule. It is shown that the projection estimator is first-order efficient. The second-order property is also discussed. Some examples are presented to show the utility of the estimator.     

On the D-stability and additive D-stability of matrices and Svicobians

We improve the available necessary conditions and sufficient conditions for the Dstability and additive D-stability of matrices. We define these dynamical properties with respect to a finite parallelepiped and propose an algorithm for checking them. For a particular class of matrices called Svicobians, we obtain some constructive necessary and sufficient conditions for Dstabilizability, D-stability, and additive D-stability.     

A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution

We introduce a treatment of parametric estimation in which optimality of an estimator is measured in probability rather than in variance (the measure for which the strongest general results are known in statistics). Our motivation is that the quality of an approximation algorithm is measured by the probability that it fails to approximate the desired quantity within a set tolerance. We concentrate on the Gaussian distribution and show that the sample mean is the unique “best” estimator, in probability, for the mean of a Gaussian distribution. We also extend this method to general penalty functions and to multidimensional spherically symmetric Gaussians. The algorithmic significance of studying the Gaussian distribution is established by showing that determining the average matching size in a graph is #P-hard, and moreover approximating it reduces to estimating the mean of a random variable that (under some mild conditions) has a distribution closely approximating a Gaussian. This random variable is (essentially) polynomial time samplable, thereby yielding an FPRAS for the problem.     

Heuristic Search Algorithms for the Minimum Volume Ellipsoid

Abstract

A method of robust estimation of multivariate location and shape that has attracted a lot of attention recently is Rousseeuw's minimum volume ellipsoid estimator (MVE). This estimator has a high breakdown point but is difficult to compute successfully. In this article, we apply methods of heuristic search to this problem, including simulated annealing, genetic algorithms, and tabu search, and compare the results to the undirected random search algorithm that is often cited. Heuristic search provides several effective algorithms that are far more computationally efficient than random search. Furthermore, random search, as currently implemented, is shown to be ineffective for larger problems.     

Adaptive Isotopic Approximation of Nonsingular Curves: the Parameterizability and Nonlocal Isotopy Approach

We consider domain subdivision algorithms for computing isotopic approximations of a nonsingular algebraic curve. The curve is given by a polynomial equation f(X,Y)=0. Two algorithms in this area are from Snyder (1992) SIGGRAPH Comput. Graphics, 26(2), 121 and Plantinga and Vegter (2004) In Proc. Eurographics Symposium on Geometry Processing, pp. 245–254. We introduce a new algorithm that combines the advantages of these two algorithms: like Snyder, we use the parameterizability criterion for subdivision, and like Plantinga and Vegter, we exploit nonlocal isotopy. We further extend our algorithm in two important and practical directions: first, we allow subdivision cells to be rectangles with arbitrary but bounded aspect ratios. Second, we extend the input domains to be regions R ₀ with arbitrary geometry and which might not be simply connected. Our algorithm halts as long as the curve has no singularities in the region, and intersects the boundary of R ₀ transversally. Our algorithm is practical and easy to implement exactly. We report some very encouraging experimental results, showing that our algorithms can be much more efficient than the algorithms of Plantinga–Vegter and Snyder.     

On the LASSO and its Dual

Abstract

Proposed by Tibshirani, the least absolute shrinkage and selection operator (LASSO) estimates a vector of regression coefficients by minimizing the residual sum of squares subject to a constraint on the l ¹-norm of the coefficient vector. The LASSO estimator typically has one or more zero elements and thus shares characteristics of both shrinkage estimation and variable selection. In this article we treat the LASSO as a convex programming problem and derive its dual. Consideration of the primal and dual problems together leads to important new insights into the characteristics of the LASSO estimator and to an improved method for estimating its covariance matrix. Using these results we also develop an efficient algorithm for computing LASSO estimates which is usable even in cases where the number of regressors exceeds the number of observations. An S-Plus library based on this algorithm is available from StatLib.     

Estimating and Visualizing Conditional Densities

Abstract

We consider the kernel estimator of conditional density and derive its asymptotic bias, variance, and mean-square error. Optimal bandwidths (with respect to integrated mean-square error) are found and it is shown that the convergence rate of the density estimator is order n ^–2/3. We also note that the conditional mean function obtained from the estimator is equivalent to a kernel smoother. Given the undesirable bias properties of kernel smoothers, we seek a modified conditional density estimator that has mean equivalent to some other nonparametric regression smoother with better bias properties. It is also shown that our modified estimator has smaller mean square error than the standard estimator in some commonly occurring situations. Finally, three graphical methods for visualizing conditional density estimators are discussed and applied to a data set consisting of maximum daily temperatures in Melbourne, Australia.     

On Semigroup Presentations and Efficiency

The purpose of this paper is twofold. First we determine some forms of the relations in a finite semigroup presentation with zero deficiency which does or does not define a group. Moreover, we conclude that a finite Rees matrix semigroup M [G; I, Λ; P] is efficient when G is efficient and the index sets I, Λ are finite.     

On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

Fused Lasso Additive Model

We consider the problem of predicting an outcome variable using p covariates that are measured on n independent observations, in a setting in which additive, flexible, and interpretable fits are desired. We propose the fused lasso additive model (FLAM), in which each additive function is estimated to be piecewise constant with a small number of adaptively chosen knots. FLAM is the solution to a convex optimization problem, for which a simple algorithm with guaranteed convergence to a global optimum is provided. FLAM is shown to be consistent in high dimensions, and an unbiased estimator of its degrees of freedom is proposed. We evaluate the performance of FLAM in a simulation study and on two datasets. Supplemental materials are available online, and the R package flam is available on CRAN.     

Finitely additive,modular, and probability functions on pre-Semirings

In this paper, we define finitely additive, probability and modular functions over semiring-like structures. We investigate finitely additive functions with the help of complemented elements of a semiring. We also generalize some classical results in probability theory such as the law of total probability, Bayes’ theorem, the equality of parallel systems, and Poincaré’s inclusion-exclusion theorem. While we prove that modular functions over a couple of known semirings are almost constant, we show it is possible to define many different modular functions over some semirings such as bottleneck algebras and the semiring (Id(D),+,?), where D is a Dedekind domain.     

An active index algorithm for the nearest point problem in a polyhedral cone

We consider the problem of finding the nearest point in a polyhedral cone C={x∈R ⁿ :D x≤0} to a given point b∈R ⁿ , where D∈R ^m×n . This problem can be formulated as a convex quadratic programming problem with special structure. We study the structure of this problem and its relationship with the nearest point problem in a pos cone through the concept of polar cones. We then use this relationship to design an efficient algorithm for solving the problem, and carry out computational experiments to evaluate its effectiveness. Our computational results show that our proposed algorithm is more efficient than other existing algorithms for solving this problem.     

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

A generalized contraction proximal point algorithm with two monotone operators

Abstract

In this work, we introduce a generalized contraction proximal point algorithm and use it to approximate common zeros of maximal monotone operators A and B in a real Hilbert space setting. The algorithm is a two step procedure that alternates the resolvents of these operators and uses general assumptions on the parameters involved. For particular cases, these relaxed parameters improve the convergence rate of the algorithm. A strong convergence result associated with the algorithm is proved under mild conditions on the parameters. Our main result improves and extends several results in the literature.