Search

Multiobjective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multiobjective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multiobjective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multiobjective shortest-path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA)—the go-to approach for tackling optimization problems on near-term quantum computers—we examine the Pareto plot that results from the scheme and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA and identify key challenges associated with this approach. Finally, through Amazon Braket, we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

Approximate computing is an evolving paradigm that aims to improve the power, speed, and area in neural network applications that can tolerate errors up to a specific limit. This letter proposes a new multiplier architecture based on the algorithm that adapts the approximate compressor from the existing and proposed compressors’ set to reduce error in the respective partial product columns. Further, the error due to the approximation in the proposed multiplier is corrected using a simple error-correcting module. Results prove that the power and power–delay product (PDP) of an 8-bit multiplier is improved by up to 39.9% and 43.6% compared with the exact multiplier and 27.5% and 23.9% compared to similar previous designs. The proposed multiplier is validated using image processing and neural network applications to prove its efficacy. [ABSTRACT FROM AUTHOR]

Recently, multi-objective evolutionary algorithms (MOEAs) have shown promising performance in terms of community detection in complex networks. However, most studies have focused on designing different strategies to achieve good community detection performance based on a single population. Unlike these studies, this study proposes a macro-micro population-based co-evolutionary multi-objective algorithm called MMCoMO for community detection in complex networks to obtain a better trade-off between exploration and exploitation. This algorithm employs two populations, i.e., macro-population and micro-population, for co-evolution to obtain better community structures. In particular, the macro-population prefers exploration and is responsible for quickly determining approximate partitions of the network to obtain good rough community structures as early as possible, whereas the micro-population favors exploitation and is responsible for searching for good fine community structures through the local search process. Thus, these two populations can be used to improve each other through interactions in the co-evolutionary process. In particular, a guiding strategy is designed using the elite (non-dominated) solutions of the macro-population to guide the micro-population, and an influencing strategy is further designed using the elite solutions of the micro-population to positively influence the macro-population. Experiments on synthetic networks and 14 real-world networks demonstrate the superiority of the proposed algorithm over several state-of-the-art community detection algorithms. [ABSTRACT FROM AUTHOR]

Fleet sizing is an important problem in the planning procedure of one-way car-sharing systems. This article investigates the fleet-sizing problem for reservation-based car-sharing systems allowing cruise parking. The system with traffic congestion is modeled as a mixed queuing network with its servers mapping the remaining road capacity. The optimal fleet size with maximum operating profit is derived, taking into account asymptotic performance metrics like reservation, vehicle availability and utilization, and occupancy of parking spaces of each of the stations. The solution is obtained based on an exact mean value analysis (MVA) algorithm and an approximate Schweitzer–Bard MVA (SB-MVA) algorithm. Numerical experiments demonstrate that the proposed method with cruise parking can meet the travel demands with greatly reduced operating cost. Another interesting finding is that a larger reservation time window implies lower parking capacity and smaller fleet size, whereas, as the time window exceeds a threshold, reducing the fleet size may damage the quality of service. [ABSTRACT FROM AUTHOR]

The ECOsystem Spaceborne Thermal Radiometer Experiment on Space Station (ECOSTRESS) onboard the International Space Station (ISS) provides standard land surface temperature (LST) products to meet community concerns on water stress and evapotranspiration. In 2019, an anomaly on the mass storage unit (MSU) changed the data acquisition mode of ECOSTRESS to a direct streaming one, eliminating three bands centered at 1.60, 8.29, and $9.20~\mu \text{m}$. This letter analyzes the feasibility of retrieving LST from ECOSTRESS data using split-window (SW) techniques which need only two thermal infrared (TIR) bands to serve as an alternative to produce LST products. Three different spilt-window algorithms have been developed and analyzed for all possible TIR band combinations using the simulated top-of-atmosphere (TOA) radiance dataset. Besides, the selected SW algorithms were validated using the intercomparison method with ECOSTRESS LST product data and the temperature-based method with surface radiation budget (SURFRAD) ground-based measurements. The result showed that SW algorithms provided higher accuracies than the temperature-emissivity separation (TES) algorithm, with the main advantage that the atmospheric profile data is not demanded prior. [ABSTRACT FROM AUTHOR]

The missile-borne synthetic aperture radar (SAR) works in the forward-squint state, and a higher flight speed will cause a very large relative radial velocity between the target and the antenna phase center (APC). The classic polar format algorithm (PFA) and its improved version do not effectively compensate for the intra-pulse Doppler history resulting from large radial velocity, which leads to defocused images. Therefore this letter proposes a modified version of the PFA, which can solve such image defocus. Compared with the classical PFA, the modified PFA has the same advantages of simplicity and efficiency while implementing higher image quality by compensation of the residual phases caused by large radial velocity. The modified PFA is suitable for hardware implementation, since only fast Fourier transform (FFT) and complex vector multiplications are required in the range dimension processing. In this letter, simulation examples are employed to verify the validity and advantages of the modified PFA. [ABSTRACT FROM AUTHOR]

In this letter, a high-resolution synthetic aperture radar (SAR) imaging algorithm based on a modified omega-K algorithm is proposed. The proposed algorithm first multiplies the reference signal. Then, the azimuth nonstationary phase error (ANSPE) is considered after performing the interpolation process based on the generalized frequency scale transformation. Finally, a well-focused SAR image can be obtained after compensating the ANSPE and correcting the residual spatial variant range migration by utilizing the range segmentation technique. The simulation results of point targets and the real-measured airborne high-resolution SAR data simultaneously verify the effectiveness and feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Two-dimensional phase unwrapping (PU) is an essential step in interferometric synthetic aperture radar (InSAR) analysis. Although the $L^{0}$ -norm PU method is desired, it is nondeterministic polynomial (NP)-hard. Thus, many PU methods have been proposed to find near-optimal solutions of the $L^{0}$ -norm. As PU is an ill-posed problem, it is difficult to choose the method with the most accurate solution unless reference data are available. In this letter, we prove that the NP-hardness of the $L^{0}$ -norm is weak, suggesting that the $\alpha $ -approximation algorithm of the $L^{0}$ -norm can be devised, that is, the obtained near-optimal solutions can be within a factor of $\alpha $ of the $L^{0}$ -norm optimal value. The primary contribution of the proof is that the $\alpha $ value of each obtained PU solution can be considered as a new index to assess the PU performance without using reference data. The validity and effectiveness of the $\alpha $ -based index have been verified using simulated and acquired interferometric datasets and three PU methods. [ABSTRACT FROM AUTHOR]

