Search

This paper addresses the scheduling problem on two identical parallel machines with a single server in charge of loading and unloading operations of jobs. Each job has to be loaded by the server before being processed on one of the two machines and unloaded by the same server after its processing. No delay is allowed between loading and processing, and between processing and unloading. The objective function involves the minimization of the makespan. This problem referred to as P2, S1|sj , tj |Cmax generalizes the classical parallel machine scheduling problem with a single server which performs only the loading (i.e., setup) operation of each job. For this NP-hard problem, no solution algorithm was proposed in the literature. Therefore, we present two mixedinteger linear programming (MILP) formulations, one with completion-time variables along with two valid inequalities and one with time-indexed variables. In addition, we propose some polynomial-time solvable cases and a tight theoretical lower bound. In addition, we show that the minimization of the makespan is equivalent to the minimization of the total idle times on the machines. To solve large-sized instances of the problem, an efficient General Variable Neighborhood Search (GVNS) metaheuristic with two mechanisms for finding an initial solution is designed. The GVNS is evaluated by comparing its performance with the results provided by the MILPs and another metaheuristic. The results show that the average percentage deviation from the theoretical lower-bound of GVNS is within 0.642%. Some managerial insights are presented and our results are compared with the related literature., Comment: 40 pages, 4 figures, 16 tables

Over the past decade, the techniques of topological data analysis (TDA) have grown into prominence to describe the shape of data. In recent years, there has been increasing interest in developing statistical methods and in particular hypothesis testing procedures for TDA. Under the statistical perspective, persistence diagrams -- the central multi-scale topological descriptors of data provided by TDA -- are viewed as random observations sampled from some population or process. In this context, one of the earliest works on hypothesis testing focuses on the two-group permutation-based approach where the associated loss function is defined in terms of within-group pairwise bottleneck or Wasserstein distances between persistence diagrams (Robinson and Turner, 2017). However, in situations where persistence diagrams are large in size and number, the permutation test in question gets computationally more costly to apply. To address this limitation, we instead consider pairwise distances between vectorized functional summaries of persistence diagrams for the loss function. In the present work, we explore the utility of the Betti function in this regard, which is one of the simplest function summaries of persistence diagrams. We introduce an alternative vectorization method for the Betti function based on integration and prove stability results with respect to the Wasserstein distance. Moreover, we propose a new shuffling technique of group labels to increase the power of the test. Through several experimental studies, on both synthetic and real data, we show that the vectorized Betti function leads to competitive results compared to the baseline method involving the Wasserstein distances for the permutation test.

Dataset Distillation is the task of synthesizing small datasets from large ones while still retaining comparable predictive accuracy to the original uncompressed dataset. Despite significant empirical progress in recent years, there is little understanding of the theoretical limitations/guarantees of dataset distillation, specifically, what excess risk is achieved by distillation compared to the original dataset, and how large are distilled datasets? In this work, we take a theoretical view on kernel ridge regression (KRR) based methods of dataset distillation such as Kernel Inducing Points. By transforming ridge regression in random Fourier features (RFF) space, we provide the first proof of the existence of small (size) distilled datasets and their corresponding excess risk for shift-invariant kernels. We prove that a small set of instances exists in the original input space such that its solution in the RFF space coincides with the solution of the original data. We further show that a KRR solution can be generated using this distilled set of instances which gives an approximation towards the KRR solution optimized on the full input data. The size of this set is linear in the dimension of the RFF space of the input set or alternatively near linear in the number of effective degrees of freedom, which is a function of the kernel, number of datapoints, and the regularization parameter $\lambda$. The error bound of this distilled set is also a function of $\lambda$. We verify our bounds analytically and empirically.

In this report we investigate whether and under what conditions virtual seismology via the acoustic Marchenko method can be applied to DAS data from a survey in the province of Groningen, The Netherlands. Virtual seismology allows to retrieve the band-limited Green's function between a virtual source at an arbitrary focal point in the subsurface, while accounting for all orders of multiples. The method requires the reflection response at the surface and an estimate of the traveltime between the surface and focal point. However, in order to successfully apply the method the reflection response needs to be free from surface waves and other direct waves, and properly scaled in order for the Marchenko scheme to converge. These limitations severely complicate the application of the Marchenko method to field data, especially seismic surveys on land. This report considers a full 2D geophone survey as well as a 1.5D approximation for a DAS survey, and compares the results of the virtual sources with an actual dynamite source. The results show that virtual seismology can be used to recreate the reflections recorded at the surface from the dynamite source using either geophone or DAS data., Comment: 7 pages, 6 figures

