Search

Network pruning can reduce the computation cost of deep neural network (DNN) models. However, sparse models often produce randomly-distributed weights to maintain accuracy, leading to irregular computations. Consequently, unstructured sparse models cannot achieve meaningful speedup on commodity hardware built for dense matrix computations. Accelerators are usually modified or designed with structured sparsity-optimized architectures for exploiting sparsity. For example, the Ampere architecture introduces a sparse tensor core, which adopts the 2:4 sparsity pattern. We propose a pruning method that builds upon the insight that matrix multiplication generally breaks the large matrix into multiple smaller tiles for parallel execution. We present the tile-wise sparsity pattern, which maintains a structured sparsity pattern at the tile level for efficient execution but allows for irregular pruning at the global scale to maintain high accuracy. In addition, the tile-wise sparsity is implemented at the global memory level, and the 2:4 sparsity executes at the register level inside the sparse tensor core. We can combine these two patterns into a tile-vector-wise (TVW) sparsity pattern to explore more fine-grained sparsity and further accelerate the sparse DNN models. We evaluate the TVW on the GPU, achieving averages of $1.85\times$, $2.75\times$, and $22.18\times$ speedups over the dense model, block sparsity, and unstructured sparsity., Comment: Accepted by IEEE Transactions on Computers. arXiv admin note: substantial text overlap with arXiv:2008.13006

This paper studies the idea of ``deception by motion'' through a two-player dynamic game played between a Mover who must retrieve resources at a goal location, and an Eater who can consume resources at two candidate goals. The Mover seeks to minimize the resource consumption at the true goal, and the Eater tries to maximize it. While the Mover has the knowledge about the true goal, the Eater cannot differentiate between the two candidates. Unlike existing works on deceptive motion control that measures the deceptiveness through the quality of inference made by a distant observer (an estimator), we incorporate their actions to directly measure the efficacy of deception through the outcome of the game. An equilibrium concept is then proposed without the notion of an estimator. We further identify a pair of equilibrium strategies and demonstrate that if the Eater optimizes for the worst-case scenario, hiding the intention (deception by ambiguity) is still effective, whereas trying to fake the true goal (deception by exaggeration) is not., Comment: Submitted to the IEEE Control Systems Letters (L-CSS), 2023

Although ankle injuries resulting from postural instability are frequently observed during high-speed and intense physical activities, most current research has been limited to static or quasi-static models of the lower limb, or has focused solely on the ankle joint itself. In this study, to explain the kinetic mechanism underlying postural instability and ankle twists, we present a nonlinear dynamical model for the human lower limb that takes into account transient behavior and large rotations. The landing of the lower limb on the ground is modeled as a mechanical system with two degrees of freedom (DoFs). The configuration of the lower limb mechanism can be completely defined by the vertical displacement and the inclination angle. We quantify the postural stability of the lower limb using a dimensionless energy threshold. Numerical examples verify the effectiveness of this stability indicator and demonstrate that individuals with a normal foot have better postural stability compared to those with flat and high-arched feet, and are less likely to experience ankle injuries in jumping and landing scenarios.

This work proposes a dynamic and adversarial resource allocation problem in a graph environment, which is referred to as the dynamic Defender-Attacker Blotto (dDAB) game. A team of defender robots is tasked to ensure numerical advantage at every node in the graph against a team of attacker robots. The engagement is formulated as a discrete-time dynamic game, where the two teams reallocate their robots in sequence and each robot can move at most one hop at each time step. The game terminates with the attacker's victory if any node has more attacker robots than defender robots. Our goal is to identify the necessary and sufficient number of defender robots to guarantee defense. Through a reachability analysis, we first solve the problem for the case where the attacker team stays as a single group. The results are then generalized to the case where the attacker team can freely split and merge into subteams. Crucially, our analysis indicates that there is no incentive for the attacker team to split, which significantly reduces the search space for the attacker's winning strategies and also enables us to design defender counter-strategies using superposition. We also present an efficient numerical algorithm to identify the necessary and sufficient number of defender robots to defend a given graph. Finally, we present illustrative examples to verify the efficacy of the proposed framework.

