MIP-GNN uses graph neural networks to predict variable biases for MIP solvers.
problem Improving combinatorial optimization through data-driven insights.
method Encoding MILP interactions as graphs, training a graph neural network to predict variable biases, and guiding the MIP solver with these predictions.
result Significant improvements in solving binary MILPs compared to default settings of state-of-the-art solvers.
Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. Asymmetric transformations before hashing were the key in solving MIPS which was otherwise hard. In the prior work, the authors use asymmetric transformations which convert th…
CAEL-MIPS learns embeddings to improve MIPS for better OPE in contextual bandits.
problem High variance in IPS weighting for OPE in large action spaces.
method Context-Action Embedding Learning (CAEL) for MIPS to minimize MSE.
result CAEL-MIPS outperforms baselines in MSE for OPE in contextual bandits.
New MIP methods improve training of integer-valued neural networks.
problem Training integer-valued neural networks with limited data and resources.
method Formulated new MIP models to optimize training efficiency and handle more data.
result Significantly outperforms previous state-of-the-art methods in accuracy, training time, and data usage.
We consider {\em Mixed Linear Regression (MLR)}, where training data have been generated from a mixture of distinct linear models (or clusters) and we seek to identify the corresponding coefficient vectors. We introduce a {\em Mixed Integer Programming (MIP)} formulation for MLR subject to regularization constraints on…
We present the first provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS). Our proposal is also the first hashing algorithm for searching with (un-normalized) inner product as the underlying similarity measure. Finding hashing schemes for MIPS was considered hard. We formally sho…
Proposes MIP, a privacy notion that requires less randomness than DP, leading to better utility.
problem Preserving privacy in machine learning models with sensitive data.
method Introduces membership inference privacy (MIP) as a new privacy notion and shows its relationship with differential privacy (DP).
result MIP can be achieved with less randomness than DP, resulting in better utility.
Amortizes MIPS by training neural networks to predict optimal keys.
problem Efficiently solving Maximum Inner Product Search for repeated queries.
method Regression-based SupportNet and KeyNet models trained on support functions.
result Significant improvement in IVF match rates for document embeddings.
Automates MIPs solution with semi-supervised graph neural networks.
problem Solving recurrent Mixed-Integer Programming (MIP) problems efficiently.
method Semi-supervised Graph Neural Networks (GNNs) for predicting variable values.
result GNNs can solve MIPs with unlabeled data and improve over other ML approaches.
New algorithms optimize neural networks with ReLU activations using sampling.
problem Optimizing trained neural networks with ReLU activations.
method Iterative algorithm and enhanced algorithm using sampling and neighborhood search.
result The methods reduce the initial MIP problem into smaller LP or MIP problems.
There has been substantial research on sub-linear time approximate algorithms for Maximum Inner Product Search (MIPS). To achieve fast query time, state-of-the-art techniques require significant preprocessing, which can be a burden when the number of subsequent queries is not sufficiently large to amortize the cost. Fu…
Proposes a new privacy notion for membership inference attacks on machine learning models.
problem Membership inference attacks on machine learning models.
method Introduces f-Membership Inference Privacy (f-MIP) and μ-Gaussian Membership Inference Privacy (μ-GMIP) to quantify and mitigate privacy risks. result Analyzes likelihood ratio-based attacks and derives μ-GMIP guarantees for stochastic gradient descent (SGD) models. Recently, locality sensitive hashing (LSH) was shown to be effective for MIPS and several algorithms including L2-ALSH, Sign-ALSH and Simple-LSH have been proposed. In this paper, we introduce the norm-range partition technique, which partitions the original dataset into sub-datasets containing items with similar 2-…
Efficient Maximum Inner Product Search (MIPS) is an important task that has a wide applicability in recommendation systems and classification with a large number of classes. Solutions based on locality-sensitive hashing (LSH) as well as tree-based solutions have been investigated in the recent literature, to perform ap…
We propose a mixed integer programming (MIP) model and iterative algorithms based on topological orders to solve optimization problems with acyclic constraints on a directed graph. The proposed MIP model has a significantly lower number of constraints compared to popular MIP models based on cycle elimination constraint…
New MIP formulations for neural network Lipschitz constant estimation.
problem Ensuring robustness of neural networks by calculating their Lipschitz constant.
method Reformulating the neural network Lipschitz estimation problem as a Quadratically Constrained MIP (MIQCQP) problem.
result Solutions of the MIQCQP formulations provide bounds on the Lipschitz constant, with conditions for exactness.
Proposes MDR estimator for unbiased OPE with large action spaces.
problem Severe bias and variance tradeoffs in OPE with large action spaces.
method Marginalized Doubly Robust (MDR) estimator, reducing variance and bias.
result MDR estimator is unbiased under weaker assumptions than MIPS.
New framework optimizes classification trees with logistic loss and ℓ1 regularization.
problem Improving interpretability and generalization of classification trees.
method Developed a generalized framework for CTs, incorporating logistic loss and ℓ1 regularization. result Optimal Logistic Tree model outperforms state-of-the-art MIP-based approaches in terms of interpretability and generalization.
We propose a faster and more accurate method for learning classification trees.
problem Learning optimal binary classification trees is challenging and slow.
method We introduce a stronger MIP formulation and Benders' decomposition method.
result Our method is 50 times faster and improves out-of-sample performance.
Optimizes risk assessment tools using mixed-integer programming.
problem Challenges in healthcare risk assessment due to label scarcity and asymmetric misclassification costs.
method Jointly optimizes scoring weights and category thresholds via mixed-integer programming (MIP).
result Prevents label-scarce category collapse and achieves more accurate risk categorization.
New MIP framework solves high-dimensional ℓ0ℓ2-regularized regression problems.
problem Exact computation of ℓ0ℓ2-regularized regression estimators is challenging for large p. method Specialized nonlinear branch-and-bound (BnB) framework with first-order optimization.
result Achieves speedups of at least 5000x compared to state-of-the-art exact methods.
The ability to integrate information in the brain is considered to be an essential property for cognition and consciousness. Integrated Information Theory (IIT) hypothesizes that the amount of integrated information (Φ) in the brain is related to the level of consciousness. IIT proposes that to quantify information i…
Neyshabur and Srebro proposed Simple-LSH, which is the state-of-the-art hashing method for maximum inner product search (MIPS) with performance guarantee. We found that the performance of Simple-LSH, in both theory and practice, suffers from long tails in the 2-norm distribution of real datasets. We propose Norm-rangin…
New MIP approach for efficient change-point detection.
problem Offline multiple change-point detection in data streams.
method Mixed-integer programming (MIP) for globally optimal PWL fitting.
result Provable tighter relaxations for segment assignment variables.
Quantum algorithm speeds up MIP solving by a near-quadratic factor.
problem Solving Mixed Integer Programs (MIPs) efficiently.
method Incremental-Quantum-Branch-and-Bound algorithm combining quantum speedup with classical search heuristics.
result Universal near-quadratic speedup over classical Branch-and-Bound algorithms.
New MIP algorithms improve sparse classifier learning times.
problem Sparse classifier learning at large scales.
method Developed exact and approximate MIP algorithms for ℓ0-regularized classification. result Significantly improved statistical performance compared to existing methods.
MIP framework improves urban flow prediction by adapting to distribution shifts.
problem Distribution shifts in urban flow data make prediction models unreliable.
method Memory-enhanced Invariant Prompt learning with learnable memory bank.
result MIP ensures robust predictions by focusing on invariant features.
A new decision tree induction method using MIP for faster optimization.
problem Optimizing decision tree split rules for better classification performance.
method Mixed-integer programming (MIP) for Gini reduction maximization, efficient search algorithm.
result bsnsing trees outperform other tree models in new case discrimination.
Regularized empirical risk minimization with constrained labels (in contrast to fixed labels) is a remarkably general abstraction of learning. For common loss and regularization functions, this optimization problem assumes the form of a mixed integer program (MIP) whose objective function is non-convex. In this form, t…
Machine learning predicts phase behavior in active matter suspensions.
problem Predicting phase behavior in active matter systems using machine learning.
method Used deep learning techniques, including fully connected networks and graph neural networks, to predict motility-induced phase separation (MIPS) in ABP suspensions.
result Strong agreement between machine learning predictions and MIPS binodal from simulations, suggesting machine learning as an effective method for phase behavior determination.
We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated …
Combines TSP and SC to solve real-world vaccine distribution.
problem Combining TSP and SC for efficient vaccine distribution.
method Mixed Integer Programming (MIP) and machine learning.
result Machine learning approach improves solution efficiency.
Value-based reinforcement learning (RL) methods like Q-learning have shown success in a variety of domains. One challenge in applying Q-learning to continuous-action RL problems, however, is the continuous action maximization (max-Q) required for optimal Bellman backup. In this work, we develop CAQL, a (class of) algor…
Mixed integer programming identifies critical neurons in neural networks.
problem Identifying neurons critical for network performance and generalization.
method Developed a mixed integer program (MIP) to assign importance scores to neurons, guiding pruning decisions.
result The method identifies multiple 'lucky' sub-networks resulting in optimized architectures that generalize across datasets.
Generalizes neural network verification by adding arbitrary cutting planes.
problem Handling general cutting plane constraints in neural network verification.
method Generalized bound propagation method (GCP-CROWN) that allows arbitrary cutting plane constraints.
result GCP-CROWN significantly improves neural network verification performance.
Memory networks are neural networks with an explicit memory component that can be both read and written to by the network. The memory is often addressed in a soft way using a softmax function, making end-to-end training with backpropagation possible. However, this is not computationally scalable for applications which …
Paper introduces DP methods for high-dimensional variable selection.
problem Sparse variable selection in high-dimensional learning.
method Pure differentially private estimators using Integer Programming.
result Achieves state-of-the-art empirical support recovery.
Transformers improve solving mixed-integer programs, especially CLSP.
problem Solving Capacitated Lot Sizing Problem (CLSP) with mixed-integer programming.
method Employing transformer models to predict binary variables in CLSP.
result Transformer model outperforms CPLEX and LSTM in solving CLSP.
New estimator reduces variance in off-policy evaluation for contextual bandits.
problem High variance in current OPE methods for contextual bandits.
method Marginal Density Ratio (MR) estimator focusing on marginal distribution shift.
result MR estimator reduces variance compared to IPW and DR methods.
Perhaps surprisingly, it is possible to predict how long an algorithm will take to run on a previously unseen input, using machine learning techniques to build a model of the algorithm's runtime as a function of problem-specific instance features. Such models have important applications to algorithm analysis, portfolio…
New algorithm solves complex variable selection problems in high dimensions.
problem Grouped variable selection in high-dimensional data.
method Optimal solutions for the ℓ0-regularized formulation using discrete optimization.
result Exact algorithms solve problems with 5 million features and 1000 observations in minutes to hours.
FairWASP optimizes training data to reduce disparities across subgroups.
problem Reducing disparities in model outputs across different subgroups in machine learning.
method A novel pre-processing approach that minimizes Wasserstein distance to the original dataset while satisfying demographic parity.
result Integer weights are optimal, allowing FairWASP to be understood as duplicating or eliminating samples.
Estimates sparse Gaussian graphical models using discrete optimization.
problem Learning a sparse graph from Gaussian graphical models.
method Proposes GraphL0BnB, an ℓ0-penalized MIP solved with a custom BnB framework. result Significant runtime and statistical performance improvements over existing methods.
CPP solves chance constrained optimization problems with a framework that combines samples and quantile lemma.
problem Chance constrained optimization problems with constraints on random variables.
method CPP framework using samples and quantile lemma to transform into deterministic problem.
result CPP provides a posteriori guarantees on constraint satisfaction and can handle different types of chance constraints.
We study a fundamental class of regression models called the second order linear model (SLM). The SLM extends the linear model to high order functional space and has attracted considerable research interest recently. Yet how to efficiently learn the SLM under full generality using nonconvex solver still remains an open…
Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such a…
Scalable model for slate recommendation learns reward probabilities.
problem Scalable personalized slate recommendation in large action spaces.
method Probabilistic Rank and Reward (PRR) model combining reward, interaction, and rank.
result PRR outperforms existing methods and is scalable to large action spaces.
Much combinatorial optimisation problems constitute a non-polynomial (NP) hard optimisation problem, i.e., they can not be solved in polynomial time. One such problem is finding the shortest route between two nodes on a graph. Meta-heuristic algorithms such as A∗ along with mixed-integer programming (MIP) methods …