Optimal local estimation is formulated in the minimax sense for inverse problems and nonlinear regression. This theory provides best mean squared finite sample error bounds for some popular statistical learning algorithms and also for several optimal improvements of other existing learning algorithms such as smoothing splines and kernel regularization. The bounds and improved algorithms are not based on asymptotics or Bayesian assumptions and are truly local for each query, not depending on cross validating estimates at other queries to optimize modeling parameters. Results are given for optimal local learning of approximately linear functions with side information (context) using real algebraic geometry. In particular, finite sample error bounds are given for ridge regression and for a local version of lasso regression. The new regression methods require only quadratic programming with linear or quadratic inequality constraints for implementation. Greedy additive expansions are then combined with local minimax learning via a change in metric. An optimal strategy is presented for fusing the local minimax estimators of a class of experts-providing optimal finite sample prediction error bounds from (random) forests. Local minimax learning is extended to kernel machines. Best local prediction error bounds for finite samples are given for Tikhonov regularization. The geometry of reproducing kernel Hilbert space is used to derive improved estimators with finite sample mean squared error (MSE) bounds for class membership probability in two class pattern classification problems. A purely local, cross validation free algorithm is proposed which uses Fisher information with these bounds to determine best local kernel shape in vector machine learning. Finally, a locally quadratic solution to the finite Fourier moments problem is presented. After reading the first three sections the reader may proceed directly to any of the subsequent applications sections.

This paper derives recursive algorithms for efficiently computing event probabilities related to order statistics and applies the results in a queue inferencing setting. Consider a set of N i.i.d. random variables in [0, 1]. When the experimental values of the random variables are arranged in ascending order from smallest to largest, one has the order statistics of the set of random variables. Both a forward and a backward recursive O(N3) algorithm are developed for computing the probability that the order statistics vector lies in a given N-rectangle. The new algorithms have applicability in inferring the statistical behavior of Poisson arrival queues, given only the start and stop times of service of all N customers served in a period of continuous congestion. The queue inference results extend the theory of the “Queue Inference Engine” (QIE), originally developed by Larson in 1990 (Larson, R. C. 1990. The queue inference engine: Deducing queue statistics from transactional data. Management Sci. 36(5) 586–601, and 1991. The queue inference engine: Addendum. Management Sci. 37(6) 1062.). The methodology is extended to a third O(N3) algorithm, employing both forward and backward recursion, that computes the conditional average probability (averaged over all N customers in a congestion period) that the in-queue wait is less than t minutes, given the departure time data and assuming first come, first served service. To our knowledge, this result is the first O(N3) exact algorithm for computing points on the in-queue waiting time distribution function, conditioned on the start and stop time data. The paper concludes with an extension to the computation of certain correlations of in-queue waiting times. Illustrative computational results are included throughout. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A constructive algorithm for uniformly approximating real continuous mappings by linear combinations of bounded sigmoidal functions is given. G. Cybenko (1989) has demonstrated the existence of uniform approximations to any continuous f provided that sigma is continuous; the proof is nonconstructive, relying on the Hahn-Branch theorem and the dual characterization of C(I/sup n/). Cybenko's result is extended to include any bounded sigmoidal (even nonmeasurable ones). The approximating functions are explicitly constructed. The number of terms in the linear combination is minimal for first-order terms.>

Minimum distance approaches are considered for the reconstruction of a real function from finitely many linear functional values. An optimal class of distances satisfying an orthogonality condition analogous to that enjoyed by linear projections in Hilbert space is derived. These optimal distances are related to measures of distances between probability distributions recently introduced by C.R. Rao and T.K. Nayak (1985) and possess the geometric properties of cross entropy useful in speech and image compression, pattern classification, and cluster analysis. Several examples from spectrum estimation and image processing are discussed.>

Addresses the two class discrimination problem in the case that each class can be viewed as being composed of a finite number of types. The prior probabilities for the types comprising both classes are unknown, the class costs are known and the conditional densities for the types are real analytic functions. An algorithm is presented that can be used to estimate an optimal discriminant function that is robust in the minimax sense. The algorithm involves a search over a set of prior weights. The convergence properties of the algorithm are examined in a series of tests involving Gaussian mixture densities.>

A Bayesian approach to the problem of finite sample detection of a signal in an unknown noise environment is formulated. A mathematical solution is given for the minimax (robust) test for detecting the presence of a stochastic signal of known prior probability in unknown additive noise of bounded magnitude. This solution remains valid for a constant signal with identical components when the additive noises are independent. This extends results of J.M. Morris (ibid., vol.IT-62, p.199-209, March 1980). Worst-case performance bounds for detecting the presence of a pattern class are derived.>

A maximum likelihood approach is developed for a pattern recognition problem where the patterns are described by configurations of simple easily recognized parts called primitives. The approach is capable of dealing with three types of noise: measurement noise in the location and shape of observed primitives, undetected or missing primitives (leakage), and the unexpected appearance of extra primitives (false alarms). The approach is called combinatorial because the likelihood function dictates that observed primitives must be assigned to known primitives in all possible combinations. Due to the complexity of the likelihood function, practical classifiers must be based on likelihood function approximations. Several are proposed, and most of these are simple enough to be used in a gradient search strategy for recognizing distorted patterns with random orientations. Examples are included to show the characteristics of combinatorial classifier performance.

A general method for discriminating between twokdependent stationary discrete random variables using marginal statistics and their first-order correlations is described.