Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

A unified approach for minimizing composite norms

We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem $$\begin{aligned} \begin{array}{ll} \min \limits _{X\in \mathbb{R }^{m\times n}}&\mu _1\Vert \sigma (\mathcal{F }(X)-G)\Vert _\alpha +\mu _2\Vert \mathcal{C }(X)-d\Vert _\beta ,\\ \text{ subject} \text{ to}&\mathcal{A }(X)-b\in \mathcal{Q }, \end{array} \end{aligned}$$ where $\sigma (X)$ denotes the vector of singular values of $X \in \mathbb{R }^{m\times n}$ , the matrix norm $\Vert \sigma (X)\Vert _{\alpha }$ denotes either the Frobenius, the nuclear, or the $\ell _2$ -operator norm of $X$ , the vector norm $\Vert .\Vert _{\beta }$ denotes either the $\ell _1$ -norm, $\ell _2$ -norm or the $\ell _{\infty }$ -norm; $\mathcal{Q }$ is a closed convex set and $\mathcal{A }(.)$ , $\mathcal{C }(.)$ , $\mathcal{F }(.)$ are linear operators from $\mathbb{R }^{m\times n}$ to vector spaces of appropriate dimensions. Basis pursuit, matrix completion, robust principal component pursuit (PCP), and stable PCP problems are all special cases of the composite norm minimization problem. Thus, FALC is able to solve all these problems in a unified manner. We show that any limit point of FALC iterate sequence is an optimal solution of the composite norm minimization problem. We also show that for all $\epsilon >0$ , the FALC iterates are $\epsilon $ -feasible and $\epsilon $ -optimal after $\mathcal{O }(\log (\epsilon ^{-1}))$ iterations, which require $\mathcal{O }(\epsilon ^{-1})$ constrained shrinkage operations and Euclidean projection onto the set $\mathcal{Q }$ . Surprisingly, on the problem sets we tested, FALC required only $\mathcal{O }(\log (\epsilon ^{-1}))$ constrained shrinkage, instead of the $\mathcal{O }(\epsilon ^{-1})$ worst case bound, to compute an $\epsilon $ -feasible and $\epsilon $ -optimal solution. To best of our knowledge, FALC is the first algorithm with a known complexity bound that solves the stable PCP problem.     

Subgame perfect equilibria in stopping games

Stopping games (without simultaneous stopping) are multi-player sequential games in which at every stage one of the players is chosen according to a stochastic process, and that player decides whether to continue the interaction or to stop it, whereby the terminal payoff vector is obtained by another stochastic process. We prove that if the payoff process is integrable, a $\delta $ -approximate subgame perfect ${\epsilon }$ -equilibrium exists for every $\delta ,\epsilon >0$ ; that is, there exists a strategy profile that is an ${\epsilon }$ -equilibrium in all subgames, except possibly in a set of subgames that occurs with probability at most $\delta $ (even after deviation by some of the players).     

On the sup-norm of Maass cusp forms of large level. III

Let $f$ be a Hecke–Maass cuspidal newform of square-free level $N$ and Laplacian eigenvalue $\lambda $ . It is shown that $\left||f \right||_\infty \ll _{\lambda ,\epsilon } N^{-\frac{1}{6}+\epsilon } \left||f \right||_2$ for any $\epsilon >0$ .     

Clock synchronization in symmetric stochastic networks

We consider a stochastic model of clock synchronization in a wireless network of $N$ sensors interacting with one dedicated accurate time server. For large $N$ we find an estimate of the final time sychronization error for global and relative synchronization. The main results concern the behavior of the network on different timescales $t_{N}\rightarrow \infty $ , $N\rightarrow \infty $ . We discuss the existence of phase transitions and find the exact timescales for which an effective clock synchronization of the system takes place.     

Donsker-type theorems for nonparametric maximum likelihood estimators

