pwc-archive/papers-with-abstracts huggingface dataset:
Classes of ODE solutions: smoothness, covering numbers, implications for noisy function fitting, and the curse of smoothness phenomenon
Authors: Ying Zhu, Mozhgan Mirzaei
Date: 2020-11-23 00:00:00

Many numerical methods for recovering ODE solutions from data rely on approximating the solutions using basis functions or kernel functions under a least square criterion. The accuracy of this approach hinges on the smoothness of the solutions. This paper provides a theoretical foundation for these methods by establishing novel results on the smoothness and covering numbers of ODE solution classes (as a measure of their "size"). Our results provide answers to "how do the degree of smoothness and the "size" of a class of ODEs affect the "size" of the associated class of solutions?" We show that: (1) for $y^{'}=f\left(y\right)$ and $y^{'}=f\left(x,\,y\right)$, if the absolute values of all $k$th ($k\leq\beta+1$) order derivatives of $f$ are bounded by $1$, then the solution can end up with the $(k+1)$th derivative whose magnitude grows factorially fast in $k$ -- "a curse of smoothness"; (2) our upper bounds for the covering numbers of the $(\beta+2)-$degree smooth solution classes are greater than those of the "standard" $(\beta+2)-$degree smooth class of univariate functions; (3) the mean squared error of least squares fitting for noisy recovery has a convergence rate no larger than $\left(\frac{1}{n}\right)^{\frac{2\left(\beta+2\right)}{2\left(\beta+2\right)+1}}$ if $n=\Omega\left(\left(\beta\sqrt{\log\left(\beta\vee1\right)}\right)^{4\beta+10}\right)$, and under this condition, the rate $\left(\frac{1}{n}\right)^{\frac{2\left(\beta+2\right)}{2\left(\beta+2\right)+1}}$ is minimax optimal in the case of $y^{'}=f\left(x,\,y\right)$; (4) more generally, for the higher order Picard type ODEs, $y^{\left(m\right)}=f\left(x,\,y,\,y^{'},\,...,y^{\left(m-1\right)}\right)$, the covering number of the solution class is bounded from above by the product of the covering number of the class $\mathcal{F}$ that $f$ ranges over and the covering number of the set where initial values lie.
Analysis of Empirical Mode Decomposition-based Load and Renewable Time Series Forecasting
Authors: Nima Safari, George Price, Chi Yung Chung
Date: 2020-11-23 00:00:00
Tasks: Time Series, Time Series Analysis, Time Series Forecasting

The empirical mode decomposition (EMD) method and its variants have been extensively employed in the load and renewable forecasting literature. Using this multiresolution decomposition, time series (TS) related to the historical load and renewable generation are decomposed into several intrinsic mode functions (IMFs), which are less non-stationary and non-linear. As such, the prediction of the components can theoretically be carried out with notably higher precision. The EMD method is prone to several issues, including modal aliasing and boundary effect problems, but the TS decomposition-based load and renewable generation forecasting literature primarily focuses on comparing the performance of different decomposition approaches from the forecast accuracy standpoint; as a result, these problems have rarely been scrutinized. Underestimating these issues can lead to poor performance of the forecast model in real-time applications. This paper examines these issues and their importance in the model development stage. Using real-world data, EMD-based models are presented, and the impact of the boundary effect is illustrated.
Automatic differentiation of Sylvester, Lyapunov, and algebraic Riccati equations
Authors: Ta-Chu Kao, Guillaume Hennequin
Date: 2020-11-23 00:00:00

Sylvester, Lyapunov, and algebraic Riccati equations are the bread and butter of control theorists. They are used to compute infinite-horizon Gramians, solve optimal control problems in continuous or discrete time, and design observers. While popular numerical computing frameworks (e.g., scipy) provide efficient solvers for these equations, these solvers are still largely missing from most automatic differentiation libraries. Here, we derive the forward and reverse-mode derivatives of the solutions to all three types of equations, and showcase their application on an inverse control problem.
Online Learning Based Risk-Averse Stochastic MPC of Constrained Linear Uncertain Systems
Authors: Chao Ning, Fengqi You
Date: 2020-11-20 00:00:00
Tasks: Model Predictive Control, Variational Inference

