-
Robust Reward Design for Markov Decision Processes
Authors:
Shuo Wu,
Haoxiang Ma,
Jie Fu,
Shuo Han
Abstract:
The problem of reward design examines the interaction between a leader and a follower, where the leader aims to shape the follower's behavior to maximize the leader's payoff by modifying the follower's reward function. Current approaches to reward design rely on an accurate model of how the follower responds to reward modifications, which can be sensitive to modeling inaccuracies. To address this…
▽ More
The problem of reward design examines the interaction between a leader and a follower, where the leader aims to shape the follower's behavior to maximize the leader's payoff by modifying the follower's reward function. Current approaches to reward design rely on an accurate model of how the follower responds to reward modifications, which can be sensitive to modeling inaccuracies. To address this issue of sensitivity, we present a solution that offers robustness against uncertainties in modeling the follower, including 1) how the follower breaks ties in the presence of nonunique best responses, 2) inexact knowledge of how the follower perceives reward modifications, and 3) bounded rationality of the follower. Our robust solution is guaranteed to exist under mild conditions and can be obtained numerically by solving a mixed-integer linear program. Numerical experiments on multiple test cases demonstrate that our solution improves robustness compared to the standard approach without incurring significant additional computing costs.
△ Less
Submitted 7 June, 2024;
originally announced June 2024.
-
A study guide for "On the Hausdorff dimension of Furstenberg sets and orthogonal projections in the plane" after T. Orponen and P. Shmerkin
Authors:
Jacob B. Fiedler,
Guo-Dong Hong,
Donggeun Ryou,
Shukun Wu
Abstract:
This article is a study guide for ``On the Hausdorff dimension of Furstenberg sets and orthogonal projections in the plane" by Orponen and Shmerkin. We begin by introducing Furstenberg set problem and exceptional set of projections and provide a summary of the proof with the core ideas.
This article is a study guide for ``On the Hausdorff dimension of Furstenberg sets and orthogonal projections in the plane" by Orponen and Shmerkin. We begin by introducing Furstenberg set problem and exceptional set of projections and provide a summary of the proof with the core ideas.
△ Less
Submitted 6 June, 2024;
originally announced June 2024.
-
Orthogonal Causal Calibration
Authors:
Justin Whitehouse,
Christopher Jung,
Vasilis Syrgkanis,
Bryan Wilder,
Zhiwei Steven Wu
Abstract:
Estimates of causal parameters such as conditional average treatment effects and conditional quantile treatment effects play an important role in real-world decision making. Given this importance, one should ensure these estimators are calibrated. While there is a rich literature on calibrating estimators of non-causal parameters, very few methods have been derived for calibrating estimators of ca…
▽ More
Estimates of causal parameters such as conditional average treatment effects and conditional quantile treatment effects play an important role in real-world decision making. Given this importance, one should ensure these estimators are calibrated. While there is a rich literature on calibrating estimators of non-causal parameters, very few methods have been derived for calibrating estimators of causal parameters, or more generally estimators of quantities involving nuisance parameters.
In this work, we provide a general framework for calibrating predictors involving nuisance estimation. We consider a notion of calibration defined with respect to an arbitrary, nuisance-dependent loss $\ell$, under which we say an estimator $θ$ is calibrated if its predictions cannot be changed on any level set to decrease loss. We prove generic upper bounds on the calibration error of any causal parameter estimate $θ$ with respect to any loss $\ell$ using a concept called Neyman Orthogonality. Our bounds involve two decoupled terms - one measuring the error in estimating the unknown nuisance parameters, and the other representing the calibration error in a hypothetical world where the learned nuisance estimates were true. We use our bound to analyze the convergence of two sample splitting algorithms for causal calibration. One algorithm, which applies to universally orthogonalizable loss functions, transforms the data into generalized pseudo-outcomes and applies an off-the-shelf calibration procedure. The other algorithm, which applies to conditionally orthogonalizable loss functions, extends the classical uniform mass binning algorithm to include nuisance estimation. Our results are exceedingly general, showing that essentially any existing calibration algorithm can be used in causal settings, with additional loss only arising from errors in nuisance estimation.
△ Less
Submitted 3 June, 2024;
originally announced June 2024.
-
Mean Field Limit for Congestion Dynamics in One Dimension
Authors:
Inwon Kim,
Antoine Mellet,
Jeremy Sheung-Him Wu
Abstract:
This paper addresses congested transport, which can be described, at macroscopic scales, by a continuity equation with a pressure variable generated from the hard-congestion constraint (maximum value of the density). The main goal of the paper is to show that, in one spatial dimension, this continuum PDE can be derived as the mean-field limit of a system of ordinary differential equations that des…
▽ More
This paper addresses congested transport, which can be described, at macroscopic scales, by a continuity equation with a pressure variable generated from the hard-congestion constraint (maximum value of the density). The main goal of the paper is to show that, in one spatial dimension, this continuum PDE can be derived as the mean-field limit of a system of ordinary differential equations that describes the motion of a large number of particles constrained to stay at some finite distance from each others. To show that these two models describe the same dynamics at different scale, we will rely on both the Eulerian and Lagrangian points of view and use two different approximations for the density and pressure variables in the continuum limit.
△ Less
Submitted 24 May, 2024;
originally announced May 2024.
-
A robust solver for H(curl) convection-diffusion and its local Fourier analysis
Authors:
Jindong Wang,
Shuonan Wu
Abstract:
In this paper, we present a robust and efficient multigrid solver based on an exponential-fitting discretization for 2D H(curl) convection-diffusion problems. By leveraging an exponential identity, we characterize the kernel of H(curl) convection-diffusion problems and design a suitable hybrid smoother. This smoother incorporates a lexicographic Gauss-Seidel smoother within a downwind type and smo…
▽ More
In this paper, we present a robust and efficient multigrid solver based on an exponential-fitting discretization for 2D H(curl) convection-diffusion problems. By leveraging an exponential identity, we characterize the kernel of H(curl) convection-diffusion problems and design a suitable hybrid smoother. This smoother incorporates a lexicographic Gauss-Seidel smoother within a downwind type and smoothing over an auxiliary problem, corresponding to H(grad) convection-diffusion problems for kernel correction. We analyze the convergence properties of the smoothers and the two-level method using local Fourier analysis (LFA). The performance of the algorithms demonstrates robustness in both convection-dominated and diffusion-dominated cases.
△ Less
Submitted 18 May, 2024;
originally announced May 2024.
-
Full error analysis of the random deep splitting method for nonlinear parabolic PDEs and PIDEs with infinite activity
Authors:
Ariel Neufeld,
Philipp Schmocker,
Sizhou Wu
Abstract:
In this paper, we present a randomized extension of the deep splitting algorithm introduced in [Beck, Becker, Cheridito, Jentzen, and Neufeld (2021)] using random neural networks suitable to approximately solve both high-dimensional nonlinear parabolic PDEs and PIDEs with jumps having (possibly) infinite activity. We provide a full error analysis of our so-called random deep splitting method. In p…
▽ More
In this paper, we present a randomized extension of the deep splitting algorithm introduced in [Beck, Becker, Cheridito, Jentzen, and Neufeld (2021)] using random neural networks suitable to approximately solve both high-dimensional nonlinear parabolic PDEs and PIDEs with jumps having (possibly) infinite activity. We provide a full error analysis of our so-called random deep splitting method. In particular, we prove that our random deep splitting method converges to the (unique viscosity) solution of the nonlinear PDE or PIDE under consideration. Moreover, we empirically analyze our random deep splitting method by considering several numerical examples including both nonlinear PDEs and nonlinear PIDEs relevant in the context of pricing of financial derivatives under default risk. In particular, we empirically demonstrate in all examples that our random deep splitting method can approximately solve nonlinear PDEs and PIDEs in 10'000 dimensions within seconds.
△ Less
Submitted 8 May, 2024;
originally announced May 2024.
-
A Double Maximization Approach for Optimizing the LM Rate of Mismatched Decoding
Authors:
Lingyi Chen,
Shitong Wu,
Xinwei Li,
Huihui Wu,
Hao Wu,
Wenyi Zhang
Abstract:
An approach is established for maximizing the Lower bound on the Mismatch capacity (hereafter abbreviated as LM rate), a key performance bound in mismatched decoding, by optimizing the channel input probability distribution. Under a fixed channel input probability distribution, the computation of the corresponding LM rate is a convex optimization problem. When optimizing the channel input probabil…
▽ More
An approach is established for maximizing the Lower bound on the Mismatch capacity (hereafter abbreviated as LM rate), a key performance bound in mismatched decoding, by optimizing the channel input probability distribution. Under a fixed channel input probability distribution, the computation of the corresponding LM rate is a convex optimization problem. When optimizing the channel input probability distribution, however, the corresponding optimization problem adopts a max-min formulation, which is generally non-convex and is intractable with standard approaches. To solve this problem, a novel dual form of the LM rate is proposed, thereby transforming the max-min formulation into an equivalent double maximization formulation. This new formulation leads to a maximization problem setup wherein each individual optimization direction is convex. Consequently, an alternating maximization algorithm is established to solve the resultant maximization problem setup. Each step of the algorithm only involves a closed-form iteration, which is efficiently implemented with standard optimization procedures. Numerical experiments show the proposed approach for optimizing the LM rate leads to noticeable rate gains.
△ Less
Submitted 1 May, 2024;
originally announced May 2024.
-
A class of maximum-based iteration methods for the generalized absolute value equation
Authors:
Shiliang Wu,
Deren Han,
Cuixia Li
Abstract:
In this paper, by using $|x|=2\max\{0,x\}-x$, a class of maximum-based iteration methods is established to solve the generalized absolute value equation $Ax-B|x|=b$. Some convergence conditions of the proposed method are presented. By some numerical experiments, the effectiveness and feasibility of the proposed method are confirmed.
In this paper, by using $|x|=2\max\{0,x\}-x$, a class of maximum-based iteration methods is established to solve the generalized absolute value equation $Ax-B|x|=b$. Some convergence conditions of the proposed method are presented. By some numerical experiments, the effectiveness and feasibility of the proposed method are confirmed.
△ Less
Submitted 17 April, 2024;
originally announced April 2024.
-
A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
Authors:
Xuetong Li,
Yuan Gao,
Hong Chang,
Danyang Huang,
Yingying Ma,
Rui Pan,
Haobo Qi,
Feifei Wang,
Shuyuan Wu,
Ke Xu,
Jing Zhou,
Xuening Zhu,
Yingqiu Zhu,
Hansheng Wang
Abstract:
This paper presents a selective review of statistical computation methods for massive data analysis. A huge amount of statistical methods for massive data computation have been rapidly developed in the past decades. In this work, we focus on three categories of statistical computation methods: (1) distributed computing, (2) subsampling methods, and (3) minibatch gradient techniques. The first clas…
▽ More
This paper presents a selective review of statistical computation methods for massive data analysis. A huge amount of statistical methods for massive data computation have been rapidly developed in the past decades. In this work, we focus on three categories of statistical computation methods: (1) distributed computing, (2) subsampling methods, and (3) minibatch gradient techniques. The first class of literature is about distributed computing and focuses on the situation, where the dataset size is too huge to be comfortably handled by one single computer. In this case, a distributed computation system with multiple computers has to be utilized. The second class of literature is about subsampling methods and concerns about the situation, where the sample size of dataset is small enough to be placed on one single computer but too large to be easily processed by its memory as a whole. The last class of literature studies those minibatch gradient related optimization techniques, which have been extensively used for optimizing various deep learning models.
△ Less
Submitted 17 March, 2024;
originally announced March 2024.
-
A weighted decoupling inequality and its application to the maximal Bochner-Riesz problem
Authors:
Shengwen Gan,
Shukun Wu
Abstract:
We prove some weighted $L^p\ell^p$-decoupling estimates when $p=2n/(n-1)$. As an application, we give a result beyond the real interpolation exponents for the maximal Bochner-Riesz operator in $\mathbb{R}^3$. We also make an improvement in the planar case.
We prove some weighted $L^p\ell^p$-decoupling estimates when $p=2n/(n-1)$. As an application, we give a result beyond the real interpolation exponents for the maximal Bochner-Riesz operator in $\mathbb{R}^3$. We also make an improvement in the planar case.
△ Less
Submitted 7 March, 2024;
originally announced March 2024.
-
Multiple Boundary Peak Solution for Critical Elliptic System with Neumann Boundary
Authors:
Yuxia Guo,
Shengyu Wu,
TingFeng Yuan
Abstract:
We consider the following elliptic system with Neumann boundary: \begin{equation} \begin{cases} -Δu + μu=v^p, &\hbox{in } Ω, \\-Δv + μv=u^q, &\hbox{in } Ω, \\\frac{\partial u}{\partial n} = \frac{\partial v}{\partial n} = 0, &\hbox{on } \partialΩ, \\u>0,v>0, &\hbox{in } Ω, \end{cases} \end{equation} where $Ω\subset \mathbb{R}^N$ is a smooth bounded domain, $μ$ is a positive constant and $(p,q)$ li…
▽ More
We consider the following elliptic system with Neumann boundary: \begin{equation} \begin{cases} -Δu + μu=v^p, &\hbox{in } Ω, \\-Δv + μv=u^q, &\hbox{in } Ω, \\\frac{\partial u}{\partial n} = \frac{\partial v}{\partial n} = 0, &\hbox{on } \partialΩ, \\u>0,v>0, &\hbox{in } Ω, \end{cases} \end{equation} where $Ω\subset \mathbb{R}^N$ is a smooth bounded domain, $μ$ is a positive constant and $(p,q)$ lies in the critical hyperbola: $$ \dfrac{1}{p+1} + \dfrac{1}{q+1} =\dfrac{N-2}{N}. $$ By using the Lyapunov-Schmidt reduction technique, we establish the existence of infinitely many solutions to above system. These solutions have multiple peaks that are located on the boundary $\partial Ω$. Our results show that the geometry of the boundary $\partialΩ,$ especially its mean curvature, plays a crucial role on the existence and the behaviour of the solutions to the problem.
△ Less
Submitted 26 February, 2024;
originally announced February 2024.
-
Maintenance policy for a system with a weighted linear combination of degradation processes
Authors:
Shaomin Wu,
Inma T. Castro
Abstract:
This paper develops maintenance policies for a system under condition monitoring. We assume that a number of defects may develop and the degradation process of each defect follows a gamma process, respectively. The system is inspected periodically and maintenance actions are performed on the defects present in the system. The effectiveness of the maintenance is assumed imperfect and it is modelled…
▽ More
This paper develops maintenance policies for a system under condition monitoring. We assume that a number of defects may develop and the degradation process of each defect follows a gamma process, respectively. The system is inspected periodically and maintenance actions are performed on the defects present in the system. The effectiveness of the maintenance is assumed imperfect and it is modelled using a geometric process. By performing these maintenance actions, different costs are incurred depending on the type and the degradation levels of the defects. Furthermore, once a linear combination of the degradation processes exceeds a pre-specified threshold, the system needs a special maintenance and an extra cost is imposed. The system is renewed after several preventive maintenance activities have been performed. The main concern of this paper is to optimise the time between renewals and the number of renewals. Numerical examples are given to illustrate the results derived in the paper.
△ Less
Submitted 22 January, 2024;
originally announced January 2024.
-
A bilinear estimate in $\mathbb{F}_p$
Authors:
Necef Kavrut,
Shukun Wu
Abstract:
We improve an $L^2\times L^2\to L^2$ estimate for a certain bilinear operator in the finite field of size $p$, where $p$ is a prime sufficiently large. Our method carefully picks the variables to apply the Cauchy-Schwarz inequality. As a corollary, we show that there exists a quadratic progression $x,x+y,x+y^2$ for nonzero $y$ inside any subset of $\mathbb{F}_p$ of density $\gtrsim p^{-1/8}$
We improve an $L^2\times L^2\to L^2$ estimate for a certain bilinear operator in the finite field of size $p$, where $p$ is a prime sufficiently large. Our method carefully picks the variables to apply the Cauchy-Schwarz inequality. As a corollary, we show that there exists a quadratic progression $x,x+y,x+y^2$ for nonzero $y$ inside any subset of $\mathbb{F}_p$ of density $\gtrsim p^{-1/8}$
△ Less
Submitted 15 January, 2024;
originally announced January 2024.
-
Airline recovery problem under disruptions: A review
Authors:
Shuai Wu,
Enze Liu,
Rui Cao,
Qiang Bai
Abstract:
In practice, both passenger and cargo flights are vulnerable to unexpected factors, such as adverse weather, airport flow control, crew absence, unexpected aircraft maintenance, and pandemic, which can cause disruptions in flight schedules. Thus, managers need to reallocate relevant resources to ensure that the airport can return to normal operations on the basis of minimum cost, which is the airl…
▽ More
In practice, both passenger and cargo flights are vulnerable to unexpected factors, such as adverse weather, airport flow control, crew absence, unexpected aircraft maintenance, and pandemic, which can cause disruptions in flight schedules. Thus, managers need to reallocate relevant resources to ensure that the airport can return to normal operations on the basis of minimum cost, which is the airline recovery problem. Airline recovery is an active research area, with a lot of publications in recent years. To better summarize the progress of airline recovery, first of all, keywords are chosen to search the relevant studies, then software is used to analyze the existing studies in terms of the number of papers, keywords, and sources. Secondly, the airline recovery problem is divided into two categories, namely Passenger-Oriented Airline Recovery Problem (POARP) and Cargo-Oriented Airline Recovery Problem (COARP). In POARP, the existing studies are classified according to recovery strategies, including common recovery strategies, cruise speed control strategy, flexible aircraft maintenance strategy, multi-modal transportation strategy, passenger-centric recovery strategy, and clubbing of flights strategy. Moreover, the POARP is discussed from the perspectives of disruption types, recovery strategies, problem types, objective functions, and solution methods. Thirdly, POARP and COARP are compared from the perspectives of timeliness, subjectivity, flexibility, transferability, and combinability. Finally, the conclusions are drawn and future study directions are provided. For future studies, it is recommended to conduct more in-depth research on dynamic and real-time recovery, incorporating human factors into the modeling, multi-modal transportation coupling, optimization of other airport processes, combination of robust scheduling and airline recovery, and optimization algorithm improvement.
△ Less
Submitted 16 January, 2024; v1 submitted 9 January, 2024;
originally announced January 2024.
-
Aggregation-diffusion phenomena: from microscopic models to free boundary problems
Authors:
Inwon Kim,
Antoine Mellet,
Jeremy Sheung-Him Wu
Abstract:
This paper reviews (and expands) some recent results on the modeling of aggregation-diffusion phenomena at various scales, focusing on the emergence of collective dynamics as a result of the competition between attractive and repulsive phenomena - especially (but not exclusively) in the context of attractive chemotaxis phenomena.
At microscopic scales, particles (or other agents) are represented…
▽ More
This paper reviews (and expands) some recent results on the modeling of aggregation-diffusion phenomena at various scales, focusing on the emergence of collective dynamics as a result of the competition between attractive and repulsive phenomena - especially (but not exclusively) in the context of attractive chemotaxis phenomena.
At microscopic scales, particles (or other agents) are represented by spheres of radius $δ>0$ and we discuss both soft-sphere models (with a pressure term penalizing the overlap of the particles) and hard-sphere models (in which overlap is prohibited). The first case leads to so-called ``blob models" which have received some attention recently as a tool to approximate non-linear diffusion by particle systems. The hard-sphere model is similar to a classical model for congested crowd motion. We review well-posedness results for these models and discuss their relationship to classical continuum description of aggregation-diffusion phenomena in the limit $δ\to0$: the classical nonlinear drift diffusion equation and its incompressible counterpart.
In the second part of the paper, we discuss recent results on the emergence and evolution of sharp interfaces when a large population of particles is considered at appropriate space and time scales: At some intermediate time scale, phase separation occurs and a sharp interface appears which evolves according to a Stefan free boundary problem (and the density function eventually relaxes to a characteristic function - metastable steady state for the original problem). At a larger time scale the attractive forces lead to surface tension phenomena and the evolution of the sharp interface can be described by a Hele-Shaw free boundary problem with surface tension. At that same time scale, we will also discuss the emergence of contact angle conditions for problems set in bounded domains.
△ Less
Submitted 3 January, 2024;
originally announced January 2024.
-
Non-commutative probability insights into the double-scaling limit SYK Model with constant perturbations: moments cumulants and $q$-independence
Authors:
Shuang Wu
Abstract:
Extending our previous results, we study the double-scaling limit SYK (DSSYK) model with an additional diagonal matrix with a fixed number $c$ of nonzero constant entries $θ$. This constant diagonal term can be rewritten in terms of Majorana fermion products. Its specific formula depends on the value of $c$. We find exact expressions for the moments of this model. More importantly, by proposing a…
▽ More
Extending our previous results, we study the double-scaling limit SYK (DSSYK) model with an additional diagonal matrix with a fixed number $c$ of nonzero constant entries $θ$. This constant diagonal term can be rewritten in terms of Majorana fermion products. Its specific formula depends on the value of $c$. We find exact expressions for the moments of this model. More importantly, by proposing a moment-cumulant relation, we reinterpret the effect of introducing a constant term in the context of non-commutative probability theory. This gives rise to a $\tilde{q}$ dependent mixture of independences within the moment formula. The parameter $\tilde{q}$, derived from the $q$-Ornstein-Uhlenbeck ($q$-OU) process, controls this transformation. It interpolates between classical independence ($\tilde{q}=1$) and Boolean independence ($\tilde{q}=0$). The underlying combinatorial structures of this model provide the non-commutative probability connections. Additionally, we explore the potential relation between these connections and their gravitational path integral counterparts.
△ Less
Submitted 13 June, 2024; v1 submitted 7 December, 2023;
originally announced December 2023.
-
Multilevel Picard approximations overcome the curse of dimensionality in the numerical approximation of general semilinear PDEs with gradient-dependent nonlinearities
Authors:
Ariel Neufeld,
Tuan Anh Nguyen,
Sizhou Wu
Abstract:
Neufeld and Wu (arXiv:2310.12545) developed a multilevel Picard (MLP) algorithm which can approximately solve general semilinear parabolic PDEs with gradient-dependent nonlinearities, allowing also for coefficient functions of the corresponding PDE to be non-constant. By introducing a particular stochastic fixed-point equation (SFPE) motivated by the Feynman-Kac representation and the Bismut-Elwor…
▽ More
Neufeld and Wu (arXiv:2310.12545) developed a multilevel Picard (MLP) algorithm which can approximately solve general semilinear parabolic PDEs with gradient-dependent nonlinearities, allowing also for coefficient functions of the corresponding PDE to be non-constant. By introducing a particular stochastic fixed-point equation (SFPE) motivated by the Feynman-Kac representation and the Bismut-Elworthy-Li formula and identifying the first and second component of the unique fixed-point of the SFPE with the unique viscosity solution of the PDE and its gradient, they proved convergence of their algorithm. However, it remained an open question whether the proposed MLP schema in arXiv:2310.12545 does not suffer from the curse of dimensionality. In this paper, we prove that the MLP algorithm in arXiv:2310.12545 indeed can overcome the curse of dimensionality, i.e. that its computational complexity only grows polynomially in the dimension $d\in \mathbb{N}$ and the reciprocal of the accuracy $\varepsilon$, under some suitable assumptions on the nonlinear part of the corresponding PDE.
△ Less
Submitted 7 December, 2023; v1 submitted 20 November, 2023;
originally announced November 2023.
-
Non-intrusive model combination for learning dynamical systems
Authors:
Shiqi Wu,
Ludovic Chamoin,
Qianxiao Li
Abstract:
In data-driven modelling of complex dynamic processes, it is often desirable to combine different classes of models to enhance performance. Examples include coupled models of different fidelities, or hybrid models based on physical knowledge and data-driven strategies. A key limitation of the broad adoption of model combination in applications is intrusiveness: training combined models typically r…
▽ More
In data-driven modelling of complex dynamic processes, it is often desirable to combine different classes of models to enhance performance. Examples include coupled models of different fidelities, or hybrid models based on physical knowledge and data-driven strategies. A key limitation of the broad adoption of model combination in applications is intrusiveness: training combined models typically requires significant modifications to the learning algorithm implementations, which may often be already well-developed and optimized for individual model spaces. In this work, we propose an iterative, non-intrusive methodology to combine two model spaces to learn dynamics from data. We show that this can be understood, at least in the linear setting, as finding the optimal solution in the direct sum of the two hypothesis spaces, while leveraging only the projection operators in each individual space. Hence, the proposed algorithm can be viewed as iterative projections, for which we can obtain estimates on its convergence properties. To highlight the extensive applicability of our framework, we conduct numerical experiments in various problem settings, with particular emphasis on various hybrid models based on the Koopman operator approach.
△ Less
Submitted 6 November, 2023;
originally announced November 2023.
-
Deep ReLU neural networks overcome the curse of dimensionality when approximating semilinear partial integro-differential equations
Authors:
Ariel Neufeld,
Tuan Anh Nguyen,
Sizhou Wu
Abstract:
In this paper we consider PIDEs with gradient-independent Lipschitz continuous nonlinearities and prove that deep neural networks with ReLU activation function can approximate solutions of such semilinear PIDEs without curse of dimensionality in the sense that the required number of parameters in the deep neural networks increases at most polynomially in both the dimension $ d $ of the correspondi…
▽ More
In this paper we consider PIDEs with gradient-independent Lipschitz continuous nonlinearities and prove that deep neural networks with ReLU activation function can approximate solutions of such semilinear PIDEs without curse of dimensionality in the sense that the required number of parameters in the deep neural networks increases at most polynomially in both the dimension $ d $ of the corresponding PIDE and the reciprocal of the prescribed accuracy $ε$.
△ Less
Submitted 26 October, 2023; v1 submitted 24 October, 2023;
originally announced October 2023.
-
Multilevel Picard algorithm for general semilinear parabolic PDEs with gradient-dependent nonlinearities
Authors:
Ariel Neufeld,
Sizhou Wu
Abstract:
In this paper we introduce a multilevel Picard approximation algorithm for general semilinear parabolic PDEs with gradient-dependent nonlinearities whose coefficient functions do not need to be constant. We also provide a full convergence and complexity analysis of our algorithm. To obtain our main results, we consider a particular stochastic fixed-point equation (SFPE) motivated by the Feynman-Ka…
▽ More
In this paper we introduce a multilevel Picard approximation algorithm for general semilinear parabolic PDEs with gradient-dependent nonlinearities whose coefficient functions do not need to be constant. We also provide a full convergence and complexity analysis of our algorithm. To obtain our main results, we consider a particular stochastic fixed-point equation (SFPE) motivated by the Feynman-Kac representation and the Bismut-Elworthy-Li formula. We show that the PDE under consideration has a unique viscosity solution which coincides with the first component of the unique solution of the stochastic fixed-point equation. Moreover, the gradient of the unique viscosity solution of the PDE exists and coincides with the second component of the unique solution of the stochastic fixed-point equation. Furthermore, we also provide a numerical example in up to $300$ dimensions to demonstrate the practical applicability of our multilevel Picard algorithm.
△ Less
Submitted 15 January, 2024; v1 submitted 19 October, 2023;
originally announced October 2023.
-
Time-Uniform Self-Normalized Concentration for Vector-Valued Processes
Authors:
Justin Whitehouse,
Zhiwei Steven Wu,
Aaditya Ramdas
Abstract:
Self-normalized processes arise naturally in many statistical tasks. While self-normalized concentration has been extensively studied for scalar-valued processes, there is less work on multidimensional processes outside of the sub-Gaussian setting. In this work, we construct a general, self-normalized inequality for $\mathbb{R}^d$-valued processes that satisfy a simple yet broad "sub-$ψ$" tail con…
▽ More
Self-normalized processes arise naturally in many statistical tasks. While self-normalized concentration has been extensively studied for scalar-valued processes, there is less work on multidimensional processes outside of the sub-Gaussian setting. In this work, we construct a general, self-normalized inequality for $\mathbb{R}^d$-valued processes that satisfy a simple yet broad "sub-$ψ$" tail condition, which generalizes assumptions based on cumulant generating functions. From this general inequality, we derive an upper law of the iterated logarithm for sub-$ψ$ vector-valued processes, which is tight up to small constants. We demonstrate applications in prototypical statistical tasks, such as parameter estimation in online linear regression and auto-regressive modeling, and bounded mean estimation via a new (multivariate) empirical Bernstein concentration inequality.
△ Less
Submitted 13 October, 2023;
originally announced October 2023.
-
Existence of Classic Solution of the Boussinesq Equation
Authors:
Shu-hong Wu
Abstract:
We generalize intermediate value Theorem to metric space,and make use of it to discuss existence of classic solution of the Boussinesq equation.
We generalize intermediate value Theorem to metric space,and make use of it to discuss existence of classic solution of the Boussinesq equation.
△ Less
Submitted 12 July, 2024; v1 submitted 23 September, 2023;
originally announced September 2023.
-
A Note on Heights of Cyclotomic Polynomials
Authors:
Gennady Bachman,
Christopher Bao,
Shenlone Wu
Abstract:
We show that for any positive integer $h$, either $h$ or $h+1$ is a height of some cyclotomic polynomial $Φ_n$, where $n$ is a product of three distinct primes.
We show that for any positive integer $h$, either $h$ or $h+1$ is a height of some cyclotomic polynomial $Φ_n$, where $n$ is a product of three distinct primes.
△ Less
Submitted 6 September, 2023;
originally announced September 2023.
-
Solving parametric elliptic interface problems via interfaced operator network
Authors:
Sidi Wu,
Aiqing Zhu,
Yifa Tang,
Benzhuo Lu
Abstract:
Learning operators mapping between infinite-dimensional Banach spaces via neural networks has attracted a considerable amount of attention in recent years. In this paper, we propose an interfaced operator network (IONet) to solve parametric elliptic interface PDEs, where different coefficients, source terms, and boundary conditions are considered as input features. To capture the discontinuities i…
▽ More
Learning operators mapping between infinite-dimensional Banach spaces via neural networks has attracted a considerable amount of attention in recent years. In this paper, we propose an interfaced operator network (IONet) to solve parametric elliptic interface PDEs, where different coefficients, source terms, and boundary conditions are considered as input features. To capture the discontinuities in both the input functions and the output solutions across the interface, IONet divides the entire domain into several separate subdomains according to the interface and uses multiple branch nets and trunk nets. Each branch net extracts latent representations of input functions at a fixed number of sensors on a specific subdomain, and each trunk net is responsible for output solutions on one subdomain. Additionally, tailored physics-informed loss of IONet is proposed to ensure physical consistency, which greatly reduces the training dataset requirement and makes IONet effective without any paired input-output observations inside the computational domain. Extensive numerical studies demonstrate that IONet outperforms existing state-of-the-art deep operator networks in terms of accuracy and versatility.
△ Less
Submitted 27 June, 2024; v1 submitted 28 August, 2023;
originally announced August 2023.
-
Exponentially-fitted finite elements for $H({\rm curl})$ and $H({\rm div})$ convection-diffusion problems
Authors:
Jindong Wang,
Shuonan Wu
Abstract:
This paper presents a novel approach to the construction of the lowest order $H(\mathrm{curl})$ and $H(\mathrm{div})$ exponentially-fitted finite element spaces ${\mathcal{S}_{1^-}^{k}}~(k=1,2)$ on 3D simplicial mesh for corresponding convection-diffusion problems. It is noteworthy that this method not only facilitates the construction of the functions themselves but also provides corresponding di…
▽ More
This paper presents a novel approach to the construction of the lowest order $H(\mathrm{curl})$ and $H(\mathrm{div})$ exponentially-fitted finite element spaces ${\mathcal{S}_{1^-}^{k}}~(k=1,2)$ on 3D simplicial mesh for corresponding convection-diffusion problems. It is noteworthy that this method not only facilitates the construction of the functions themselves but also provides corresponding discrete fluxes simultaneously. Utilizing this approach, we successfully establish a discrete convection-diffusion complex and employ a specialized weighted interpolation to establish a bridge between the continuous complex and the discrete complex, resulting in a coherent framework. Furthermore, we demonstrate the commutativity of the framework when the convection field is locally constant, along with the exactness of the discrete convection-diffusion complex. Consequently, these types of spaces can be directly employed to devise the corresponding discrete scheme through a Petrov-Galerkin method.
△ Less
Submitted 15 August, 2023;
originally announced August 2023.
-
A Monotone Discretization for the Fractional Obstacle Problem
Authors:
Rubing Han,
Shuonan Wu,
Hao Zhou
Abstract:
We introduce a novel monotone discretization method for addressing obstacle problems involving the integral fractional Laplacian with homogeneous Dirichlet boundary conditions over bounded Lipschitz domains. This problem is prevalent in mathematical finance, particle systems, and elastic theory. By leveraging insights from the successful monotone discretization of the fractional Laplacian, we esta…
▽ More
We introduce a novel monotone discretization method for addressing obstacle problems involving the integral fractional Laplacian with homogeneous Dirichlet boundary conditions over bounded Lipschitz domains. This problem is prevalent in mathematical finance, particle systems, and elastic theory. By leveraging insights from the successful monotone discretization of the fractional Laplacian, we establish uniform boundedness, solution existence, and uniqueness for the numerical solutions of the fractional obstacle problem. We employ a policy iteration approach for efficient solution of discrete nonlinear problems and prove its finite convergence. Our improved policy iteration, adapted to solution regularity, demonstrates superior performance by modifying discretization across different regions. Numerical examples underscore the method's efficacy.
△ Less
Submitted 12 August, 2023; v1 submitted 22 July, 2023;
originally announced July 2023.
-
A preconditioned MINRES method for block lower triangular Toeplitz systems
Authors:
Congcong Li,
Xuelei Lin,
Sean Hon,
Shu-Lin Wu
Abstract:
In this study, a novel preconditioner based on the absolute-value block $α$-circulant matrix approximation is developed, specifically designed for nonsymmetric dense block lower triangular Toeplitz (BLTT) systems that emerge from the numerical discretization of evolutionary equations. Our preconditioner is constructed by taking an absolute-value of a block $α$-circulant matrix approximation to the…
▽ More
In this study, a novel preconditioner based on the absolute-value block $α$-circulant matrix approximation is developed, specifically designed for nonsymmetric dense block lower triangular Toeplitz (BLTT) systems that emerge from the numerical discretization of evolutionary equations. Our preconditioner is constructed by taking an absolute-value of a block $α$-circulant matrix approximation to the BLTT matrix. To apply our preconditioner, the original BLTT linear system is converted into a symmetric form by applying a time-reversing permutation transformation. Then, with our preconditioner, the preconditioned minimal residual method (MINRES) solver is employed to solve the symmetrized linear system. With properly chosen $α$, the eigenvalues of the preconditioned matrix are proven to be clustered around $\pm1$ without any significant outliers. With the clustered spectrum, we show that the preconditioned MINRES solver for the preconditioned system has a convergence rate independent of system size. To the best of our knowledge, this is the first preconditioned MINRES method with size-independent convergence rate for the dense BLTT system. The efficacy of the proposed preconditioner is corroborated by our numerical experiments, which reveal that it attains optimal convergence.
△ Less
Submitted 21 December, 2023; v1 submitted 15 July, 2023;
originally announced July 2023.
-
On the Sublinear Regret of GP-UCB
Authors:
Justin Whitehouse,
Zhiwei Steven Wu,
Aaditya Ramdas
Abstract:
In the kernelized bandit problem, a learner aims to sequentially compute the optimum of a function lying in a reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims to minimize regret, which is a measure of the suboptimality of the choices made. Arguably the most popular algorithm is the Gaussian Process Upper Confidence Bound (…
▽ More
In the kernelized bandit problem, a learner aims to sequentially compute the optimum of a function lying in a reproducing kernel Hilbert space given only noisy evaluations at sequentially chosen points. In particular, the learner aims to minimize regret, which is a measure of the suboptimality of the choices made. Arguably the most popular algorithm is the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm, which involves acting based on a simple linear estimator of the unknown function. Despite its popularity, existing analyses of GP-UCB give a suboptimal regret rate, which fails to be sublinear for many commonly used kernels such as the Matérn kernel. This has led to a longstanding open question: are existing regret analyses for GP-UCB tight, or can bounds be improved by using more sophisticated analytical techniques? In this work, we resolve this open question and show that GP-UCB enjoys nearly optimal regret. In particular, our results yield sublinear regret rates for the Matérn kernel, improving over the state-of-the-art analyses and partially resolving a COLT open problem posed by Vakili et al. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel $k$. Applying this key idea together with a largely overlooked concentration result in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide a tighter analysis of the GP-UCB algorithm.
△ Less
Submitted 14 August, 2023; v1 submitted 14 July, 2023;
originally announced July 2023.
-
A hybridizable discontinuous Galerkin method for magnetic advection-diffusion problems
Authors:
Jindong Wang,
Shuonan Wu
Abstract:
We propose and analyze a hybridizable discontinuous Galerkin (HDG) method for solving a mixed magnetic advection-diffusion problem within a more general Friedrichs system framework. With carefully constructed numerical traces, we introduce two distinct stabilization parameters: $τ_t$ for the tangential trace and $τ_n$ for the normal trace. These parameters are tailored to satisfy different require…
▽ More
We propose and analyze a hybridizable discontinuous Galerkin (HDG) method for solving a mixed magnetic advection-diffusion problem within a more general Friedrichs system framework. With carefully constructed numerical traces, we introduce two distinct stabilization parameters: $τ_t$ for the tangential trace and $τ_n$ for the normal trace. These parameters are tailored to satisfy different requirements, ensuring the stability and convergence of the method. Furthermore, we incorporate a weight function to facilitate the establishment of stability conditions. We also investigate an elementwise postprocessing technique that proves to be effective for both two-dimensional and three-dimensional problems in terms of broken $H({\rm curl})$ semi-norm accuracy improvement. Extensive numerical examples are presented to showcase the performance and effectiveness of the HDG method and the postprocessing techniques.
△ Less
Submitted 31 May, 2023;
originally announced May 2023.
-
Parareal algorithm via Chebyshev-Gauss spectral collocation method
Authors:
Quan Zhou,
Yicheng Liu,
Shu-Lin Wu
Abstract:
We present the Parareal-CG algorithm for time-dependent differential equations in this work. The algorithm is a parallel in time iteration algorithm utilizes Chebyshev-Gauss spectral collocation method for fine propagator F and backward Euler method for coarse propagator G. As far as we know, this is the first time that the spectral method used as the F propagator of the parareal algorithm. By con…
▽ More
We present the Parareal-CG algorithm for time-dependent differential equations in this work. The algorithm is a parallel in time iteration algorithm utilizes Chebyshev-Gauss spectral collocation method for fine propagator F and backward Euler method for coarse propagator G. As far as we know, this is the first time that the spectral method used as the F propagator of the parareal algorithm. By constructing the stable function of the Chebyshev-Gauss spectral collocation method for the symmetric positive definite (SPD) problem, we find out that the Parareal-CG algorithm and the Parareal-TR algorithm, whose F propagator is chosen to be a trapezoidal ruler, converge similarly, i.e., the Parareal-CG algorithm converge as fast as Parareal-Euler algorithm with sufficient Chebyhsev-Gauss points in every coarse grid. Numerical examples including ordinary differential equations and time-dependent partial differential equations are given to illustrate the high efficiency and accuracy of the proposed algorithm.
△ Less
Submitted 20 April, 2023;
originally announced April 2023.
-
Two families of $n$-rectangle nonconforming finite elements for sixth-order elliptic equations
Authors:
Xianlin Jin,
Shuonan Wu
Abstract:
In this paper, we propose two families of nonconforming finite elements on $n$-rectangle meshes of any dimension to solve the sixth-order elliptic equations. The unisolvent property and the approximation ability of the new finite element spaces are established. A new mechanism, called the exchange of sub-rectangles, for investigating the weak continuities of the proposed elements is discovered. Wi…
▽ More
In this paper, we propose two families of nonconforming finite elements on $n$-rectangle meshes of any dimension to solve the sixth-order elliptic equations. The unisolvent property and the approximation ability of the new finite element spaces are established. A new mechanism, called the exchange of sub-rectangles, for investigating the weak continuities of the proposed elements is discovered. With the help of some conforming relatives for the $H^3$ problems, we establish the quasi-optimal error estimate for the tri-harmonic equation in the broken $H^3$ norm of any dimension. The theoretical results are validated further by the numerical tests in both 2D and 3D situations.
△ Less
Submitted 10 March, 2023;
originally announced March 2023.
-
Nonlocal approximation of nonlinear diffusion equations
Authors:
José Antonio Carrillo,
Antonio Esposito,
Jeremy Sheung-Him Wu
Abstract:
We show that degenerate nonlinear diffusion equations can be asymptotically obtained as a limit from a class of nonlocal partial differential equations. The nonlocal equations are obtained as gradient flows of interaction-like energies approximating the internal energy. We construct weak solutions as the limit of a (sub)sequence of weak measure solutions by using the Jordan-Kinderlehrer-Otto schem…
▽ More
We show that degenerate nonlinear diffusion equations can be asymptotically obtained as a limit from a class of nonlocal partial differential equations. The nonlocal equations are obtained as gradient flows of interaction-like energies approximating the internal energy. We construct weak solutions as the limit of a (sub)sequence of weak measure solutions by using the Jordan-Kinderlehrer-Otto scheme from the context of $2$-Wasserstein gradient flows. Our strategy allows to cover the porous medium equation, for the general slow diffusion case, extending previous results in the literature. As a byproduct of our analysis, we provide a qualitative particle approximation.
△ Less
Submitted 11 October, 2023; v1 submitted 16 February, 2023;
originally announced February 2023.
-
Some properties of the solution of the vertical tensor complementarity problem
Authors:
Li-Ming Li,
Shi-Liang Wu
Abstract:
In this paper, we mainly focus on the existence and uniqueness of the vertical tensor complementarity problem. Firstly, combining the generalized-order linear complementarity problem with the tensor complementarity problem, the vertical tensor complementarity problem is introduced. Secondly, we define some sets of special tensors, and illustrate the inclusion relationships. Finally, we show that t…
▽ More
In this paper, we mainly focus on the existence and uniqueness of the vertical tensor complementarity problem. Firstly, combining the generalized-order linear complementarity problem with the tensor complementarity problem, the vertical tensor complementarity problem is introduced. Secondly, we define some sets of special tensors, and illustrate the inclusion relationships. Finally, we show that the solution set of the vertical tensor complementarity problem is bounded under certain conditions, and some sufficient conditions for the existence and uniqueness of the solution of the vertical tensor complementarity problem are obtained from the view of the degree theory and the equal form of the minimum function.
△ Less
Submitted 2 December, 2022;
originally announced December 2022.
-
Spectrality of a class of infinite convolutions on $\mathbb{R}$
Authors:
Sha Wu,
Yingqing Xiao
Abstract:
Given an integer $m\geq1$. Let $Σ^{(m)}=\{1,2, \cdots, m\}^{\mathbb{N}}$ be a symbolic space, and let $\{(b_{k},D_{k})\}_{k=1}^{m}:=\{(b_{k}, \{0,1,\cdots, p_{k}-1\}t_{k}) \}_{k=1}^{m}$ be a finite sequence pairs, where integers $| b_{k}| $, $p_{k}\geq2$, $|t_{k}|\geq 1$ and $ p_{k},t_{1},t_{2}, \cdots, t_{m}$ are pairwise coprime integers for all $1\leq k\leq m$. In this paper, we show that for a…
▽ More
Given an integer $m\geq1$. Let $Σ^{(m)}=\{1,2, \cdots, m\}^{\mathbb{N}}$ be a symbolic space, and let $\{(b_{k},D_{k})\}_{k=1}^{m}:=\{(b_{k}, \{0,1,\cdots, p_{k}-1\}t_{k}) \}_{k=1}^{m}$ be a finite sequence pairs, where integers $| b_{k}| $, $p_{k}\geq2$, $|t_{k}|\geq 1$ and $ p_{k},t_{1},t_{2}, \cdots, t_{m}$ are pairwise coprime integers for all $1\leq k\leq m$. In this paper, we show that for any infinite word $σ=\left(σ_{n}\right)_{n=1}^{\infty}\inΣ^{(m)}$, the infinite convolution $$ μ_σ=δ_{b_{σ_{1}}^{-1} D_{σ_{1}}} * δ_{\left(b_{σ_{1}} b_{σ_{2}}\right)^{-1} D_{σ_{2}}} * δ_{\left(b_{σ_{1}} b_{σ_{2}} b_{σ_{3}}\right)^{-1}D_{σ_{3}}} * \cdots $$ is a spectral measure if and only if $p_{σ_n}\mid b_{σ_n}$ for all $n\geq2$ and $σ\notin \bigcup_{l=1}^\infty\prod_{l}$, where $\prod_{l}=\{i_{1}i_{2}\cdots i_{l}j^{\infty}\inΣ^{(m)}: i_{l}\neq j, |b_{j}|=p_{j}, |t_{j}|\neq1\}$.
△ Less
Submitted 1 December, 2022;
originally announced December 2022.
-
Convergence of a particle method for a regularized spatially homogeneous Landau equation
Authors:
José A. Carrillo,
Matias G. Delgadino,
Jeremy S. H. Wu
Abstract:
We study a regularized version of the Landau equation, which was recently introduced in~\cite{CHWW20} to numerically approximate the Landau equation with good accuracy at reasonable computational cost. We develop the existence and uniqueness theory for weak solutions, and we reinforce the numerical findings in~\cite{CHWW20} by rigorously proving the validity of particle approximations to the regul…
▽ More
We study a regularized version of the Landau equation, which was recently introduced in~\cite{CHWW20} to numerically approximate the Landau equation with good accuracy at reasonable computational cost. We develop the existence and uniqueness theory for weak solutions, and we reinforce the numerical findings in~\cite{CHWW20} by rigorously proving the validity of particle approximations to the regularized Landau equation.
△ Less
Submitted 13 November, 2022;
originally announced November 2022.
-
Kakeya sets from lines in $SL_2$
Authors:
Nets Hawk Katz,
Shukun Wu,
Joshua Zahl
Abstract:
We prove that every Kakeya set in $\mathbb{R}^3$ formed from lines of the form $(a,b,0) + \operatorname{span}(c,d,1)$ with $ad-bc=1$ must have Hausdorff dimension $3$; Kakeya sets of this type are called $SL_2$ Kakeya sets. This result was also recently proved by Fässler and Orponen using different techniques. Our method combines induction on scales with a special structural property of $SL_2$ Kak…
▽ More
We prove that every Kakeya set in $\mathbb{R}^3$ formed from lines of the form $(a,b,0) + \operatorname{span}(c,d,1)$ with $ad-bc=1$ must have Hausdorff dimension $3$; Kakeya sets of this type are called $SL_2$ Kakeya sets. This result was also recently proved by Fässler and Orponen using different techniques. Our method combines induction on scales with a special structural property of $SL_2$ Kakeya sets, which says that locally such sets look like the pre-image of an arrangement of plane curves above a special type of map from $\mathbb{R}^3$ to $\mathbb{R}^2$, called a twisting projection. This reduces the study of $SL_2$ Kakeya sets to a Kakeya-type problem for plane curves; the latter is analyzed using a variant of Wolff's circular maximal function.
△ Less
Submitted 15 August, 2023; v1 submitted 9 November, 2022;
originally announced November 2022.
-
Rainbow Connection for Complete Multipartite Graphs
Authors:
Igor Araujo,
Kareem Benaissa,
Richard Bi,
Sean English,
Shengan Wu,
Pai Zheng
Abstract:
A path in an edge-colored graph is said to be rainbow if no color repeats on it. An edge-colored graph is said to be rainbow $k$-connected if every pair of vertices is connected by $k$ internally disjoint rainbow paths. The rainbow $k$-connection number $\mathrm{rc}_k(G)$ is the minimum number of colors $\ell$ such that there exists a coloring with $\ell$ colors that makes $G$ rainbow $k$-connecte…
▽ More
A path in an edge-colored graph is said to be rainbow if no color repeats on it. An edge-colored graph is said to be rainbow $k$-connected if every pair of vertices is connected by $k$ internally disjoint rainbow paths. The rainbow $k$-connection number $\mathrm{rc}_k(G)$ is the minimum number of colors $\ell$ such that there exists a coloring with $\ell$ colors that makes $G$ rainbow $k$-connected. Let $f(k,t)$ be the minimum integer such that every $t$-partite graph with part sizes at least $f(k,t)$ has $\mathrm{rc}_k(G) \le 4$ if $t=2$ and $\mathrm{rc}_k(G) \le 3$ if $t \ge 3$. Answering a question of Fujita, Liu and Magnant, we show that
\[
f(k,t) = \left\lceil \frac{2k}{t-1} \right\rceil
\]
for all $k\geq 2$, $t\geq 2$. We also give some conditions for which $\mathrm{rc}_k(G) \le 3$ if $t=2$ and $\mathrm{rc}_k(G) \le 2$ if $t \ge 3$.
△ Less
Submitted 19 February, 2023; v1 submitted 21 October, 2022;
originally announced October 2022.
-
An improved restriction estimate in $\mathbb{R}^3$
Authors:
Hong Wang,
Shukun Wu
Abstract:
We improve the $L^{p}\rightarrow L^p$ restriction estimate in $\mathbb{R}^3$ to the range $p>3+3/14$, based on some Kakeya type incidence estimates and the refined decoupling theorem.
We improve the $L^{p}\rightarrow L^p$ restriction estimate in $\mathbb{R}^3$ to the range $p>3+3/14$, based on some Kakeya type incidence estimates and the refined decoupling theorem.
△ Less
Submitted 14 October, 2022; v1 submitted 7 October, 2022;
originally announced October 2022.
-
The perturbation bound of the extended vertical linear complementarity problem
Authors:
Shiliang Wu,
Wen Li,
Hehui Wang
Abstract:
In this paper, we discuss the perturbation analysis of the extended vertical linear complementarity problem (EVLCP). Under the assumption of the row $\mathcal{W}$-property, several absolute and relative perturbation bounds of EVLCP are given, which can be reduced to some existing results. Some numerical examples are given to show the proposed bounds.
In this paper, we discuss the perturbation analysis of the extended vertical linear complementarity problem (EVLCP). Under the assumption of the row $\mathcal{W}$-property, several absolute and relative perturbation bounds of EVLCP are given, which can be reduced to some existing results. Some numerical examples are given to show the proposed bounds.
△ Less
Submitted 3 October, 2022;
originally announced October 2022.
-
Error analysis based on inverse modified differential equations for discovery of dynamics using linear multistep methods and deep learning
Authors:
Aiqing Zhu,
Sidi Wu,
Yifa Tang
Abstract:
Along with the practical success of the discovery of dynamics using deep learning, the theoretical analysis of this approach has attracted increasing attention. Prior works have established the grid error estimation with auxiliary conditions for the discovery of dynamics using linear multistep methods and deep learning. And we extend the existing error analysis in this work. We first introduce the…
▽ More
Along with the practical success of the discovery of dynamics using deep learning, the theoretical analysis of this approach has attracted increasing attention. Prior works have established the grid error estimation with auxiliary conditions for the discovery of dynamics using linear multistep methods and deep learning. And we extend the existing error analysis in this work. We first introduce the concept of inverse modified differential equations (IMDE) for linear multistep methods and show that the learned model returns a close approximation of the IMDE. Based on the IMDE, we prove that the error between the discovered system and the target system is bounded by the sum of the LMM discretization error and the learning loss. Furthermore, the learning loss is quantified by combining the approximation and generalization theories of neural networks, and thereby we obtain the priori error estimates for the discovery of dynamics using linear multistep methods. Several numerical experiments are performed to verify the theoretical analysis.
△ Less
Submitted 22 May, 2023; v1 submitted 24 September, 2022;
originally announced September 2022.
-
Lower and upper bounds of the superposition of renewal processes and extensions
Authors:
Shaomin Wu
Abstract:
Consider a system consisting of multiple sockets into each of which a component is inserted. If a component fails, it is replaced immediately and system operation resumes. Then the failure process of the system is the superposition of renewal processes (or superimposed renewal process, SRP). If the label of the components that cause the system to fail are unknown but the times between failures are…
▽ More
Consider a system consisting of multiple sockets into each of which a component is inserted. If a component fails, it is replaced immediately and system operation resumes. Then the failure process of the system is the superposition of renewal processes (or superimposed renewal process, SRP). If the label of the components that cause the system to fail are unknown but the times between failures are known, we refer to such data as {\it masked failure data}. To estimate the SRP based on masked failure data is challenging.
This paper obtains the lower and upper bounds of the rate of the SRP when only masked failure data are available. If repair (rather than replacement) is conducted on failed components, the failure process of the system is the superposition of generalized renewal processes (SGRPs). The paper then derives the lower and upper bounds of the rate of SGRPs and proposes to use a weighted linear combination of the bounds to approximate the SGRP. Discussions are provided for possible extensions of the bounds for systems with other structures such as parallel systems. An algorithm for simulating the SGRP is then proposed. Numerical examples are used to illustrate the proposed approximation method.
△ Less
Submitted 23 August, 2022;
originally announced August 2022.
-
Discontinuous Galerkin methods for magnetic advection-diffusion problems
Authors:
Jindong Wang,
Shuonan Wu
Abstract:
We devise and analyze a class of the primal discontinuous Galerkin methods for the magnetic advection-diffusion problems based on the weighted-residual approach. In addition to the upwind stabilization, we find a new mechanism under the vector case that provides more flexibility in constructing the schemes. For the more general Friedrichs system, we show the stability and optimal error estimate, w…
▽ More
We devise and analyze a class of the primal discontinuous Galerkin methods for the magnetic advection-diffusion problems based on the weighted-residual approach. In addition to the upwind stabilization, we find a new mechanism under the vector case that provides more flexibility in constructing the schemes. For the more general Friedrichs system, we show the stability and optimal error estimate, which boil down to two core ingredients -- the weight function and the special projection -- that contain information of advection. Numerical experiments are provided to verify the theoretical results.
△ Less
Submitted 2 August, 2022;
originally announced August 2022.
-
Banach-Mazur Distance from $\ell_p^3$ to $\ell_\infty^3$
Authors:
Longzhen Zhang,
Lingxu Meng,
Senlin Wu
Abstract:
The maximum of the Banach-Mazur distance $d_{BM}^M(X,\ell_\infty^n)$, where $X$ ranges over the set of all $n$-dimensional real Banach spaces, is difficult to compute. In fact, it is already not easy to get the maximum of $d_{BM}^M(\ell_p^n,\ell_\infty^n)$ for all $p\in [1,\infty]$. We prove that $d_{BM}^M(\ell_p^3,\ell_\infty^3)\leq 9/5,~\forall p\in[1,\infty]$. As an application, the following r…
▽ More
The maximum of the Banach-Mazur distance $d_{BM}^M(X,\ell_\infty^n)$, where $X$ ranges over the set of all $n$-dimensional real Banach spaces, is difficult to compute. In fact, it is already not easy to get the maximum of $d_{BM}^M(\ell_p^n,\ell_\infty^n)$ for all $p\in [1,\infty]$. We prove that $d_{BM}^M(\ell_p^3,\ell_\infty^3)\leq 9/5,~\forall p\in[1,\infty]$. As an application, the following result related to Borsuk's partition problem in Banach spaces is obtained: any subset $A$ of $\ell_p^3$ having diameter $1$ is the union of $8$ subsets of $A$ whose diameters are at most $0.9$.
△ Less
Submitted 12 July, 2022;
originally announced July 2022.
-
The error and perturbation bounds of the general absolute value equations
Authors:
Shi-Liang Wu,
Cui-Xia Li
Abstract:
To our knowledge, the error and perturbation bounds of the general absolute value equations are not discussed. In order to fill in this study gap, in this paper, by introducing a class of absolute value functions, we study the error and perturbation bounds of two types of the general absolute value equations (AVEs): $Ax-B|x|=b$ and $Ax-|Bx|=b$. Some useful error bounds and perturbation bounds of t…
▽ More
To our knowledge, the error and perturbation bounds of the general absolute value equations are not discussed. In order to fill in this study gap, in this paper, by introducing a class of absolute value functions, we study the error and perturbation bounds of two types of the general absolute value equations (AVEs): $Ax-B|x|=b$ and $Ax-|Bx|=b$. Some useful error bounds and perturbation bounds of the above two types of absolute value equations are provided. Without limiting the matrix type, some computable estimates for the above upper bounds are given. By applying the absolute value equations, a new approach for some existing perturbation bounds of the linear complementarity problem (LCP) in (SIAM J. Optim., 18 (2007), pp. 1250-1265) is provided. Some numerical examples for the AVEs from the LCP are given to show the feasibility of the perturbation bounds.
△ Less
Submitted 17 April, 2024; v1 submitted 3 July, 2022;
originally announced July 2022.
-
A $C^{0}$ finite element approximation of planar oblique derivative problems in non-divergence form
Authors:
Guangwei Gao,
Shuonan Wu
Abstract:
This paper proposes a $C^{0}$ (non-Lagrange) primal finite element approximation of the linear elliptic equations in non-divergence form with oblique boundary conditions in planar, curved domains. As an extension of [Calcolo, 58 (2022), No. 9], the Miranda-Talenti estimate for oblique boundary conditions at a discrete level is established by enhancing the regularity on the vertices. Consequently,…
▽ More
This paper proposes a $C^{0}$ (non-Lagrange) primal finite element approximation of the linear elliptic equations in non-divergence form with oblique boundary conditions in planar, curved domains. As an extension of [Calcolo, 58 (2022), No. 9], the Miranda-Talenti estimate for oblique boundary conditions at a discrete level is established by enhancing the regularity on the vertices. Consequently, the coercivity constant for the proposed scheme is exactly the same as that from PDE theory. The quasi-optimal order error estimates are established by carefully studying the approximation property of the finite element spaces. Numerical experiments are provided to verify the convergence theory and to demonstrate the accuracy and efficiency of the proposed methods.
△ Less
Submitted 26 June, 2022;
originally announced June 2022.
-
Folding rotationally symmetrical tableaux via webs
Authors:
Kevin Purbhoo,
Shelley Wu
Abstract:
Rectangular standard Young tableaux with 2 or 3 rows are in bijection with $U_q(\mathfrak{sl}_2)$-webs and $U_q(\mathfrak{sl}_3)$-webs respectively. When $W$ is a web with a reflection symmetry, the corresponding tableau $T_W$ has a rotational symmetry. Folding $T_W$ transforms it into a domino tableau $D_W$. We study the relationships between these correspondences. For 2-row tableaux, folding a r…
▽ More
Rectangular standard Young tableaux with 2 or 3 rows are in bijection with $U_q(\mathfrak{sl}_2)$-webs and $U_q(\mathfrak{sl}_3)$-webs respectively. When $W$ is a web with a reflection symmetry, the corresponding tableau $T_W$ has a rotational symmetry. Folding $T_W$ transforms it into a domino tableau $D_W$. We study the relationships between these correspondences. For 2-row tableaux, folding a rotationally symmetric tableau corresponds to "literally folding" the web along its axis of symmetry. For $3$-row tableaux, we give simple algorithms, which provide direct bijective maps between symmetrical webs and domino tableaux (in both directions). These details of these algorithms reflect the intuitive idea that $D_W$ corresponds to "$W$ modulo symmetry".
△ Less
Submitted 6 July, 2022; v1 submitted 20 June, 2022;
originally announced June 2022.
-
Multilevel Picard approximation algorithm for semilinear partial integro-differential equations and its complexity analysis
Authors:
Ariel Neufeld,
Sizhou Wu
Abstract:
In this paper we introduce a multilevel Picard approximation algorithm for semilinear parabolic partial integro-differential equations (PIDEs). We prove that the numerical approximation scheme converges to the unique viscosity solution of the PIDE under consideration. To that end, we derive a Feynman-Kac representation for the unique viscosity solution of the semilinear PIDE, extending the classic…
▽ More
In this paper we introduce a multilevel Picard approximation algorithm for semilinear parabolic partial integro-differential equations (PIDEs). We prove that the numerical approximation scheme converges to the unique viscosity solution of the PIDE under consideration. To that end, we derive a Feynman-Kac representation for the unique viscosity solution of the semilinear PIDE, extending the classical Feynman-Kac representation for linear PIDEs. Furthermore, we show that the algorithm does not suffer from the curse of dimensionality, i.e. the computational complexity of the algorithm is bounded polynomially in the dimension $d$ and the reciprocal of the prescribed accuracy $\varepsilon$. We also provide a numerical example in up to 10'000 dimensions to demonstrate its applicability.
△ Less
Submitted 14 September, 2023; v1 submitted 19 May, 2022;
originally announced May 2022.
-
SYK model with an extra diagonal perturbation: phase transition in the eigenvalue spectrum
Authors:
Shuang Wu
Abstract:
We study the SYK model with an extra constant source, i.e. a constant matrix or equivalently a diagonal matrix with only one non-zero entry $λ_1$. By using methods from analytic combinatorics, we find exact expressions for the moments of this model. We further prove that the spectrum of this model can have a gap when $λ_1>λ^c_1$, thus exhibiting a phase transition in $λ_1$. In this case, a single…
▽ More
We study the SYK model with an extra constant source, i.e. a constant matrix or equivalently a diagonal matrix with only one non-zero entry $λ_1$. By using methods from analytic combinatorics, we find exact expressions for the moments of this model. We further prove that the spectrum of this model can have a gap when $λ_1>λ^c_1$, thus exhibiting a phase transition in $λ_1$. In this case, a single isolated eigenvalue splits off from SYK's eigenvalues distribution. We located this single eigenvalue by analyzing the singular behavior of a supercritical functional composition scheme. In certain limit our results recover the ones of random matrices with non-zero mean entries.
△ Less
Submitted 21 April, 2022;
originally announced April 2022.
-
Square function estimates for conical regions
Authors:
Shengwen Gan,
Shukun Wu
Abstract:
We prove square function estimates for certain conical regions. Specifically, let $\{Δ_j\}$ be regions of the unit sphere $\mathbb{S}^{n-1}$ and let $S_j f$ be the smooth Fourier restriction of $f$ to the conical region $\{ξ\in\mathbb{R}^n:ξ/|ξ|\inΔ_j\}$. We are interested in the following estimate
$$\Big\|(\sum_j|S_jf|^2)^{1/2}\Big\|_p\lesssim_εδ^{-ε}\|f\|_p.$$
The first result is: when…
▽ More
We prove square function estimates for certain conical regions. Specifically, let $\{Δ_j\}$ be regions of the unit sphere $\mathbb{S}^{n-1}$ and let $S_j f$ be the smooth Fourier restriction of $f$ to the conical region $\{ξ\in\mathbb{R}^n:ξ/|ξ|\inΔ_j\}$. We are interested in the following estimate
$$\Big\|(\sum_j|S_jf|^2)^{1/2}\Big\|_p\lesssim_εδ^{-ε}\|f\|_p.$$
The first result is: when $\{Δ_j\}$ is a set of disjoint $δ$-balls, then the estimate holds for $p=4$. The second result is: In $\mathbb{R}^3$, when $\{Δ_j\}$ is a set of disjoint $δ\timesδ^{1/2}$-rectangles contained in the band $\mathbb{S}^2\cap N_δ(\{ξ_1^2+ξ_2^2=ξ_3^2\})$ and ${\rm{supp}}\widehat f\subset \{ξ\in\mathbb{R}^3:ξ/|ξ|\in\mathbb{S}^2\cap N_δ(\{ξ_1^2+ξ_2^2=ξ_3^2\})\}$, then the estimate holds for $p=8$. The two estimates are sharp.
△ Less
Submitted 28 March, 2022; v1 submitted 22 March, 2022;
originally announced March 2022.
-
GBEM: Galerkin Boundary Element Method for 3-D Capacitance Extraction
Authors:
Shengkun Wu,
Xingquan Li
Abstract:
For modern IC design, electromagnetic coupling among interconnect wires plays an increasingly important role in signoff analysis. The requirement of fast and accurate capacitance extraction is becoming more and more urgent.The critical step of extracting capacitance among interconnect wires is solving electric field. However, due to the high computational complexity, solving electric field is extr…
▽ More
For modern IC design, electromagnetic coupling among interconnect wires plays an increasingly important role in signoff analysis. The requirement of fast and accurate capacitance extraction is becoming more and more urgent.The critical step of extracting capacitance among interconnect wires is solving electric field. However, due to the high computational complexity, solving electric field is extreme timing-consuming. To improve computational efficiency, we propose a Galerkin boundary element method (GBEM) to extract capacitance. The advantage of this method is that it can greatly reduce the number of boundary elements on the premise of ensuring that the error is small enough. As a consequence, the matrix order of the discretization equation will also decrease. The experiments in this paper have proved this advantage of our algorithm. Moreover, we have took advantage of some mathematical theorems in this paper. Our attempt shows that there will be more connections between the capacitance extraction and some mathematical conception so that we can use more mathematical tools to solve the problems of capacitance extraction.
△ Less
Submitted 15 March, 2022;
originally announced March 2022.
