Ensemble-based approaches are very effective in various fields in raising the accuracy of its individual members, when some voting rule is applied for aggregating the individual decisions. In this paper, we investigate how to find and characterize the ensembles having the highest accuracy if the total cost of the ensemble members is bounded. This question leads to Knapsack problem with non-linear and non-separable objective function in binary and multiclass classification if the majority voting is chosen for the aggregation. As the conventional solving methods cannot be applied for this task, a novel stochastic approach was introduced in the binary case where the energy function is discussed as the joint probability function of the member accuracy. We show some theoretical results with respect to the expected ensemble accuracy and its variance in the multiclass classification problem which can help us to solve the Knapsack problem.

Many practical problems involve the recovery of a binary matrix from partial information, which makes the binary matrix completion (BMC) technique received increasing attention in machine learning. In particular, we consider a special case of BMC problem, in which only a subset of positive elements can be observed. In recent years, convex regularization based methods are the mainstream approaches for this task. However, the applications of nonconvex surrogates in standard matrix completion have demonstrated better empirical performance. Accordingly, we propose a novel BMC model with nonconvex regularizers and provide the recovery guarantee for the model. Furthermore, for solving the resultant nonconvex optimization problem, we improve the popular proximal algorithm with acceleration strategies. It can be guaranteed that the convergence rate of the algorithm is in the order of ${1/T}$, where $T$ is the number of iterations. Extensive experiments conducted on both synthetic and real-world data sets demonstrate the superiority of the proposed approach over other competing methods.

The use of distances based on optimal transportation has recently shown promise for discrimination of power spectra. In particular, spectral estimation methods based on l1 regularization as well as covariance based methods can be shown to be robust with respect to such distances. These transportation distances provide a geometric framework where geodesics corresponds to smooth transition of spectral mass, and have been useful for tracking. In this paper, we investigate the use of these distances for automatic target recognition. We study the use of the Monge-Kantorovich distance compared to the standard l2 distance for classifying civilian vehicles based on SAR images. We use a version of the Monge-Kantorovich distance that applies also for the case where the spectra may have different total mass, and we formulate the optimization problem as a minimum flow problem that can be computed using efficient algorithms.

This paper describes a problem arising in sea exploration, where the aim is to schedule the expedition of a ship for collecting information about the resources on the seafloor. The aim is to collect data by probing on a set of carefully chosen locations, so that the information available is optimally enriched. This problem has similarities with the orienteering problem, where the aim is to plan a time-limited trip for visiting a set of vertices, collecting a prize at each of them, in such a way that the total value collected is maximum. In our problem, the score at each vertex is associated with an estimation of the level of the resource on the given surface, which is done by regression using Gaussian processes. Hence, there is a correlation among scores on the selected vertices; this is a first difference with respect to the standard orienteering problem. The second difference is the location of each vertex, which in our problem is a freely chosen point on a given surface.

We consider the densest $k$-subgraph problem, which seeks to identify the $k$-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum clique problem. We propose a new convex relaxation for the densest $k$-subgraph problem, based on a nuclear norm relaxation of a low-rank plus sparse decomposition of the adjacency matrices of $k$-node subgraphs to partially address this intractability. We establish that the densest $k$-subgraph can be recovered with high probability from the optimal solution of this convex relaxation if the input graph is randomly sampled from a distribution of random graphs constructed to contain an especially dense $k$-node subgraph with high probability. Specifically, the relaxation is exact when the edges of the input graph are added independently at random, with edges within a particular $k$-node subgraph added with higher probability than other edges in the graph. We provide a sufficient condition on the size of this subgraph $k$ and the expected density under which the optimal solution of the proposed relaxation recovers this $k$-node subgraph with high probability. Further, we propose a first-order method for solving this relaxation based on the alternating direction method of multipliers, and empirically confirm our predicted recovery thresholds using simulations involving randomly generated graphs, as well as graphs drawn from social and collaborative networks.

