We define the notion of a Ricci curvature lower bound for parametrized statistical models. Following the seminal ideas of Lott–Sturm–Villani, we define this notion based on the geodesic convexity of the Kullback–Leibler divergence in a Wasserstein statistical manifold, that is, a manifold of probability distributions endowed with a Wasserstein metric tensor structure. Within these definitions, which are based on Fisher information matrix and Wasserstein Christoffel symbols, the Ricci curvature is related to both, information geometry and Wasserstein geometry. These definitions allow us to formulate bounds on the convergence rate of Wasserstein gradient flows and information functional inequalities in parameter space. We discuss examples of Ricci curvature lower bounds and convergence rates in exponential family models.

No abstract uploaded!

No abstract uploaded!

A major challenge for ridesharing platforms is to guarantee profit and fairness simultaneously, especially in the presence of misaligned incentives of drivers and riders. We focus on the dispatchingpricing problem to maximize the total revenue while keeping both drivers and riders satisfied. We study the computational complexity of the problem, provide a novel two-phased pricing solution with revenue and fairness guarantees, extend it to stochastic settings and develop a dynamic (a.k.a., learning-while-doing) algorithm that actively collects data to learn the demand distribution during the scheduling process. We also conduct extensive experiments to demonstrate the effectiveness of our algorithms.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

A recent line of work has studied the statistical properties of neural networks to great success from a {\it mean field theory} perspective, making and verifying very precise predictions of neural network behavior and test time performance. In this paper, we build upon these works to explore two methods for taming the behaviors of random residual networks (with only fully connected layers and no batchnorm). The first method is {\it width variation (WV)}, ie varying the widths of layers as a function of depth. We show that width decay reduces gradient explosion without affecting the mean forward dynamics of the random network. The second method is {\it variance variation (VV)}, ie changing the initialization variances of weights and biases over depth. We show VV, used appropriately, can reduce gradient explosion of tanh and ReLU resnets from \exp (\Theta (\sqrt L)) and \exp (\Theta (\sqrt L)) respectively to constant \exp (\Theta (\sqrt L)) . A complete phase-diagram is derived for how variance decay affects different dynamics, such as those of gradient and activation norms. In particular, we show the existence of many phase transitions where these dynamics switch between exponential, polynomial, logarithmic, and even constant behaviors. Using the obtained mean field theory, we are able to track surprisingly well how VV at initialization time affects training and test time performance on MNIST after a set number of epochs: the level sets of test/train set accuracies coincide with the level sets of the expectations of certain gradient norms or of metric expressivity (as defined in\cite {yang_meanfield_2017}), a measure of expansion in a random neural network. Based on insights from past works in

No abstract uploaded!

Following the recent trend in explicit neural memory structures, we present a new design of an external memory, wherein memories are stored in an Euclidean key space \mathbb R^ n . An LSTM controller performs read and write via specialized read and write heads. It can move a head by either providing a new address in the key space (aka random access) or moving from its previous position via a Lie group action (aka Lie access). In this way, the" L" and" R" instructions of a traditional Turing Machine are generalized to arbitrary elements of a fixed Lie group action. For this reason, we name this new model the Lie Access Neural Turing Machine, or LANTM.

We develop an auto-reservoir computing framework, Auto-Reservoir Neural Network (ARNN), to efficiently and accurately make multi-step-ahead predictions based on a short-term high-dimensional time series. Different from traditional reservoir computing whose reservoir is an external dynamical system irrelevant to the target system, ARNN directly transforms the observed high-dimensional dynamics as its reservoir, which maps the high-dimensional/spatial data to the future temporal values of a target variable based on our spatiotemporal information (STI) transformation. Thus, the multi-step prediction of the target variable is achieved in an accurate and computationally efficient manner. ARNN is successfully applied to both representative models and real-world datasets, all of which show satisfactory performance in the multi-step-ahead prediction, even when the data are peturbed by noise and when the system is time-varying. Actually, such ARNN transformation equivalently expands the sample size and thus has great potential in practical applications in artificial intelligence and machine learning.