This article proposes a lateral vehicle trajectory planning and control algorithm using a model predictive control (MPC) scheme for an automated perpendicular parking system. Previous work showed that approximated clothoid-based local path planning using a virtual towing distance provides low computational time and the stability of lateral vehicle motion in a parking system. However, this approach cannot function in certain parking situations and may cause undesirable steering maneuvers due to state-dependent planning. We present a new approximated clothoid path based on lateral vehicle kinematics to cope with these problems. Using the proposed kinematic model, we formulate an MPC problem for path planning. Then, the proposed lateral vehicle trajectory planning becomes an MPC problem under constraints. Besides, we show that lateral vehicle motion for vertical parking can be implemented using simple kinematic lateral motion control. Experimental results show that the vehicle with the proposed method moves smoothly and completes the given parking mission under constraints, even under tight parking space conditions. [ABSTRACT FROM AUTHOR]

Least-mean-squares (LMS) solvers such as Linear / Ridge-Regression and SVD not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as matrix factorizations. We suggest an algorithm that gets a finite set of $n$ n $d$ d -dimensional real vectors and returns a subset of $d+1$ d + 1 vectors with positive weights whose weighted sum is exactly the same. The constructive proof in Caratheodory's Theorem computes such a subset in $O(n^2d^2)$ O (n 2 d 2) time and thus not used in practice. Our algorithm computes this subset in $O(nd+d^4\log {n})$ O (n d + d 4 log n) time, using $O(\log n)$ O (log n) calls to Caratheodory's construction on small but “smart” subsets. This is based on a novel paradigm of fusion between different data summarization techniques, known as sketches and coresets. For large values of $d$ d , we suggest a faster construction that takes $O(nd)$ O (n d) time and returns a weighted subset of $O(d)$ O (d) sparsified input points. Here, a sparsified point means that some of its entries were set to zero. As an application, we show how to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed data is trivial. Extensive experimental results and open source code are provided. [ABSTRACT FROM AUTHOR]

How can we efficiently find very large numbers of clusters C in very large datasets N of potentially high dimensionality D? Here we address the question by using a novel variational approach to optimize Gaussian mixture models (GMMs) with diagonal covariance matrices. The variational method approximates expectation maximization (EM) by applying truncated posteriors as variational distributions and partial E-steps in combination with coresets. Run time complexity to optimize the clustering objective then reduces from O(NCD) per conventional EM iteration to O(N′G2D) for a variational EM iteration on coresets (with coreset size N ′ ≤ N and truncation parameter G ≪ C). Based on the strongly reduced run time complexity per iteration, which scales sublinearly with NC, we then provide a concrete, practically applicable, parallelized and highly efficient clustering algorithm. In numerical experiments on standard large-scale benchmarks we (A) show that also overall clustering times scale sublinearly with NC, and (B) observe substantial wall-clock speedups compared to already highly efficient recently reported results. The algorithm’s sublinear scaling allows for applications at scales where alternative methods cease to be applicable. We demonstrate such very large-scale applicability using the YFCC100M benchmark, for which we realize with a GMM of up to 50.000 clusters an optimization of a data density model with up to 150 M parameters. [ABSTRACT FROM AUTHOR]

Adversarial attacks have been extensively studied in recent years since they can identify the vulnerability of deep learning models before deployed. In this paper, we consider the black-box adversarial setting, where the adversary needs to craft adversarial examples without access to the gradients of a target model. Previous methods attempted to approximate the true gradient either by using the transfer gradient of a surrogate white-box model or based on the feedback of model queries. However, the existing methods inevitably suffer from low attack success rates or poor query efficiency since it is difficult to estimate the gradient in a high-dimensional input space with limited information. To address these problems and improve black-box attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling and gradient averaging, respectively. Our methods can take the advantage of a transfer-based prior given by the gradient of a surrogate model and the query information simultaneously. Through theoretical analyses, the transfer-based prior is appropriately integrated with model queries by an optimal coefficient in each method. Extensive experiments demonstrate that, in comparison with the alternative state-of-the-arts, both of our methods require much fewer queries to attack black-box models with higher success rates. [ABSTRACT FROM AUTHOR]

In this article, we consider an iterative adaptive dynamic programming (ADP) algorithm within the Hamiltonian-driven framework to solve the Hamilton–Jacobi–Bellman (HJB) equation for the infinite-horizon optimal control problem in continuous time for nonlinear systems. First, a novel function, “min-Hamiltonian,” is defined to capture the fundamental properties of the classical Hamiltonian. It is shown that both the HJB equation and the policy iteration (PI) algorithm can be formulated in terms of the min-Hamiltonian within the Hamiltonian-driven framework. Moreover, we develop an iterative ADP algorithm that takes into consideration the approximation errors during the policy evaluation step. We then derive a sufficient condition on the iterative value gradient to guarantee closed-loop stability of the equilibrium point as well as convergence to the optimal value. A model-free extension based on an off-policy reinforcement learning (RL) technique is also provided. Finally, numerical results illustrate the efficacy of the proposed framework. [ABSTRACT FROM AUTHOR]