We introduce an asymmetric distance in the space of learning tasks, and a framework to compute their complexity. These concepts are foundational to the practice of transfer learning, ubiquitous in Deep Learning, whereby a parametric model is pre-trained for a task, and then used for another after fine-tuning. The framework we develop is intrinsically non-asymptotic, capturing the finite nature of the training dataset, yet it allows distinguishing learning from memorization. It encompasses, as special cases, classical notions from Kolmogorov complexity, Shannon, and Fisher Information. However, unlike some of those frameworks, it can be applied easily to large-scale models and real-world datasets. It is the first framework to explicitly account for the optimization scheme, which plays a crucial role in Deep Learning, in measuring complexity and information.

A framework previously introduced in [3] for solving a sequence of stochastic optimization problems with bounded changes in the minimizers is extended and applied to machine learning problems such as regression and classification. The stochastic optimization problems arising in these machine learning problems is solved using algorithms such as stochastic gradient descent (SGD). A method based on estimates of the change in the minimizers and properties of the optimization algorithm is introduced for adaptively selecting the number of samples at each time step to ensure that the excess risk, i.e., the expected gap between the loss achieved by the approximate minimizer produced by the optimization algorithm and the exact minimizer, does not exceed a target level. A bound is developed to show that the estimate of the change in the minimizers is non-trivial provided that the excess risk is small enough. Extensions relevant to the machine learning setting are considered, including a cost-based approach to select the number of samples with a cost budget over a fixed horizon, and an approach to applying cross-validation for model selection. Finally, experiments with synthetic and real data are used to validate the algorithms.

This paper reviews recent advances in the field of optimization under uncertainty via a modern data lens, highlights key research challenges and promise of data-driven optimization that organically integrates machine learning and mathematical programming for decision-making under uncertainty, and identifies potential research opportunities. A brief review of classical mathematical programming techniques for hedging against uncertainty is first presented, along with their wide spectrum of applications in Process Systems Engineering. A comprehensive review and classification of the relevant publications on data-driven distributionally robust optimization, data-driven chance constrained program, data-driven robust optimization, and data-driven scenario-based optimization is then presented. This paper also identifies fertile avenues for future research that focuses on a closed-loop data-driven optimization framework, which allows the feedback from mathematical programming to machine learning, as well as scenario-based optimization leveraging the power of deep learning techniques. Perspectives on online learning-based data-driven multistage optimization with a learning-while-optimizing scheme is presented.

We propose a new topic modeling procedure that takes advantage of the fact that the There are many extensions of LDA, including a nonparametric Latent Dirichlet Allocation (LDA) log likelihood extension based on the Dirichlet process function is asymptotically equivalent called Hierarchical Dirichlet Process (Teh et al., to the logarithm of the volume of the topic 2005), a correlated topic extension based on the logistic simplex. This allows topic modeling to be normal prior on the topic proportions (Lafferty reformulated as finding the probability simplex and Blei, 2006), and a time-varying topic modeling that minimizes its volume and encloses extension (Blei and Lafferty, 2006). There are the documents that are represented as distributions two main approaches for estimation of the parameters over words. A convex relaxation of probabilistic topic models: the variational of the minimum volume topic model optimization approximation popularized by Blei et al. (2003) and is proposed, and it is shown that the sampling based approach studied by Pritchard the relaxed problem has the same global et al. (2000).

As algorithms are increasingly used to make important decisions pertaining to individuals, algorithmic discrimination is becoming a prominent concern. The seminal work of Dwork et al. [ITCS 2012] introduced the notion of individual fairness (IF): given a task-specific similarity metric, every pair of similar individuals should receive similar outcomes. In this work, we study fairness when individuals have diverse preferences over the possible outcomes. We show that in such settings, individual fairness can be too restrictive: requiring individual fairness can lead to less-preferred outcomes for the very individuals that IF aims to protect (e.g. a protected minority group). We introduce and study a new notion of preference-informed individual fairness (PIIF), a relaxation of individual fairness that allows for outcomes that deviate from IF, provided the deviations are in line with individuals' preferences. We show that PIIF can allow for solutions that are considerably more beneficial to individuals than the best IF solution. We further show how to efficiently optimize any convex objective over the outcomes subject to PIIF, for a rich class of individual preferences. Motivated by fairness concerns in targeted advertising, we apply this new fairness notion to the multiple-task setting introduced by Dwork and Ilvento [ITCS 2019]. We show that, in this setting too, PIIF can allow for considerably more beneficial solutions, and we extend our efficient optimization algorithm to this setting.