pwc-archive/papers-with-abstracts huggingface dataset:
Multi-Scale Message Passing Neural PDE Solvers
Authors: Léonard Equer, T. Konstantin Rusch, Siddhartha Mishra
Date: 2023-02-07 00:00:00

We propose a novel multi-scale message passing neural network algorithm for learning the solutions of time-dependent PDEs. Our algorithm possesses both temporal and spatial multi-scale resolution features by incorporating multi-scale sequence models and graph gating modules in the encoder and processor, respectively. Benchmark numerical experiments are presented to demonstrate that the proposed algorithm outperforms baselines, particularly on a PDE with a range of spatial and temporal scales.
From Utilitarian to Rawlsian Designs for Algorithmic Fairness
Authors: Daniel E. Rigobon
Date: 2023-02-07 00:00:00
Tasks: Fairness

There is a lack of consensus within the literature as to how `fairness' of algorithmic systems can be measured, and different metrics can often be at odds. In this paper, we approach this task by drawing on the ethical frameworks of utilitarianism and John Rawls. Informally, these two theories of distributive justice measure the `good' as either a population's sum of utility, or worst-off outcomes, respectively. We present a parameterized class of objective functions that interpolates between these two (possibly) conflicting notions of the `good'. This class is shown to represent a relaxation of the Rawlsian `veil of ignorance', and its sequence of optimal solutions converges to both a utilitarian and Rawlsian optimum. Several other properties of this class are studied, including: 1) a relationship to regularized optimization, 2) feasibility of consistent estimation, and 3) algorithmic cost. In several real-world datasets, we compute optimal solutions and construct the tradeoff between utilitarian and Rawlsian notions of the `good'. Empirically, we demonstrate that increasing model complexity can manifest strict improvements to both measures of the `good'. This work suggests that the proper degree of `fairness' can be informed by a designer's preferences over the space of induced utilitarian and Rawlsian `good'.
Learning to cooperatively estimate road surface friction
Authors: Jens-Patrick Langstand, Maben Rabi
Date: 2023-02-07 00:00:00
Tasks: Friction

We present a system for estimating the friction of the pavement surface at any curved road section, by arriving at a consensus estimate, based on data from vehicles that have recently passed through that section. This estimate can help following vehicles. To keep costs down, we depend only on standard automotive sensors, such as the IMU, and sensors for the steering angle and wheel speeds. Our system's workflow consists of: (i) processing of measurements from existing vehicular sensors, to implement a virtual sensor that captures the effect of low friction on the vehicle, (ii) transmitting short kinematic summaries from vehicles to a road side unit (RSU), using V2X communication, and (iii) estimating the friction coefficients, by running a machine learning regressor at the RSU, on summaries from individual vehicles, and then combining several such estimates. In designing and implementing our system over a road network, we face two key questions: (i) should each individual road section have a local friction coefficient regressor, or can we use a global regressor that covers all the possible road sections? and (ii) how accurate are the resulting regressor estimates? We test the performance of design variations of our solution, using simulations on the commercial package Dyna4. We consider a single vehicle type with varying levels of tyre wear, and a range of road friction coefficients. We find that: (a) only a marginal loss of accuracy is incurred in using a global regressor as compared to local regressors, (b) the consensus estimate at the RSU has a worst case error of about ten percent, if the combination is based on at least fifty recently passed vehicles, and (c) our regressors have root mean square (RMS) errors that are less than five percent. The RMS error rate of our system is half as that of a commercial friction estimation service.
Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting
Authors: Benjamin Gess, Sebastian Kassing
Date: 2023-02-07 00:00:00
Tasks: Friction

We prove explicit bounds on the exponential rate of convergence for the momentum stochastic gradient descent scheme (MSGD) for arbitrary, fixed hyperparameters (learning rate, friction parameter) and its continuous-in-time counterpart in the context of non-convex optimization. In the small step-size regime and in the case of flat minima or large noise intensities, these bounds prove faster convergence of MSGD compared to plain stochastic gradient descent (SGD). The results are shown for objective functions satisfying a local Polyak-Lojasiewicz inequality and under assumptions on the variance of MSGD that are satisfied in overparametrized settings. Moreover, we analyze the optimal choice of the friction parameter and show that the MSGD process almost surely converges to a local minimum.
Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy
Authors: Blake Woodworth, Konstantin Mishchenko, Francis Bach
Date: 2023-02-07 00:00:00

We present an algorithm for minimizing an objective with hard-to-compute gradients by using a related, easier-to-access function as a proxy. Our algorithm is based on approximate proximal point iterations on the proxy combined with relatively few stochastic gradients from the objective. When the difference between the objective and the proxy is $\delta$-smooth, our algorithm guarantees convergence at a rate matching stochastic gradient descent on a $\delta$-smooth objective, which can lead to substantially better sample efficiency. Our algorithm has many potential applications in machine learning, and provides a principled means of leveraging synthetic data, physics simulators, mixed public and private data, and more.
On the Limitation and Experience Replay for GNNs in Continual Learning
Authors: Junwei Su, Difan Zou, Chuan Wu
Date: 2023-02-07 00:00:00
Tasks: Continual Learning, Incremental Learning, Model Selection

Continual learning seeks to empower models to progressively acquire information from a sequence of tasks. This approach is crucial for many real-world systems, which are dynamic and evolve over time. Recent research has witnessed a surge in the exploration of Graph Neural Networks (GNN) in Node-wise Graph Continual Learning (NGCL), a practical yet challenging paradigm involving the continual training of a GNN on node-related tasks. Despite recent advancements in continual learning strategies for GNNs in NGCL, a thorough theoretical understanding, especially regarding its learnability, is lacking. Learnability concerns the existence of a learning algorithm that can produce a good candidate model from the hypothesis/weight space, which is crucial for model selection in NGCL development. This paper introduces the first theoretical exploration of the learnability of GNN in NGCL, revealing that learnability is heavily influenced by structural shifts due to the interconnected nature of graph data. Specifically, GNNs may not be viable for NGCL under significant structural changes, emphasizing the need to manage structural shifts. To mitigate the impact of structural shifts, we propose a novel experience replay method termed Structure-Evolution-Aware Experience Replay (SEA-ER). SEA-ER features an innovative experience selection strategy that capitalizes on the topological awareness of GNNs, alongside a unique replay strategy that employs structural alignment to effectively counter catastrophic forgetting and diminish the impact of structural shifts on GNNs in NGCL. Our extensive experiments validate our theoretical insights and the effectiveness of SEA-ER.
OPORP: One Permutation + One Random Projection
Authors: Ping Li, Xiaoyun Li
Date: 2023-02-07 00:00:00
Tasks: Retrieval

Consider two $D$-dimensional data vectors (e.g., embeddings): $u, v$. In many embedding-based retrieval (EBR) applications where the vectors are generated from trained models, $D=256\sim 1024$ are common. In this paper, OPORP (one permutation + one random projection) uses a variant of the ``count-sketch'' type of data structures for achieving data reduction/compression. With OPORP, we first apply a permutation on the data vectors. A random vector $r$ is generated i.i.d. with moments: $E(r_i) = 0, E(r_i^2)=1, E(r_i^3) =0, E(r_i^4)=s$. We multiply (as dot product) $r$ with all permuted data vectors. Then we break the $D$ columns into $k$ equal-length bins and aggregate (i.e., sum) the values in each bin to obtain $k$ samples from each data vector. One crucial step is to normalize the $k$ samples to the unit $l_2$ norm. We show that the estimation variance is essentially: $(s-1)A + \frac{D-k}{D-1}\frac{1}{k}\left[ (1-\rho^2)^2 -2A\right]$, where $A\geq 0$ is a function of the data ($u,v$). This formula reveals several key properties: (1) We need $s=1$. (2) The factor $\frac{D-k}{D-1}$ can be highly beneficial in reducing variances. (3) The term $\frac{1}{k}(1-\rho^2)^2$ is a substantial improvement compared with $\frac{1}{k}(1+\rho^2)$, which corresponds to the un-normalized estimator. We illustrate that by letting the $k$ in OPORP to be $k=1$ and repeat the procedure $m$ times, we exactly recover the work of ``very spars random projections'' (VSRP). This immediately leads to a normalized estimator for VSRP which substantially improves the original estimator of VSRP. In summary, with OPORP, the two key steps: (i) the normalization and (ii) the fixed-length binning scheme, have considerably improved the accuracy in estimating the cosine similarity, which is a routine (and crucial) task in modern embedding-based retrieval (EBR) applications.
Revised Conditional t-SNE: Looking Beyond the Nearest Neighbors
Authors: Edith Heiter, Bo Kang, Ruth Seurinck, Jefrey Lijffijt
Date: 2023-02-07 00:00:00

Conditional t-SNE (ct-SNE) is a recent extension to t-SNE that allows removal of known cluster information from the embedding, to obtain a visualization revealing structure beyond label information. This is useful, for example, when one wants to factor out unwanted differences between a set of classes. We show that ct-SNE fails in many realistic settings, namely if the data is well clustered over the labels in the original high-dimensional space. We introduce a revised method by conditioning the high-dimensional similarities instead of the low-dimensional similarities and storing within- and across-label nearest neighbors separately. This also enables the use of recently proposed speedups for t-SNE, improving the scalability. From experiments on synthetic data, we find that our proposed method resolves the considered problems and improves the embedding quality. On real data containing batch effects, the expected improvement is not always there. We argue revised ct-SNE is preferable overall, given its improved scalability. The results also highlight new open questions, such as how to handle distance variations between clusters.
Learning Translation Quality Evaluation on Low Resource Languages from Large Language Models
Authors: Amirkeivan Mohtashami, Mauro Verzetti, Paul K. Rubenstein
Date: 2023-02-07 00:00:00
Tasks: Machine Translation, Translation

Learned metrics such as BLEURT have in recent years become widely employed to evaluate the quality of machine translation systems. Training such metrics requires data which can be expensive and difficult to acquire, particularly for lower-resource languages. We show how knowledge can be distilled from Large Language Models (LLMs) to improve upon such learned metrics without requiring human annotators, by creating synthetic datasets which can be mixed into existing datasets, requiring only a corpus of text in the target language. We show that the performance of a BLEURT-like model on lower resource languages can be improved in this way.
A Bayesian Optimization approach for calibrating large-scale activity-based transport models
Authors: Serio Agriesti, Vladimir Kuzmanovski, Jaakko Hollmén, Claudio Roncoli, Bat-hen Nahmias-Biran
Date: 2023-02-07 00:00:00
Tasks: Bayesian Optimization, Management

The use of Agent-Based and Activity-Based modeling in transportation is rising due to the capability of addressing complex applications such as disruptive trends (e.g., remote working and automation) or the design and assessment of disaggregated management strategies. Still, the broad adoption of large-scale disaggregate models is not materializing due to the inherently high complexity and computational needs. Activity-based models focused on behavioral theory, for example, may involve hundreds of parameters that need to be calibrated to match the detailed socio-economical characteristics of the population for any case study. This paper tackles this issue by proposing a novel Bayesian Optimization approach incorporating a surrogate model in the form of an improved Random Forest, designed to automate the calibration process of the behavioral parameters. The proposed method is tested on a case study for the city of Tallinn, Estonia, where the model to be calibrated consists of 477 behavioral parameters, using the SimMobility MT software. Satisfactory performance is achieved in the major indicators defined for the calibration process: the error for the overall number of trips is equal to 4% and the average error in the OD matrix is 15.92 vehicles per day.
Robustness Implies Fairness in Causal Algorithmic Recourse
Authors: Ahmad-Reza Ehyaei, Amir-Hossein Karimi, Bernhard Schölkopf, Setareh Maghsudi
Date: 2023-02-07 00:00:00
Tasks: Adversarial Robustness, Fairness

Algorithmic recourse aims to disclose the inner workings of the black-box decision process in situations where decisions have significant consequences, by providing recommendations to empower beneficiaries to achieve a more favorable outcome. To ensure an effective remedy, suggested interventions must not only be low-cost but also robust and fair. This goal is accomplished by providing similar explanations to individuals who are alike. This study explores the concept of individual fairness and adversarial robustness in causal algorithmic recourse and addresses the challenge of achieving both. To resolve the challenges, we propose a new framework for defining adversarially robust recourse. The new setting views the protected feature as a pseudometric and demonstrates that individual fairness is a special case of adversarial robustness. Finally, we introduce the fair robust recourse problem to achieve both desirable properties and show how it can be satisfied both theoretically and empirically.
Diverse Probabilistic Trajectory Forecasting with Admissibility Constraints
Authors: Laura Calem, Hedi Ben-Younes, Patrick Pérez, Nicolas Thome
Date: 2023-02-07 00:00:00
Tasks: Diversity, Motion Planning, Structured Prediction, Trajectory Forecasting

Predicting multiple trajectories for road users is important for automated driving systems: ego-vehicle motion planning indeed requires a clear view of the possible motions of the surrounding agents. However, the generative models used for multiple-trajectory forecasting suffer from a lack of diversity in their proposals. To avoid this form of collapse, we propose a novel method for structured prediction of diverse trajectories. To this end, we complement an underlying pretrained generative model with a diversity component, based on a determinantal point process (DPP). We balance and structure this diversity with the inclusion of knowledge-based quality constraints, independent from the underlying generative model. We combine these two novel components with a gating operation, ensuring that the predictions are both diverse and within the drivable area. We demonstrate on the nuScenes driving dataset the relevance of our compound approach, which yields significant improvements in the diversity and the quality of the generated trajectories.
On the relationship between multivariate splines and infinitely-wide neural networks
Authors: Francis Bach
Date: 2023-02-07 00:00:00

We consider multivariate splines and show that they have a random feature expansion as infinitely wide neural networks with one-hidden layer and a homogeneous activation function which is the power of the rectified linear unit. We show that the associated function space is a Sobolev space on a Euclidean ball, with an explicit bound on the norms of derivatives. This link provides a new random feature expansion for multivariate splines that allow efficient algorithms. This random feature expansion is numerically better behaved than usual random Fourier features, both in theory and practice. In particular, in dimension one, we compare the associated leverage scores to compare the two random expansions and show a better scaling for the neural network expansion.
Ensemble Value Functions for Efficient Exploration in Multi-Agent Reinforcement Learning
Authors: Lukas Schäfer, Oliver Slumbers, Stephen Mcaleer, Yali Du, Stefano V. Albrecht, David Mguni
Date: 2023-02-07 00:00:00
Tasks: Efficient Exploration, Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning (RL)

Multi-agent reinforcement learning (MARL) requires agents to explore within a vast joint action space to find joint actions that lead to coordination. Existing value-based MARL algorithms commonly rely on random exploration, such as $\epsilon$-greedy, to explore the environment which is not systematic and inefficient at identifying effective actions in multi-agent problems. Additionally, the concurrent training of the policies of multiple agents during training can render the optimisation non-stationary. This can lead to unstable value estimates, highly variant gradients, and ultimately hinder coordination between agents. To address these challenges, we propose ensemble value functions for multi-agent exploration (EMAX). EMAX is a framework to seamlessly extend value-based MARL algorithms. EMAX leverages an ensemble of value functions for each agent to guide their exploration, reduce the variance of their optimisation, and makes their policies more robust to miscoordination. EMAX achieves these benefits by (1) systematically guiding the exploration of agents with a UCB policy towards parts of the environment that require multiple agents to coordinate. (2) EMAX computes average value estimates across the ensemble as target values to reduce the variance of gradients and make optimisation more stable. (3) During evaluation, EMAX selects actions following a majority vote across the ensemble to reduce the likelihood of miscoordination. We first instantiate independent DQN with EMAX and evaluate it in 11 general-sum tasks with sparse rewards. We show that EMAX improves final evaluation returns by 185% across all tasks. We then evaluate EMAX on top of IDQN, VDN and QMIX in 21 common-reward tasks, and show that EMAX improves sample efficiency and final evaluation returns across all tasks over all three vanilla algorithms by 60%, 47%, and 538%, respectively.
A unified recipe for deriving (time-uniform) PAC-Bayes bounds
Authors: Ben Chugg, Hongjian Wang, Aaditya Ramdas
Date: 2023-02-07 00:00:00
Tasks: Generalization Bounds, valid

We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixtures, (c) the Donsker-Varadhan formula (or other convex duality principles), and (d) Ville's inequality. Our main result is a PAC-Bayes theorem which holds for a wide class of discrete stochastic processes. We show how this result implies time-uniform versions of well-known classical PAC-Bayes bounds, such as those of Seeger, McAllester, Maurer, and Catoni, in addition to many recent bounds. We also present several novel bounds. Our framework also enables us to relax traditional assumptions; in particular, we consider nonstationary loss functions and non-i.i.d. data. In sum, we unify the derivation of past bounds and ease the search for future bounds: one may simply check if our supermartingale or submartingale conditions are met and, if so, be guaranteed a (time-uniform) PAC-Bayes bound.
Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity
Authors: Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, Jin Zhang
Date: 2023-02-07 00:00:00

Gradient methods have become mainstream techniques for Bi-Level Optimization (BLO) in learning fields. The validity of existing works heavily rely on either a restrictive Lower-Level Strong Convexity (LLSC) condition or on solving a series of approximation subproblems with high accuracy or both. In this work, by averaging the upper and lower level objectives, we propose a single loop Bi-level Averaged Method of Multipliers (sl-BAMM) for BLO that is simple yet efficient for large-scale BLO and gets rid of the limited LLSC restriction. We further provide non-asymptotic convergence analysis of sl-BAMM towards KKT stationary points, and the comparative advantage of our analysis lies in the absence of strong gradient boundedness assumption, which is always required by others. Thus our theory safely captures a wider variety of applications in deep learning, especially where the upper-level objective is quadratic w.r.t. the lower-level variable. Experimental results demonstrate the superiority of our method.
Learning Discretized Neural Networks under Ricci Flow
Authors: Jun Chen, Hanwen Chen, Mengmeng Wang, Guang Dai, Ivor W. Tsang, Yong liu
Date: 2023-02-07 00:00:00

In this paper, we study Discretized Neural Networks (DNNs) composed of low-precision weights and activations, which suffer from either infinite or zero gradients due to the non-differentiable discrete function during training. Most training-based DNNs in such scenarios employ the standard Straight-Through Estimator (STE) to approximate the gradient w.r.t. discrete values. However, the use of STE introduces the problem of gradient mismatch, arising from perturbations in the approximated gradient. To address this problem, this paper reveals that this mismatch can be interpreted as a metric perturbation in a Riemannian manifold, viewed through the lens of duality theory. Building on information geometry, we construct the Linearly Nearly Euclidean (LNE) manifold for DNNs, providing a background for addressing perturbations. By introducing a partial differential equation on metrics, i.e., the Ricci flow, we establish the dynamical stability and convergence of the LNE metric with the $L^2$-norm perturbation. In contrast to previous perturbation theories with convergence rates in fractional powers, the metric perturbation under the Ricci flow exhibits exponential decay in the LNE manifold. Experimental results across various datasets demonstrate that our method achieves superior and more stable performance for DNNs compared to other representative training-based methods.