This paper investigates the problem of designing data-driven stochastic Model Predictive Control (MPC) for linear time-invariant systems under additive stochastic disturbance, whose probability distribution is unknown but can be partially inferred from data. We propose a novel online learning based risk-averse stochastic MPC framework in which Conditional Value-at-Risk (CVaR) constraints on system states are required to hold for a family of distributions called an ambiguity set. The ambiguity set is constructed from disturbance data by leveraging a Dirichlet process mixture model that is self-adaptive to the underlying data structure and complexity. Specifically, the structural property of multimodality is exploit-ed, so that the first- and second-order moment information of each mixture component is incorporated into the ambiguity set. A novel constraint tightening strategy is then developed based on an equivalent reformulation of distributionally ro-bust CVaR constraints over the proposed ambiguity set. As more data are gathered during the runtime of the controller, the ambiguity set is updated online using real-time disturbance data, which enables the risk-averse stochastic MPC to cope with time-varying disturbance distributions. The online variational inference algorithm employed does not require all collected data be learned from scratch, and therefore the proposed MPC is endowed with the guaranteed computational complexity of online learning. The guarantees on recursive feasibility and closed-loop stability of the proposed MPC are established via a safe update scheme. Numerical examples are used to illustrate the effectiveness and advantages of the proposed MPC.
Dimensionality reduction, regularization, and generalization in overparameterized regressions
Authors: Ningyuan Huang, David W. Hogg, Soledad Villar
Date: 2020-11-23 00:00:00
Tasks: Data Poisoning, Dimensionality Reduction, regression

Overparameterization in deep learning is powerful: Very large models fit the training data perfectly and yet often generalize well. This realization brought back the study of linear models for regression, including ordinary least squares (OLS), which, like deep learning, shows a "double-descent" behavior: (1) The risk (expected out-of-sample prediction error) can grow arbitrarily when the number of parameters $p$ approaches the number of samples $n$, and (2) the risk decreases with $p$ for $p>n$, sometimes achieving a lower value than the lowest risk for $p<n$. The divergence of the risk for OLS can be avoided with regularization. In this work, we show that for some data models it can also be avoided with a PCA-based dimensionality reduction (PCA-OLS, also known as principal component regression). We provide non-asymptotic bounds for the risk of PCA-OLS by considering the alignments of the population and empirical principal components. We show that dimensionality reduction improves robustness while OLS is arbitrarily susceptible to adversarial attacks, particularly in the overparameterized regime. We compare PCA-OLS theoretically and empirically with a wide range of projection-based methods, including random projections, partial least squares (PLS), and certain classes of linear two-layer neural networks. These comparisons are made for different data generation models to assess the sensitivity to signal-to-noise and the alignment of regression coefficients with the features. We find that methods in which the projection depends on the training data can outperform methods where the projections are chosen independently of the training data, even those with oracle knowledge of population quantities, another seemingly paradoxical phenomenon that has been identified previously. This suggests that overparameterization may not be necessary for good generalization.
Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
Authors: Josh Alman, Timothy Chu, Gary Miller, Shyam Narayanan, Mark Sellke, Zhao Song
Date: 2020-11-23 00:00:00
Tasks: BIG-bench Machine Learning, LEMMA