Personal videos often contain visual distractors, which are objects that are accidentally captured that can distract viewers from focusing on the main subjects. We propose a method to automatically detect and localize these distractors through learning from a manually labeled dataset. To achieve spatially and temporally coherent detection, we propose extracting features at the Temporal-Superpixel (TSP) level using a traditional SVM-based learning framework. We also experiment with end-to-end learning using Convolutional Neural Networks (CNNs), which achieves slightly higher performance than other methods. The classification result is further refined in a post-processing step based on graph-cut optimization. Experimental results show that our method achieves an accuracy of 81% and a recall of 86%. We demonstrate several ways of removing the detected distractors to improve the video quality, including video hole filling; video frame replacement; and camera path re-planning. The user study results show that our method can significantly improve the aesthetic quality of videos.

Image retargeting techniques adjust images into different sizes and have attracted much attention recently. Objective quality assessment (OQA) of image retargeting results is often desired to automatically select the best results. Existing OQA methods train a model using some benchmarks (e.g., RetargetMe), in which subjective scores evaluated by users are provided. Observing that it is challenging even for human subjects to give consistent scores for retargeting results of different source images (diff-source-results), in this paper we propose a learning-based OQA method that trains a General Regression Neural Network (GRNN) model based on relative scores --- which preserve the ranking --- of retargeting results of the same source image (same-source-results). In particular, we develop a novel training scheme with provable convergence that learns a common base scalar for same-source-results. With this source specific offset, our computed scores not only preserve the ranking of subjective scores for same-source-results, but also provide a reference to compare the diff-source-results. We train and evaluate our GRNN model using human preference data collected in RetargetMe. We further introduce a subjective benchmark to evaluate the generalizability of different OQA methods. Experimental results demonstrate that our method outperforms ten representative OQA methods in ranking prediction and has better generalizability to different datasets.

Training process is crucial for the deployment of the network in applications which have two strict requirements on both accuracy and robustness. However, most existing approaches are in a dilemma, i.e. model accuracy and robustness forming an embarrassing tradeoff – the improvement of one leads to the drop of the other. The challenge remains for as we try to improve the accuracy and robustness simultaneously. In this paper, we propose a novel training method via introducing the auxiliary classifiers for training on corrupted samples, while the clean samples are normally trained with the primary classifier. In the training stage, a novel distillation method named input-aware self distillation is proposed to facilitate the primary classifier to learn the robust information from auxiliary classifiers. Along with it, a new normalization method - selective batch normal- ization is proposed to prevent the model from the negative influence of corrupted images. At the end of the training period, a L2-norm penalty is applied to the weights of primary and auxiliary classifiers such that their weights are asymptotically identical. In the stage of inference, only the primary classifier is used and thus no extra computation and storage are needed. Extensive experiments on CIFAR10, CIFAR100 and ImageNet show that noticeable improvements on both accuracy and robustness can be observed by the proposed auxiliary training. On average, auxiliary training achieves 2.21% accuracy and 21.64% robustness (measured by corruption error) improvements over traditional training methods on CIFAR100. Codes have been released on github.

This paper proposes a neural network approach for efficiently solving general nonlinear convex programs with second-order cone constraints. The proposed neural network model was developed based on a smoothed natural residual merit function involving an unconstrained minimization reformulation of the complementarity problem. We study the existence and convergence of the trajectory of the neural network. Moreover, we show some stability properties for the considered neural network, such as the Lyapunov stability, asymptotic stability, and exponential stability. The examples in this paper provide a further demonstration of the effectiveness of the proposed neural network. This paper can be viewed as a follow-up version of [20], [26] because more stability results are obtained.

No abstract uploaded!

We study randomly initialized residual networks using mean field theory and the theory of difference equations. Classical feedforward neural networks, such as those with tanh activations, exhibit exponential behavior on the average when propagating inputs forward or gradients backward. The exponential forward dynamics causes rapid collapsing of the input space geometry, while the exponential backward dynamics causes drastic vanishing or exploding gradients. We show, in contrast, that by adding skip connections, the network will, depending on the nonlinearity, adopt subexponential forward and backward dynamics, and in many cases in fact polynomial. The exponents of these polynomials are obtained through analytic methods and proved and verified empirically to be correct. In terms of the" edge of chaos" hypothesis, these subexponential and polynomial laws allow residual networks to" hover over the boundary between stability and chaos," thus preserving the geometry of the input space and the gradient information flow. In our experiments, for each activation function we study here, we initialize residual networks with different hyperparameters and train them on MNIST. Remarkably, our initialization time theory can accurately predict test time performance of these networks, by tracking either the expected amount of gradient explosion or the expected squared distance between the images of two input vectors. Importantly, we show, theoretically as well as empirically, that common initializations such as the Xavier or the He schemes are not optimal for residual networks, because the optimal initialization variances depend on the depth

