pwc-archive/papers-with-abstracts huggingface dataset:
Analysis of a Reaction-Diffusion Susceptible-Infected-Susceptible Epidemic Patch Model Incorporating Movement Inside and Among Patches
Authors: Shanshan Chen, Yixiang Wu
Date: 2023-01-17 00:00:00

In this paper, we propose and analyze a reaction-diffusion susceptible-infected-susceptible (SIS) epidemic patch model. The individuals are assumed to reside in different patches, where they are able to move inside and among the patches. The movement of individuals inside the patches is descried by diffusion terms, and the movement pattern among patches is modeled by an essentially nonnegative matrix. We define a basic reproduction number $\mathcal{R}_0$ for the model and show that it is a threshold value for disease extinction versus persistence. The monotone dependence of $\mathcal{R}_0$ on the movement rates of infected individuals is proved when the dispersal pattern is symmetric or non-symmetric. Numerical simulations are performed to illustrate the impact of the movement of individuals inside and among patches on the transmission of the disease.
Artificial Benchmark for Community Detection with Outliers (ABCD+o)
Authors: Bogumił Kamiński, Paweł Prałat, François Théberge
Date: 2023-01-13 00:00:00
Tasks: Community Detection

The Artificial Benchmark for Community Detection graph (ABCD) is a random graph model with community structure and power-law distribution for both degrees and community sizes. The model generates graphs with similar properties as the well-known LFR one, and its main parameter $\xi$ can be tuned to mimic its counterpart in the LFR model, the mixing parameter $\mu$. In this paper, we extend the ABCD model to include potential outliers. We perform some exploratory experiments on both the new ABCD+o model as well as a real-world network to show that outliers possess some desired, distinguishable properties.
On the impact of spatial heterogeneity and drift rate in a three-patch two-species Lotka-Volterra competition model over a stream
Authors: Shanshan Chen, Jie Liu, Yixiang Wu
Date: 2023-01-16 00:00:00

In this paper, we study a three-patch two-species Lotka-Volterra competition patch model over a stream network. The individuals are subject to both random and directed movements, and the two species are assumed to be identical except for the movement rates. The environment is heterogeneous, and the carrying capacity is lager in upstream locations. We treat one species as a resident species and investigate whether the other species can invade or not. Our results show that the spatial heterogeneity of environment and the magnitude of the drift rates have a large impact on the competition outcomes of the stream species.
Temporal-lobe Epilepsy: Harmonic and Anharmonic Periodicity in Microeletrode Voltage
Authors: Francois A. Marshall
Date: 2023-01-16 00:00:00
Tasks: Rhythm, Time Series, Time Series Analysis

Temporal-lobe epilepsy in humans is often associated with widespread, synchronized neuron firing that co-occurs with traveling waves in local field potential. These traveling waves generate stochastic oscillations in a time series of microelectrode voltage, and previous work has deemed it informative for traveling-wave analysis to study the mean periodicity. This manuscript reveals that: a) mean voltage (i.e., traveling-wave periodicity) adequately explains the observed voltage periodicity only for a select few time intervals during seizure; and b) mean voltage has a 7 Hz cosine-series representation indicative of a nonlinear system response given alpha-rhythm input. The a) result implies that residual noise should be modelled explicitly, while b) motivates a departure from the conventional plane-wave modeling regime in source-localization efforts. The 7 Hz fundamental frequency is unsurprising given the relative transparency of the brain to 14 Hz alpha rhythms in neurophysiological diseases (14 Hz being a subharmonic frequency of the 7 Hz signal).
Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes
Authors: Mohammad Vahid Jamali, Xiyang Liu, Ashok Vardhan Makkuva, Hessam Mahdavifar, Sewoong Oh, Pramod Viswanath
Date: 2023-01-16 00:00:00

Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths. In this paper, we focus on subcodes of RM codes with flexible rates. We first extend the RPA decoding algorithm to RM subcodes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different approaches to prune the projections. Next, we derive the soft-decision based version of our algorithm, called soft-subRPA, that not only improves upon the performance of subRPA but also enables a differentiable decoding algorithm. Building upon the soft-subRPA algorithm, we then provide a framework for training a machine learning (ML) model to search for \textit{good} sets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly smaller number of projections. We also show that the choice of the projections in decoding RM subcodes matters significantly, and our ML-aided projection pruning scheme is able to find a \textit{good} selection, i.e., with negligible performance degradation compared to the full-projection case, given a reasonable number of projections.
Computability of Optimizers
Authors: Yunseok Lee, Holger Boche, Gitta Kutyniok
Date: 2023-01-15 00:00:00

Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.
Semantic and Effective Communication for Remote Control Tasks with Dynamic Feature Compression
Authors: Pietro Talli, Francesco Pase, Federico Chiariotti, Andrea Zanella, Michele Zorzi
Date: 2023-01-14 00:00:00
Tasks: Deep Reinforcement Learning, Feature Compression, Quantization