Large time-varying graphs are increasingly common in financial, social and biological settings. Feature extraction that efficiently encodes the complex structure of sparse, multi-layered, dynamic graphs presents computational and methodological challenges. In the past decade, a persistence diagram (PD) from topological data analysis (TDA) has become a popular descriptor of shape of data with a well-defined distance between points. However, applications of TDA to graphs, where there is no intrinsic concept of distance between the nodes, remain largely unexplored. This paper addresses this gap in the literature by introducing a computationally efficient framework to extract shape information from graph data. Our framework has two main steps: first, we compute a PD using the so-called lower-star filtration which utilizes quantitative node attributes, and then vectorize it by averaging the associated Betti function over successive scale values on a one-dimensional grid. Our approach avoids embedding a graph into a metric space and has stability properties against input noise. In simulation studies, we show that the proposed vector summary leads to improved change point detection rate in time-varying graphs. In a real data application, our approach provides up to 22% gain in anomalous price prediction for the Ethereum cryptocurrency transaction networks.

Distributed Acoustic Sensing (DAS) is a novel technology that allows sampling of the seismic wavefield densely over a broad frequency band. This makes it an ideal tool for surface wave studies. In this study, we evaluate the potential of DAS to image the near-surface using synthetic data and active-source field DAS data recorded with straight fibers in Groningen, the Netherlands. First, we recover the laterally varying surface wave phase velocities (i.e., local dispersion curves) from the fundamental-mode surface waves. We utilize the Multi Offset Phase Analysis (MOPA) for the recovery of the laterally varying phase velocities. In this way, we take into account the lateral variability of the subsurface structures. Then, instead of inverting each local dispersion curve independently, we propose to use a novel 2D transdimensional surface wave tomography algorithm to image the subsurface. In this approach, we parameterize the model space using 2D Voronoi cells and invert all the local dispersion curves simultaneously to consider the lateral spatial correlation of the inversion result. Additionally, this approach reduces the solution nonuniqueness of the inversion problem. The proposed methodology successfully recovered the shear-wave velocity of the synthetic data. Application to the field data also confirms the reliability of the proposed algorithm. The recovered 2D shear-wave velocity profile is compared to shear-wave velocity logs obtained at the location of two boreholes, which shows a good agreement.

Distributed Acoustic Sensing (DAS) has been limited in its use for surface-seismic reflection measurements, due to the fiber's decreased sensitivity when the fiber is deployed horizontally. Deploying the fiber in a helically wound fashion has the promise of being more sensitive to broadside waves (e.g. P-wave reflections) and less sensitive to surface waves than straight fiber. We examine these claims by burying a set of straight fibers (SF) and helically wound fibers (HWF) with different wrapping angles, using standard and engineered fibers. These fibers were buried in a 2 m deep trench in a farmland in the province of Groningen in the Netherlands. They are linked up to two interrogating systems and an electrically driven vibrator was used as a seismic source. We observe in our field data that using HWF has a destructive effect on the surface-wave amplitudes. Our data confirmed the effect of the wrapping angle on the polarity of the surface-wave arrival and the dampening effect of the helical winding, both behaving in quite a predictable fashion. Apart from the effect of the wrapping angle, the different design choices, e.g. cable filling and material type, did not show a significant effect on the amplitude of the signals. As for P-wave reflections, we observe that both engineered SF and HWF provide reflection images comparable to those obtained from the geophone data despite the straight fiber's decreased broadside sensitivity. A polarity reversal and an amplitude difference between SF and HWF fibers are observed. Finally, we show that the combined use of SF and HWF proved to be useful since SF showed better sensitivity in the shallower part and HWF in the deeper part., Comment: This manuscript has been submitted to GEOPHYSICS journal

Modern end-to-end learning systems can learn to explicitly infer control from perception. However, it is difficult to guarantee stability and robustness for these systems since they are often exposed to unstructured, high-dimensional, and complex observation spaces (e.g., autonomous driving from a stream of pixel inputs). We propose to leverage control Lyapunov functions (CLFs) to equip end-to-end vision-based policies with stability properties and introduce stability attention in CLFs (att-CLFs) to tackle environmental changes and improve learning flexibility. We also present an uncertainty propagation technique that is tightly integrated into att-CLFs. We demonstrate the effectiveness of att-CLFs via comparison with classical CLFs, model predictive control, and vanilla end-to-end learning in a photo-realistic simulator and on a real full-scale autonomous vehicle., Comment: First two authors contributed equally; L4DC 2023

