Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer NSGA-II have been conducted (AAAI 2022, GECCO 2022 (to appear), arxiv 2022). We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of two multimodal objectives. We prove that if the population size $N$ is at least four times the size of the Pareto front, then the NSGA-II with four different ways to select parents and bit-wise mutation optimizes the OneJumpZeroJump benchmark with jump size~$2 \le k \le n/4$ in time $O(N n^k)$. When using fast mutation, a recently proposed heavy-tailed mutation operator, this guarantee improves by a factor of $k^{\Omega(k)}$. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.
相關內容
Colonoscopy is considered the golden standard for cancer screening of the lower gastrointestinal (GI) tract, with screening programs all over the world considering lowering the recommended screening age. Nonetheless, conventional colonoscopy can cause discomfort to patients due to the forces occurring between colonoscopes and the walls of the colon. Robotic solutions have been proposed to reduce discomfort, and improve accessibility and image quality. Aiming at addressing the limitations of traditional and robotic colonoscopy, in this paper, we present the SoftSCREEN System, a novel Soft Shapeshifting Capsule Robot for Endoscopy based on Eversion Navigation. A plurality of tracks surrounds the body of the system. These tracks are driven by a single motor paired with a worm gear and evert from the internal rigid chassis, enabling fullbody track-based navigation. Two inflatable toroidal chambers enclosing this rigid chassis and passing through the tracks, cause them to displace when inflated. This displacement can be used to regulate the contact with the surrounding wall, thus enabling traction control and adjustment of the overall system diameter to match the local lumen size. The design of the first tethered prototype at 2:1 scale of the SoftSCREEN system is presented in this work. The experimental results show efficient navigation capabilities for different lumen diameters and curvatures, paving the way for a novel robot capable of robust navigation and reliable control of the imaging, with potential for applications beyond colonoscopy, including gastroscopy and capsule endoscopy.
In the Internet of Things (IoT) environment, edge computing can be initiated at anytime and anywhere. However, in an IoT, edge computing sessions are often ephemeral, i.e., they last for a short period of time and can often be discontinued once the current application usage is completed or the edge devices leave the system due to factors such as mobility. Therefore, in this paper, the problem of ephemeral edge computing in an IoT is studied by considering scenarios in which edge computing operates within a limited time period. To this end, a novel online framework is proposed in which a source edge node offloads its computing tasks from sensors within an area to neighboring edge nodes for distributed task computing, within the limited period of time of an ephemeral edge computing system. The online nature of the framework allows the edge nodes to optimize their task allocation and decide on which neighbors to use for task processing, even when the tasks are revealed to the source edge node in an online manner, and the information on future task arrivals is unknown. The proposed framework essentially maximizes the number of computed tasks by jointly considering the communication and computation latency. To solve the problem, an online greedy algorithm is proposed and solved by using the primal-dual approach. Since the primal problem provides an upper bound of the original dual problem, the competitive ratio of the online approach is analytically derived as a function of the task sizes and the data rates of the edge nodes. Simulation results show that the proposed online algorithm can achieve a near-optimal task allocation with an optimality gap that is no higher than 7.1% compared to the offline, optimal solution with complete knowledge of all tasks.
The input to the \emph{Triangle Evacuation} problem is a triangle $ABC$. Given a starting point $S$ on the perimeter of the triangle, a feasible solution to the problem consists of two unit-speed trajectories of mobile agents that eventually visit every point on the perimeter of $ABC$. The cost of a feasible solution (evacuation cost) is defined as the supremum over all points $T$ of the time it takes that $T$ is visited for the first time by an agent plus the distance of $T$ to the other agent at that time. Similar evacuation type problems are well studied in the literature covering the unit circle, the $\ell_p$ unit circle for $p\geq 1$, the square, and the equilateral triangle. We extend this line of research to arbitrary non-obtuse triangles. Motivated by the lack of symmetry of our search domain, we introduce 4 different algorithmic problems arising by letting the starting edge and/or the starting point $S$ on that edge to be chosen either by the algorithm or the adversary. To that end, we provide a tight analysis for the algorithm that has been proved to be optimal for the previously studied search domains, as well as we provide lower bounds for each of the problems. Both our upper and lower bounds match and extend naturally the previously known results that were established only for equilateral triangles.
Different from traditional reflection-only reconfigurable intelligent surfaces (RISs), simultaneously transmitting and reflecting RISs (STAR-RISs) represent a novel technology, which extends the half-space coverage to full-space coverage by simultaneously transmitting and reflecting incident signals. STAR-RISs provide new degrees-of-freedom (DoF) for manipulating signal propagation. Motivated by the above, a novel STAR-RIS assisted non-orthogonal multiple access (NOMA) (STAR-RIS-NOMA) system is proposed in this paper. Our objective is to maximize the achievable sum rate by jointly optimizing the decoding order, power allocation coefficients, active beamforming, and transmission and reflection beamforming. However, the formulated problem is non-convex with intricately coupled variables. To tackle this challenge, a suboptimal two-layer iterative algorithm is proposed. Specifically, in the inner-layer iteration, for a given decoding order, the power allocation coefficients, active beamforming, transmission and reflection beamforming are optimized alternatingly. For the outer-layer iteration, the decoding order of NOMA users in each cluster is updated with the solutions obtained from the inner-layer iteration. Moreover, an efficient decoding order determination scheme is proposed based on the equivalent-combined channel gains. Simulation results are provided to demonstrate that the proposed STAR-RIS-NOMA system, aided by our proposed algorithm, outperforms conventional RIS-NOMA and RIS assisted orthogonal multiple access (RIS-OMA) systems.
We propose a deterministic-statistical method for an inverse source problem using multiple frequency limited aperture far field data. The direct sampling method is used to obtain a disc such that it contains the compact support of the source. The Dirichlet eigenfunctions of the disc are used to expand the source function. Then the inverse problem is recast as a statistical inference problem for the expansion coefficients and the Bayesian inversion is employed to reconstruct the coefficients. The stability of the statistical inverse problem with respect to the measured data is justified in the sense of Hellinger distance. A preconditioned Crank-Nicolson (pCN) Metropolis-Hastings (MH) algorithm is implemented to explore the posterior density function of the unknowns. Numerical examples show that the proposed method is effective for both smooth and non-smooth sources given limited-aperture data.
The edges of the characteristic imset polytope, $\operatorname{CIM}_p$, were recently shown to have strong connections to causal discovery as many algorithms could be interpreted as greedy restricted edge-walks, even though only a strict subset of the edges are known. To better understand the general edge structure of the polytope we describe the edge structure of faces with a clear combinatorial interpretation: for any undirected graph $G$ we have the face $\operatorname{CIM}_G$, the convex hull of the characteristic imsets of DAGs with skeleton $G$. We give a full edge-description of $\operatorname{CIM}_G$ when $G$ is a tree, leading to interesting connections to other polytopes. In particular the well-studied stable set polytope can be recovered as a face of $\operatorname{CIM}_G$ when $G$ is a tree. Building on this connection we are also able to give a description of all edges of $\operatorname{CIM}_G$ when $G$ is a cycle, suggesting possible inroads for generalization. We then introduce an algorithm for learning directed trees from data, utilizing our newly discovered edges, that outperforms classical methods on simulated Gaussian data.
We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for polytopes defined by integer constraints in terms of the height of the integers and certain subdeterminants of the constraint matrix, which in some cases improves previously known results. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure $1-o(1)$ and polynomial diameter. Both bounds rely on spectral gaps -- of a certain Schr\"odinger operator in the first case, and a certain continuous time Markov chain in the second -- which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.
Much of the literature on optimal design of bandit algorithms is based on minimization of expected regret. It is well known that designs that are optimal over certain exponential families can achieve expected regret that grows logarithmically in the number of arm plays, at a rate governed by the Lai-Robbins lower bound. In this paper, we show that when one uses such optimized designs, the regret distribution of the associated algorithms necessarily has a very heavy tail, specifically, that of a truncated Cauchy distribution. Furthermore, for $p>1$, the $p$'th moment of the regret distribution grows much faster than poly-logarithmically, in particular as a power of the total number of arm plays. We show that optimized UCB bandit designs are also fragile in an additional sense, namely when the problem is even slightly mis-specified, the regret can grow much faster than the conventional theory suggests. Our arguments are based on standard change-of-measure ideas, and indicate that the most likely way that regret becomes larger than expected is when the optimal arm returns below-average rewards in the first few arm plays, thereby causing the algorithm to believe that the arm is sub-optimal. To alleviate the fragility issues exposed, we show that UCB algorithms can be modified so as to ensure a desired degree of robustness to mis-specification. In doing so, we also provide a sharp trade-off between the amount of UCB exploration and the tail exponent of the resulting regret distribution.
This paper investigates the post-hoc calibration of confidence for "exploratory" machine learning classification problems. The difficulty in these problems stems from the continuing desire to push the boundaries of which categories have enough examples to generalize from when curating datasets, and confusion regarding the validity of those categories. We argue that for such problems the "one-versus-all" approach (top-label calibration) must be used rather than the "calibrate-the-full-response-matrix" approach advocated elsewhere in the literature. We introduce and test four new algorithms designed to handle the idiosyncrasies of category-specific confidence estimation. Chief among these methods is the use of kernel density ratios for confidence calibration including a novel, bulletproof algorithm for choosing the bandwidth. We test our claims and explore the limits of calibration on a bioinformatics application (PhANNs) as well as the classic MNIST benchmark. Finally, our analysis argues that post-hoc calibration should always be performed, should be based only on the test dataset, and should be sanity-checked visually.
Parallel-in-time methods for partial differential equations (PDEs) have been the subject of intense development over recent decades, particularly for diffusion-dominated problems. It has been widely reported in the literature, however, that many of these methods perform quite poorly for advection-dominated problems. Here we analyze the particular iterative parallel-in-time algorithm of multigrid reduction-in-time (MGRIT) for discretizations of constant-wave-speed linear advection problems. We focus on common method-of-lines discretizations that employ upwind finite differences in space and Runge-Kutta methods in time. Using a convergence framework we developed in previous work, we prove for a subclass of these discretizations that, if using the standard approach of rediscretizing the fine-grid problem on the coarse grid, robust MGRIT convergence with respect to CFL number and coarsening factor is not possible. This poor convergence and non-robustness is caused, at least in part, by an inadequate coarse-grid correction for smooth Fourier modes known as characteristic components.We propose an alternative coarse-grid that provides a better correction of these modes. This coarse-grid operator is related to previous work and uses a semi-Lagrangian discretization combined with an implicitly treated truncation error correction. Theory and numerical experiments show the coarse-grid operator yields fast MGRIT convergence for many of the method-of-lines discretizations considered, including for both implicit and explicit discretizations of high order.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191