This paper proposes using the neural networks to efficiently solve the second-order cone programs (SOCP). To establish the neural networks, the SOCP is first reformulated as a second-order cone complementarity problem (SOCCP) with the KarushKuhnTucker conditions of the SOCP. The SOCCP functions, which transform the SOCCP into a set of nonlinear equations, are then utilized to design the neural networks. We propose two kinds of neural networks with the different SOCCP functions. The first neural network uses the FischerBurmeister function to achieve an unconstrained minimization with a merit function. We show that the merit function is a Lyapunov function and this neural network is asymptotically stable. The second neural network utilizes the natural residual function with the cone projection function to achieve low computation complexity. It is shown to be Lyapunov stable and converges globally

In a Data-Generating Experiment, the observed sample, x, has intractable or unavailable c.d.f., F_θ, and θ’s statistical nature is unknown; θ is element of metric space (Θ, dΘ). Matching estimates of θ are introduced, learning from the “best” x-matches with samples X^∗ from F_{θ^∗}, θ^∗ ∈ Θ. Under mild conditions, these nonparametric estimates are uniformly consistent and the upper bounds on their rates of convergence in probability have the same rate and depend on the Kolmogorov entropies of an increasing sequence of sets covering Θ. When Θ ⊆ Rm and the observations are i.i.d. the upper bounds can be, \sqrt{log n}/\sqrt{n} when m is known, and \sqrt{m_n·log n}/\sqrt{n} when m is unknown; m ≥ 1, m_n ↑ ∞ at a desired rate. Upper bounds can also be obtained for dependent observations. These rates hold for observations in R^d, complementing recent results obtained for real, i.i.d. observations, under stronger assumptions and using weak probability distances; d ≥ 1. In simulations, the Matching estimates are successful for the mixture of 2 normals and for Tukey’s (a, b, g, h) and the (a, b, g, k) models. Computers’ evolution will allow for more and faster comparisons, resulting in improved Matching estimates for universal use in Machine Learning.

Learning rate is arguably the most important hyper-parameter to tune when training a neural network. As manually setting right learning rate remains a cumbersome process, adaptive learning rate algorithms aim at automating such a process. Motivated by the success of the Barzilai–Borwein (BB) step-size method in many gradient descent methods for solving convex problems, this paper aims at investigating the potential of the BB method for training neural networks. With strong motivation from related convergence analysis, the BB method is generalized to adaptive learning rate of mini-batch gradient descent. The experiments showed that, in contrast to many existing methods, the proposed BB method is highly insensitive to initial learning rate, especially in terms of generalization performance. Also, the BB method showed its advantages on both learning speed and generalization performance over other available methods.

When sample, X = x, is observed from intractable c.d.f. Fθ, or a Black-Box with input θ, an Approximate Bayesian Computation (ABC) method provides approximate posterior, π_ϵ. θ^∗ is included in the support of π_ϵ when the Matching distance ρ(S(x^∗), S(x)) ≤ ϵ; x^∗ is a sample drawn from F_{θ^∗}, θ^∗ is obtained from prior π, S is a summary statistic, ϵ > 0. ABC concerns include: the use of only one sample, x^∗, for each θ^∗; the choices of S, ρ and ϵ; π_ϵ(θ^∗), which is determined by arbitrary kernel, K(x, x^∗; ϵ), creating visual π_ϵ-artifacts. The concerns are accommodated with the introduced Fiducial(F)-ABC for all (θ^∗ drawn): M x^∗ are drawn from F_{θ^∗}; a universal S is used, the empirical measure indexed by sets which activate its sufficiency for exchangeable observations-vectors and have been neglected; a strong, probability distance ρ is used, inherently connected with S and Matching; light is thrown to ϵ’s nature and value; πϵ is obtained from the proportions of x∗ matching x. F-ABC for all posterior is closer to Bayesian philosophy, which does not use θ^∗-exclusions. Under few, mild assumptions, π_ϵ converges to the posterior, π(θ|x), when ϵ ↓ 0, and rates of concentration of T (F_{θ^∗}) to T (F_θ) are obtained when n ↑ ∞; T is a functional. Satisfactory F-ABC for all θ^∗ drawn posteriors are depicted for parametric and data generating models, including Tukey’s (a, b, g, h)-model, a 5-parameter normal mixture and a time series model. Various advantages of the F-ABC for all are presented over coarsened posteriors for observations in R^d, d ≥ 1.

