Stochastic, Distributed and Federated Optimization for Machine Learning

We study optimization algorithms for the finite sum problems frequently arising in machine learning applications. First, we propose novel variants of stochastic gradient descent with a variance reduction property that enables linear convergence for strongly convex objectives. Second, we study distributed setting, in which the data describing the optimization problem does not fit into a single computing node. In this case, traditional methods are inefficient, as the communication costs inherent in distributed optimization become the bottleneck. We propose a communication-efficient framework which iteratively forms local subproblems that can be solved with arbitrary local optimization algorithms. Finally, we introduce the concept of Federated Optimization/Learning, where we try to solve the machine learning problems without having data stored in any centralized manner. The main motivation comes from industry when handling user-generated data. The current prevalent practice is that companies collect vast amounts of user data and store them in datacenters. An alternative we propose is not to collect the data in first place, and instead occasionally use the computational power of users’ devices to solve the very same optimization problems, while alleviating privacy concerns at the same time. In such setting, minimization of communication rounds is the primary goal, and we demonstrate that solving the optimization problems in such circumstances is conceptually tractable.

Kernel Feature Selection via Conditional Covariance Minimization

We propose a framework for feature selection that employs kernel-based measures of independence to find a subset of covariates that is maximally predictive of the response. Building on past work in kernel dimension reduction, we formulate our approach as a constrained optimization problem involving the trace of the conditional covariance operator, and additionally provide some consistency results. We then demonstrate on a variety of synthetic and real data sets that our method compares favorably with other state-of-the-art algorithms.

A K-means clustering algorithm for multivariate big data with correlated components

Common clustering algorithms require multiple scans of all the data to achieve convergence, and this is prohibitive when large databases, with millions of data, must be processed. Some algorithms to extend the popular K-means method to the analysis of big data are present in literature since the publication of (Bradley et al, Scaling clustering algorithms to large databases, 1998) but they assume that the random vectors which are processed and grouped have uncorrelated components. Unfortunately this is not the case in many practical situations. We here propose an extension of the algorithm of Bradley, Fayyad and Reina to the processing of massive multivariate data, having correlated components.

ProtoDash: Fast Interpretable Prototype Selection

In this paper we propose an efficient algorithm ProtoDash for selecting prototypical examples from complex datasets. Our work builds on top of the learn to criticize (L2C) work by Kim et al. (2016) and generalizes it in at least two notable ways: 1) ProtoDash not only selects prototypes for a given sparsity level m but it also associates non-negative weights with each of them indicative of the importance of each prototype. 2) ProtoDash not only finds prototypical examples for a dataset X, but it can also find prototypical examples from X that best represent another dataset Y, where X and Y belong to the same feature space. We provide approximation guarantees for our algorithm by showing that the problem is weakly submodular and depict its efficacy on diverse domains namely; retail, digit recognition (MNIST) and on the latest publicly available 40 health questionnaires obtained from the Center for Disease Control (CDC) website maintained by the US Dept. of Health. We validate the results quantitatively as well as qualitatively based on expert feedback and recently published scientific studies on public health.

Graph Based Recommendations: From Data Representation to Feature Extraction and Application

Modeling users for the purpose of identifying their preferences and then personalizing services on the basis of these models is a complex task, primarily due to the need to take into consideration various explicit and implicit signals, missing or uncertain information, contextual aspects, and more. In this study, a novel generic approach for uncovering latent preference patterns from user data is proposed and evaluated. The approach relies on representing the data using graphs, and then systematically extracting graph-based features and using them to enrich the original user models. The extracted features encapsulate complex relationships between users, items, and metadata. The enhanced user models can then serve as an input to any recommendation algorithm. The proposed approach is domain-independent (demonstrated on data from movies, music, and business recommender systems), and is evaluated using several state-of-the-art machine learning methods, on different recommendation tasks, and using different evaluation metrics. The results show a unanimous improvement in the recommendation accuracy across tasks and domains. In addition, the evaluation provides a deeper analysis regarding the performance of the approach in special scenarios, including high sparsity and variability of ratings.

Towards lightweight convolutional neural networks for object detection

We propose model with larger spatial size of feature maps and evaluate it on object detection task. With the goal to choose the best feature extraction network for our model we compare several popular lightweight networks. After that we conduct a set of experiments with channels reduction algorithms in order to accelerate execution. Our vehicle detection models are accurate, fast and therefore suit for embedded visual applications. With only 1.5 GFLOPs our best model gives 95.13 AP on validation subset of challenging DETRAC dataset. The smallest of our models is the first to achieve real-time inference speed on CPU with reasonable accuracy drop to 91.72 AP.

Machine Learning, Deepest Learning: Statistical Data Assimilation Problems