Let ${\mathcal{P}}$ be a nonparametric probability model consisting of smooth probability densities and let ${\hat{p}_{n}}$ be the corresponding maximum likelihood estimator based on n independent observations each distributed according to the law ${\mathbb{P}}$ . With $\hat{\mathbb{P}}_{n}$ denoting the measure induced by the density ${\hat{p}_{n}}$ , define the stochastic process ${\hat{\nu}}_{n}: f\longmapsto \sqrt{n} \int fd({\hat{\mathbb{P}}}_{n} -\mathbb{P})$ where f ranges over some function class ${\mathcal{F}}$ . We give a general condition for Donsker classes ${\mathcal{F}}$ implying that the stochastic process $\hat{\nu}_{n}$ is asymptotically equivalent to the empirical process in the space ${\ell ^{\infty }(\mathcal{F})}$ of bounded functions on ${ \mathcal{F}}$ . This implies in particular that $\hat{\nu}_{n}$ converges in law in ${\ell ^{\infty }(\mathcal{F})}$ to a mean zero Gaussian process. We verify the general condition for a large family of Donsker classes ${\mathcal{ F}}$ . We give a number of applications: convergence of the probability measure ${\hat{\mathbb{P}}_{n}}$ to ${\mathbb{P}}$ at rate ${\sqrt{n}}$ in certain metrics metrizing the topology of weak(-star) convergence; a unified treatment of convergence rates of the MLE in a continuous scale of Sobolev-norms; ${\sqrt{n}}$ -efficient estimation of nonlinear functionals defined on ${\mathcal{P}}$ ; limit theorems at rate ${\sqrt{n}}$ for the maximum likelihood estimator of the convolution product ${\mathbb{P\ast P}}$ .     

A subelliptic analogue of Aronson–Serrin’s Harnack inequality

We study the Harnack inequality for weak solutions of a class of degenerate parabolic quasilinear PDE $$\begin{aligned} \partial _t u={-}X_i^* A_i(x,t,u,Xu)+ B(x,t,u,Xu), \end{aligned}$$ in cylinders $\Omega \times (0,T)$ where $\Omega \subset M$ is an open subset of a manifold $M$ endowed with control metric $d$ corresponding to a system of Lipschitz continuous vector fields $X=(X_1,\ldots ,X_m)$ and a measure $d\sigma $ . We show that the Harnack inequality follows from the basic hypothesis of doubling condition and a weak Poincaré inequality in the metric measure space $(M,d,d\sigma )$ . We also show that such hypothesis hold for a class of Riemannian metrics $g_\epsilon $ collapsing to a sub-Riemannian metric $\lim _{\epsilon \rightarrow 0} g_\epsilon =g_0$ uniformly in the parameter $\epsilon \ge 0$ .     

Local linear estimation for stochastic processes driven by \alpha -stable L\acute{\mathbf{e}}vy motion

The $\alpha $ α -stable L $\acute{\mathrm{e}}$ e ´ vy motion together with the Poisson process and Brownian motion are the most important examples of L $\acute{\mathrm{e}}$ e ´ vy processes, which form the first class of stochastic processes being studied in the modern spirit. In this paper, the stochastic processes driven by $\alpha $ α -stable L $\acute{\mathrm{e}}$ e ´ vy motion are considered, local linear estimator of the drift function for these processes is discussed. Under mild conditions, we derive consistency of the local linear estimator of the drift function. The performance of the proposed estimator is assessed by simulation study.     

Optimal L^2, H^1 and L^\infty analysis of finite volume methods for the stationary Navier–Stokes equations with large data

Previous work on the stability and convergence analysis of numerical methods for the stationary Navier–Stokes equations was carried out under the uniqueness condition of the solution, which required that the data be small enough in certain norms. In this paper an optimal analysis for the finite volume methods is performed for the stationary Navier–Stokes equations, which relaxes the solution uniqueness condition and thus the data requirement. In particular, optimal order error estimates in the $H^1$ -norm for velocity and the $L^2$ -norm for pressure are obtained with large data, and a new residual technique for the stationary Navier–Stokes equations is introduced for the first time to obtain a convergence rate of optimal order in the $L^2$ -norm for the velocity. In addition, after proving a number of additional technical lemmas including weighted $L^2$ -norm estimates for regularized Green’s functions associated with the Stokes problem, optimal error estimates in the $L^\infty $ -norm are derived for the first time for the velocity gradient and pressure without a logarithmic factor $O(|\log h|)$ for the stationary Naiver–Stokes equations.     

Pareto–Fenchel {\epsilon} -subdifferential sum rule and {\epsilon} -efficiency

