pwc-archive/papers-with-abstracts huggingface dataset:
Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions
Authors: Nikolaos Karalias, Joshua Robinson, Andreas Loukas, Stefanie Jegelka
Date: 2022-08-08 00:00:00
Tasks: Combinatorial Optimization, Vocal Bursts Intensity Prediction

Integrating functions on discrete domains into neural networks is key to developing their capability to reason about discrete objects. But, discrete domains are (1) not naturally amenable to gradient-based optimization, and (2) incompatible with deep learning architectures that rely on representations in high-dimensional vector spaces. In this work, we address both difficulties for set functions, which capture many important discrete problems. First, we develop a framework for extending set functions onto low-dimensional continuous domains, where many extensions are naturally defined. Our framework subsumes many well-known extensions as special cases. Second, to avoid undesirable low-dimensional neural network bottlenecks, we convert low-dimensional extensions into representations in high-dimensional spaces, taking inspiration from the success of semidefinite programs for combinatorial optimization. Empirically, we observe benefits of our extensions for unsupervised neural combinatorial optimization, in particular with high-dimensional representations.
Rapid Flow Behavior Modeling of Thermal Interface Materials Using Deep Neural Networks
Authors: Simon Baeuerle, Marius Gebhardt, Jonas Barth, Andreas Steimer, Ralf Mikut
Date: 2022-08-08 00:00:00
Tasks: Management

Thermal Interface Materials (TIMs) are widely used in electronic packaging. Increasing power density and limited assembly space pose high demands on thermal management. Large cooling surfaces need to be covered efficiently. When joining the heatsink, previously dispensed TIM spreads over the cooling surface. Recommendations on the dispensing pattern exist only for simple surface geometries such as rectangles. For more complex geometries, Computational Fluid Dynamics (CFD) simulations are used in combination with manual experiments. While CFD simulations offer a high accuracy, they involve simulation experts and are rather expensive to set up. We propose a lightweight heuristic to model the spreading behavior of TIM. We further speed up the calculation by training an Artificial Neural Network (ANN) on data from this model. This offers rapid computation times and further supplies gradient information. This ANN can not only be used to aid manual pattern design of TIM, but also enables an automated pattern optimization. We compare this approach against the state-of-the-art and use real product samples for validation.
Channel Estimation under Hardware Impairments: Bayesian Methods versus Deep Learning
Authors: Özlem Tugfe Demir, Emil Björnson
Date: 2022-08-08 00:00:00
Tasks: Deep Learning

This paper considers the impact of general hardware impairments in a multiple-antenna base station and user equipments on the uplink performance. First, the effective channels are analytically derived for distortion-aware receivers when using finite-sized signal constellations. Next, a deep feedforward neural network is designed and trained to estimate the effective channels. Its performance is compared with state-of-the-art distortion-aware and unaware Bayesian linear minimum mean-squared error (LMMSE) estimators. The proposed deep learning approach improves the estimation quality by exploiting impairment characteristics, while LMMSE methods treat distortion as noise.
Solving the Online Assignment Problem with Machine Learned Advice
Authors: Clarence Gabriel R. Kasilag, Pollux M. Rey, Jhoirene B. Clemente
Date: 2022-08-08 00:00:00

The online assignment problem plays an important role in operational research and computer science which is why immense attention has been given to improving its solution quality. Due to the incomplete information about the input, it is difficult for online algorithms to produce the optimal solution. The quality of the solution of an online algorithm is measured using a competitive ratio. No online deterministic algorithm can achieve a competitive ratio better than (2n-1). It has been shown that advice in online computation improves the lower bound of the competitive ratio of online problems. Advice in online computation can be interpreted as additional information for the online algorithm to compensate for the lack of information about the whole input sequence. In this study, we investigate how introducing machine-learned advice could improve the competitive ratio for this problem. We provide an online algorithm for the online assignment problem by simulating a machine learning algorithm that predicts the whole input in advance. We utilize an optimal offline algorithm to provide a matching solution from the predicted input. Furthermore, we investigate how the prediction error of machine learning affects the competitive ratio of the online algorithm. We utilize a benchmark data set to perform our empirical analysis. We show that as the Machine Learning prediction error increases, the solution quality decreases. Moreover, the magnitude of error is directly proportional to the size of the input. This result is analogous to the competitive ratio of the best deterministic algorithm for the online assignment problem which is dependent also on the parameter n.
Towards lifelong learning of Recurrent Neural Networks for control design
Authors: Fabio Bonassi, Jing Xie, Marcello Farina, Riccardo Scattolini
Date: 2022-08-08 00:00:00
Tasks: Lifelong learning