We investigate the use of artificial neural networks (NNs) as an alternative tool to current analytical methods for recognizing knots in a given polymer conformation. The motivation is twofold. First, it is of interest to examine whether NNs are effective at learning the global and sequential properties that uniquely define a knot. Second, knot classification is an important and unsolved problem in mathematical and physical sciences, and NNs may provide insights into this problem. Motivated by these points, we generate millions of polymer conformations for five knot types: 0, 3_1, 4_1, 5_1, and 5_2, and we design various NN models for classification. Our best model achieves a five-class classification accuracy of above 99% on a polymer of 100 monomers. We find that the sequential modeling ability of recurrent NNs is crucial for this result, as it outperforms feed-forward NNs and successfully generalizes to differently sized conformations as well. We present our methods and suggest that deep learning may be used in specific applications of knot detection where some error is permissible. Hopefully, with further development, NNs can offer an alternative computational method for knot identification and facilitate knot research in mathematical and physical sciences.

Diffusion, a fundamental internal mechanism emerging in many physical processes, describes the interaction among different objects. In many learning tasks with limited training samples, the diffusion connects the labeled and unlabeled data points and is a critical component for achieving high classification accuracy. Many existing deep learning approaches directly impose the fusion loss when training neural networks. In this work, inspired by the convection-diffusion ordinary differential equations (ODEs), we propose a novel diffusion residual network (Diff-ResNet), internally introduces diffusion into the architectures of neural networks. Under the structured data assumption, it is proved that the proposed diffusion block can increase the distance-diameter ratio that improves the separability of inter-class points and reduces the distance among local intra-class points. Moreover, this property can be easily adopted by the residual networks for constructing the separable hyperplanes. Extensive experiments of synthetic binary classification, semi-supervised graph node classification and few-shot image classification in various datasets validate the effectiveness of the proposed method.

In a Data-Generating Experiment (DGE), the data, X, is often obtained either from a Black-Box with inputs θ and Y, or from a Quantile function or a learning machine, f(Y, θ); θ is unknown, element of metric space (Θ, ρ), Y is random. If X has intractable or unknown c.d.f., Fθ, non-identifiability of θ cannot be confirmed and when present, among others, limits the predictive accuracy of the learned model, f(Y, \hat{θ}); \hat{θ} estimate of θ. In Machine Learning, non-identifiability of θ is ubiquitous and its extent is a criterion for selecting a learning machine. Empirical indices, EDI and PPVI, are introduced using P-values of Kolmogorov-Smirnov tests: i) to confirm almost surely, using generated data, the discrimination of θ from θ^∗, namely that the Kolmogorov distance, dK(Fθ, Fθ^∗), is positive, ii) to confirm identifiability of θ(∈ Θ) by repeating i) for θ^∗ in a sieve of Θ, since neighboring parameter values are in practice indistinguishable, and iii) most important, to compare EDI-graphs of DGEs, preferring more discrimination and less non-identifiability among parameters, and select one DGE to use. In applications, EDI-graphs confirm nonidentifiability in mixture models and in models parametrised with sums of parameters. EDI and PPVI explain why Tukey’s g-and-h model (DGE1) has better g-discrimination than the g-and-k model (DGE2), unless the sample size is extremely large; h_0 = k_0. EDIgraphs indicate that Normal learning machines have better parameter discrimination thanSigmoid learning machines and their parameters are non-identifiable.