The paper is centered around a sum rule for the efficient (Pareto) ${\epsilon}$ -subdifferential of two convex vector mappings, having the property to be exact under a qualification condition. Such a formula has not been explored previously. Our formula which holds under the Attouch?CBrézis as well as Moreau?CRockafellar conditions, reveals strangely a primordial presence of the convex (Fenchel) ${\epsilon}$ -subdifferential. This appearance turns out to be rather favorable. This effectively permits to derive approximate efficiency conditions in terms of Pareto subgradient and vectorial normal cone, which completely characterizes an ${\epsilon}$ -efficient solution in constrained convex vector optimization in (partially) ordered spaces. Our sum rule also allows a fundamental deduction of relation between Pareto and Fenchel ${\epsilon}$ -subdifferentials, which, in reality, brings out a certain gap linking ${\epsilon}$ -efficiency with ${\epsilon}$ -optimality. Scalarization approaches in connection with ${\epsilon}$ -subdifferentials are first established by simple proofs. This principle has contributed for a large part, not only for discovering the sum formula, but also for establishing some punctual necessary and/or sufficient conditions for Pareto ${\epsilon}$ -subdifferentiability.     

Averaged Pointwise Bounds for Deformations of Schrödinger Eigenfunctions

Let (M,g) be an n-dimensional, compact Riemannian manifold and ${P_0(\hbar) = -\hbar{^2} \Delta_g + V(x)}$ be a semiclassical Schrödinger operator with ${\hbar \in (0,\hbar_0]}$ . Let ${E(\hbar) \in [E-o(1),E+o(1)]}$ and ${(\phi_{\hbar})_{\hbar \in (0,\hbar_0]}}$ be a family of L ²-normalized eigenfunctions of ${P_0(\hbar)}$ with ${P_0(\hbar) \phi_{\hbar} = E(\hbar) \phi_{\hbar}}$ . We consider magnetic deformations of ${P_0(\hbar)}$ of the form ${P_u(\hbar) = - \Delta_{\omega_u}(\hbar) + V(x)}$ , where ${\Delta_{\omega_u}(\hbar) = (\hbar d + i \omega_u(x))^*({\hbar}d + i \omega_u(x))}$ . Here, u is a k-dimensional parameter running over ${B^k(\epsilon)}$ (the ball of radius ${\epsilon}$ ), and the family of the magnetic potentials ${(w_u)_{u\in B^k(\epsilon)}}$ satisfies the admissibility condition given in Definition 1.1. This condition implies that k ≥ n and is generic under this assumption. Consider the corresponding family of deformations of ${(\phi_{\hbar})_{\hbar \in (0, \hbar_0]}}$ , given by ${(\phi^u_{\hbar})_{\hbar \in(0, \hbar_0]}}$ , where $$\phi_{\hbar}^{(u)}:= {\rm e}^{-it_0 P_u(\hbar)/\hbar}\phi_{\hbar}$$ for ${|t_0|\in (0,\epsilon)}$ ; the latter functions are themselves eigenfunctions of the ${\hbar}$ -elliptic operators ${Q_u(\hbar): ={\rm e}^{-it_0P_u(\hbar)/\hbar} P_0(\hbar) {\rm e}^{it_0 P_u(\hbar)/\hbar}}$ with eigenvalue ${E(\hbar)}$ and ${Q_0(\hbar) = P_{0}(\hbar)}$ . Our main result, Theorem1.2, states that for ${\epsilon >0 }$ small, there are constants ${C_j=C_j(M,V,\omega,\epsilon) > 0}$ with j = 1,2 such that $$C_{1}\leq \int\limits_{\mathcal{B}^k(\epsilon)} |\phi_{\hbar}^{(u)}(x)|^2 \, {\rm d}u \leq C_{2}$$ , uniformly for ${x \in M}$ and ${\hbar \in (0,h_0]}$ . We also give an application to eigenfunction restriction bounds in Theorem 1.3.     

The convex hull of the lattice points inside a curve