This work studies the behaviors of two large-population teams competing in a discrete environment. The team-level interactions are modeled as a zero-sum game while the agent dynamics within each team is formulated as a collaborative mean-field team problem. Drawing inspiration from the mean-field literature, we first approximate the large-population team game with its infinite-population limit. Subsequently, we construct a fictitious centralized system and transform the infinite-population game to an equivalent zero-sum game between two coordinators. We study the optimal coordination strategies for each team via a novel reachability analysis and later translate them back to decentralized strategies that the original agents deploy. We prove that the strategies are $\epsilon$-optimal for the original finite-population team game, and we further show that the suboptimality diminishes when team size approaches infinity. The theoretical guarantees are verified by numerical examples., Comment: Published in AAAI 2024

In this work, we extend the convex bodies chasing problem (CBC) to an adversarial setting, where an agent (the Player) is tasked with chasing a sequence of convex bodies generated adversarially by another agent (the Opponent). The Player aims to minimize the total cost associated with its own movements, while the Opponent tries to maximize the same cost. The set of feasible convex bodies is finite and known to both agents, which allows us to provide performance guarantees with max-min optimality. Under certain assumptions, we show the continuity of the optimal value function, and propose an algorithm to numerically approximate the optimal policies for both the Player and the Opponent within a guaranteed tolerance. Finally, the theoretical results are verified through numerical examples.

This paper presents the jump law of co-states in optimal control for state-dependent switched systems. The number of switches and the switching modes are assumed to be known a priori. A proposed jump law is rigorously derived by theoretical analysis and illustrated by simulation results. An algorithm is then proposed to solve optimal control for state-dependent hybrid systems. Through numerical simulations, we further show that the proposed approach is more efficient than existing methods in solving optimal control for state-dependent switched systems.

Transformer architecture has become the de-facto model for many machine learning tasks from natural language processing and computer vision. As such, improving its computational efficiency becomes paramount. One of the major computational inefficiency of Transformer-based models is that they spend the identical amount of computation throughout all layers. Prior works have proposed to augment the Transformer model with the capability of skimming tokens to improve its computational efficiency. However, they suffer from not having effectual and end-to-end optimization of the discrete skimming predictor. To address the above limitations, we propose the Transkimmer architecture, which learns to identify hidden state tokens that are not required by each layer. The skimmed tokens are then forwarded directly to the final output, thus reducing the computation of the successive layers. The key idea in Transkimmer is to add a parameterized predictor before each layer that learns to make the skimming decision. We also propose to adopt reparameterization trick and add skim loss for the end-to-end training of Transkimmer. Transkimmer achieves 10.97x average speedup on GLUE benchmark compared with vanilla BERT-base baseline with less than 1% accuracy degradation., Comment: Published as a conference paper at ACL 2022

In this work we present a hierarchical framework for solving discrete stochastic pursuit-evasion games (PEGs) in large grid worlds. With a partition of the grid world into superstates (e.g., "rooms"), the proposed approach creates a two-resolution decision-making process, which consists of a set of local PEGs at the original state level and an aggregated PEG at the superstate level. Having much smaller cardinality, both the local games and the aggregated game can be easily solved to a Nash equilibrium. To connect the decision-making at the two resolutions, we use the Nash values of the local PEGs as the rewards for the aggregated game. Through numerical simulations, we show that the proposed hierarchical framework significantly reduces the computation overhead, while still maintaining a satisfactory level of performance when competing against the flat Nash policies.

This work studies a dynamic, adversarial resource allocation problem in environments modeled as graphs. A blue team of defender robots are deployed in the environment to protect the nodes from a red team of attacker robots. We formulate the engagement as a discrete-time dynamic game, where the robots can move at most one hop in each time step. The game terminates with the attacker's win if any location has more attacker robots than defender robots at any time. The goal is to identify dynamic resource allocation strategies, as well as the conditions that determines the winner: graph structure, available resources, and initial conditions. We analyze the problem using reachable sets and show how the outdegree of the underlying graph directly influences the difficulty of the defending task. Furthermore, we provide algorithms that identify sufficiency of attacker's victory.