Intelligent intersection managers can improve safety by detecting dangerous drivers or failure modes in autonomous vehicles, warning oncoming vehicles as they approach an intersection. In this work, we present FailureNet, a recurrent neural network trained end-to-end on trajectories of both nominal and reckless drivers in a scaled miniature city. FailureNet observes the poses of vehicles as they approach an intersection and detects whether a failure is present in the autonomy stack, warning cross-traffic of potentially dangerous drivers. FailureNet can accurately identify control failures, upstream perception errors, and speeding drivers, distinguishing them from nominal driving. The network is trained and deployed with autonomous vehicles in the MiniCity. Compared to speed or frequency-based predictors, FailureNet's recurrent neural network structure provides improved predictive power, yielding upwards of 84% accuracy when deployed on hardware., Comment: 8 pages. Accepted to ICRA 2023

We propose a new dataset distillation algorithm using reparameterization and convexification of implicit gradients (RCIG), that substantially improves the state-of-the-art. To this end, we first formulate dataset distillation as a bi-level optimization problem. Then, we show how implicit gradients can be effectively used to compute meta-gradient updates. We further equip the algorithm with a convexified approximation that corresponds to learning on top of a frozen finite-width neural tangent kernel. Finally, we improve bias in implicit gradients by parameterizing the neural network to enable analytical computation of final-layer parameters given the body parameters. RCIG establishes the new state-of-the-art on a diverse series of dataset distillation tasks. Notably, with one image per class, on resized ImageNet, RCIG sees on average a 108\% improvement over the previous state-of-the-art distillation algorithm. Similarly, we observed a 66\% gain over SOTA on Tiny-ImageNet and 37\% on CIFAR-100.

Modern deep learning requires large volumes of data, which could contain sensitive or private information that cannot be leaked. Recent work has shown for homogeneous neural networks a large portion of this training data could be reconstructed with only access to the trained network parameters. While the attack was shown to work empirically, there exists little formal understanding of its effective regime which datapoints are susceptible to reconstruction. In this work, we first build a stronger version of the dataset reconstruction attack and show how it can provably recover the \emph{entire training set} in the infinite width regime. We then empirically study the characteristics of this attack on two-layer networks and reveal that its success heavily depends on deviations from the frozen infinite-width Neural Tangent Kernel limit. Next, we study the nature of easily-reconstructed images. We show that both theoretically and empirically, reconstructed images tend to "outliers" in the dataset, and that these reconstruction attacks can be used for \textit{dataset distillation}, that is, we can retrain on reconstructed images and obtain high predictive accuracy.

The cooperation of a human pilot with an autonomous agent during flight control realizes parallel autonomy. We propose an air-guardian system that facilitates cooperation between a pilot with eye tracking and a parallel end-to-end neural control system. Our vision-based air-guardian system combines a causal continuous-depth neural network model with a cooperation layer to enable parallel autonomy between a pilot and a control system based on perceived differences in their attention profiles. The attention profiles for neural networks are obtained by computing the networks' saliency maps (feature importance) through the VisualBackProp algorithm, while the attention profiles for humans are either obtained by eye tracking of human pilots or saliency maps of networks trained to imitate human pilots. When the attention profile of the pilot and guardian agents align, the pilot makes control decisions. Otherwise, the air-guardian makes interventions and takes over the control of the aircraft. We show that our attention-based air-guardian system can balance the trade-off between its level of involvement in the flight and the pilot's expertise and attention. The guardian system is particularly effective in situations where the pilot was distracted due to information overload. We demonstrate the effectiveness of our method for navigating flight scenarios in simulation with a fixed-wing aircraft and on hardware with a quadrotor platform.

The James Webb Space Telescope (JWST) discovered several luminous high-redshift galaxy candidates with stellar masses of $M_{*} \gtrsim 10^{9} \, \rm{M_{\odot}}$ at photometric redshifts $z_{\mathrm{phot}} \gtrsim 10$ which allows to constrain galaxy and structure formation models. For example, Adams et al. identified the candidate ID 1514 with $\log_{10}(M_{*}/M_{\odot}) = {9.8}_{-0.2}^{+0.2}$ located at $z_{\mathrm{phot}} = 9.85_{-0.12}^{+0.18}$ and Naidu et al. found even more distant candidates labeled as GL-z11 and GL-z13 with $\log_{10}(M_{*}/M_{\odot}) = 9.4_{-0.3}^{+0.3}$ at $z_{\mathrm{phot}}=10.9_{-0.4}^{+0.5}$ and $\log_{10}(M_{*}/M_{\odot}) = 9.0_{-0.4}^{+0.3}$ at $z_{\mathrm{phot}} = 13.1_{-0.7}^{+0.8}$, respectively. Assessing the computations of the IllustrisTNG (TNG50-1 and TNG100-1) and EAGLE projects, we investigate if the stellar mass buildup as predicted by the $\Lambda$CDM paradigm is consistent with these observations assuming that the early JWST calibration is correct and that the candidates are indeed located at $z \gtrsim 10$. Galaxies formed in the $\Lambda$CDM paradigm are by more than an order of magnitude less massive in stars than the observed galaxy candidates implying that the stellar mass buildup is more efficient in the early Universe than predicted by the $\Lambda$CDM models. This in turn would suggest that structure formation is more enhanced at $z \gtrsim 10$ than predicted by the $\Lambda$CDM framework. We show that different star formation histories could reduce the stellar masses of the galaxy candidates alleviating the tension. Finally, we calculate the galaxy-wide initial mass function (gwIMF) of the galaxy candidates assuming the integrated galaxy IMF theory. The gwIMF becomes top-heavy for metal-poor starforming galaxies decreasing therewith the stellar masses compared to an invariant canonical IMF., Comment: Accepted for publication in ApJL, 10 pages, 4 figures, 1 tables