The coordination of robotic swarms and the remote wireless control of industrial systems are among the major use cases for 5G and beyond systems: in these cases, the massive amounts of sensory information that needs to be shared over the wireless medium can overload even high-capacity connections. Consequently, solving the effective communication problem by optimizing the transmission strategy to discard irrelevant information can provide a significant advantage, but is often a very complex task. In this work, we consider a prototypal system in which an observer must communicate its sensory data to an actor controlling a task (e.g., a mobile robot in a factory). We then model it as a remote Partially Observable Markov Decision Process (POMDP), considering the effect of adopting semantic and effective communication-oriented solutions on the overall system performance. We split the communication problem by considering an ensemble Vector Quantized Variational Autoencoder (VQ-VAE) encoding, and train a Deep Reinforcement Learning (DRL) agent to dynamically adapt the quantization level, considering both the current state of the environment and the memory of past messages. We tested the proposed approach on the well-known CartPole reference control problem, obtaining a significant performance increase over traditional approaches
Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes
Authors: Konstantin Mishchenko, Slavomír Hanzely, Peter Richtárik
Date: 2023-01-17 00:00:00
Tasks: Federated Learning, Meta-Learning, Personalized Federated Learning

In this work, we consider the problem of minimizing the sum of Moreau envelopes of given functions, which has previously appeared in the context of meta-learning and personalized federated learning. In contrast to the existing theory that requires running subsolvers until a certain precision is reached, we only assume that a finite number of gradient steps is taken at each iteration. As a special case, our theory allows us to show the convergence of First-Order Model-Agnostic Meta-Learning (FO-MAML) to the vicinity of a solution of Moreau objective. We also study a more general family of first-order algorithms that can be viewed as a generalization of FO-MAML. Our main theoretical achievement is a theoretical improvement upon the inexact SGD framework. In particular, our perturbed-iterate analysis allows for tighter guarantees that improve the dependency on the problem's conditioning. In contrast to the related work on meta-learning, ours does not require any assumptions on the Hessian smoothness, and can leverage smoothness and convexity of the reformulation based on Moreau envelopes. Furthermore, to fill the gaps in the comparison of FO-MAML to the Implicit MAML (iMAML), we show that the objective of iMAML is neither smooth nor convex, implying that it has no convergence guarantees based on the existing theory.
Scaling Deep Networks with the Mesh Adaptive Direct Search algorithm
Authors: Dounia Lakhmiri, Mahdi Zolnouri, Vahid Partovi Nia, Christophe Tribes, Sébastien Le Digabel
Date: 2023-01-17 00:00:00
Tasks: image-classification, Image Classification