Transformer models have achieved promising results on natural language processing (NLP) tasks including extractive question answering (QA). Common Transformer encoders used in NLP tasks process the hidden states of all input tokens in the context paragraph throughout all layers. However, different from other tasks such as sequence classification, answering the raised question does not necessarily need all the tokens in the context paragraph. Following this motivation, we propose Block-skim, which learns to skim unnecessary context in higher hidden layers to improve and accelerate the Transformer performance. The key idea of Block-Skim is to identify the context that must be further processed and those that could be safely discarded early on during inference. Critically, we find that such information could be sufficiently derived from the self-attention weights inside the Transformer model. We further prune the hidden states corresponding to the unnecessary positions early in lower layers, achieving significant inference-time speedup. To our surprise, we observe that models pruned in this way outperform their full-size counterparts. Block-Skim improves QA models' accuracy on different datasets and achieves 3 times speedup on BERT-base model., Comment: Published as a conference paper at AAAI 2022

Meshfree methods for in silico modelling and simulation of cardiac electrophysiology are gaining more and more popularity. These methods do not require a mesh and are more suitable than the Finite Element Method (FEM) to simulate the activity of complex geometrical structures like the human heart. However, challenges such as numerical integration accuracy and time efficiency remain and limit their applicability. Recently, the Fragile Points Method (FPM) has been introduced in the meshfree methods family. It uses local, simple, polynomial, discontinuous functions to construct trial and test functions in the Galerkin weak form. This allows for accurate integration and improved efficiency while enabling the imposition of essential and natural boundary conditions as in the FEM. In this work, we consider the application of FPM for cardiac electrophysiology simulation. We derive the cardiac monodomain model using the FPM formulation and we solve several benchmark problems in 2D and 3D. We show that FPM leads to solutions of similar accuracy and efficiency with FEM while alleviating the need for a mesh. Additionally, FPM demonstrates better convergence than FEM in the considered benchmarks., Comment: 14 pages, 7 figures, 3 tables, research article

Mean-field games (MFG) were introduced to efficiently analyze approximate Nash equilibria in large population settings. In this work, we consider entropy-regularized mean-field games with a finite state-action space in a discrete time setting. We show that entropy regularization provides the necessary regularity conditions, that are lacking in the standard finite mean field games. Such regularity conditions enable us to design fixed-point iteration algorithms to find the unique mean-field equilibrium (MFE). Furthermore, the reference policy used in the regularization provides an extra parameter, through which one can control the behavior of the population. We first consider a stochastic game with a large population of $N$ homogeneous agents. We establish conditions for the existence of a Nash equilibrium in the limiting case as $N$ tends to infinity, and we demonstrate that the Nash equilibrium for the infinite population case is also an $\epsilon$-Nash equilibrium for the $N$-agent system, where the sub-optimality $\epsilon$ is of order $\mathcal{O}\big(1/\sqrt{N}\big)$. Finally, we verify the theoretical guarantees through a resource allocation example and demonstrate the efficacy of using a reference policy to control the behavior of a large population.

Optical neuroimaging is a vital tool for understanding the brain structure and the connection between regions and nuclei. However, the image noise introduced in the sample preparation and the imaging system hinders the extraction of the possible knowlege from the dataset, thus denoising for the optical neuroimaging is usually necessary. The supervised denoisng methods often outperform the unsupervised ones, but the training of the supervised denoising models needs the corresponding clean labels, which is not always avaiable due to the high labeling cost. On the other hand, those semantic labels, such as the located soma positions, the reconstructed neuronal fibers, and the nuclei segmentation result, are generally available and accumulated from everyday neuroscience research. This work connects a supervised denoising and a semantic segmentation model together to form a end-to-end model, which can make use of the semantic labels while still provides a denoised image as an intermediate product. We use both the supervised and the self-supervised models for the denoising and introduce a new cost term for the joint denoising and the segmentation setup. We test the proposed approach on both the synthetic data and the real-world data, including the optical neuroimaing dataset and the electron microscope dataset. The result shows that the joint denoising result outperforms the one using the denoising method alone and the joint model benefits the segmentation and other downstream task as well.

