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.     

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.      

Lower bound for the oracle projection posterior convergence rate

In Babenko and Belitser (2010), a new notion for the posterior concentration rate is proposed, the so-called oracle risk rate, the best possible rate over an appropriately chosen estimators family, which is a local quantity (as compared, e.g., with global minimax rates). The program of oracle estimation and Bayes oracle posterior optimality is fully implemented in the above paper for the Gaussian white noise model and the projection estimators family.In this note, we complement the upper bound results of Babenko and Belitser (2010) on the posterior concentration rate by a lower bound result, namely that the concentration rate of the posterior distribution around the ‘true’ value cannot be faster than the oracle projection rate.     

Adaptive estimation in the single-index model via oracle approach

In the framework of nonparametric multivariate function estimation we are interested in structural adaptation. We assume that the function to be estimated has the “single-index” structure where neither the link function nor the index vector is known. This article suggests a novel procedure that adapts simultaneously to the unknown index and the smoothness of the link function. For the proposed procedure, we prove a “local” oracle inequality (described by the pointwise seminorm), which is then used to obtain the upper bound on the maximal risk of the adaptive estimator under assumption that the link function belongs to a scale of Hölder classes. The lower bound on the minimax risk shows that in the case of estimating at a given point the constructed estimator is optimally rate adaptive over the considered range of classes. For the same procedure we also establish a “global” oracle inequality (under the L _r norm, r < ∞) and examine its performance over the Nikol’skii classes. This study shows that the proposed method can be applied to estimating functions of inhomogeneous smoothness, that is whose smoothness may vary from point to point.     

Oracle inequality for conditional density estimation and an actuarial example

Conditional density estimation in a parametric regression setting, where the problem is to estimate a parametric density of the response given the predictor, is a classical and prominent topic in regression analysis. This article explores this problem in a nonparametric setting where no assumption about shape of an underlying conditional density is made. For the first time in the literature, it is proved that there exists a nonparametric data-driven estimator that matches performance of an oracle which: (i) knows the underlying conditional density, (ii) adapts to an unknown design of predictors, (iii) performs a dimension reduction if the response does not depend on the predictor, (iv) is minimax over a vast set of anisotropic bivariate function classes. All these results are established via an oracle inequality which is on par with ones known in the univariate density estimation literature. Further, the asymptotically optimal estimator is tested on an interesting actuarial example which explores a relationship between credit scoring and premium for basic auto-insurance for 54 undergraduate college students.     

Semi-Infinite Programming and Applications to Minimax Problems

A minimisation problem with infinitely many constraints – semi-infinite programming problem (SIP) is considered. The problem is solved using a two stage procedure that searches for global maximum violation of the constraints. A version of the algorithm that searches for any violation of constraints is also considered, and the performance of the two algorithm is compared. An application to solving minimax problem (with and without coupled constraints) is given and a comparison with the algorithm for continuous minimax of Rustem and Howe (2001) is included. Finally, we consider an application to chemical engineering problems.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Beyond Canonical DC-Optimization: The Single Reverse Polar Problem

We propose a novel generalization of the Canonical Difference of Convex problem (CDC), and we study the convergence of outer approximation algorithms for its solution, which use an approximated oracle for checking the global optimality conditions. Although the approximated optimality conditions are similar to those of CDC, this new class of problems is shown to significantly differ from its special case. Indeed, outer approximation approaches for CDC need be substantially modified in order to cope with the more general problem, bringing to new algorithms. We develop a hierarchy of conditions that guarantee global convergence, and we build three different cutting plane algorithms relying on them.     

Robust model selection for a semimartingale continuous time regression from discrete data

The paper considers the problem of estimating a periodic function in a continuous time regression model observed under a general semimartingale noise with an unknown distribution in the case when continuous observation cannot be provided and only discrete time measurements are available. Two specific types of noises are studied in detail: a non-Gaussian Ornstein–Uhlenbeck process and a time-varying linear combination of a Brownian motion and compound Poisson process. We develop new analytical tools to treat the adaptive estimation problems from discrete data. A lower bound for the frequency sampling, needed for the efficiency of the procedure constructed by discrete observations, has been found. Sharp non-asymptotic oracle inequalities for the robust quadratic risk have been derived. New convergence rates for the efficient procedures have been obtained. An example of the regression with a martingale noise exhibits that the minimax robust convergence rate may be both higher or lower as compared with the minimax rate for the “white noise” model. The results of Monte-Carlo simulations are given.     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

Reducibility of minimax to minisum 0–1 programming problems

We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion.     

A Lower Bound for the Penalty Parameter in the Exact Minimax Penalty Function Method for Solving Nondifferentiable Extremum Problems

In the paper, we consider the exact minimax penalty function method used for solving a general nondifferentiable extremum problem with both inequality and equality constraints. We analyze the relationship between an optimal solution in the given constrained extremum problem and a minimizer in its associated penalized optimization problem with the exact minimax penalty function under the assumption of convexity of the functions constituting the considered optimization problem (with the exception of those equality constraint functions for which the associated Lagrange multipliers are negative—these functions should be assumed to be concave). The lower bound of the penalty parameter is given such that, for every value of the penalty parameter above the threshold, the equivalence holds between the set of optimal solutions in the given extremum problem and the set of minimizers in its associated penalized optimization problem with the exact minimax penalty function.     