Deep neural networks are getting larger. Their implementation on edge and IoT devices becomes more challenging and moved the community to design lighter versions with similar performance. Standard automatic design tools such as \emph{reinforcement learning} and \emph{evolutionary computing} fundamentally rely on cheap evaluations of an objective function. In the neural network design context, this objective is the accuracy after training, which is expensive and time-consuming to evaluate. We automate the design of a light deep neural network for image classification using the \emph{Mesh Adaptive Direct Search}(MADS) algorithm, a mature derivative-free optimization method that effectively accounts for the expensive blackbox nature of the objective function to explore the design space, even in the presence of constraints.Our tests show competitive compression rates with reduced numbers of trials.
Asymptotic normality and optimality in nonsmooth stochastic approximation
Authors: Damek Davis, Dmitriy Drusvyatskiy, Liwei Jiang
Date: 2023-01-16 00:00:00
Tasks: Open-Ended Question Answering

In their seminal work, Polyak and Juditsky showed that stochastic approximation algorithms for solving smooth equations enjoy a central limit theorem. Moreover, it has since been argued that the asymptotic covariance of the method is best possible among any estimation procedure in a local minimax sense of H\'{a}jek and Le Cam. A long-standing open question in this line of work is whether similar guarantees hold for important non-smooth problems, such as stochastic nonlinear programming or stochastic variational inequalities. In this work, we show that this is indeed the case.
Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization
Authors: Lesi Chen, Jing Xu, Luo Luo
Date: 2023-01-16 00:00:00
Tasks: Stochastic Optimization

We consider the optimization problem of the form $\min_{x \in \mathbb{R}^d} f(x) \triangleq \mathbb{E}_{\xi} [F(x; \xi)]$, where the component $F(x;\xi)$ is $L$-mean-squared Lipschitz but possibly nonconvex and nonsmooth. The recently proposed gradient-free method requires at most $\mathcal{O}( L^4 d^{3/2} \epsilon^{-4} + \Delta L^3 d^{3/2} \delta^{-1} \epsilon^{-4})$ stochastic zeroth-order oracle complexity to find a $(\delta,\epsilon)$-Goldstein stationary point of objective function, where $\Delta = f(x_0) - \inf_{x \in \mathbb{R}^d} f(x)$ and $x_0$ is the initial point of the algorithm. This paper proposes a more efficient algorithm using stochastic recursive gradient estimators, which improves the complexity to $\mathcal{O}(L^3 d^{3/2} \epsilon^{-3}+ \Delta L^2 d^{3/2} \delta^{-1} \epsilon^{-3})$.
Approximation of optimization problems with constraints through kernel Sum-Of-Squares
Authors: Pierre-Cyril Aubin-Frankowski, Alessandro Rudi
Date: 2023-01-16 00:00:00
Tasks: Articles, global-optimization

Handling an infinite number of inequality constraints in infinite-dimensional spaces occurs in many fields, from global optimization to optimal transport. These problems have been tackled individually in several previous articles through kernel Sum-Of-Squares (kSoS) approximations. We propose here a unified theorem to prove convergence guarantees for these schemes. Pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. Assuming further that the functions appearing in the problem are smooth, focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints. Our approach is illustrated in learning vector fields with side information, here the invariance of a set.
Risk-Averse Reinforcement Learning via Dynamic Time-Consistent Risk Measures
Authors: Xian Yu, Siqian Shen
Date: 2023-01-14 00:00:00
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Traditional reinforcement learning (RL) aims to maximize the expected total reward, while the risk of uncertain outcomes needs to be controlled to ensure reliable performance in a risk-averse setting. In this paper, we consider the problem of maximizing dynamic risk of a sequence of rewards in infinite-horizon Markov Decision Processes (MDPs). We adapt the Expected Conditional Risk Measures (ECRMs) to the infinite-horizon risk-averse MDP and prove its time consistency. Using a convex combination of expectation and conditional value-at-risk (CVaR) as a special one-step conditional risk measure, we reformulate the risk-averse MDP as a risk-neutral counterpart with augmented action space and manipulation on the immediate rewards. We further prove that the related Bellman operator is a contraction mapping, which guarantees the convergence of any value-based RL algorithms. Accordingly, we develop a risk-averse deep Q-learning framework, and our numerical studies based on two simple MDPs show that the risk-averse setting can reduce the variance and enhance robustness of the results.
CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence
Authors: Kun Huang, Shi Pu
Date: 2023-01-14 00:00:00
Tasks: Distributed Optimization