After their birth a significant fraction of all stars pass through the tidal threshold (prah) of their cluster of origin into the classical tidal tails. The asymmetry between the number of stars in the leading and trailing tails tests gravitational theory. All five open clusters with tail data (Hyades, Praesepe, Coma Berenices, COIN-Gaia 13, NGC 752) have visibly more stars within dcl = 50 pc of their centre in their leading than their trailing tail. Using the Jerabkova-compact-convergent-point (CCP) method, the extended tails have been mapped out for four nearby 600-2000 Myr old open clusters to dcl>50 pc. These are on near-circular Galactocentric orbits, a formula for estimating the orbital eccentricity of an open cluster being derived. Applying the Phantom of Ramses code to this problem, in Newtonian gravitation the tails are near-symmetrical. In Milgromian dynamics (MOND) the asymmetry reaches the observed values for 50 < dcl/pc < 200, being maximal near peri-galacticon, and can slightly invert near apo-galacticon, and the K\"upper epicyclic overdensities are asymmetrically spaced. Clusters on circular orbits develop orbital eccentricity due to the asymmetrical spill-out, therewith spinning up opposite to their orbital angular momentum. This positive dynamical feedback suggests Milgromian open clusters to demise rapidly as their orbital eccentricity keeps increasing. Future work is necessary to better delineate the tidal tails around open clusters of different ages and to develop a Milgromian direct n-body code., Comment: 28 pages, 19 figures, MNRAS, published

Dataset distillation compresses large datasets into smaller synthetic coresets which retain performance with the aim of reducing the storage and computational burden of processing the entire dataset. Today's best-performing algorithm, \textit{Kernel Inducing Points} (KIP), which makes use of the correspondence between infinite-width neural networks and kernel-ridge regression, is prohibitively slow due to the exact computation of the neural tangent kernel matrix, scaling $O(|S|^2)$, with $|S|$ being the coreset size. To improve this, we propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel, which reduces the kernel matrix computation to $O(|S|)$. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets, both in kernel regression and finite-width network training. We demonstrate the effectiveness of our approach on tasks involving model interpretability and privacy preservation., Comment: Accepted to the Conference on the Advances in Neural Information Processing Systems (NeurIPS) 2022

Two key challenges facing modern deep learning are mitigating deep networks' vulnerability to adversarial attacks and understanding deep learning's generalization capabilities. Towards the first issue, many defense strategies have been developed, with the most common being Adversarial Training (AT). Towards the second challenge, one of the dominant theories that has emerged is the Neural Tangent Kernel (NTK) -- a characterization of neural network behavior in the infinite-width limit. In this limit, the kernel is frozen, and the underlying feature map is fixed. In finite widths, however, there is evidence that feature learning happens at the earlier stages of the training (kernel learning) before a second phase where the kernel remains fixed (lazy training). While prior work has aimed at studying adversarial vulnerability through the lens of the frozen infinite-width NTK, there is no work that studies the adversarial robustness of the empirical/finite NTK during training. In this work, we perform an empirical study of the evolution of the empirical NTK under standard and adversarial training, aiming to disambiguate the effect of adversarial training on kernel learning and lazy training. We find under adversarial training, the empirical NTK rapidly converges to a different kernel (and feature map) than standard training. This new kernel provides adversarial robustness, even when non-robust training is performed on top of it. Furthermore, we find that adversarial training on top of a fixed kernel can yield a classifier with $76.1\%$ robust accuracy under PGD attacks with $\varepsilon = 4/255$ on CIFAR-10., Comment: Accepted to the Conference on Advances in Neural Information Processing Systems (NeurIPS) 2022