Neural Information Processing Systems http://nips.cc/

Z that represents some transfer of mass between elements of w and v . The proof is the same for W . Proposition 2. Suppose that the target row and column representative distributions are the same, The the Kantorovich OT problem and whose rank is at most min(rank(Z), rank( W)) . Proof of proposition 2. From linear algebra, we have that Proof of proposition 3. We suppose that The optimal transport problem can be formulated and solved as the Earth Mover's Distance (EMD) We report the biclustering performance on the synthetic datasets in table 2. At least one of our models finds the perfect partition in all cases. The gene-expression matrices used are the Cumida Breast Cancer and Leukemia datasets. Their characteristics are shown in Table 3. Table 3: Characteristics of the gene expression datasets.

We prove that the corresponding information-theoretic universal rate-distortionperception function is operationally achievable in an approximate sense.

The method scales well with the number of points, and it can be used to find the global solution for large-scale problems with thousands of points.

We study the optimal design of additive mechanisms for vector-valued queries under $ε$-differential privacy (DP). Given only the sensitivity of a query and a norm-monotone cost function measuring utility loss, we ask which noise distribution minimizes expected cost among all additive $ε$-DP mechanisms. Using convex rearrangement theory, we show that this infinite-dimensional optimization problem admits a reduction to a one-dimensional compact and convex family of radially symmetric distributions whose extreme points are the staircase distributions. As a consequence, we prove that for any dimension, any norm, and any norm-monotone cost function, there exists an $ε$-DP staircase mechanism that is optimal among all additive mechanisms. This result resolves a conjecture of Geng, Kairouz, Oh, and Viswanath, and provides a geometric explanation for the emergence of staircase mechanisms as extremal solutions in differential privacy.

We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time, in the oracle model. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.