This article presents a rough-to-fine evolutionary multiobjective optimization algorithm based on the decomposition for solving problems in which the solutions are initially far from the Pareto-optimal set. Subsequently, a tree is constructed by a modified $k$ -means algorithm on $N$ uniform weight vectors, and each node of the tree contains a weight vector. Each node is associated with a subproblem with the help of its weight vector. Consequently, a subproblem tree can be established. It is easy to find that the descendant subproblems are refinements of their ancestor subproblems. The proposed algorithm approaches the Pareto front (PF) by solving a few subproblems in the first few levels to obtain a rough PF and gradually refining the PF by involving the subproblems level-by-level. This strategy is highly favorable for solving problems in which the solutions are initially far from the Pareto set. Moreover, the proposed algorithm has lower time complexity. Theoretical analysis shows the complexity of dealing with a new candidate solution is $\mathcal {O}(M \log N)$ , where $M$ is the number of objectives. Empirical studies demonstrate the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Although cell-free massive multiple-input–multiple-output (mMIMO) Internet-of-Things (IoT) systems can improve spectral efficiency (SE) significantly compared with conventional cellular mMIMO IoT systems due to high coverage and no intercell interference, the pilot contamination and active sensors (ASs) interference can still seriously limit the further improvement of SE. In this article, we first develop a model of the cell-free mMIMO IoT system and then derive a mathematical expression of the SE to formulate a maximized sum SE optimization problem for jointly controlling pilot and data power. This problem is nonconvex; thus, a successive convex approximation (SCA) iteration algorithm is proposed, which, in fact, approximates the objective and constraint function in each iteration, and converts the initial optimization problem into an easy-to-solve geometric programming (GP) problem. Finally, simulation results show that our proposed algorithm outperforms the existing algorithms related to power control optimization in terms of the sum SE performance. [ABSTRACT FROM AUTHOR]

This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. Typically, the performance of TD(0) and TD($\lambda$ λ ) is very sensitive to the choice of stepsizes. Oftentimes, TD(0) suffers from slow convergence. Motivated by the tight link between the TD(0) learning algorithm and the stochastic gradient methods, we develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation that we term AdaTD(0). In contrast to the TD(0), AdaTD(0) is robust or less sensitive to the choice of stepsizes. Analytically, we establish that to reach an $\epsilon$ ε accuracy, the number of iterations needed is $\tilde{O}(\epsilon ^{-2}\ln ^4\frac{1}{\epsilon }/\ln ^4\frac{1}{\rho })$ O ˜ (ε - 2 ln 4 1 ε / ln 4 1 ρ) in the general case, where $\rho$ ρ represents the speed of the underlying Markov chain converges to the stationary distribution. This implies that the iteration complexity of AdaTD(0) is no worse than that of TD(0) in the worst case. When the stochastic semi-gradients are sparse, we provide theoretical acceleration of AdaTD(0). Going beyond TD(0), we develop an adaptive variant of TD($\lambda$ λ ), which is referred to as AdaTD($\lambda$ λ ). Empirically, we evaluate the performance of AdaTD(0) and AdaTD($\lambda$ λ ) on several standard reinforcement learning tasks, which demonstrate the effectiveness of our new approaches. [ABSTRACT FROM AUTHOR]

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and the scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy-tensor estimating error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy. [ABSTRACT FROM AUTHOR]

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e., $2\times 2$ 2 × 2 bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage. [ABSTRACT FROM AUTHOR]

One of the most extensively studied combinatorial optimization problems is the Travelling Salesman Problem (TSP). Considerable research efforts in the past have resulted in exact solvers. However, the runtime of such hand-crafted solutions increases exponentially with problem size. Ising model based solvers have also gained prominence due to their abilities to find fast and approximate solutions for combinatorial optimization problems. However, such Ising based heuristics also suffer from scalability as the solution quality becomes increasingly sub-optimal with increase in problem size. In this work, we propose Neuro-Ising – a machine learning framework which uses Ising models to find clusters of near-optimal partial solutions of large scale TSPs and combines those solutions by employing a supervised data driven mechanism, which we model as a Graph Neural Network (GNN). The GNN is trained from solution instances obtained through exact solvers and hence, the proposed approach generalizes to unseen problems while avoiding the run-time complexity otherwise required, if the solution is built from scratch. Using standard computing resources, our proposed framework rapidly converges to near-optimal solutions for 15 TSPs (upto $\sim 5k$ cities) from the TSPLib benchmark suite. We report $\sim 10.66\times $ speedup over Tabu Search for 8 problems. Furthermore, compared to two state-of-the-art clustering-based TSP solvers, Neuro-Ising achieves $\sim 38 \times $ faster convergence along with $\sim 8.9\%$ better quality of solution, on average. [ABSTRACT FROM AUTHOR]

Owing to its good compression ability, discrete cosine transform (DCT) is widely used in signal processing, including high-efficiency video coding (HEVC). For efficient implementation, approximate DCTs and integer DCTs were proposed, but the challenge in the tradeoff between coding performance and implementation cost always exists. To solve this problem, this article proposes a new algorithm to derive Int-DCT with good coding performance and low hardware cost. To address the multiobjective optimization problem, we extract information from the initially shortlisted transform matrices to derive the weighting factors for the different matrices properties. Those properties having a higher impact to the performance are assigned with higher weights and vice versa. Subsequently, an efficient search algorithm is proposed to shortlist those candidates which can lead to better coding performance evaluated by the proposed measure. Last but not the least, a splitting method is proposed to search the efficient extended double-base number system (EDBNS) representation of the coefficients for hardware implementation and select the solution which encounters the lowest cost. The experimental results in ASIC demonstrate that the implementation area and power cost of designs by the new algorithm are reduced by at least 11.1% and 17.5% for 32-point transform, respectively, over other competing algorithms. Meanwhile, the transforms generated by the proposed algorithm causes negligible impact to coding performance compared to the original transforms in HEVC. [ABSTRACT FROM AUTHOR]