Mixed-based point cloud augmentation is a popular solution to the problem of limited availability of large-scale public datasets. But the mismatch between mixed points and corresponding semantic labels hinders the further application in point-wise tasks such as part segmentation. This paper proposes a point cloud augmentation approach, PointManifoldCut(PMC), which replaces the neural network embedded points, rather than the Euclidean space coordinates. This approach takes the advantage that points at the higher levels of the neural network are already trained to embed its neighbors relations and mixing these representation will not mingle the relation between itself and its label. We set up a spatial transform module after PointManifoldCut operation to align the new instances in the embedded space. The effects of different hidden layers and methods of replacing points are also discussed in this paper. The experiments show that our proposed approach can enhance the performance of point cloud classification as well as segmentation networks, and brings them additional robustness to attacks and geometric transformations. The code of this paper is available at: https://github.com/fun0515/PointManifoldCut.

Online continual learning from data streams in dynamic environments is a critical direction in the computer vision field. However, realistic benchmarks and fundamental studies in this line are still missing. To bridge the gap, we present a new online continual object detection benchmark with an egocentric video dataset, Objects Around Krishna (OAK). OAK adopts the KrishnaCAM videos, an ego-centric video stream collected over nine months by a graduate student. OAK provides exhaustive bounding box annotations of 80 video snippets (~17.5 hours) for 105 object categories in outdoor scenes. The emergence of new object categories in our benchmark follows a pattern similar to what a single person might see in their day-to-day life. The dataset also captures the natural distribution shifts as the person travels to different places. These egocentric long-running videos provide a realistic playground for continual learning algorithms, especially in online embodied settings. We also introduce new evaluation metrics to evaluate the model performance and catastrophic forgetting and provide baseline studies for online continual object detection. We believe this benchmark will pose new exciting challenges for learning from non-stationary data in continual learning. The OAK dataset and the associated benchmark are released at https://oakdata.github.io/., Comment: ICCV 2021

This paper provides a framework to quantify the sensitivity associated with behavioral models based on Cumulative Prospect Theory (CPT). These are used to design dynamic pricing strategies aimed at maximizing performance metrics of the Shared Mobility On-Demand Service (SMoDS), as solutions to a constrained nonlinear optimization problem. We analyze the sensitivity of both the optimal tariff as well as the optimal objective function with respect to CPT model parameters. In addition to deriving analytical solutions under certain assumptions, more general numerical results are obtained via computational experiments and simulations to analyze the sensitivity. We find that the model is relatively robust for small to moderate parameter perturbations. Although some of the trends in sensitivity are fairly general, the exact nature of variations in many cases depends heavily on the specific travel scenarios and modes being considered. This is primarily due to the complex nonlinearities in the problem, as well as the significant heterogeneity in passenger preferences across different types of trips., Comment: 29 pages, 13 figures, submitted to Transportation Research Part B: Methodological

Three kinds of Fragile Points Methods based on Petrov-Galerkin weak-forms (PG-FPMs) are proposed for analyzing heat conduction problems in nonhomogeneous anisotropic media. This is a follow-up of the previous study on the original FPM based on a symmetric Galerkin weak-form. The trial function is piecewise-continuous, written as local Taylor expansions at the Fragile Points. A modified Radial Basis Function-based Differential Quadrature (RBF-DQ) method is employed for establishing the local approximation. The Dirac delta function, Heaviside step function, and the local fundamental solution of the governing equation are alternatively used as test functions. Vanishing or pure contour integral formulation in subdomains or on local boundaries can be obtained. Extensive numerical examples in 2D and 3D are provided as validations. The collocation method (PG-FPM-1) is superior in transient analysis with arbitrary point distribution and domain partition. The finite volume method (PG-FPM-2) shows the best efficiency, saving 25% to 50% computational time comparing with the Galerkin FPM. The singular solution method (PG-FPM-3) is highly efficient in steady-state analysis. The anisotropy and nonhomogeneity give rise to no difficulties in all the methods. The proposed PG-FPM approaches represent an improvement to the original Galerkin FPM, as well as to other meshless methods in earlier literature.

