Worst Case Complexity of Problems with Random Information Noise

We study the worst case complexity of solving problems for which information is partial and contaminated by random noise. It is well known that if information is exact then adaption does not help for solving linear problems, i.e., for approximating linear operators over convex and symmetric sets. On the other hand, randomization can sometimes help significantly. It turns out that for noisy information, adaption may lead to much better approximations than nonadaption, even for linear problems. This holds because, in the presence of noise, adaption is equivalent to randomization. We present sharp bounds on the worst case complexity of problems with random noise in terms of the randomized complexity with exact information. The results obtained are applied to thed-variate integration andL_∞-approximation of functions belonging to Hölder and Sobolev classes. Information is given by function evaluations with Gaussian noise of variance σ². For exact information, the two problems are intractable since the complexity is proportional to (1/ε)^qwhereqgrows linearly withd. For noisy information the situation is different. For integration, the ε-complexity is of order σ²/ε²as ε goes to zero. Hence the curse of dimensionality is broken due to random noise. for approximation, the complexity is of order σ²(1/ε)^q+2ln(1/ε), and the problem is intractable also with random noise.     

Measure Theoretic Results for Approximation by Neural Networks with Limited Weights

In this article, we study approximation properties of single hidden layer neural networks with weights varying in finitely many directions and with thresholds from an open interval. We obtain a necessary and simultaneously su?cient measure theoretic condition for density of such networks in the space of continuous functions. Further, we prove a density result for neural networks with a specifically constructed activation function and a fixed number of neurons.     

Optimal Asset Allocation: A Worst Scenario Expectation Approach

Mean-variance criterion has long been the main stream approach in the optimal portfolio theory. The investors try to balance the risk and the return on their portfolio. In this paper, the deviation of the asset return from the investor’s expectation in the worst scenario is used as the measure of risk for portfolio selection. One important advantage of this approach is that the investors can base on their own knowledge, information, and preference on various risks, in addition to the asset’s volatility, to adjust their exposure to various risks. It also pinpoints one main concern of the investors when they invest, the amount they lose in the worst situation.     

Approximation of Neural Network Dynamics by Reaction-Diffusion Equations