This paper proposes a method for lifelong learning of Recurrent Neural Networks, such as NNARX, ESN, LSTM, and GRU, to be used as plant models in control system synthesis. The problem is significant because in many practical applications it is required to adapt the model when new information is available and/or the system undergoes changes, without the need to store an increasing amount of data as time proceeds. Indeed, in this context, many problems arise, such as the well known Catastrophic Forgetting and Capacity Saturation ones. We propose an adaptation algorithm inspired by Moving Horizon Estimators, deriving conditions for its convergence. The described method is applied to a simulated chemical plant, already adopted as a challenging benchmark in the existing literature. The main results achieved are discussed.
Detecting User Exits from Online Behavior: A Duration-Dependent Latent State Model
Authors: Tobias Hatt, Stefan Feuerriegel
Date: 2022-08-08 00:00:00

In order to steer e-commerce users towards making a purchase, marketers rely upon predictions of when users exit without purchasing. Previously, such predictions were based upon hidden Markov models (HMMs) due to their ability of modeling latent shopping phases with different user intents. In this work, we develop a duration-dependent hidden Markov model. In contrast to traditional HMMs, it explicitly models the duration of latent states and thereby allows states to become "sticky". The proposed model is superior to prior HMMs in detecting user exits: out of 100 user exits without purchase, it correctly identifies an additional 18. This helps marketers in better managing the online behavior of e-commerce customers. The reason for the superior performance of our model is the duration dependence, which allows our model to recover latent states that are characterized by a distorted sense of time. We finally provide a theoretical explanation for this, which builds upon the concept of "flow".
Sparse Representation Learning with Modified q-VAE towards Minimal Realization of World Model
Authors: Taisuke Kobayashi, Ryoma Watanuki
Date: 2022-08-08 00:00:00
Tasks: Representation Learning

Extraction of low-dimensional latent space from high-dimensional observation data is essential to construct a real-time robot controller with a world model on the extracted latent space. However, there is no established method for tuning the dimension size of the latent space automatically, suffering from finding the necessary and sufficient dimension size, i.e. the minimal realization of the world model. In this study, we analyze and improve Tsallis-based variational autoencoder (q-VAE), and reveal that, under an appropriate configuration, it always facilitates making the latent space sparse. Even if the dimension size of the pre-specified latent space is redundant compared to the minimal realization, this sparsification collapses unnecessary dimensions, allowing for easy removal of them. We experimentally verified the benefits of the sparsification by the proposed method that it can easily find the necessary and sufficient six dimensions for a reaching task with a mobile manipulator that requires a six-dimensional state space. Moreover, by planning with such a minimal-realization world model learned in the extracted dimensions, the proposed method was able to exert a more optimal action sequence in real-time, reducing the reaching accomplishment time by around 20 %. The attached video is uploaded on youtube: https://youtu.be/-QjITrnxaRs
Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory
Authors: Jiehao Liang, Zhao Song, Zhaozhuo Xu, Junze Yin, Danyang Zhuo
Date: 2022-08-08 00:00:00
Tasks: Density Estimation

