In this paper we present a new perspective on error analysis of Legendre approximations for differentiable functions. We start by introducing a sequence of Legendre-Gauss-Lobatto polynomials and prove their theoretical properties, such as an explicit and optimal upper bound. We then apply these properties to derive a new and explicit bound for the Legendre coefficients of differentiable functions and establish some explicit and optimal error bounds for Legendre projections in the $L^2$ and $L^{\infty}$ norms. Illustrative examples are provided to demonstrate the sharpness of our new results.
相關內容
Robust iterative methods for solving large sparse systems of linear algebraic equations often suffer from the problem of optimizing the corresponding tuning parameters. To improve the performance of the problem of interest, specific parameter tuning is required, which in practice can be a time-consuming and tedious task. This paper proposes an optimization algorithm for tuning the numerical method parameters. The algorithm combines the evolution strategy with the pre-trained neural network used to filter the individuals when constructing the new generation. The proposed coupling of two optimization approaches allows to integrate the adaptivity properties of the evolution strategy with a priori knowledge realized by the neural network. The use of the neural network as a preliminary filter allows for significant weakening of the prediction accuracy requirements and reusing the pre-trained network with a wide range of linear systems. The detailed algorithm efficiency evaluation is performed for a set of model linear systems, including the ones from the SuiteSparse Matrix Collection and the systems from the turbulent flow simulations. The obtained results show that the pre-trained neural network can be effectively reused to optimize parameters for various linear systems, and a significant speedup in the calculations can be achieved at the cost of about 100 trial solves. The hybrid evolution strategy decreases the calculation time by more than 6 times for the black box matrices from the SuiteSparse Matrix Collection and by a factor of 1.4-2 for the sequence of linear systems when modeling turbulent flows. This results in a speedup of up to 1.8 times for the turbulent flow simulations performed in the paper.
We introduce an efficient scheme for the construction of quadrature rules for bandlimited functions. While the scheme is predominantly based on well-known facts about prolate spheroidal wave functions of order zero, it has the asymptotic CPU time estimate $O(n log n)$ to construct an n-point quadrature rule. Moreover, the size of the ``$n log n$'' term in the CPU time estimate is small, so for all practical purposes the CPU time cost is proportional to $n$. The performance of the algorithm is illustrated by several numerical examples.
The notions and certain fundamental characteristics of the proximal and limiting normal cones with respect to a set are first presented in this paper. We present the ideas of the limiting coderivative and subdifferential with respect to a set of multifunctions and singleton mappings, respectively, based on these normal cones. The necessary and sufficient conditions for the Aubin property with respect to a set of multifunctions are then described by using the limiting coderivative with respect to a set. As a result of the limiting subdifferential with respect to a set, we offer the requisite optimality criteria for local solutions to optimization problems. In addition, we also provide examples to demonstrate the outcomes.
This paper investigates the problem of efficient constrained global optimization of hybrid models that are a composition of a known white-box function and an expensive multi-output black-box function subject to noisy observations, which often arises in real-world science and engineering applications. We propose a novel method, Constrained Upper Quantile Bound (CUQB), to solve such problems that directly exploits the composite structure of the objective and constraint functions that we show leads substantially improved sampling efficiency. CUQB is a conceptually simple, deterministic approach that avoid constraint approximations used by previous methods. Although the CUQB acquisition function is not available in closed form, we propose a novel differentiable sample average approximation that enables it to be efficiently maximized. We further derive bounds on the cumulative regret and constraint violation under a non-parametric Bayesian representation of the black-box function. Since these bounds depend sublinearly on the number of iterations under some regularity assumptions, we establis bounds on the convergence rate to the optimal solution of the original constrained problem. In contrast to most existing methods, CUQB further incorporates a simple infeasibility detection scheme, which we prove triggers in a finite number of iterations when the original problem is infeasible (with high probability given the Bayesian model). Numerical experiments on several test problems, including environmental model calibration and real-time optimization of a reactor system, show that CUQB significantly outperforms traditional Bayesian optimization in both constrained and unconstrained cases. Furthermore, compared to other state-of-the-art methods that exploit composite structure, CUQB achieves competitive empirical performance while also providing substantially improved theoretical guarantees.
The complexity of learning problems, such as Generative Adversarial Network (GAN) and its variants, multi-task and meta-learning, hyper-parameter learning, and a variety of real-world vision applications, demands a deeper understanding of their underlying coupling mechanisms. Existing approaches often address these problems in isolation, lacking a unified perspective that can reveal commonalities and enable effective solutions. Therefore, in this work, we proposed a new framework, named Learning with Constraint Learning (LwCL), that can holistically examine challenges and provide a unified methodology to tackle all the above-mentioned complex learning and vision problems. Specifically, LwCL is designed as a general hierarchical optimization model that captures the essence of these diverse learning and vision problems. Furthermore, we develop a gradient-response based fast solution strategy to overcome optimization challenges of the LwCL framework. Our proposed framework efficiently addresses a wide range of applications in learning and vision, encompassing three categories and nine different problem types. Extensive experiments on synthetic tasks and real-world applications verify the effectiveness of our approach. The LwCL framework offers a comprehensive solution for tackling complex machine learning and computer vision problems, bridging the gap between theory and practice.
We propose a novel method for testing serial independence of object-valued time series in metric spaces, which is more general than Euclidean or Hilbert spaces. The proposed method is fully nonparametric, free of tuning parameters, and can capture all nonlinear pairwise dependence. The key concept used in this paper is the distance covariance in metric spaces, which is extended to auto distance covariance for object-valued time series. Furthermore, we propose a generalized spectral density function to account for pairwise dependence at all lags and construct a Cramer-von Mises type test statistic. New theoretical arguments are developed to establish the asymptotic behavior of the test statistic. A wild bootstrap is also introduced to obtain the critical values of the non-pivotal limiting null distribution. Extensive numerical simulations and two real data applications are conducted to illustrate the effectiveness and versatility of our proposed method.
We provide a unified operational framework for the study of causality, non-locality and contextuality, in a fully device-independent and theory-independent setting. Our work has its roots in the sheaf-theoretic framework for contextuality by Abramsky and Brandenburger, which it extends to include arbitrary causal orders (be they definite, dynamical or indefinite). We define a notion of causal function for arbitrary spaces of input histories, and we show that the explicit imposition of causal constraints on joint outputs is equivalent to the free assignment of local outputs to the tip events of input histories. We prove factorisation results for causal functions over parallel, sequential, and conditional sequential compositions of the underlying spaces. We prove that causality is equivalent to continuity with respect to the lowerset topology on the underlying spaces, and we show that partial causal functions defined on open sub-spaces can be bundled into a presheaf. In a striking departure from the Abramsky-Brandenburger setting, however, we show that causal functions fail, under certain circumstances, to form a sheaf. We define empirical models as compatible families in the presheaf of probability distributions on causal functions, for arbitrary open covers of the underlying space of input histories. We show the existence of causally-induced contextuality, a phenomenon arising when the causal constraints themselves become context-dependent, and we prove a no-go result for non-locality on total orders, both static and dynamical.
We study a class of nonlinear nonlocal conservation laws with discontinuous flux, modeling crowd dynamics and traffic flow, without any additional conditions on finiteness/discreteness of the set of discontinuities or on the monotonicity of the kernel/the discontinuous coefficient. Strong compactness of the Godunov and Lax-Friedrichs type approximations is proved, providing the existence of entropy solutions. A proof of the uniqueness of the adapted entropy solutions is provided, establishing the convergence of the entire sequence of finite volume approximations to the adapted entropy solution. As per the current literature, this is the first well-posedness result for the aforesaid class and connects the theory of nonlocal conservation laws (with discontinuous flux), with its local counterpart in a generic setup. Some numerical examples are presented to display the performance of the schemes and explore the limiting behavior of these nonlocal conservation laws to their local counterparts.
The vertex cover problem is a fundamental and widely studied combinatorial optimization problem. It is known that its standard linear programming relaxation is integral for bipartite graphs and half-integral for general graphs. As a consequence, the natural rounding algorithm based on this relaxation computes an optimal solution for bipartite graphs and a $2$-approximation for general graphs. This raises the question of whether one can interpolate the rounding curve of the standard linear programming relaxation in a beyond the worst-case manner, depending on how close the graph is to being bipartite. In this paper, we consider a simple rounding algorithm that exploits the knowledge of an induced bipartite subgraph to attain improved approximation ratios. Equivalently, we suppose that we work with a pair $(G, S)$, consisting of a graph with an odd cycle transversal. If $S$ is a stable set, we prove a tight approximation ratio of $1 + 1/\rho$, where $2\rho -1$ denotes the odd girth (i.e., length of the shortest odd cycle) of the contracted graph $\tilde{G} := G /S$ and satisfies $\rho \in [2,\infty]$. If $S$ is an arbitrary set, we prove a tight approximation ratio of $\left(1+1/\rho \right) (1 - \alpha) + 2 \alpha$, where $\alpha \in [0,1]$ is a natural parameter measuring the quality of the set $S$. The technique used to prove tight improved approximation ratios relies on a structural analysis of the contracted graph $\tilde{G}$. Tightness is shown by constructing classes of weight functions matching the obtained upper bounds. As a byproduct of the structural analysis, we obtain improved tight bounds on the integrality gap and the fractional chromatic number of 3-colorable graphs. We also discuss algorithmic applications in order to find good odd cycle transversals and show optimality of the analysis.
We consider the scalar conservation law in one space dimension with a genuinely nonlinear flux. We assume that an appropriate velocity function depending on the entropy solution of the conservation law is given for the comprising particles, and study their corresponding trajectories under the flow. The differential equation that each of these trajectories satisfies depends on the entropy solution of the conservation law which is typically discontinuous in both time and space variables. The existence and uniqueness of these trajectories are guaranteed by the Filippov theory of differential equations. We show that such a Filippov solution is compatible with the front tracking and vanishing viscosity approximations in the sense that the approximate trajectories given by either of these methods converge uniformly to the trajectories corresponding to the entropy solution of the scalar conservation law. For certain classes of flux functions, illustrated by traffic flow, we prove the H\"older continuity of the particle trajectories with respect to the initial field or the flux function. We then consider the inverse problem of recovering the initial field or the flux function of the scalar conservation law from discrete pointwise measurements of the particle trajectories. We show that the above continuity properties translate to the stability of the Bayesian regularised solutions of these inverse problems with respect to appropriate approximations of the forward map. We also discuss the limitations of the situation where the same inverse problems are considered with pointwise observations made from the entropy solution itself.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191