We propose a novel semi-supervised learning (SSL) assumption—the high separation probability (HSP) assumption—that is complementary to the common low density separation (LDS) assumption, and a highly accurate and efficient SSL algorithm, the transductive minimax probability machine (TMPM). Under the HSP assumption, a preferred classifier should ensure that with high probability the samples are far away from the decision boundary. Similarly, the LDS assumption states that the decision boundary should lie in a low-density region. A remarkable property of HSP is that it provides an elegant theoretical framework for analyzing the generalization performance of SSL, while it remains difficult for the LDS assumption to have a quantitative criterion on how it fits the data. Moreover, it has the same paradigm as the minimax probability machine (MPM) and yields an intractable mixed-integer optimization for solving the transductive label assignment problem. Consequently, we propose TMPM with a label-switching strategy and iterative manner to formalize our approximate solution. Theoretically, we analyze the computational complexity, convergence property, and generalization error bound of TMPM. Empirically, we show that TMPM achieves competitive performance on a wide range of datasets, while being almost one order of magnitude faster than existing SSL approaches. [ABSTRACT FROM AUTHOR]

This article presents a simple yet effective method for computing geodesic distances on triangle meshes. Unlike the popular window propagation methods that partition mesh edges into intervals of varying lengths, our method places evenly-spaced, source-independent Steiner points on edges. Given a source vertex, our method constructs a Steiner-point graph that partitions the surface into mutually exclusive tracks, called geodesic tracks. Inside each triangle, the tracks form sub-regions in which the change of distance field is approximately linear. Our method does not require any pre-computation, and can effectively balance speed and accuracy. Experimental results show that with 5 Steiner points on each edge, the mean relative error is less than 0.3 $\%$ % for common 3D models used in the graphics community. We propose a set of effective filtering rules to eliminate a large amount of useless broadcast events. For a 1000K-face model, our method runs 10 times faster than the conventional Steiner point method that examines a complete graph of Steiner points in each triangle. We also observe that using more Steiner points increases the accuracy at only a small extra computational cost. Our method works well for meshes with poor triangulation and non-manifold configuration, which often poses challenges to the existing PDE methods. We show that geodesic tracks, as a new data structure that encodes rich information of discrete geodesics, support accurate geodesic path and isoline tracing, and efficient distance query. Our method can be easily extended to meshes with non-constant density functions and/or anisotropic metrics. [ABSTRACT FROM AUTHOR]

This article deals with nonconvex stochastic optimization problems in deep learning. Appropriate learning rates, based on theory, for adaptive-learning-rate optimization algorithms (e.g., Adam and AMSGrad) to approximate the stationary points of such problems are provided. These rates are shown to allow faster convergence than previously reported for these algorithms. Specifically, the algorithms are examined in numerical experiments on text and image classification and are shown in experiments to perform better with constant learning rates than algorithms using diminishing learning rates. [ABSTRACT FROM AUTHOR]

This article introduces a new deep learning approach to approximately solve the covering salesman problem (CSP). In this approach, given the city locations of a CSP as input, a deep neural network model is designed to directly output the solution. It is trained using the deep reinforcement learning without supervision. Specifically, in the model, we apply the multihead attention (MHA) to capture the structural patterns, and design a dynamic embedding to handle the dynamic patterns of the problem. Once the model is trained, it can generalize to various types of CSP tasks (different sizes and topologies) without the need of retraining. Through controlled experiments, the proposed approach shows desirable time complexity: it runs more than 20 times faster than the traditional heuristic solvers with a tiny gap of optimality. Moreover, it significantly outperforms the current state-of-the-art deep learning approaches for combinatorial optimization in the aspect of both training and inference. In comparison with traditional solvers, this approach is highly desirable for most of the challenging tasks in practice that are usually large scale and require quick decisions. [ABSTRACT FROM AUTHOR]

This article proposes robust inverse $Q$ -learning algorithms for a learner to mimic an expert’s states and control inputs in the imitation learning problem. These two agents have different adversarial disturbances. To do the imitation, the learner must reconstruct the unknown expert cost function. The learner only observes the expert’s control inputs and uses inverse $Q$ -learning algorithms to reconstruct the unknown expert cost function. The inverse $Q$ -learning algorithms are robust in that they are independent of the system model and allow for the different cost function parameters and disturbances between two agents. We first propose an offline inverse $Q$ -learning algorithm which consists of two iterative learning loops: 1) an inner $Q$ -learning iteration loop and 2) an outer iteration loop based on inverse optimal control. Then, based on this offline algorithm, we further develop an online inverse $Q$ -learning algorithm such that the learner mimics the expert behaviors online with the real-time observation of the expert control inputs. This online computational method has four functional approximators: a critic approximator, two actor approximators, and a state-reward neural network (NN). It simultaneously approximates the parameters of $Q$ -function and the learner state reward online. Convergence and stability proofs are rigorously studied to guarantee the algorithm performance. [ABSTRACT FROM AUTHOR]

Focusing on the performance deterioration of nonlinear filtering algorithms in the error-in-variable (EIV) model, a nonlinear version of maximum total correntropy (MTC) algorithm called kernel recursive maximum total correntropy (KRMTC) is proposed in this brief, which constructs a nonlinear relationship based on MTC criterion between inputs and outputs in high-dimensional feature space. Compared with existing kernel adaptive filtering (KAF) algorithms based on traditional mean square error (MSE) and maximum correntropy criteria (MCC), the proposed algorithm can handle nonlinear modeling problems in the EIV model well. In addition, an approximate linear dependency (ALD) criterion is applied to reduce the computational complexity of KRMTC. To verify the feasibility of the proposed algorithm, firstly, the convergence of the KRMTC algorithm under some assumptions is discussed and its local convergence condition is given. Secondly, the proposed algorithm is applied to the Lorenz time-series prediction and wind prediction simulations. Simulation results display that the KRMTC algorithm has better performance than kernel recursive least squares (KRLS) and kernel recursive maximum correntropy (KRMC) algorithms in EIV case. [ABSTRACT FROM AUTHOR]

