We consider the graphon mean-field system introduced in the work of Bayraktar, Chakraborty, and Wu. It is the large-population limit of a heterogeneously interacting diffusive particle system, where the interaction is of mean-field type with weights characterized by an underlying graphon function. Through observation of continuous-time trajectories within the particle system, we construct plug-in estimators of the particle density, the drift coefficient, and thus the graphon interaction weights of the mean-field system. Our estimators for the density and drift are direct results of kernel interpolation on the empirical data, and a deconvolution method leads to an estimator of the underlying graphon function. We show that, as the number of particles increases, the graphon estimator converges to the true graphon function pointwisely, and as a consequence, in the cut metric. Besides, we conduct a minimax analysis within a particular class of particle systems to justify the pointwise optimality of the density and drift estimators.
相關內容
We describe a simple deterministic near-linear time approximation scheme for uncapacitated minimum cost flow in undirected graphs with real edge weights, a problem also known as transshipment. Specifically, our algorithm takes as input a (connected) undirected graph $G = (V, E)$, vertex demands $b \in \mathbb{R}^V$ such that $\sum_{v \in V} b(v) = 0$, positive edge costs $c \in \mathbb{R}_{>0}^E$, and a parameter $\varepsilon > 0$. In $O(\varepsilon^{-2} m \log^{O(1)} n)$ time, it returns a flow $f$ such that the net flow out of each vertex is equal to the vertex's demand and the cost of the flow is within a $(1 + \varepsilon)$ factor of optimal. Our algorithm is combinatorial and has no running time dependency on the demands or edge costs. With the exception of a recent result presented at STOC 2022 for polynomially bounded edge weights, all almost- and near-linear time approximation schemes for transshipment relied on randomization to embed the problem instance into low-dimensional space. Our algorithm instead deterministically approximates the cost of routing decisions that would be made if the input were subject to a random tree embedding. To avoid computing the $\Omega(n^2)$ vertex-vertex distances that an approximation of this kind suggests, we also limit the available routing decisions using distances explicitly stored in the well-known Thorup-Zwick distance oracle.
As mini UAVs become increasingly useful in the civilian work domain, the need for a method for them to operate safely in a cluttered environment is growing, especially for fixed-wing UAVs as they are incapable of following the stop-decide-execute methodology. This paper presents preliminary research to design a reactive collision avoidance algorithm based on the improved definition of the repulsive forces used in the Artificial potential field algorithms to allow feasible and safe navigation of fixed-wing UAVs in cluttered, dynamic environments. We present simulation results of the improved definition in multiple scenarios, and we have also discussed possible future studies to improve upon these results.
Augmented Lagrangian (AL) methods are a well known class of algorithms for solving constrained optimization problems. They have been extended to the solution of saddle-point systems of linear equations. We study an AL (SPAL) algorithm for unsymmetric saddle-point systems and derive convergence and semi-convergence properties, even when the system is singular. At each step, our SPAL requires the exact solution of a linear system of the same size but with an SPD (2,2) block. To improve efficiency, we introduce an inexact SPAL algorithm. We establish its convergence properties under reasonable assumptions. Specifically, we use a gradient method, known as the Barzilai-Borwein (BB) method, to solve the linear system at each iteration. We call the result the augmented Lagrangian BB (SPALBB) algorithm and study its convergence. Numerical experiments on test problems from Navier-Stokes equations and coupled Stokes-Darcy flow show that SPALBB is more robust and efficient than BICGSTAB and GMRES. SPALBB often requires the least CPU time, especially on large systems.
In many practical applications, evaluating the joint impact of combinations of environmental variables is important for risk management and structural design analysis. When such variables are considered simultaneously, non-stationarity can exist within both the marginal distributions and dependence structure, resulting in complex data structures. In the context of extremes, few methods have been proposed for modelling trends in extremal dependence, even though capturing this feature is important for quantifying joint impact. Moreover, most proposed techniques are only applicable to data structures exhibiting asymptotic dependence. Motivated by observed dependence trends of data from the UK Climate Projections, we propose a novel semi-parametric modelling framework for bivariate extremal dependence structures. This framework allows us to capture a wide variety of dependence trends for data exhibiting asymptotic independence. When applied to the climate projection dataset, our model detects significant dependence trends in observations and, in combination with models for marginal non-stationarity, can be used to produce estimates of bivariate risk measures at future time points.
In this work is considered a spectral problem, involving a second order term on the domain boundary: the Laplace-Beltrami operator. A variational formulation is presented, leading to a finite element discretization. For the Laplace-Beltrami operator to make sense on the boundary, the domain is smooth: consequently the computational domain (classically a polygonal domain) will not match the physical one. Thus, the physical domain is discretized using high order curved meshes so as to reduce the \textit{geometric error}. The \textit{lift operator}, which is aimed to transform a function defined on the mesh domain into a function defined on the physical one, is recalled. This \textit{lift} is a key ingredient in estimating errors on eigenvalues and eigenfunctions. A bootstrap method is used to prove the error estimates, which are expressed both in terms of \textit{finite element approximation error} and of \textit{geometric error}, respectively associated to the finite element degree $k\ge 1$ and to the mesh order~$r\ge 1$. Numerical experiments are led on various smooth domains in 2D and 3D, which allow us to validate the presented theoretical results.
Circuit complexity, defined as the minimum circuit size required for implementing a particular Boolean computation, is a foundational concept in computer science. Determining circuit complexity is believed to be a hard computational problem [1]. Recently, in the context of black holes, circuit complexity has been promoted to a physical property, wherein the growth of complexity is reflected in the time evolution of the Einstein-Rosen bridge (``wormhole'') connecting the two sides of an AdS ``eternal'' black hole [2]. Here we explore another link between complexity and thermodynamics for circuits of given functionality, making the physics-inspired approach relevant to real computational problems, for which functionality is the key element of interest. In particular, our thermodynamic framework provides a new perspective on the obfuscation of programs of arbitrary length -- an important problem in cryptography -- as thermalization through recursive mixing of neighboring sections of a circuit, which can be viewed as the mixing of two containers with ``gases of gates''. This recursive process equilibrates the average complexity and leads to the saturation of the circuit entropy, while preserving functionality of the overall circuit. The thermodynamic arguments hinge on ergodicity in the space of circuits which we conjecture is limited to disconnected ergodic sectors due to fragmentation. The notion of fragmentation has important implications for the problem of circuit obfuscation as it implies that there are circuits with same size and functionality that cannot be connected via local moves. Furthermore, we argue that fragmentation is unavoidable unless the complexity classes NP and coNP coincide, a statement that implies the collapse of the polynomial hierarchy of computational complexity theory to its first level.
Generalized cross-validation (GCV) is a widely-used method for estimating the squared out-of-sample prediction risk that employs a scalar degrees of freedom adjustment (in a multiplicative sense) to the squared training error. In this paper, we examine the consistency of GCV for estimating the prediction risk of arbitrary ensembles of penalized least-squares estimators. We show that GCV is inconsistent for any finite ensemble of size greater than one. Towards repairing this shortcoming, we identify a correction that involves an additional scalar correction (in an additive sense) based on degrees of freedom adjusted training errors from each ensemble component. The proposed estimator (termed CGCV) maintains the computational advantages of GCV and requires neither sample splitting, model refitting, or out-of-bag risk estimation. The estimator stems from a finer inspection of the ensemble risk decomposition and two intermediate risk estimators for the components in this decomposition. We provide a non-asymptotic analysis of the CGCV and the two intermediate risk estimators for ensembles of convex penalized estimators under Gaussian features and a linear response model. Furthermore, in the special case of ridge regression, we extend the analysis to general feature and response distributions using random matrix theory, which establishes model-free uniform consistency of CGCV.
A rectilinear drawing of a graph is a drawing of the graph in the plane in which the edges are drawn as straight-line segments. The rectilinear crossing number of a graph is the minimum number of pairs of edges that cross over all rectilinear drawings of the graph. Let $n \ge r$ be positive integers. The graph $K_n^r$, is the complete $r$-partite graph on $n$ vertices, in which every set of the partition has at least $\lfloor n/r \rfloor$ vertices. The layered graph, $L_n^r$, is an $r$-partite graph on $n$ vertices, in which for every $1\le i \le r-1$, all the vertices in the $i$-th partition are adjacent to all the vertices in the $(i+1)$-th partition. In this paper, we give upper bounds on the rectilinear crossing numbers of $K_n^r$ and~$L_n^r$.
The diameter of the Cayley graph of the Rubik's Cube group is the fewest number of turns needed to solve the Cube from any initial configurations. For the 2$\times$2$\times$2 Cube, the diameter is 11 in the half-turn metric, 14 in the quarter-turn metric, 19 in the semi-quarter-turn metric, and 10 in the bi-quarter-turn metric. For the 3$\times$3$\times$3 Cube, the diameter was determined by Rokicki et al. to be 20 in the half-turn metric and 26 in the quarter-turn metric. This study shows that a modified version of the coupon collector's problem in probabilistic theory can predict the diameters correctly for both 2$\times$2$\times$2 and 3$\times$3$\times$3 Cubes insofar as the quarter-turn metric is adopted. In the half-turn metric, the diameters are overestimated by one and two, respectively, for the 2$\times$2$\times$2 and 3$\times$3$\times$3 Cubes, whereas for the 2$\times$2$\times$2 Cube in the semi-quarter-turn and bi-quarter-turn metrics, they are overestimated by two and underestimated by one, respectively. Invoking the same probabilistic logic, the diameters of the 4$\times$4$\times$4 and 5$\times$5$\times$5 Cubes are predicted to be 48 (41) and 68 (58) in the quarter-turn (half-turn) metric, whose precise determinations are far beyond reach of classical supercomputing. It is shown that the probabilistically estimated diameter is approximated by $\ln N / \ln r + \ln N / r$, where $N$ is the number of configurations and $r$ is the branching ratio.
Hashing has been widely used in approximate nearest search for large-scale database retrieval for its computation and storage efficiency. Deep hashing, which devises convolutional neural network architecture to exploit and extract the semantic information or feature of images, has received increasing attention recently. In this survey, several deep supervised hashing methods for image retrieval are evaluated and I conclude three main different directions for deep supervised hashing methods. Several comments are made at the end. Moreover, to break through the bottleneck of the existing hashing methods, I propose a Shadow Recurrent Hashing(SRH) method as a try. Specifically, I devise a CNN architecture to extract the semantic features of images and design a loss function to encourage similar images projected close. To this end, I propose a concept: shadow of the CNN output. During optimization process, the CNN output and its shadow are guiding each other so as to achieve the optimal solution as much as possible. Several experiments on dataset CIFAR-10 show the satisfying performance of SRH.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191