Recent research on the multi-head attention mechanism, especially that in pre-trained models such as BERT, has shown us heuristics and clues in analyzing various aspects of the mechanism. As most of the research focus on probing tasks or hidden states, previous works have found some primitive patterns of attention head behavior by heuristic analytical methods, but a more systematic analysis specific on the attention patterns still remains primitive. In this work, we clearly cluster the attention heatmaps into significantly different patterns through unsupervised clustering on top of a set of proposed features, which corroborates with previous observations. We further study their corresponding functions through analytical study. In addition, our proposed features can be used to explain and calibrate different attention heads in Transformer models.

In the first part of this two-paper series, a new Fragile Points Method (FPM), in both primal and mixed formulations, is presented for analyzing flexoelectric effects in 2D dielectric materials. In the present paper, a number of numerical results are provided as validations, including linear and quadratic patch tests, flexoelectric effects in continuous domains, and analyses of stationary cracks in dielectric materials. A discussion of the influence of the electroelastic stress is also given, showing that Maxwell stress could be significant and thus the full flexoelectric theory is recommended to be employed for nano-scale structures. The present primal as well as mixed FPMs also show their suitability and effectiveness in simulating crack initiation and propagation with flexoelectric effect. Flexoelectricity, coupled with piezoelectric effect, can help, hinder, or deflect the crack propagation paths and should not be neglected in nano-scale crack analysis. In FPM, no remeshing or trial function enhancement are required in modeling crack propagation. A new Bonding-Energy-Rate(BER)-based crack criterion as well as classic stress-based criterion are used for crack development simulations. Other complex problems such as dynamic crack developments, fracture, fragmentation and 3D flexoelectric analyses will be given in our future studies.

Flexoelectricity refers to a phenomenon which involves a coupling of the mechanical strain gradient and electric polarization. In this study, a meshless Fragile Points Method (FPM), is presented for analyzing flexoelectric effects in dielectric solids. Local, simple, polynomial and discontinuous trial and test functions are generated with the help of a local meshless Differential Quadrature approximation of derivatives. Both primal and mixed FPM are developed, based on two alternate flexoelectric theories, with or without the electric gradient effect and Maxwell stress. In the present primal as well as mixed FPM, only the displacements and electric potential are retained as explicit unknown variables at each internal Fragile Point in the final algebraic equations. Thus the number of unknowns in the final system of algebraic equations is kept to be absolutely minimal. An algorithm for simulating crack initiation and propagation using the present FPM is presented, with classic stress-based criterion as well as a Bonding-Energy-Rate(BER)-based criterion for crack development. The present primal and mixed FPM approaches represent clear advantages as compared to the current methods for computational flexoelectric analyses, using primal as well as mixed Finite Element Methods, Element Free Galerkin (EFG) Methods, Meshless Local Petrov Galerkin (MLPG) Methods, and Isogeometric Analysis (IGA) Methods, because of the following new features: they are simpler Galerkin meshless methods using polynomial trial and test functions; minimal DoFs per Point make it very user-friendly; arbitrary polygonal subdomains make it flexible for modeling complex geometries; the numerical integration of the primal as well as mixed FPM weak forms is trivially simple; and FPM can be easily employed in crack development simulations without remeshing or trial function enhancement.

We explore the use of policy approximations to reduce the computational cost of learning Nash equilibria in zero-sum stochastic games. We propose a new Q-learning type algorithm that uses a sequence of entropy-regularized soft policies to approximate the Nash policy during the Q-function updates. We prove that under certain conditions, by updating the regularized Q-function, the algorithm converges to a Nash equilibrium. We also demonstrate the proposed algorithm's ability to transfer previous training experiences, enabling the agents to adapt quickly to new environments. We provide a dynamic hyper-parameter scheduling scheme to further expedite convergence. Empirical results applied to a number of stochastic games verify that the proposed algorithm converges to the Nash equilibrium, while exhibiting a major speed-up over existing algorithms., Comment: Accepted at IJCAI-21