In this paper, we consider solving the distributed optimization problem over a multi-agent network under the communication restricted setting. We study a compressed decentralized stochastic gradient method, termed ``compressed exact diffusion with adaptive stepsizes (CEDAS)", and show the method asymptotically achieves comparable convergence rate as centralized { stochastic gradient descent (SGD)} for both smooth strongly convex objective functions and smooth nonconvex objective functions under unbiased compression operators. In particular, to our knowledge, CEDAS enjoys so far the shortest transient time (with respect to the graph specifics) for achieving the convergence rate of centralized SGD, which behaves as $\mathcal{O}(n{C^3}/(1-\lambda_2)^{2})$ under smooth strongly convex objective functions, and $\mathcal{O}(n^3{C^6}/(1-\lambda_2)^4)$ under smooth nonconvex objective functions, where $(1-\lambda_2)$ denotes the spectral gap of the mixing matrix, and $C>0$ is the compression-related parameter. In particular, CEDAS exhibits the shortest transient times when $C < \mathcal{O}(1/(1 - \lambda_2)^2)$, which is common in practice. Numerical experiments further demonstrate the effectiveness of the proposed algorithm.
Calculation of Epidemic First Passage and Peak Time Probability Distributions
Authors: Jacob Curran-Sebastian, Lorenzo Pellis, Ian Hall, Thomas House
Date: 2023-01-17 00:00:00

Understanding the timing of the peak of a disease outbreak forms an important part of epidemic forecasting. In many cases, such information is essential for planning increased hospital bed demand and for designing of public health interventions. The time taken for an outbreak to become large is inherently stochastic, and therefore uncertain, but after a sufficient number of infections has been reached the subsequent dynamics can be modelled accurately using ordinary differential equations. Here, we present analytical and numerical methods for approximating the time at which a stochastic model of a disease outbreak reaches a large number of cases and for quantifying the uncertainty arising from demographic stochasticity around that time. We then project this uncertainty forwards in time using an ordinary differential equation model in order to obtain a distribution for the peak timing of the epidemic that agrees closely with large simulations but that, for error tolerances relevant to most realistic applications, requires a fraction of the computational cost of full Monte Carlo approaches.
Deep Conditional Measure Quantization
Authors: Gabriel Turinici
Date: 2023-01-17 00:00:00
Tasks: Quantization

Quantization of a probability measure means representing it with a finite set of Dirac masses that approximates the input distribution well enough (in some metric space of probability measures). Various methods exists to do so, but the situation of quantizing a conditional law has been less explored. We propose a method, called DCMQ, involving a Huber-energy kernel-based approach coupled with a deep neural network architecture. The method is tested on several examples and obtains promising results.
Geometric ergodicity of SGLD via reflection coupling
Authors: Lei LI, Jian-Guo Liu, Yuliang Wang
Date: 2023-01-17 00:00:00

We consider the geometric ergodicity of the Stochastic Gradient Langevin Dynamics (SGLD) algorithm under nonconvexity settings. Via the technique of reflection coupling, we prove the Wasserstein contraction of SGLD when the target distribution is log-concave only outside some compact set. The time discretization and the minibatch in SGLD introduce several difficulties when applying the reflection coupling, which are addressed by a series of careful estimates of conditional expectations. As a direct corollary, the SGLD with constant step size has an invariant distribution and we are able to obtain its geometric ergodicity in terms of $W_1$ distance. The generalization to non-gradient drifts is also included.
A delayed dual risk model
Authors: Lingjiong Zhu
Date: 2023-01-16 00:00:00
Tasks: model