Minimizing maximum risk for fair network connection with interval data

In this paper we introduce a minimax model for network connection problems with interval parameters. We consider how to connect given nodes in a network with a path or a spanning tree under a given budget, where each link is associated with an interval and can be established at a cost of any value in the interval. The quality of an individual link （or the risk of link failure, etc.） depends on its construction cost and associated interval. To achieve fairness of the network connection, our model aims at the minimization of the maximum risk over all links used. We propose two algorithms that find optimal paths and spanning trees in polynomial time, respectively. The polynomial solvability indicates salient difference between our minimax model and the model of robust deviation criterion for network connection with interval data, which gives rise to NP-hard optimization problems.     

Error bounds of two smoothing approximations for semi-infinite minimax problems

In the paper we investigate smoothing method for solving semi-infinite minimax problems. Not like most of the literature in semi-infinite minimax problems which are concerned with the continuous time version（i.e., the one dimensional semi-infinite minimax problems）, the primary focus of this paper is on multi- dimensional semi-infinite minimax problems. The global error bounds of two smoothing approximations for the objective function are given and compared. It is proved that the smoothing approximation given in this paper can provide a better error bound than the existing one in literature.     

On the characterization of fisher information and stability of the least favorable lattice distributions

The paper is concerned with the stability properties of the least favorable distributions minimizing the Fisher information in a given class of distributions. The derivation of a least favorable distribution (the solution of a variational problem) is a necessary stage of the Huber minimax approach in robust estimation of a location parameter. Generally, the solutions of variational problems essentially depend on the regularity restrictions of a functional class. The stability of these optimal solutions to violations of the smoothness restrictions is studied under the lattice distribution classes. The discrete analogues of Fisher information are obtained in these cases. They have the form of the Hellinger metrics with the estimation of a real continuous location parameter and the form of the X² metrics with the estimation of an integer discrete location parameter. The analytical expressions for the corresponding least favorable discrete distributions are derived in some classes of lattice distributions by means of generating functions and Bellman's recursive functional equations of dynamic programming. These classes include the class of nondegenerate distributions with a restriction on the value of the density in the center of symmetry, the class of finite distributions, and the class of contaminated distributions. The obtained least favorable lattice distributions preserve the structure of their prototypes in the continuous case. These results show the stability of robust minimax solutions under different types of transitions from the continuous distribution to the discrete one. Proceedings of the Seminar on Stability Problems for Stochastic Models, Hajduszoboszló, Hungary, 1997, Part II.     

The root–unroot algorithm for density estimation as implemented via wavelet block thresholding

We propose and implement a density estimation procedure which begins by turning density estimation into a nonparametric regression problem. This regression problem is created by binning the original observations into many small size bins, and by then applying a suitable form of root transformation to the binned data counts. In principle many common nonparametric regression estimators could then be applied to the transformed data. We propose use of a wavelet block thresholding estimator in this paper. Finally, the estimated regression function is un-rooted by squaring and normalizing. The density estimation procedure achieves simultaneously three objectives: computational efficiency, adaptivity, and spatial adaptivity. A numerical example and a practical data example are discussed to illustrate and explain the use of this procedure. Theoretically it is shown that the estimator simultaneously attains the optimal rate of convergence over a wide range of the Besov classes. The estimator also automatically adapts to the local smoothness of the underlying function, and attains the local adaptive minimax rate for estimating functions at a point. There are three key steps in the technical argument: Poissonization, quantile coupling, and oracle risk bound for block thresholding in the non-Gaussian setting. Some of the technical results may be of independent interest.     

An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions

We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function.     

Hyperbolic smoothing function method for minimax problems

In this article, an approach for solving finite minimax problems is proposed. This approach is based on the use of hyperbolic smoothing functions. In order to apply the hyperbolic smoothing we reformulate the objective function in the minimax problem and study the relationship between the original minimax and reformulated problems. We also study main properties of the hyperbolic smoothing function. Based on these results an algorithm for solving the finite minimax problem is proposed and this algorithm is implemented in general algebraic modelling system. We present preliminary results of numerical experiments with well-known nonsmooth optimization test problems. We also compare the proposed algorithm with the algorithm that uses the exponential smoothing function as well as with the algorithm based on nonlinear programming reformulation of the finite minimax problem.     

A note on some analytic center cutting plane methods for convex feasibility and minimization problems

Recently Goffin, Luo and Ye have analyzed the complexity of an analytic center algorithm for convex feasibility problems defined by a separation oracle. The oracle is called at the (possibly approximate) analytic center of the set given by the linear inequalities which are the previous answers of the oracle. We discuss oracles for the problem of minimizing a convex (possibly nondifferentiable) function subject to box constraints, and give corresponding complexity estimates.The research of the first author is supported by the Polish Academy of Sciences; the research of the second author is supported by the State Committee for Scientific Research under Grant 8S50502206.     

Double Shrinkage Estimators in the GMANOVA Model

In the GMANOVA model or equivalent growth curve model, shrinkage effects on the MLE (maximum likelihood estimator) are considered under an invariant risk matrix. We first study the fundamental structure of the problem through which we decompose the estimation problem into some conditional problems and then demonstrate some classes of double shrinkage minimax estimators which uniformly dominate the MLE in the matrix risk.