Broadcasting is an essential operation in wireless networks for disseminating the message from the source node to all other nodes. Unfortunately, the problem of Minimum Latency Broadcast Scheduling (MLBS) in duty-cycled wireless sensor networks is not well studied. In existing works, the construction of broadcast tree and the scheduling of transmissions are conducted separately, where a tree-based structure is used as the input of the scheduling algorithm. Relying on a pre-determined tree may result in a much large latency even using the optimal scheduling method. Thus, the MLBS problem in duty-cycled WSNs without the above limitation is investigated in this paper. First, to avoid relying on a pre-determined structure, a two-step scheduling algorithm is proposed to construct the broadcast tree and compute a collision-free schedule simultaneously. To the best of our knowledge, this is the first work that can integrate these two kinds of operations together. Second, a novel transmission mode, i.e., concurrent broadcasting, is first introduced for wireless networks and several techniques are designed to further improve the broadcast latency. Third, the multiple messages broadcasting and all-to-all broadcasting algorithms, which can generate a series of broadcast schedules independently without a pre-determined tree, are also proposed by taking care of the collisions in both the current and the previous broadcast schedules. Finally, the theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in terms of latency. [ABSTRACT FROM AUTHOR]

Provisioning reliable network services for mobile users in edge computing environments is the top priority of network service providers, as unreliable services will result in tremendous losses of revenues and customers. In this paper, we study a novel service reliability augmentation problem in a mobile edge computing (MEC) network, where mobile users request network services with service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant virtualized network function (VNF) instance placement in case the primary VNF instance fails. We aim to augment the service reliability of each admitted request to its specified reliability expectation, subject to computing capacity on each cloudlet. To this end, we first formulate a novel service reliability augmentation problem for each request with an SFC and a reliability expectation requirement, by augmenting its reliability through redundant VNF instance deployment. We then show that the problem is NP-hard, and provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets. We then deal with the service reliability augmentation problem of an admitted request under the assumption that all secondary VNF instances of each primary VNF instance must be placed into the cloudlets no more than $l$ l hops from the cloudlet of its primary VNF instance for a fixed $l$ l with $1\leq l \leq n-1$ 1 ≤ l ≤ n - 1 , where $n$ n is the number of cloudlets in the network, for which we formulate an integer linear program solution, and develop a randomized algorithm with a good approximation ratio and high probability, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We third study the service reliability augmentation problem for a set of admitted requests by extending the proposed algorithm for the service reliability augmentation problem for a single request admission. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts. [ABSTRACT FROM AUTHOR]

Automated hyperparameter optimization (HPO) has gained great popularity and is an important component of most automated machine learning frameworks. However, the process of designing HPO algorithms is still an unsystematic and manual process: new algorithms are often built on top of prior work, where limitations are identified and improvements are proposed. Even though this approach is guided by expert knowledge, it is still somewhat arbitrary. The process rarely allows for gaining a holistic understanding of which algorithmic components drive performance and carries the risk of overlooking good algorithmic design choices. We present a principled approach to automated benchmark-driven algorithm design applied to multifidelity HPO (MF-HPO). First, we formalize a rich space of MF-HPO candidates that includes, but is not limited to, common existing HPO algorithms and then present a configurable framework covering this space. To find the best candidate automatically and systematically, we follow a programming-by-optimization approach and search over the space of algorithm candidates via Bayesian optimization. We challenge whether the found design choices are necessary or could be replaced by more naive and simpler ones by performing an ablation analysis. We observe that using a relatively simple configuration (in some ways, simpler than established methods) performs very well as long as some critical configuration parameters are set to the right value. [ABSTRACT FROM AUTHOR]

Many inverse problems in machine learning, system identification, and image processing include nuisance parameters, which are important for the recovering of other parameters. Separable nonlinear optimization problems fall into this category. The special separable structure in these problems has inspired several efficient optimization strategies. A well-known method is the variable projection (VP) that projects out a subset of the estimated parameters, resulting in a reduced problem that includes fewer parameters. The expectation maximization (EM) is another separated method that provides a powerful framework for the estimation of nuisance parameters. The relationships between EM and VP were ignored in previous studies, though they deal with a part of parameters in a similar way. In this article, we explore the internal relationships and differences between VP and EM. Unlike the algorithms that separate the parameters directly, the hierarchical identification algorithm decomposes a complex model into several linked submodels and identifies the corresponding parameters. Therefore, this article also studies the difference and connection between the hierarchical algorithm and the parameter-separated algorithms like VP and EM. In the numerical simulation part, Monte Carlo experiments are performed to further compare the performance of different algorithms. The results show that the VP algorithm usually converges faster than the other two algorithms and is more robust to the initial point of the parameters. [ABSTRACT FROM AUTHOR]

The vehicular sensor network (VSN) is a bright candidate for many applications owing to its particular advantages. Such an application is air pollution monitoring, a critical issue associated directly with public health. We also notice that public transports are well-suited to deploy the network for this type of application. In this article, we propose a practical approach that leverages public buses to build the vehicle network with attached sensors for air pollution monitoring toward minimizing the deployment cost. Therefore, we hereafter call this problem vehicular sensor deployment (VSD). We first convert the VSD issue to a flow network described by a directed graph. Then, based on air sampling requirements, capacity constraints, and flow conservation of the flow network, we formulate the problem as an integer linear programming (ILP) model that yields the optimal solution. In addition, we suggest an approximation algorithm implemented by the linear programming relaxation technique combined with the randomized rounding algorithm (LPR-RRA), which provides approximate solutions to large-scale VSD problems. We also propose a greedy-based algorithm (GBA) to solve the problem against the most effective sampling in each iteration. Finally, we conduct experiments to evaluate the performance of the proposed algorithms as well as the influences of associated factors on the deployment cost. Simulation results show that the approximation algorithm approaches the optimal and outperforms the greedy. [ABSTRACT FROM AUTHOR]