In this paper, we develop a new technique which we call representation theory of the real hyperrectangle, which describes how to compute the eigenvectors and eigenvalues of certain matrices arising from hyperrectangles. We show that these matrices arise naturally when analyzing a number of different algorithmic tasks such as kernel methods, neural network training, natural language processing, and the design of algorithms using the polynomial method. We then use our new technique along with these connections to prove several new structural results in these areas, including: $\bullet$ A function is a positive definite Manhattan kernel if and only if it is a completely monotone function. These kernels are widely used across machine learning; one example is the Laplace kernel which is widely used in machine learning for chemistry. $\bullet$ A function transforms Manhattan distances to Manhattan distances if and only if it is a Bernstein function. This completes the theory of Manhattan to Manhattan metric transforms initiated by Assouad in 1980. $\bullet$ A function applied entry-wise to any square matrix of rank $r$ always results in a matrix of rank $< 2^{r-1}$ if and only if it is a polynomial of sufficiently low degree. This gives a converse to a key lemma used by the polynomial method in algorithm design. Our work includes a sophisticated combination of techniques from different fields, including metric embeddings, the polynomial method, and group representation theory.
The Interconnectivity Vector: A Finite-Dimensional Vector Representation of Persistent Homology
Authors: Megan Johnson, Jae-Hun Jung
Date: 2020-11-23 00:00:00

Persistent Homology (PH) is a useful tool to study the underlying structure of a data set. Persistence Diagrams (PDs), which are 2D multisets of points, are a concise summary of the information found by studying the PH of a data set. However, PDs are difficult to incorporate into a typical machine learning workflow. To that end, two main methods for representing PDs have been developed: kernel methods and vectorization methods. In this paper we propose a new finite-dimensional vector, called the interconnectivity vector, representation of a PD adapted from Bag-of-Words (BoW). This new representation is constructed to demonstrate the connections between the homological features of a data set. This initial definition of the interconnectivity vector proves to be unstable, but we introduce a stabilized version of the vector and prove its stability with respect to small perturbations in the inputs. We evaluate both versions of the presented vectorization on several data sets and show their high discriminative power.
Classical Shadows With Noise
Authors: Dax Enshan Koh, Sabee Grewal
Date: 2020-11-23 00:00:00
Tasks: Quantum State Tomography

The classical shadows protocol, recently introduced by Huang, Kueng, and Preskill [Nat. Phys. 16, 1050 (2020)], is a quantum-classical protocol to estimate properties of an unknown quantum state. Unlike full quantum state tomography, the protocol can be implemented on near-term quantum hardware and requires few quantum measurements to make many predictions with a high success probability. In this paper, we study the effects of noise on the classical shadows protocol. In particular, we consider the scenario in which the quantum circuits involved in the protocol are subject to various known noise channels and derive an analytical upper bound for the sample complexity in terms of a shadow seminorm for both local and global noise. Additionally, by modifying the classical post-processing step of the noiseless protocol, we define a new estimator that remains unbiased in the presence of noise. As applications, we show that our results can be used to prove rigorous sample complexity upper bounds in the cases of depolarizing noise and amplitude damping.
Assessment and Linear Programming under Fuzzy Conditions
Authors: Michael Voskoglou
Date: 2020-11-20 00:00:00

A new fuzzy method is developed using triangular/trapezoidal fuzzy numbers for evaluating a group's mean performance, when qualitative grades instead of numerical scores are used for assessing its members' individual performance. Also, a new technique is developed for solving Linear Programming problems with fuzzy coefficients and everyday life applications are presented to illustrate our results.
A General Framework for Distributed Inference with Uncertain Models
Authors: James Z. Hare, Cesar A. Uribe, Lance Kaplan, Ali Jadbabaie
Date: 2020-11-20 00:00:00
Tasks: Learning Theory, Two-sample testing

This paper studies the problem of distributed classification with a network of heterogeneous agents. The agents seek to jointly identify the underlying target class that best describes a sequence of observations. The problem is first abstracted to a hypothesis-testing framework, where we assume that the agents seek to agree on the hypothesis (target class) that best matches the distribution of observations. Non-Bayesian social learning theory provides a framework that solves this problem in an efficient manner by allowing the agents to sequentially communicate and update their beliefs for each hypothesis over the network. Most existing approaches assume that agents have access to exact statistical models for each hypothesis. However, in many practical applications, agents learn the likelihood models based on limited data, which induces uncertainty in the likelihood function parameters. In this work, we build upon the concept of uncertain models to incorporate the agents' uncertainty in the likelihoods by identifying a broad set of parametric distribution that allows the agents' beliefs to converge to the same result as a centralized approach. Furthermore, we empirically explore extensions to non-parametric models to provide a generalized framework of uncertain models in non-Bayesian social learning.
AI Governance for Businesses
Authors: Johannes Schneider, Rene Abraham, Christian Meske, Jan vom Brocke
Date: 2020-11-20 00:00:00
Tasks: Ethics, Management

