arXiv research

Algorithm for exact partitioning of high-order models using convex tensor relaxation.

The paper develops mixed-integer formulations for neural networks using partitioning.

Improved neural network robustness certification through tighter convex relaxations.

Region-specific linear models are widely used in practical applications because of their non-linear but highly interpretable model representations. One of the key challenges in their use is non-convexity in simultaneous optimization of regions and region-specific models. This paper proposes novel convex region-specific…

Study on estimating Gaussian mean from coarse data, resolving identifiability and computational efficiency questions.

Exact partitioning of high-order planted models achieved through convex optimization.

We consider the problem of approximating partition functions for Ising models. We make use of recent tools in combinatorial optimization: the Sherali-Adams and Lasserre convex programming hierarchies, in combination with variational methods to get algorithms for calculating partition functions in these families. These …

Recently, there has been an increasing interest in designing distributed convex optimization algorithms under the setting where the data matrix is partitioned on features. Algorithms under this setting sometimes have many advantages over those under the setting where data is partitioned on samples, especially when the …

The paper extends localisation technique to multiple constraints in Euclidean spaces.

We study the stability of partitions in convex domains involving simultaneous coexistence of three phases, viz. triple junctions. We present a careful derivation of the formula for the second variation of area, written in a suitable form with particular attention to boundary and spine terms, and prove, in contrast to t…

Paper corrects GIRP algorithm to ensure isotonic models.

A new algorithm, Regular Tree Search, tackles non-convex simulation optimization problems.

Proposes SPFB method for optimizing partition functions in stochastic learning.

The Mondrian process represents an elegant and powerful approach for space partition modelling. However, as it restricts the partitions to be axis-aligned, its modelling flexibility is limited. In this work, we propose a self-consistent Binary Space Partitioning (BSP)-Tree process to generalize the Mondrian process. Th…

Bounds on the log partition function are important in a variety of contexts, including approximate inference, model fitting, decision theory, and large deviations analysis. We introduce a new class of upper bounds on the log partition function, based on convex combinations of distributions in the exponential domain, th…

Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulation is identified and a novel rearrangement algorithm is proposed, which we show is strictly decreas…

Paper presents an efficient algorithm for estimating Lipschitz functions from noisy data.

Study optimizes perimeter in convex domains with anisotropic constraints.

CDL index improves clustering validation for non-convex data.

In this paper, we study stability and instability problem for type-II partitioning problem. First, we make a complete classification of stable type-II stationary hypersurfaces in a ball in a space form as totally geodesic $n$-balls. Second, for general ambient spaces and convex domains, we give some topological restric…

Convex regression is a promising area for bridging statistical estimation and deterministic convex optimization. New piecewise linear convex regression methods are fast and scalable, but can have instability when used to approximate constraints or objective functions for optimization. Ensemble methods, like bagging, sm…

Efficient algorithms learn from coarse labels instead of fine grained ones.

Deep learning models generalize by extending decision boundaries outside the convex hull of training data.

In this paper, we consider unsupervised partitioning problems, such as clustering, image segmentation, video segmentation and other change-point detection problems. We focus on partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, which include mean-based change-point detect…

A new learning rule consistently reduces error over data samples.

Asynchronous federated learning for vertically partitioned data improves efficiency and privacy.

We study the stability of partitions involving two or more phases in convex domains under the assumption of at most two-phase contact, thus excluding in particular triple junctions. We present a detailed derivation of the second variation formula with particular attention to the boundary terms, and then study the sign …

Proposes a partitioned least squares model for feature grouping.

When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then perform several epochs of training on the re-shuffled (either locally or globally) data. The above …

A new framework for verifying robustness of neural networks.

We learn the structure of a Markov Network between two groups of random variables from joint observations. Since modelling and learning the full MN structure may be hard, learning the links between two groups directly may be a preferable option. We introduce a novel concept called the \emph{partitioned ratio} whose fac…

Quantum algorithm speeds up Gibbs partition function estimation.

For a given $1$-Lipschitz map $u\colon\mathbb{R}^n\to\mathbb{R}^m$ we define a partition, up to a set of Lebesgue measure zero, of $\mathbb{R}^n$ into maximal closed convex sets such that restriction of $u$ is an isometry on these sets. We consider a disintegration, with respect to this partition, of a log-concave meas…

Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi armed bandit sett…

We develop a variant of multiclass logistic regression that is significantly more robust to noise. The algorithm has one weight vector per class and the surrogate loss is a function of the linear activations (one per class). The surrogate loss of an example with linear activation vector $\mathbf{a}$ and class $c$ has t…

We study the problem of estimating a temporally varying coefficient and varying structure (VCVS) graphical model underlying nonstationary time series data, such as social states of interacting individuals or microarray expression profiles of gene networks, as opposed to i.i.d. data from an invariant model widely consid…

Paper improves neural network robustness analysis for safety-critical systems.

New method for distributed online learning with communication constraints reduces joint regret.

The dual Minkowski problem for even data asks what are the necessary and sufficient conditions on an even prescribed measure on the unit sphere for it to be the $q$-th dual curvature measure of an origin-symmetric convex body in $\mathbb{R}^n$. A full solution to this is given when $1 < q < n$. The necessary and suffic…

In this paper we present a new approach for tightening upper bounds on the partition function. Our upper bounds are based on fractional covering bounds on the entropy function, and result in a concave program to compute these bounds and a convex program to tighten them. To solve these programs effectively for general r…

The paper tackles MAP inference over non-convex constraints in safety-critical settings.

We present the extention and application of a new unsupervised statistical learning technique--the Partition Decoupling Method--to gene expression data. Because it has the ability to reveal non-linear and non-convex geometries present in the data, the PDM is an improvement over typical gene expression analysis algorith…

We introduce a new class of lower bounds on the log partition function of a Markov random field which makes use of a reversed Jensen's inequality. In particular, our method approximates the intractable distribution using a linear combination of spanning trees with negative weights. This technique is a lower-bound count…

Centroid-based methods including k-means and fuzzy c-means are known as effective and easy-to-implement approaches to clustering purposes in many applications. However, these algorithms cannot be directly applied to supervised tasks. This paper thus presents a generative model extending the centroid-based clustering ap…

Recent research has made significant progress on the problem of bounding log partition functions for exponential family graphical models. Such bounds have associated dual parameters that are often used as heuristic estimates of the marginal probabilities required in inference and learning. However these variational est…

This paper studies the lower bound complexity for the optimization problem whose objective function is the average of $n$ individual smooth convex functions. We consider the algorithm which gets access to gradient and proximal oracle for each individual component. For the strongly-convex case, we prove such an algorith…

Two new methods improve block-sparse signal recovery from noisy data.

The minimum message length principle is an information theoretic criterion that links data compression with statistical inference. This paper studies the strict minimum message length (SMML) estimator for $d$-dimensional exponential families with continuous sufficient statistics, for all $d \ge 1$. The partition of an …