Multi-scale exposure fusion (MEF) is an efficient way to fuse differently exposed low dynamic range (LDR) images of a high dynamic range (HDR) scene into an information enriched LDR image. In this paper, a new MEF algorithm is proposed to merge the differently exposed LDR images by introducing novel content adaptive edge-preserving smoothing (CAS) pyramids for the weight maps of all the LDR images. With the proposed CAS pyramids, details in the brightest and darkest regions of the HDR scene are preserved better than existing MEF algorithms on top of the Gaussian pyramids and edge-preserving smoothing pyramids. Comparisons experimentally demonstrate the effectiveness of the proposed algorithm to nine state-of-the-art MEF algorithms from both subjective and objective points of view regardless the image sizes. [ABSTRACT FROM AUTHOR]

Geometric model fitting is a fundamental task in computer vision, which serves as the pre-requisite of many downstream applications. While the problem has a simple intrinsic structure where the solution can be parameterized within a few degrees of freedom, the ubiquitously existing outliers are the main challenge. In previous studies, random sampling techniques have been established as the practical choice, since optimization-based methods are usually too time-demanding. This prospective study is intended to design efficient algorithms that benefit from a general optimization-based view. In particular, two important types of loss functions are discussed, i.e., truncated and $l_1$ l 1 losses, and efficient solvers have been derived for both upon specific approximations. Based on this philosophy, a class of algorithms are introduced to perform deterministic search for the inliers or geometric model. Recommendations are made based on theoretical and experimental analyses. Compared with the existing solutions, the proposed methods are both simple in computation and robust to outliers. Extensive experiments are conducted on publicly available datasets for geometric estimation, which demonstrate the superiority of our methods compared with the state-of-the-art ones. Additionally, we apply our method to the recent benchmark for wide-baseline stereo evaluation, leading to a significant improvement of performance. Our code is publicly available at https://github.com/AoxiangFan/EifficientDeterministicSearch. [ABSTRACT FROM AUTHOR]

Symbol detection (SD) plays an important role in a digital communication system. However, most SD algorithms require channel state information (CSI), which is often difficult to estimate accurately. As a consequence, it is challenging for these SD algorithms to approach the performance of the maximum likelihood detection (MLD) algorithm. To address this issue, we employ both semi-supervised learning and ensemble learning to design a flexible parallelizable approach in this paper. First, we prove theoretically that the proposed algorithms can arbitrarily approach the performance of the MLD algorithm with perfect CSI. Second, to enable parallel implementation and also enhance design flexibility, we further propose a parallelizable approach for multi-output systems. Finally, comprehensive simulation results are provided to demonstrate the effectiveness and superiority of the designed algorithms. In particular, the proposed algorithms approach the performance of the MLD algorithm with perfect CSI, and outperform it when the CSI is imperfect. Interestingly, a detector constructed with received signals from only two receiving antennas (less than the size of the whole receiving antenna array) can also provide good detection performance. [ABSTRACT FROM AUTHOR]

In the phase retrieval problem one seeks to recover an unknown $n$ dimensional signal vector $\mathbf {x}$ from $m$ measurements of the form $y_{i} = |(\mathbf {A} \mathbf {x})_{i}|$ , where $\mathbf {A}$ denotes the sensing matrix. Many algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix $\mathbf {A}$ is generated by sub-sampling $n$ columns of a uniformly random (i.e., Haar distributed) orthogonal matrix, in the high dimensional asymptotic regime ($m,n \rightarrow \infty, n/m \rightarrow \kappa $), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For a special class of linearized message-passing algorithms, we show that the state evolution is universal: it continues to hold even when $\mathbf {A}$ is generated by randomly sub-sampling columns of the Hadamard-Walsh matrix, if the signal is drawn from a Gaussian prior. [ABSTRACT FROM AUTHOR]

As the artificial intelligence and Internet of Things (AIoT) develop rapidly, the deployment of artificial neural networks in edge computing is becoming significant with great challenge. The binarized convolutional neural network (BCNN) is one of the most widely adopted light-weight ANNs in AIoT, which can achieve the balance of system accuracy and hardware resource consumption, compared to others. To achieve high power and area efficiency in BCNN deployment, many approximate computing (AxC) techniques are integrated to make full use of the resilience of BCNN. As the research focused on the integration of AxC in circuit design, the design of AxC itself is not fully considered when applied to specific applications or domains. Based on circuit-architecture-system co-design, this article proposes an efficient BCNN deployment method, including a quality-circuit co-design method for approximate adder generation, a quality-aware intercompensation approach for addition tree, and a computing quality involved retraining approach for BCNN deployment. Experimental results show that the proposed quality model can achieve 86.43% in average accuracy while evaluating nine types of typical approximate adders. The proposed method is conducted on the applications of keyword spotting of GSCD, MNIST, and CIFAR-10, and we can further rise the approximation degree by 50%–75%, while reducing the accuracy by less than 1%. [ABSTRACT FROM AUTHOR]

Approximate computing is an attractive paradigm for reducing the design complexity of error-resilient systems, therefore, improving performance and saving power consumption. In this work, we propose a new two-level approximate logic synthesis method based on cube insertion and removal procedures. The experimental results have shown significant literal count and runtime reduction compared to the state-of-the-art approach. The method scalability is illustrated for a high error threshold over large benchmark circuits. The obtained solutions have presented a literal number reduction up to 38%, 56%, and 93% with respect to an error rate of 1%, 3%, and 5%, respectively. [ABSTRACT FROM AUTHOR]