In this paper, we study a dual risk model with delays in the spirit of Dassios-Zhao. When a new innovation occurs, there is a delay before the innovation turns into a profit. We obtain large initial surplus asymptotics for the ruin probability and ruin time distributions. For some special cases, we get closed-form formulas. Numerical illustrations will also be provided.
Inference via robust optimal transportation: theory and methods
Authors: Yiming Ma, Hang Liu, Davide La Vecchia, Metthieu Lerasle
Date: 2023-01-16 00:00:00
Tasks: Domain Adaptation

Optimal transportation theory and the related $p$-Wasserstein distance ($W_p$, $p\geq 1$) are widely-applied in statistics and machine learning. In spite of their popularity, inference based on these tools has some issues. For instance, it is sensitive to outliers and it may not be even defined when the underlying model has infinite moments. To cope with these problems, first we consider a robust version of the primal transportation problem and show that it defines the {robust Wasserstein distance}, $W^{(\lambda)}$, depending on a tuning parameter $\lambda > 0$. Second, we illustrate the link between $W_1$ and $W^{(\lambda)}$ and study its key measure theoretic aspects. Third, we derive some concentration inequalities for $W^{(\lambda)}$. Fourth, we use $W^{(\lambda)}$ to define minimum distance estimators, we provide their statistical guarantees and we illustrate how to apply the derived concentration inequalities for a data driven selection of $\lambda$. Fifth, we provide the {dual} form of the robust optimal transportation problem and we apply it to machine learning problems (generative adversarial networks and domain adaptation). Numerical exercises provide evidence of the benefits yielded by our novel methods.
Understanding Best Subset Selection: A Tale of Two C(omplex)ities
Authors: Saptarshi Roy, Ambuj Tewari, Ziwei Zhu
Date: 2023-01-16 00:00:00
Tasks: Model Selection, Variable Selection, Vocal Bursts Valence Prediction

We consider the problem of best subset selection (BSS) under high-dimensional sparse linear regression model. Recently, Guo et al. (2020) showed that the model selection performance of BSS depends on a certain identifiability margin, a measure that captures the model discriminative power of BSS under a general correlation structure that is robust to the design dependence, unlike its computational surrogates such as LASSO, SCAD, MCP, etc. Expanding on this, we further broaden the theoretical understanding of best subset selection in this paper and show that the complexities of the residualized signals, the portion of the signals orthogonal to the true active features, and spurious projections, describing the projection operators associated with the irrelevant features, also play fundamental roles in characterizing the margin condition for model consistency of BSS. In particular, we establish both necessary and sufficient margin conditions depending only on the identifiability margin and the two complexity measures. We also partially extend our sufficiency result to the case of high-dimensional sparse generalized linear models (GLMs).
Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency
Authors: Wenlong Mou, Peng Ding, Martin J. Wainwright, Peter L. Bartlett
Date: 2023-01-16 00:00:00
Tasks: regression

We study optimal procedures for estimating a linear functional based on observational data. In many problems of this kind, a widely used assumption is strict overlap, i.e., uniform boundedness of the importance ratio, which measures how well the observational data covers the directions of interest. When it is violated, the classical semi-parametric efficiency bound can easily become infinite, so that the instance-optimal risk depends on the function class used to model the regression function. For any convex and symmetric function class $\mathcal{F}$, we derive a non-asymptotic local minimax bound on the mean-squared error in estimating a broad class of linear functionals. This lower bound refines the classical semi-parametric one, and makes connections to moduli of continuity in functional estimation. When $\mathcal{F}$ is a reproducing kernel Hilbert space, we prove that this lower bound can be achieved up to a constant factor by analyzing a computationally simple regression estimator. We apply our general results to various families of examples, thereby uncovering a spectrum of rates that interpolate between the classical theories of semi-parametric efficiency (with $\sqrt{n}$-consistency) and the slower minimax rates associated with non-parametric function estimation.