Let $C$ be a smooth convex closed plane curve. The $C$ -ovals $C(R,u,v)$ are formed by expanding by a factor  $R$ , then translating by  $(u,v)$ . The number of vertices $V(R,u,v)$ of the convex hull of the integer points within or on  $C(R,u,v)$ has order  $R^{2/3}$ (Balog and Bárány) and has average size $BR^{2/3}$ as $R$ varies (Balog and Deshouillers). We find the space average of  $V(R,u,v)$ over vectors  $(u,v)$ to be  $BR^{2/3}$ with an explicit coefficient  $B$ , and show that the average over  $R$ has the same  $B$ . The proof involves counting edges and finding the domain $D(q,a)$ of an integer vector, the set of  $(u,v)$ for which the convex hull has a directed edge parallel to  $(q,a)$ . The resulting sum over bases of the integer lattice is approximated by a triple integral.     

Convergence of the eigenvalues of the p-Laplace operator as p goes to 1

Let $(\lambda ^k_p)_k$ be the usual sequence of min-max eigenvalues for the $p$ -Laplace operator with $p\in (1,\infty )$ and let $(\lambda ^k_1)_k$ be the corresponding sequence of eigenvalues of the 1-Laplace operator. For bounded $\Omega \subseteq \mathbb{R }^n$ with Lipschitz boundary the convergence $\lambda ^k_p\rightarrow \lambda ^k_1$ as $p\rightarrow 1$ is shown for all $k\in \mathbb{N }$ . The proof uses an approximation of $BV(\Omega )$ -functions by $C_0^\infty (\Omega )$ -functions in the sense of strict convergence on $\mathbb{R }^n$ .     

A characterization of {\square(\kappa^{+})} in extender models

We prove that, in any fine structural extender model with Jensen’s λ-indexing, there is a ${\square(\kappa^{+})}$ -sequence if and only if there is a pair of stationary subsets of ${\kappa^{+} \cap {\rm {cof}}( < \kappa)}$ without common reflection point of cofinality ${ < \kappa}$ which, in turn, is equivalent to the existence of a family of size ${ < \kappa}$ of stationary subsets of ${\kappa^{+} \cap {\rm {cof}}( < \kappa)}$ without common reflection point of cofinality ${ < \kappa}$ . By a result of Burke/Jensen, ${\square_\kappa}$ fails whenever ${\kappa}$ is a subcompact cardinal. Our result shows that in extender models, it is still possible to construct a canonical ${\square(\kappa^{+})}$ -sequence where ${\kappa}$ is the first subcompact.     

The Saito–Kurokawa lifting and Darmon points

Let $E_{/_\mathbb{Q }}$ be an elliptic curve of conductor $Np$ with $p\not \mid N$ and let $f$ be its associated newform of weight $2$ . Denote by $f_\infty $ the $p$ -adic Hida family passing though $f$ , and by $F_\infty $ its $\varLambda $ -adic Saito–Kurokawa lift. The $p$ -adic family $F_\infty $ of Siegel modular forms admits a formal Fourier expansion, from which we can define a family of normalized Fourier coefficients $\{\widetilde{A}_T(k)\}_T$ indexed by positive definite symmetric half-integral matrices $T$ of size $2\times 2$ . We relate explicitly certain global points on $E$ (coming from the theory of Darmon points) with the values of these Fourier coefficients and of their $p$ -adic derivatives, evaluated at weight $k=2$ .     

SIP: critical value functions have finite modulus of non-convexity

We consider semi-infinite programming problems ${{\rm SIP}(z)}$ depending on a finite dimensional parameter ${z \in \mathbb{R}^p}$ . Provided that ${\bar{x}}$ is a strongly stable stationary point of ${{\rm SIP}(\bar{z})}$ , there exists a locally unique and continuous stationary point mapping ${z \mapsto x(z)}$ . This defines the local critical value function ${\varphi(z) := f(x(z); z)}$ , where ${x \mapsto f(x; z)}$ denotes the objective function of ${{\rm SIP}(z)}$ for a given parameter vector ${z\in \mathbb{R}^p}$ . We show that ${\varphi}$ is the sum of a convex function and a smooth function. In particular, this excludes the appearance of negative kinks in the graph of ${\varphi}$ .     

Computable representations for convex hulls of low-dimensional quadratic forms