Online streaming feature selection (OSFS) has attracted extensive attention during the past decades. Current approaches commonly assume that the feature space of fixed data instances dynamically increases without any missing data. However, this assumption does not always hold in many real applications. Motivated by this observation, this study aims to implement online feature selection from sparse streaming features, i.e., features flow in one by one with missing data as instance count remains fixed. To do so, this study proposes a latent-factor-analysis-based online sparse-streaming-feature selection algorithm (LOSSA). Its main idea is to apply latent factor analysis to pre-estimate missing data in sparse streaming features before conducting feature selection, thereby addressing the missing data issue effectively and efficiently. Theoretical and empirical studies indicate that LOSSA can significantly improve the quality of OSFS when missing data are encountered in target instances. [ABSTRACT FROM AUTHOR]

This article studies the mean standard deviation (mean-std) Canadian traveller problem (CTP). Different from the canonical CTP, which aims at minimizing the traveller's expected travel time, while considering edge breakdown probabilities, we introduce the reliability version of CTP, which tries to find a routing policy with the minimal linear combination of the travel time's mean and standard deviation. With the recent development of internet-of-things (IoT) technology, the transportation network's edges' travel-time statistics, i.e., mean and standard deviation, as well as the traversal probabilities, are available to the end users. With those information, we propose a dual dynamic programming (DDP) method, which simultaneously estimates the first-order and the second-order moments of a given decision-list (DL) policy, and thereby makes improvements towards to the optimal one through the generalized policy iteration (GPI) scheme. We construct an open source benchmark environment to evaluate the performance of different mean-std CTP solutions, and show that the DDP method outperforms state of the arts in a range of transportation networks. [ABSTRACT FROM AUTHOR]

In this article, we consider the problem of estimating diffraction attenuation from the approximation of terrain using a multiple bridged knife-edge model. This model can be considered as a generalization of the well-known multiple knife-edge (MKE) one where spaces between knife-edges are bridged by reflecting surfaces. A series-based-standard solution is presented in the literature but suffers from its very high computational complexity. We, thus, propose to generalize the recursive Vogler algorithm developed for the MKE model to tackle this problem. To reduce complexity, the proposed algorithm exploits the recursive form to avoid repeated calculations of the existing solution. Moreover, we provide a complexity analysis of both the standard algorithm and the proposed algorithm based on the number of computed integrals. Both theoretical and numerical results show that our proposed algorithm is faster than the original one while having identical accuracy, hence proving the effectiveness of our solution. [ABSTRACT FROM AUTHOR]

There is growing interest in applying distributed machine learning to edge computing, forming federated edge learning. Federated edge learning faces non-i.i.d. and heterogeneous data, and the communication between edge workers, possibly through distant locations and with unstable wireless networks, is more costly than their local computational overhead. In this work, we propose ${{\sf DONE}}$ DONE , a distributed approximate Newton-type algorithm with fast convergence rate for communication-efficient federated edge learning. First, with strongly convex and smooth loss functions, ${{\sf DONE}}$ DONE approximates the Newton direction in a distributed manner using the classical Richardson iteration on each edge worker. Second, we prove that ${{\sf DONE}}$ DONE has linear-quadratic convergence and analyze its communication complexities. Finally, the experimental results with non-i.i.d. and heterogeneous data show that ${{\sf DONE}}$ DONE attains a comparable performance to Newton's method. Notably, ${{\sf DONE}}$ DONE requires fewer communication iterations compared to distributed gradient descent and outperforms DANE, FEDL, and GIANT, state-of-the-art approaches, in the case of non-quadratic loss functions. [ABSTRACT FROM AUTHOR]

In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogeneous servers that will achieve the goal of maximizing the system’s gain defined as the value of completed tasks minus system operation costs. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy optimization algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing, we deploy a DRL module to predict the best allocation sequence for each arriving batch of tasks based on the knowledge (allocation strategies) learnt from previous batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximize the total gain increase. We show that our greedy strategy has a performance guarantee of competitive ratio $\frac{1}{1+\kappa }$ 1 1 + κ to the optimal offline solution, which improves the existing result for the same problem, where $\kappa$ κ is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy algorithm by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRL’s prediction error within a proven worst-case performance guarantee for any allocation sequence. It enables a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of combining machine learning (ML) and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems. [ABSTRACT FROM AUTHOR]

This article considers a federated temporal difference (TD) learning algorithm and provides both asymptotic and finite-time analyses. To protect each worker agent's cost information from being acquired by possible attackers, we propose a privacy-preserving variant of the algorithm by adding perturbation to the exchanged information. We show the rigorous differential privacy guarantee by using moments accountant and derive an upper bound of the utility loss for the privacy-preserving algorithm. Evaluations are also provided to corroborate the efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

This brief addresses the problem of implementing very large constant multiplications by a single variable under the shift-adds architecture using a minimum number of adders/subtractors. Due to the intrinsic complexity of the problem, we introduce an approximate algorithm, called TÕLL, which partitions the very large constants into smaller ones. To reduce the number of operations, TÕLL incorporates graph-based and common subexpression elimination methods proposed for the shift-adds design of constant multiplications. It can also consider the delay of a multiplierless design defined in terms of the maximum number of operations in series, i.e., the number of adder-steps, while reducing the number of operations. High-level experimental results show that the adder-steps of a shift-adds design can be reduced significantly with a little overhead in the number of operations. Gate-level experimental results indicate that while the shift-adds design can lead to a 36.6% reduction in gate-level area with respect to a design using a multiplier, the delay-aware optimization can yield a 48.3% reduction in minimum achievable delay of the shift-adds design when compared to the area-aware optimization. [ABSTRACT FROM AUTHOR]

