We study k-median clustering under the sequential no-substitution setting. In this setting, a data stream is sequentially observed, and some of the points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. We give the first algorithm for this setting that obtains a constant approximation factor on the optimal cost under a random arrival order, an exponential improvement over previous work. This is also the first constant approximation guarantee that holds without any structural assumptions on the input data. Moreover, the number of selected centers is only quasi-linear in k. Our algorithm and analysis are based on a careful cost estimation that avoids outliers, a new concept of a linear bin division, and a multiscale approach to center selection.

Despite a great deal of research, it is still not well-understood why trained neural networks are highly vulnerable to adversarial examples. In this work we focus on two-layer neural networks trained using data which lie on a low dimensional linear subspace. We show that standard gradient methods lead to non-robust neural networks, namely, networks which have large gradients in directions orthogonal to the data subspace, and are susceptible to small adversarial L2-perturbations in these directions. Moreover, we show that decreasing the initialization scale of the training algorithm, or adding L2 regularization, can make the trained network more robust to adversarial perturbations orthogonal to the data.

We present an implicit neural representation to learn the spatio-temporal space of kinematic motions. Unlike previous work that represents motion as discrete sequential samples, we propose to express the vast motion space as a continuous function over time, hence the name Neural Motion Fields (NeMF). Specifically, we use a neural network to learn this function for miscellaneous sets of motions, which is designed to be a generative model conditioned on a temporal coordinate t and a random vector z for controlling the style. The model is then trained as a Variational Autoencoder (VAE) with motion encoders to sample the latent space. We train our model with a diverse human motion dataset and quadruped dataset to prove its versatility, and finally deploy it as a generic motion prior to solve task-agnostic problems and show its superiority in different motion generation and editing applications, such as motion interpolation, in-betweening, and re-navigating. More details can be found on our project page: https://cs.yale.edu/homes/

In order to expand the polynomial surface fitting in 3D dimensional space into the high dimensional feature space using a neural network with parameter Θ, we define f1(gω):= g and f2(cυ):= c, where f means MLP layer. Then, the multiplication of real numbers gω cυ in the polynomial function is represented as g c, i.e., gω cυ:= g c, and the orders ω,υ [0,1,...,τ]. Then, the final bivariate function used in our hyper surface fitting is Nθ,τ(G,C) = Θ(G C), where Gand C are high dimensional features of the 3D point clouds extracted by the two different modules, which are introduced in Sec.3.3 and Sec.3.4 of the paper, respectively. The other terms except the principal terms in the polynomial equation are not used in the estimation of the normal. Based on this, we use the max-pooling over all features from the hyper surface fitting 2 Figure 1: Visualization of the contribution of each 3D point to estimate the normal of the query point (black).