arXiv research

This paper improves neural network compression by using robust low-rank approximations.

Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study the problem of maximizing a monotone submodular function in the streaming setting with a cardinality constraint $k$. We first propose Sieve-Streaming++, which requires just…

We consider the mean-variance hedging problem under partial information in the case where the flow of observable events does not contain the full information on the underlying asset price process. We introduce a martingale equation of a new type and characterize the optimal strategy in terms of the solution of this equ…

The space of positively curved hermitian metrics on a positive holomorphic line bundle over a compact complex manifold is an infinite-dimensional symmetric space. It is shown by Phong and Sturm that geodesics in this space can be uniformly approximated by geodesics in the finite dimensional spaces of Bergman metrics. W…

In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the…

A new method detects and displays pairwise dependence between variates.

The paper clusters hypergraphs to find diverse and experienced groups based on past experiences.

Randomly initialized ReLU networks of depth two can approximate smooth functions well.

Mean field inference in probabilistic models is generally a highly nonconvex problem. Existing optimization methods, e.g., coordinate ascent algorithms, can only generate local optima. In this work we propose provable mean filed methods for probabilistic log-submodular models and its posterior agreement (PA) with stron…

Poor approximators found in neural networks and random feature models.

The paper analyzes deep ReLU CNNs' approximation properties in 2D space.

In this paper, we propose a variable selection method for general nonparametric kernel-based estimation. The proposed method consists of two-stage estimation: (1) construct a consistent estimator of the target function, (2) approximate the estimator using a few variables by l1-type penalized estimation. We see that the…

Weight decay is one of the standard tricks in the neural network toolbox, but the reasons for its regularization effect are poorly understood, and recent results have cast doubt on the traditional interpretation in terms of $L_2$ regularization. Literal weight decay has been shown to outperform $L_2$ regularization for…

We consider the case of derivative-free algorithms for non-convex optimization, also known as zero order algorithms, that use only function evaluations rather than gradients. For a wide variety of gradient approximators based on finite differences, we establish asymptotic convergence to second order stationary points u…

We propose a general modeling and algorithmic framework for discrete structure recovery that can be applied to a wide range of problems. Under this framework, we are able to study the recovery of clustering labels, ranks of players, signs of regression coefficients, cyclic shifts, and even group elements from a unified…

A new cost-frugal HPO method controls training cost during optimization.

Paper proposes DG-ETC for online submodular maximization with stochastic bandit feedback.

Algorithm finds safe zones in policy Markov Decision Processes to limit trajectory escape.

We establish $L^{\infty}$ and $L^2$ error bounds for functions of many variables that are approximated by linear combinations of ReLU (rectified linear unit) and squared ReLU ridge functions with $\ell^1$ and $\ell^0$ controls on their inner and outer parameters. With the squared ReLU ridge function, we show th…

We quantify uncertainty in Oja's algorithm's leading eigenvector estimation.

In this paper, we consider an online optimization process, where the objective functions are not convex (nor concave) but instead belong to a broad class of continuous submodular functions. We first propose a variant of the Frank-Wolfe algorithm that has access to the full gradient of the objective functions. We show t…

Generative Adversarial Networks (GANs) have become a popular method to learn a probability model from data. In this paper, we aim to provide an understanding of some of the basic issues surrounding GANs including their formulation, generalization and stability on a simple benchmark where the data has a high-dimensional…

New methods optimize sums of bivariate functions on finite domains.

Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc., require extracting a small but representative summary from a massive dataset. Often, such problems can be posed as maximizing a submodular set function subject to a cardinality constr…

Sharp bounds on neural network approximation rates and widths.

Paper develops approximation and statistical theory for signature-based path regression.

Paper develops a new objective for hierarchical clustering in Euclidean space.

We consider the problem of group testing with sum observations and noiseless answers, in which we aim to locate multiple objects by querying the number of objects in each of a sequence of chosen sets. We study a probabilistic setting with entropy loss, in which we assume a joint Bayesian prior density on the locations …

Study analyzes broker's gain from trade in repeated context-based trading.

Quantifies polynomial approximation rates for smooth functions under various distributions.

Proves depth 2 neural networks can't approximate certain functions as well as depth 3 networks.

In this paper, we study fundamental problems of maximizing DR-submodular continuous functions that have real-world applications in the domain of machine learning, economics, operations research and communication systems. It captures a subclass of non-convex optimization that provides both theoretical and practical guar…

We consider the problem of function approximation by two-layer neural nets with random weights that are "nearly Gaussian" in the sense of Kullback-Leibler divergence. Our setting is the mean-field limit, where the finite population of neurons in the hidden layer is replaced by a continuous ensemble. We show that the pr…

In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edge is labeled positive or negative. The goal is to obtain a clustering of the vertices that minimizes disagreements -- the number of negative…

Improves clustering interpretability with decision trees.

The Graph Convolutional Network (GCN) model and its variants are powerful graph embedding tools for facilitating classification and clustering on graphs. However, a major challenge is to reduce the complexity of layered GCNs and make them parallelizable and scalable on very large graphs -- state-of the art techniques a…

Proposes a new method for two-dimensional data discretization.

Local Gaussian correlation struggles in tails but a new method improves it.

We develop an efficient algorithm for low-rank approximation with improved approximation guarantees.