Artificial Intelligence (AI) governance regulates the exercise of authority and control over the management of AI. It aims at leveraging AI through effective use of data and minimization of AI-related cost and risk. While topics such as AI governance and AI ethics are thoroughly discussed on a theoretical, philosophical, societal and regulatory level, there is limited work on AI governance targeted to companies and corporations. This work views AI products as systems, where key functionality is delivered by machine learning (ML) models leveraging (training) data. We derive a conceptual framework by synthesizing literature on AI and related fields such as ML. Our framework decomposes AI governance into governance of data, (ML) models and (AI) systems along four dimensions. It relates to existing IT and data governance frameworks and practices. It can be adopted by practitioners and academics alike. For practitioners the synthesis of mainly research papers, but also practitioner publications and publications of regulatory bodies provides a valuable starting point to implement AI governance, while for academics the paper highlights a number of areas of AI governance that deserve more attention.
Explainable Composition of Aggregated Assistants
Authors: Sarath Sreedharan, Tathagata Chakraborti, Yara Rizk, Yasaman Khazaeni
Date: 2020-11-21 00:00:00

A new design of an AI assistant that has become increasingly popular is that of an "aggregated assistant" -- realized as an orchestrated composition of several individual skills or agents that can each perform atomic tasks. In this paper, we will talk about the role of planning in the automated composition of such assistants and explore how concepts in automated planning can help to establish transparency of the inner workings of the assistant to the end-user.
Spatially Correlated Patterns in Adversarial Images
Authors: Nandish Chattopadhyay, Lionell Yip En Zhi, Bryan Tan Bing Xing, Anupam Chattopadhyay
Date: 2020-11-21 00:00:00
Tasks: Benchmarking, Blocking

Adversarial attacks have proved to be the major impediment in the progress on research towards reliable machine learning solutions. Carefully crafted perturbations, imperceptible to human vision, can be added to images to force misclassification by an otherwise high performing neural network. To have a better understanding of the key contributors of such structured attacks, we searched for and studied spatially co-located patterns in the distribution of pixels in the input space. In this paper, we propose a framework for segregating and isolating regions within an input image which are particularly critical towards either classification (during inference), or adversarial vulnerability or both. We assert that during inference, the trained model looks at a specific region in the image, which we call Region of Importance (RoI); and the attacker looks at a region to alter/modify, which we call Region of Attack (RoA). The success of this approach could also be used to design a post-hoc adversarial defence method, as illustrated by our observations. This uses the notion of blocking out (we call neutralizing) that region of the image which is highly vulnerable to adversarial attacks but is not important for the task of classification. We establish the theoretical setup for formalising the process of segregation, isolation and neutralization and substantiate it through empirical analysis on standard benchmarking datasets. The findings strongly indicate that mapping features into the input space preserves the significant patterns typically observed in the feature-space while adding major interpretability and therefore simplifies potential defensive mechanisms.
BARS: Joint Search of Cell Topology and Layout for Accurate and Efficient Binary ARchitectures
Authors: Tianchen Zhao, Xuefei Ning, Xiangsheng Shi, Songyi Yang, Shuang Liang, Peng Lei, Jianfei Chen, Huazhong Yang, Yu Wang
Date: 2020-11-21 00:00:00
Tasks: Neural Architecture Search