We formulate a strong equivalence between machine learning, artificial intelligence methods and the formulation of statistical data assimilation as used widely in physical and biological sciences. The correspondence is that layer number in the artificial network setting is the analog of time in the data assimilation setting. Within the discussion of this equivalence we show that adding more layers (making the network deeper) is analogous to adding temporal resolution in a data assimilation framework. How one can find a candidate for the global minimum of the cost functions in the machine learning context using a method from data assimilation is discussed. Calculations on simple models from each side of the equivalence are reported. Also discussed is a framework in which the time or layer label is taken to be continuous, providing a differential equation, the Euler-Lagrange equation, which shows that the problem being solved is a two point boundary value problem familiar in the discussion of variational methods. The use of continuous layers is denoted ‘deepest learning’. These problems respect a symplectic symmetry in continuous time/layer phase space. Both Lagrangian versions and Hamiltonian versions of these problems are presented. Their well-studied implementation in a discrete time/layer, while respected the symplectic structure, is addressed. The Hamiltonian version provides a direct rationale for back propagation as a solution method for the canonical momentum.

Complex and Holographic Embeddings of Knowledge Graphs: A Comparison

Embeddings of knowledge graphs have received significant attention due to their excellent performance for tasks like link prediction and entity resolution. In this short paper, we are providing a comparison of two state-of-the-art knowledge graph embeddings for which their equivalence has recently been established, i.e., ComplEx and HolE [Nickel, Rosasco, and Poggio, 2016; Trouillon et al., 2016; Hayashi and Shimbo, 2017]. First, we briefly review both models and discuss how their scoring functions are equivalent. We then analyze the discrepancy of results reported in the original articles, and show experimentally that they are likely due to the use of different loss functions. In further experiments, we evaluate the ability of both models to embed symmetric and antisymmetric patterns. Finally, we discuss advantages and disadvantages of both models and under which conditions one would be preferable to the other.