Kernel density estimation (KDE) stands out as a challenging task in machine learning. The problem is defined in the following way: given a kernel function $f(x,y)$ and a set of points $\{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$, we would like to compute $\frac{1}{n}\sum_{i=1}^{n} f(x_i,y)$ for any query point $y \in \mathbb{R}^d$. Recently, there has been a growing trend of using data structures for efficient KDE. However, the proposed KDE data structures focus on static settings. The robustness of KDE data structures over dynamic changing data distributions is not addressed. In this work, we focus on the dynamic maintenance of KDE data structures with robustness to adversarial queries. Especially, we provide a theoretical framework of KDE data structures. In our framework, the KDE data structures only require subquadratic spaces. Moreover, our data structure supports the dynamic update of the dataset in sublinear time. Furthermore, we can perform adaptive queries with the potential adversary in sublinear time.
Neural Optimization Machine: A Neural Network Approach for Optimization
Authors: Jie Chen, Yongming Liu
Date: 2022-08-08 00:00:00
Tasks: Multiobjective Optimization

A novel neural network (NN) approach is proposed for constrained optimization. The proposed method uses a specially designed NN architecture and training/optimization procedure called Neural Optimization Machine (NOM). The objective functions for the NOM are approximated with NN models. The optimization process is conducted by the neural network's built-in backpropagation algorithm. The NOM solves optimization problems by extending the architecture of the NN objective function model. This is achieved by appropriately designing the NOM's structure, activation function, and loss function. The NN objective function can have arbitrary architectures and activation functions. The application of the NOM is not limited to specific optimization problems, e.g., linear and quadratic programming. It is shown that the increase of dimension of design variables does not increase the computational cost significantly. Then, the NOM is extended for multiobjective optimization. Finally, the NOM is tested using numerical optimization problems and applied for the optimal design of processing parameters in additive manufacturing.
Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach
Authors: Saber Jafarpour, Alexander Davydov, Matthew Abate, Francesco Bullo, Samuel Coogan
Date: 2022-08-08 00:00:00

This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks based upon non-Euclidean contraction theory. The basic idea is to cast the robustness analysis of a neural network as a reachability problem and use (i) the $\ell_{\infty}$-norm input-output Lipschitz constant and (ii) the tight inclusion function of the network to over-approximate its reachable sets. First, for a given implicit neural network, we use $\ell_{\infty}$-matrix measures to propose sufficient conditions for its well-posedness, design an iterative algorithm to compute its fixed points, and provide upper bounds for its $\ell_\infty$-norm input-output Lipschitz constant. Second, we introduce a related embedded network and show that the embedded network can be used to provide an $\ell_\infty$-norm box over-approximation of the reachable sets of the original network. Moreover, we use the embedded network to design an iterative algorithm for computing the upper bounds of the original system's tight inclusion function. Third, we use the upper bounds of the Lipschitz constants and the upper bounds of the tight inclusion functions to design two algorithms for the training and robustness verification of implicit neural networks. Finally, we apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms
Authors: Leszek Szczecinski, Harsh Sukheja
Date: 2022-08-08 00:00:00

The linear ordering problem (LOP), which consists in ordering M objects from their pairwise comparisons, is commonly applied in many areas of research. While efforts have been made to devise efficient LOP algorithms, verification of whether the data are rankable, that is, if the linear ordering problem (LOP) solutions have a meaningful interpretation, received much less attention. To address this problem, we adopt a probabilistic perspective where the results of pairwise comparisons are modeled as Bernoulli variables with a common parameter and we estimate the latter from the observed data. The brute-force approach to the required enumeration has a prohibitive complexity of O(M !), so we reformulate the problem and introduce a concept of the Slater spectrum that generalizes the Slater index, and then devise an algorithm to find the spectrum with complexity O(M^3 2^M) that is manageable for moderate values of M. Furthermore, with a minor modification of the algorithm, we are able to find all solutions of the LOP with the complexity O(M 2^M). Numerical examples are shown on synthetic and real-world data, and the algorithms are publicly available.
Information bottleneck theory of high-dimensional regression: relevancy, efficiency and optimality
Authors: Vudtiwat Ngampruetikorn, David J. Schwab
Date: 2022-08-08 00:00:00
Tasks: regression, Vocal Bursts Intensity Prediction

Avoiding overfitting is a central challenge in machine learning, yet many large neural networks readily achieve zero training loss. This puzzling contradiction necessitates new approaches to the study of overfitting. Here we quantify overfitting via residual information, defined as the bits in fitted models that encode noise in training data. Information efficient learning algorithms minimize residual information while maximizing the relevant bits, which are predictive of the unknown generative models. We solve this optimization to obtain the information content of optimal algorithms for a linear regression problem and compare it to that of randomized ridge regression. Our results demonstrate the fundamental trade-off between residual and relevant information and characterize the relative information efficiency of randomized regression with respect to optimal algorithms. Finally, using results from random matrix theory, we reveal the information complexity of learning a linear map in high dimensions and unveil information-theoretic analogs of double and multiple descent phenomena.
Counterfactual Fairness Is Basically Demographic Parity
Authors: Lucas Rosenblatt, R. Teal Witter
Date: 2022-08-07 00:00:00
Tasks: counterfactual, Fairness

Making fair decisions is crucial to ethically implementing machine learning algorithms in social settings. In this work, we consider the celebrated definition of counterfactual fairness [Kusner et al., NeurIPS, 2017]. We begin by showing that an algorithm which satisfies counterfactual fairness also satisfies demographic parity, a far simpler fairness constraint. Similarly, we show that all algorithms satisfying demographic parity can be trivially modified to satisfy counterfactual fairness. Together, our results indicate that counterfactual fairness is basically equivalent to demographic parity, which has important implications for the growing body of work on counterfactual fairness. We then validate our theoretical findings empirically, analyzing three existing algorithms for counterfactual fairness against three simple benchmarks. We find that two simple benchmark algorithms outperform all three existing algorithms -- in terms of fairness, accuracy, and efficiency -- on several data sets. Our analysis leads us to formalize a concrete fairness goal: to preserve the order of individuals within protected groups. We believe transparency around the ordering of individuals within protected groups makes fair algorithms more trustworthy. By design, the two simple benchmark algorithms satisfy this goal while the existing algorithms for counterfactual fairness do not.
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Authors: Sally Dong, Haotian Jiang, Yin Tat Lee, Swati Padmanabhan, Guanghao Ye
Date: 2022-08-07 00:00:00

Many fundamental problems in machine learning can be formulated by the convex program \[ \min_{\theta\in R^d}\ \sum_{i=1}^{n}f_{i}(\theta), \] where each $f_i$ is a convex, Lipschitz function supported on a subset of $d_i$ coordinates of $\theta$. One common approach to this problem, exemplified by stochastic gradient descent, involves sampling one $f_i$ term at every iteration to make progress. This approach crucially relies on a notion of uniformity across the $f_i$'s, formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation to $\epsilon$-accuracy in $\widetilde{O}(\sum_{i=1}^n d_i \log (1 /\epsilon))$ gradient computations, with no assumptions on the condition number. The previous best algorithm independent of the condition number is the standard cutting plane method, which requires $O(nd \log (1/\epsilon))$ gradient computations. As a corollary, we improve upon the evaluation oracle complexity for decomposable submodular minimization by Axiotis et al. (ICML 2021). Our main technical contribution is an adaptive procedure to select an $f_i$ term at every iteration via a novel combination of cutting-plane and interior-point methods.
Estimating Topic Exposure for Under-Represented Users on Social Media
Authors: Mansooreh Karami, Ahmadreza Mosallanezhad, Paras Sheth, Huan Liu
Date: 2022-08-07 00:00:00

Online Social Networks (OSNs) facilitate access to a variety of data allowing researchers to analyze users' behavior and develop user behavioral analysis models. These models rely heavily on the observed data which is usually biased due to the participation inequality. This inequality consists of three groups of online users: the lurkers - users that solely consume the content, the engagers - users that contribute little to the content creation, and the contributors - users that are responsible for creating the majority of the online content. Failing to consider the contribution of all the groups while interpreting population-level interests or sentiments may yield biased results. To reduce the bias induced by the contributors, in this work, we focus on highlighting the engagers' contributions in the observed data as they are more likely to contribute when compared to lurkers, and they comprise a bigger population as compared to the contributors. The first step in behavioral analysis of these users is to find the topics they are exposed to but did not engage with. To do so, we propose a novel framework that aids in identifying these users and estimates their topic exposure. The exposure estimation mechanism is modeled by incorporating behavioral patterns from similar contributors as well as users' demographic and profile information.
Stochastic Scaling in Loss Functions for Physics-Informed Neural Networks
Authors: Ethan Mills, Alexey Pozdnyakov
Date: 2022-08-07 00:00:00

Differential equations are used in a wide variety of disciplines, describing the complex behavior of the physical world. Analytic solutions to these equations are often difficult to solve for, limiting our current ability to solve complex differential equations and necessitating sophisticated numerical methods to approximate solutions. Trained neural networks act as universal function approximators, able to numerically solve differential equations in a novel way. In this work, methods and applications of neural network algorithms for numerically solving differential equations are explored, with an emphasis on varying loss functions and biological applications. Variations on traditional loss function and training parameters show promise in making neural network-aided solutions more efficient, allowing for the investigation of more complex equations governing biological principles.
An Empirical Analysis of the Laplace and Neural Tangent Kernels
Authors: Ronaldas Paulius Lencevicius
Date: 2022-08-07 00:00:00

The neural tangent kernel is a kernel function defined over the parameter distribution of an infinite width neural network. Despite the impracticality of this limit, the neural tangent kernel has allowed for a more direct study of neural networks and a gaze through the veil of their black box. More recently, it has been shown theoretically that the Laplace kernel and neural tangent kernel share the same reproducing kernel Hilbert space in the space of $\mathbb{S}^{d-1}$ alluding to their equivalence. In this work, we analyze the practical equivalence of the two kernels. We first do so by matching the kernels exactly and then by matching posteriors of a Gaussian process. Moreover, we analyze the kernels in $\mathbb{R}^d$ and experiment with them in the task of regression.
Adaptive incomplete multi-view learning via tensor graph completion
Authors: Heng Zhang, Xiaohong Chen
Date: 2022-08-07 00:00:00
Tasks: MULTI-VIEW LEARNING

With the advancement of the data acquisition techniques, multi-view learning has become a hot topic. Some multi-view learning methods assume that the multi-view data is complete, which means that all instances are present, but this too ideal. Certain tensor-based methods for handing incomplete multi-view data have emerged and have achieved better result. However, there are still some problems, such as use of traditional tensor norm which makes the computation high and is not able to handle out-of-sample. To solve these two problems, we proposed a new incomplete multi view learning method. A new tensor norm is defined to implement graph tensor data recover. The recovered graphs are then regularized to a consistent low-dimensional representation of the samples. In addition, adaptive weights are equipped to each view to adjust the importance of different views. Compared with the existing methods, our method nor only explores the consistency among views, but also obtains the low-dimensional representation of the new samples by using the learned projection matrix. An efficient algorithm based on inexact augmented Lagrange multiplier (ALM) method are designed to solve the model and convergence is proved. Experimental results on four datasets show the effectiveness of our method.