Network pruning can reduce the high computation cost of deep neural network (DNN) models. However, to maintain their accuracies, sparse models often carry randomly-distributed weights, leading to irregular computations. Consequently, sparse models cannot achieve meaningful speedup on commodity hardware (e.g., GPU) built for dense matrix computations. As such, prior works usually modify or design completely new sparsity-optimized architectures for exploiting sparsity. We propose an algorithm-software co-designed pruning method that achieves latency speedups on existing dense architectures. Our work builds upon the insight that the matrix multiplication generally breaks the large matrix into multiple smaller tiles for parallel execution. We propose a tiling-friendly "tile-wise" sparsity pattern, which maintains a regular pattern at the tile level for efficient execution but allows for irregular, arbitrary pruning at the global scale to maintain the high accuracy. We implement and evaluate the sparsity pattern on GPU tensor core, achieving a 1.95x speedup over the dense model., Comment: 12pages, ACM/IEEE Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC20)

A meshless Fragile Points Method (FPM) is presented for analyzing 2D flexoelectric problems. Local, simple, polynomial and discontinuous trial and test functions are generated with the help of a local meshless differential quadrature approximation of the first three derivatives. Interior Penalty Numerical Fluxes are employed to ensure the consistency of the method. Based on a Galerkin weak-form formulation, the present FPM leads to symmetric and sparse matrices, and avoids the difficulties of numerical integration in the previous meshfree methods. Numerical examples including isotropic and anisotropic materials with flexoelectric and piezoelectric effects are provided as validations. The present method is much simpler than the Finite Element Method, or the Element-Free Galerkin (EFG) and Meshless Local Petrov-Galerkin (MLPG) methods, and the numerical integration of the weak form is trivially simple.

We present a framework that incorporates the idea of bounded rationality into dynamic stochastic pursuit-evasion games. The solution of a stochastic game is characterized, in general, by its (Nash) equilibria in feedback form. However, computing these Nash equilibrium strategies may require extensive computational resources. In this paper, the agents are modeled as bounded rational entities having limited computational resources. We illustrate the framework by applying it to a pursuit-evasion game between two vehicles in a stochastic wind field, where both the pursuer and the evader are bounded rational. We show how such a game may be analyzed by properly casting it as an iterative sequence of finite-state Markov Decision Processes (MDPs). Leveraging tools and algorithms from cognitive hierarchy theory ("level-$k$ thinking") we compute the solution of the ensuing discrete game, while taking into consideration the rationality level of each agent. We also present an online algorithm for each agent to infer its opponent rationality level., Comment: 16 pages, 5 figures, submitted to Journal of Guidance, Control, and Dynamics

A new and effective computational approach is presented for analyzing transient heat conduction problems. The approach consists of a meshless Fragile Points Method (FPM) being utilized for spatial discretization, and a Local Variational Iteration (LVI) scheme for time discretization. Anisotropy and nonhomogeneity do not give rise to any difficulties in the present implementation. The meshless FPM is based on a Galerkin weak-form formulation and thus leads to symmetric matrices. Local, very simple, polynomial and discontinuous trial and test functions are employed. In the meshless FPM, Interior Penalty Numerical Fluxes are introduced to ensure the consistency of the method. The LVIM in the time domain is generated as a combination of the Variational Iteration Method (VIM) applied over a large time interval and numerical algorithms. A set of collocation nodes are employed in each finitely large time interval. The FPM + LVIM approach is capable of solving transient heat transfer problems in complex geometries with mixed boundary conditions, including pre-existing cracks. Numerical examples are presented in 2D and 3D domains. Both functionally graded materials and composite materials are considered. It is shown that, with suitable computational parameters, the FPM + LVIM approach is not only accurate, but also efficient, and has reliable stability under relatively large time intervals. The present methodology represents a considerable improvement to the current state of science in computational transient heat conduction in anisotropic nonhomogeneous media.