Better bounds on optimal measurement and entanglement recovery, with applications to uncertainty and monogamy relations
Heavy-tailed fractional Pearson diffusions
Double Reweighted Estimators for the Parameters of the Multivariate t Distribution
Achievable Rates for Probabilistic Shaping
Estimating Large Precision Matrices via Modified Cholesky Decomposition
Data-driven discovery of Koopman eigenfunctions for control
Interpretable & Explorable Approximations of Black Box Models
UPSET and ANGRI : Breaking High Performance Image Classifiers
Shakespearizing Modern Language Using Copy-Enriched Sequence-to-Sequence Models
Connectivity Keeping Stars in 2-Connected Graphs
Unsupervised Submodular Rank Aggregation on Score-based Permutations
Polynomial bases: positivity and Schur multiplication
B tensors and tensor complementarity problems
CharManteau: Character Embedding Models For Portmanteau Creation
Buy-and-Hold Property for Fully Incomplete Markets when Super-replicating Markovian Claims
Biased Predecessor Search
Complexity Metric for Code-Mixed Social Media Text
Sentiment Identification in Code-Mixed Social Media Text
Dining Philosophers, Leader Election and Ring Size problems, in the quantum setting
A note on the impossibility of ‘fairness’
Major index over descent for pattern-avoiding permutations
A Survey of Recent Advances in CNN-based Single Image Crowd Counting and Density Estimation
Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
The Complexity of Human Computation: A Concrete Model with an Application to Passwords
The minimal measurement number problem in phase retrieval: a review of recent developments
The $\ell_\infty$ Perturbation of HOSVD and Low Rank Tensor Denoising
Model compression as constrained optimization, with application to neural nets. Part I: general framework
Per-Tone model for Common Mode sensor based alien noise cancellation for Downstream xDSL
Data-Driven Sparse Structure Selection for Deep Neural Networks
Mustafin varieties, moduli spaces and tropical geometry
Adversarial Representation Learning for Domain Adaptation
Like What You Like: Knowledge Distill via Neuron Selectivity Transfer
DarkRank: Accelerating Deep Metric Learning via Cross Sample Similarities Transfer
Copy-move Forgery Detection based on Convolutional Kernel Network
Firefighting on trees and Cayley graphs
Estimating the Number of Sources in Magnetoencephalography Using Spiked Population Eigenvalues
Exponential random graphs behave like mixtures of stochastic block models
Random Matching under Priorities: Stability and No Envy Concepts
A free boundary problem in biological selection models
Option Pricing in a Regime Switching Stochastic Volatility Model
R-Rec: A rule-based system for contextual suggestion using tag-description similarity
Learning Geometric Concepts with Nasty Noise
Exploration of object recognition from 3D point cloud
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Laplacian-Steered Neural Style Transfer
Regression approaches for Approximate Bayesian Computation
Synchronization of moving oscillators in three dimensional space
Multiple Range-Restricted Bidirectional Gated Recurrent Units with Attention for Relation Classification
The Weisfeiler-Leman algorithm and the diameter of Schreier graphs
Convergence rate in the rough donsker theorem
Enhancing synchronization in chaotic oscillators by induced heterogeneity
Learning-based Image Enhancement for Visual Odometry in Challenging HDR Environments
Path deviations outperform approximate stability in heterogeneous congestion games
Outage Probability of Power-based Non-Orthogonal Multiple Access (NOMA) on the Uplink of a 5G Cell
SADA: A General Framework to Support Robust Causation Discovery with Theoretical Guarantee
A Matern based multivariate Gaussian random process for a consistent model of the horizontal wind components and related variables
R-PHOC: Segmentation-Free Word Spotting using CNN
Weak uniqueness and density estimates for sdes with coefficients depending on some path-functionals
Sensitivity analysis using perturbed-law based indices for quantiles and application to an industrial case
Addendum to ‘Local Controllability of the Two-Link Magneto-Elastic Micro-Swimmer’
Dispersive shallow water wave modelling. Part II: Numerical simulation on a globally flat space
Fast Multi-frame Stereo Scene Flow with Motion Segmentation
Measuring heavy-tailedness of distributions
Learning to Design Games: Strategic Environments in Deep Reinforcement Learning
Particle rejuvenation of Rao-Blackwellized Sequential Monte Carlo smoothers for Conditionally Linear and Gaussian models
Benchmarking Denoising Algorithms with Real Photographs
Robust Multi-Image HDR Reconstruction for the Modulo Camera
The Influence of Feature Representation of Text on the Performance of Document Classification
Automated Experiment Design for Data-Efficient Verification of Parametric Markov Decision Processes
On principal curves with a length constraint
A dataset for Computer-Aided Detection of Pulmonary Embolism in CTA images
Asymptotics of the order statistics for a process with a regenerative structure
Shapley effects for sensitivity analysis with dependent inputs: comparisons with Sobol’ indices, numerical estimation and applications
Generative diffeomorphic atlas construction from brain and spinal cord MRI data
Consistent parameter estimation in general stochastic block models with overlaps
Resource Allocations for Secure Cognitive Satellite Terrestrial Networks
Bounding the number of common zeros of multivariate polynomials and their consecutive derivatives
Align and Copy: UZH at SIGMORPHON 2017 Shared Task for Morphological Reinflection
On the classification of $\mathbb{Z}_4$-codes
Improving Content-Invariance in Gated Autoencoders for 2D and 3D Object Rotation
Learning latent structure of large random graphs
Gini estimation under infinite variance
Employee turnover prediction and retention policies design: a case study
An Attention Mechanism for Answer Selection Using a Combined Global and Local View
Towards Recommender Systems for Police Photo Lineup
Full street simplified three player Kuhn poker
Development & Implementation of the Trigger for a Short-baseline Reactor Antineutrino Experiment (SoLid)
AlignGAN: Learning to Align Cross-Domain Images with Conditional Generative Adversarial Networks
Video Representation Learning and Latent Concept Mining for Large-scale Multi-label Video Classification
Partition algebras $\mathsf{P}_k(n)$ with $2k>n$ and the fundamental theorems of invariant theory for the symmetric group $\mathsf{S}_n$
Robustness Among Multiwinner Voting Rules
Model enumeration in propositional circumscription via unsatisfiable core analysis
Quasilinear SPDEs in divergence-form
Determining sentiment in citation text and analyzing its impact on the proposed ranking index
SHADHO: Massively Scalable Hardware-Aware Distributed Hyperparameter Optimization
Theory of the superposition principle for randomized connectionist representations in neural networks
Spectral Modes of Network Dynamics Reveal Increased Informational Complexity Near Criticality
Calibrations for minimal networks in a covering space setting
The Complex Negotiation Dialogue Game
Determining the Dimension of the Improper Signal Subspace in Complex-Valued Data
Homogeneous Wavelets and Framelets with the Refinable Structure
Variational discretization of a control-constrained parabolic bang-bang optimal control problem
Label Organized Memory Augmented Neural Network
On Directed Feedback Vertex Set parameterized by treewidth
Machine Learning Tests for Effects on Multiple Outcomes
Convolutional 2D Knowledge Graph Embeddings
Like trainer, like bot? Inheritance of bias in algorithmic content moderation
Cerebellar-Inspired Learning Rule for Gain Adaptation of Feedback Controllers
Single-sink Fractionally Subadditive Network Design
Creative Robot Dance with Variational Encoder
A Benamou–Brenier formulation of martingale optimal transport
Hindsight Experience Replay
Group Strategyproof Pareto-Stable Marriage with Indifferences via the Generalized Assignment Game