Let ${\mathcal{C}}$ be the convex hull of points ${{\{{1 \choose x}{1 \choose x}^T \,|\, x\in \mathcal{F}\subset \Re^n\}}}$ . Representing or approximating ${\mathcal{C}}$ is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if n ≤ 4 and ${\mathcal{F}}$ is a simplex, then ${\mathcal{C}}$ has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). We also prove that if n = 2 and ${\mathcal{F}}$ is a box, then ${\mathcal{C}}$ has a representation that combines semidefiniteness with constraints on product terms obtained from the reformulation-linearization technique (RLT). The simplex result generalizes known representations for the convex hull of ${{\{(x_1, x_2, x_1x_2)\,|\, x\in\mathcal{F}\}}}$ when ${\mathcal{F}\subset\Re^2}$ is a triangle, while the result for box constraints generalizes the well-known fact that in this case the RLT constraints generate the convex hull of ${{\{(x_1, x_2, x_1x_2)\,|\, x\in\mathcal{F}\}}}$ . When n = 3 and ${\mathcal{F}}$ is a box, we show that a representation for ${\mathcal{C}}$ can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube.     

Creature forcing and large continuum: the joy of halving

For ${f,g\in\omega^\omega}$ let ${c^\forall_{f,g}}$ be the minimal number of uniform g-splitting trees needed to cover the uniform f-splitting tree, i.e., for every branch ν of the f-tree, one of the g-trees contains ν. Let ${c^\exists_{f,g}}$ be the dual notion: For every branch ν, one of the g-trees guesses ν(m) infinitely often. We show that it is consistent that ${c^\exists_{f_\epsilon,g_\epsilon}{=}c^\forall_{f_\epsilon,g_\epsilon}{=}\kappa_\epsilon}$ for continuum many pairwise different cardinals ${\kappa_\epsilon}$ and suitable pairs ${(f_\epsilon,g_\epsilon)}$ . For the proof we introduce a new mixed-limit creature forcing construction.     

The Moduli Space of Riemann Surfaces of Large Genus

Let ${\mathcal{M}_{g,\epsilon}}$ be the ${\epsilon}$ -thick part of the moduli space ${\mathcal{M}_g}$ of closed genus g surfaces. In this article, we show that the number of balls of radius r needed to cover ${\mathcal{M}_{g,\epsilon}}$ is bounded below by ${(c_1g)^{2g}}$ and bounded above by ${(c_2g)^{2g}}$ , where the constants c ₁, c ₂depend only on ${\epsilon}$ and r, and in particular not on g. Using this counting result we prove that there are Riemann surfaces of arbitrarily large injectivity radius that are not close (in the Teichmüller metric) to a finite cover of a fixed closed Riemann surface. This result illustrates the sharpness of the Ehrenpreis conjecture.     

On the Generality of Assuming that a Family of Continuous Functions Separates Points

For an algebra ${\mathcal{A}}$ of complex-valued, continuous functions on a compact Hausdorff space (X, τ), it is standard practice to assume that ${\mathcal{A}}$ separates points in the sense that for each distinct pair ${x, y \in X}$ , there exists an ${f \in \mathcal{A}}$ such that ${f(x) \neq f(y)}$ . If ${\mathcal{A}}$ does not separate points, it is known that there exists an algebra ${\widehat{\mathcal{A}}}$ on a compact Hausdorff space ${(\widehat{X}, \widehat{\tau})}$ that does separate points such that the map ${\mathcal{A} \mapsto \widehat{\mathcal{A}}}$ is a uniform norm isometric algebra isomorphism. So it is, to a degree, without loss of generality that we assume ${\mathcal{A}}$ separates points. The construction of ${{\widehat{\mathcal{A}}}}$ and ${(\widehat{X}, \widehat{\tau})}$ does not require that ${\mathcal{A}}$ has any algebraic structure nor that ${(X, \tau)}$ has any properties, other than being a topological space. In this work we develop a framework for determining the degree to which separation of points may be assumed without loss of generality for any family ${\mathcal{A}}$ of bounded, complex-valued, continuous functions on any topological space ${(X, \tau)}$ . We also demonstrate that further structures may be preserved by the mapping ${\mathcal{A} \mapsto \widehat{\mathcal{A}}}$ , such as boundaries of weak peak points, the Lipschitz constant when the functions are Lipschitz on a compact metric space, and the involutive structure of real function algebras on compact Hausdorff spaces.