We present two model-based neural network architectures purposed for sporadic user detection and channel estimation in massive machine-type communications. In the scenario under consideration, a base station assigns the users a set of pilot sequences that is linearly dependent, but because user activity is sporadic the detection/estimation problem is amenable to sparse recovery algorithms. Further, we consider a millimeter-wave wireless channel, so that the channel vectors are sparse in a known dictionary. We apply the deep unfolding framework to design custom neural network layers by unrolling two iterative optimization algorithms: (1) linearized alternating direction method of multipliers, which we apply to a constrained convex problem, and (2) vector approximate message passing featuring a novel denoiser based on the iterative shrinkage thresholding algorithm. The networks thus inherit domain knowledge as encapsulated by the signal model, and suitable operations as informed by the algorithms—in the same spirit as convolutional networks that exploit structure inherent in images and audio, except grounded in optimization and statistics. The networks, trained on synthetic data generated from the block-fading millimeter-wave multiple access channel model, offer improved complexity and accuracy relative to their iterative counterparts, and are potentially a boon to cell-free MIMO systems. [ABSTRACT FROM AUTHOR]

Wireless multiplayer interactive virtual reality (VR) game has the high computing workload of VR and unpredictable interaction among players, which brings severe challenges to the design of wireless communication systems. In this paper, we propose a wireless multiplayer interactive VR game transmission framework based on mobile edge computing (MEC) that is able to model the interaction among players and compute the post-processing procedures at the MEC server or the mobile VR device. In the framework, the absolute delay of each player is used to avoid VR vertigo and the inter-player delay among players is used to model the fairness of the interactive game. Aiming to minimize the average inter-player delay, we optimize the computing resource allocation of the MEC server, the wireless bandwidth allocation and the post-processing decision policy subject to the constraints of the absolute delay requirements, the local energy limits of players, the total bandwidth limit and the computing resources limit. To tackle the non-convex problem efficiently, we design an iterative algorithm based on the NESTT-G algorithm which iteratively optimizes the truncated first-order Taylor approximation of the objective. Numerical results demonstrate the proposed algorithm can reduce the average inter-player delay significantly with lower complexity, and also reveal the impact of different parameters and the channel state conditions on the post-processing decision and edge resource allocation. [ABSTRACT FROM AUTHOR]

State estimation algorithms deployed in modern grids are vulnerable towards false data injection attacks. This work demonstrates a novel attack vector (AV) formulation scheme by exploiting the low-rank subspace of the topology matrix. With constraints over the state deviation vector, this work showcases that the developed AV can effectively bypass the residue test for a demonstrated test bench. [ABSTRACT FROM AUTHOR]

Convolutional transform learning (CTL), learning filters by minimizing the data fidelity loss function in an unsupervised way, is becoming very pervasive, resulting from keeping the best of both worlds: the benefit of unsupervised learning and the success of the convolutional neural network. There have been growing interests in developing efficient CTL algorithms. However, developing a convergent and accelerated CTL algorithm with accurate representations simultaneously with proper sparsity is an open problem. This article presents a new CTL framework with a $log$ regularizer that can not only obtain accurate representations but also yield strong sparsity. To efficiently address our nonconvex composite optimization, we propose to employ the proximal difference of the convex algorithm (PDCA) which relies on decomposing the nonconvex regularizer into the difference of two convex parts and then optimizes the convex subproblems. Furthermore, we introduce the extrapolation technology to accelerate the algorithm, leading to a fast and efficient CTL algorithm. In particular, we provide a rigorous convergence analysis for the proposed algorithm under the accelerated PDCA. The experimental results demonstrate that the proposed algorithm can converge more stably to desirable solutions with lower approximation error and simultaneously with stronger sparsity and, thus, learn filters efficiently. Meanwhile, the convergence speed is faster than the existing CTL algorithms. [ABSTRACT FROM AUTHOR]

Bilevel optimization involves two levels of optimization, where one optimization problem is nested within the other. The structure of the problem often requires solving a large number of inner optimization problems that make these kinds of optimization problems expensive to solve. The reaction set mapping and the lower level optimal value function mapping are often used to reduce bilevel optimization problems to a single level; however, the mappings are not known a priori, and the need is to be estimated. Though there exist a few studies that rely on the estimation of these mappings, they are often applied to problems where one of these mappings has a known form, that is, piecewise linear, convex, etc. In this article, we utilize both these mappings together to solve general bilevel optimization problems without any assumptions on the structure of these mappings. Kriging approximations are created during the generations of an evolutionary algorithm, where the population members serve as the samples for creating the approximations. One of the important features of the proposed algorithm is the creation of an auxiliary optimization problem using the Kriging-based metamodel of the lower level optimal value function that solves an approximate relaxation of the bilevel optimization problem. The auxiliary problem when used for local search is able to accelerate the evolutionary algorithm toward the bilevel optimal solution. We perform experiments on two sets of test problems and a problem from the domain of control theory. Our experiments suggest that the approach is quite promising and can lead to substantial savings when solving bilevel optimization problems. The approach is able to outperform state-of-the-art methods that are available for solving bilevel problems, in particular, the savings in function evaluations for the lower level problem are substantial with the proposed approach. [ABSTRACT FROM AUTHOR]

Reinforcement learning (RL) has demonstrated its ability to solve high dimensional tasks by leveraging non-linear function approximators. However, these successes are mostly achieved by ’black-box’ policies in simulated domains. When deploying RL to the real world, several concerns regarding the use of a ’black-box’ policy might be raised. In order to make the learned policies more transparent, we propose in this paper a policy iteration scheme that retains a complex function approximator for its internal value predictions but constrains the policy to have a concise, hierarchical, and human-readable structure, based on a mixture of interpretable experts. Each expert selects a primitive action according to a distance to a prototypical state. A key design decision to keep such experts interpretable is to select the prototypical states from trajectory data. The main technical contribution of the paper is to address the challenges introduced by this non-differentiable prototypical state selection procedure. Experimentally, we show that our proposed algorithm can learn compelling policies on continuous action deep RL benchmarks, matching the performance of neural network based policies, but returning policies that are more amenable to human inspection than neural network or linear-in-feature policies. [ABSTRACT FROM AUTHOR]