Binary Neural Networks (BNNs) have received significant attention due to their promising efficiency. Currently, most BNN studies directly adopt widely-used CNN architectures, which can be suboptimal for BNNs. This paper proposes a novel Binary ARchitecture Search (BARS) flow to discover superior binary architecture in a large design space. Specifically, we analyze the information bottlenecks that are related to both the topology and layout architecture design choices. And we propose to automatically search for the optimal information flow. To achieve that, we design a two-level (Macro & Micro) search space tailored for BNNs and apply a differentiable neural architecture search (NAS) to explore this search space efficiently. The macro-level search space includes width and depth decisions, which is required for better balancing the model performance and complexity. We also design the micro-level search space to strengthen the information flow for BNN. %A notable challenge of BNN architecture search lies in that binary operations exacerbate the "collapse" problem of differentiable NAS, for which we incorporate various search and derive strategies to stabilize the search process. On CIFAR-10, BARS achieves 1.5% higher accuracy with 2/3 binary operations and 1/10 floating-point operations comparing with existing BNN NAS studies. On ImageNet, with similar resource consumption, BARS-discovered architecture achieves a 6% accuracy gain than hand-crafted binary ResNet-18 architectures and outperforms other binary architectures while fully binarizing the architecture backbone.
Large-Scale Multi-Agent Deep FBSDEs
Authors: Tianrong Chen, Ziyi Wang, Ioannis Exarchos, Evangelos A. Theodorou
Date: 2020-11-21 00:00:00
Tasks: Autonomous Racing, Decision Making, Deep Learning

In this paper we present a scalable deep learning framework for finding Markovian Nash Equilibria in multi-agent stochastic games using fictitious play. The motivation is inspired by theoretical analysis of Forward Backward Stochastic Differential Equations (FBSDE) and their implementation in a deep learning setting, which is the source of our algorithm's sample efficiency improvement. By taking advantage of the permutation-invariant property of agents in symmetric games, the scalability and performance is further enhanced significantly. We showcase superior performance of our framework over the state-of-the-art deep fictitious play algorithm on an inter-bank lending/borrowing problem in terms of multiple metrics. More importantly, our approach scales up to 3000 agents in simulation, a scale which, to the best of our knowledge, represents a new state-of-the-art. We also demonstrate the applicability of our framework in robotics on a belief space autonomous racing problem.
Reinforcement learning with distance-based incentive/penalty (DIP) updates for highly constrained industrial control systems
Authors: Hyungjun Park, Daiki Min, Jong-hyun Ryu, Dong Gu Choi
Date: 2020-11-22 00:00:00
Tasks: Reinforcement Learning (RL)

Typical reinforcement learning (RL) methods show limited applicability for real-world industrial control problems because industrial systems involve various constraints and simultaneously require continuous and discrete control. To overcome these challenges, we devise a novel RL algorithm that enables an agent to handle a highly constrained action space. This algorithm has two main features. First, we devise two distance-based Q-value update schemes, incentive update and penalty update, in a distance-based incentive/penalty update technique to enable the agent to decide discrete and continuous actions in the feasible region and to update the value of these types of actions. Second, we propose a method for defining the penalty cost as a shadow price-weighted penalty. This approach affords two advantages compared to previous methods to efficiently induce the agent to not select an infeasible action. We apply our algorithm to an industrial control problem, microgrid system operation, and the experimental results demonstrate its superiority.
A Bayesian Account of Measures of Interpretability in Human-AI Interaction
Authors: Sarath Sreedharan, Anagha Kulkarni, Tathagata Chakraborti, David E. Smith, Subbarao Kambhampati
Date: 2020-11-22 00:00:00

Existing approaches for the design of interpretable agent behavior consider different measures of interpretability in isolation. In this paper we posit that, in the design and deployment of human-aware agents in the real world, notions of interpretability are just some among many considerations; and the techniques developed in isolation lack two key properties to be useful when considered together: they need to be able to 1) deal with their mutually competing properties; and 2) an open world where the human is not just there to interpret behavior in one specific form. To this end, we consider three well-known instances of interpretable behavior studied in existing literature -- namely, explicability, legibility, and predictability -- and propose a revised model where all these behaviors can be meaningfully modeled together. We will highlight interesting consequences of this unified model and motivate, through results of a user study, why this revision is necessary.