The equations of the Hopfield network, without the constraint of symmetry, can have complex behaviours. Cottet borrowed techniques from particle methods to show that a class of such networks with symmetric, translation-invariant connection matrices may be approximated by a reaction–diffusion equation. This idea is extended to a wider class of network connections yielding a slightly more complex reaction–diffusion equation. It is also shown that the approximation holds rigorously only in certain spatial regions (even for Cottet's special case) but the small regions where it fails, namely within transition layers between regions of high and low activity, are not likely to be critical.     

Approximation by Max-Product Neural Network Operators of Kantorovich Type

In the present paper, we develop the theory of max-product neural network operators in a Kantorovich-type version, which is suitable in order to study the case of L^p-approximation for not necessarily continuous data. Moreover, also the case of the pointwise and uniform approximation of continuous functions is considered. Finally, several examples of sigmoidal functions for which the above theory can be applied are presented.     

神经网络的函数逼近能力分析

本文综述了多层前传网络（ＭＬＰ）及径向基函数网络（ＲＢＦ）对函数任意精度逼近的能力，比较了两种网络的最佳逼近特性。对激活函数类的扩充作了介绍，并说明有限数值精度对函数逼近能力实现的影响。     

Approximation and Complexity II: Iterated Integration

We introduce two classes of real analytic functions W \subset U on an interval. Starting with rational functions to construct functions in W we allow the application of three types of operations: addition, integration, and multiplication by a polynomial with rational coefficients. In a similar way, to construct functions in U we allow integration, addition, and multiplication of functions already constructed in U and multiplication by rational numbers. Thus, U is a subring of the ring of Pfaffian functions [7]. Two lower bounds on the L _∈fty -norm are proved on a function f from W (or from U , respectively) in terms of the complexity of constructing f .     

L~p空间中神经网络逼近的几何速度

该文主要研究了L~p空间中神经网络逼近的几何速度.将凸贪婪迭代法应用于L~p空间中满足"δ-角度的条件"的一类函数.作者将文献的结论推广到L~p空间中,得到当0q1时人工神经网络逼近的速度是o(q~n).     

Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.     

由斜坡函数激发的神经网络算子逼近

首先,引入一种由斜坡函数激发的神经网络算子,建立了其对连续函数逼近的正、逆定理,给出了其本质逼近阶.其次,引入这种神经网络算子的线性组合以提高逼近阶,并且研究了这种组合的同时逼近问题.最后,利用Steklov函数构造了一种新的神经网络算子,建立了其在L~p[a,b]空间逼近的正、逆定理.     

Toward Best Approximation of Nonlinear Systems: A Case of Models with Memory

The problem of nonlinear dynamical system modeling, considered in this paper, is motivated by restrictions arising in real-world tasks. The restrictions are that first, a system input cannot be entirely observed for one trial. Second, the system model must be subjected to the causality principle. Third, the input is corrupted by noise so that no relationship between the reference input and noise is known. Fourth, the model should have some degrees of freedom so that the associated accuracy can be regulated by a variation of these freedom degrees. We propose and justify new procedures for the nonlinear system modeling that are initialized by these motivations. The models are nonlinear and given by so called r-degree operators that can be reduced to a matrix form presentation. To satisfy the restrictions above, the matrices have special structures that we call the lower p-band matrices. The degree r of the models is the required degree of freedom. The rigorous analysis of errors associated with the presented techniques is given. Numerical experiments with real data demonstrate the efficiency of the proposed approach.     

Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Worst Case Setting

We consider approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces with finite-order weights. This means we consider functions of d variables that can be represented as sums of functions of at most q^* variables. Here, q^* is fixed (and presumably small) and d may be arbitrarily large. For the univariate problem, d = 1, we assume we know algorithms A1,ε that use O(ε−p) function or linear functional evaluations to achieve an error ε in the worst case setting. Based on these algorithms A_1,ε, we provide a construction of polynomial-time algorithms A_d,ε for the general d-variate problem with the number of evaluations bounded roughly by ε^−pd^q* to achieve an error ε in the worst case setting.     

On the Approximation of the SABR with Mean Reversion Model: A Probabilistic Approach

Abstract

In this paper, we study the stochastic alpha beta rho with mean reversion model (SABR-MR). We first compare the SABR model with the SABR-MR model in terms of future volatility to point out the fundamental difference in the models’ dynamics. We then derive an efficient probabilistic approximation for the SABR-MR model to price European options. Similar to the method derived in Kennedy, J. E., Mitra, S., & Pham, D. (2012). On the approximation of the SABR model: A probabilistic approach. Applied Mathematical Finance, 19(6), 553–586., we focus on capturing the terminal distribution of the underlying asset (conditional on the terminal volatility) to arrive at the implied volatilities of the corresponding European options for all strikes and maturities. Our resulting method allows us to work with a wide range of parameters that cover the long-dated option and different market conditions.     

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.     

Stochastic Approximation in Real Time: A Pipe Line Approach

1.IntroductionTheobjectiveofthisworkistostudystochasticapproximationinrea1time.Apipelineapproachissuggested.Asymptoticpropertiesoftheprocedurearedeve1oped,andcomparisonsofrateofconvergencewiththeclassicalalgorithmsaremade.LetxeE',andf(.):EL-FL-Thetraditio…     

Lagrange Interpolation for the Disk Algebra: The Worst Case

We consider Lagrange interpolation polynomials for functions in the disk algebra with nodes on the boundary of the unit disk. In case that the closure of the set of nodes does not cover the boundary of the unit disk we prove that there exists a residual set of functions in the disk algebra, such that the Lagrange interpolation polynomials of each of these functions form a dense subset of the space of all holomorphic functions defined on the unit disk.