Research

The AI/OR NRT program has an important research component, where PhD students perform research with their faculty mentors on basic and applied research that integrates AI and OR technologies in the context of challenge problems that are suggested by faculty members, students, and USC’s CAIS, METRANS, and CREATE centers. In the following, we provide examples of research topics that combine AI and OR in which students may engage as they join. 

Mechanism Design with AI for Large-Scale Agent Systems

Many large-scale OR systems (in e- commerce, ride-sharing, and e-markets) involve a central planner and a large group of agents, where the central planner designs a mechanism to incentivize the agents to behave in a desired way. However, the central planner may not a priori know the utility function (or preferences) of each agent. With such asym- metric information, adverse selection occurs, making the central planner unable to identify the appropriate contract for each agent. The central planner also faces the “curse of many agents” when computing the equilibrium strategies. An interesting AI/OR research topic is figuring out how to use AI-based methods to solve these challenges in information asymmetry and computational cost. For example, one could use inverse reinforcement learning (for utility recovery), mean-field approximation (for dimension reduction), and AI-based sequential questionnaire design (for population differentiation), predicated on recent develop- ments in multi-agent reinforcement learning and games under asymmetric information.

Generating Alternative Solutions in Constrained Discrete Optimization

Providing a single optimal solution is often insufficient for discrete constrained optimization problems, either because the optimization models cannot capture all aspects of the problem or because some constraints are somewhat soft. Examples are generating game levels that are playable but also interesting/aesthetically pleasing to the player and wildlife conservation planning where conservation decisions might have to trade off between species benefit, budget, and spatial compactness. An interesting AI/OR research topic is developing scalable approaches for generating alternative solutions from two novel perspectives: 1) user-defined: computing top-k solutions given criteria ranking (addressing shortcomings of genetic algorithms, ε-constrained methods, and multi-objective branch-and-bound); and 2) diversity: combining generative models, such as GANs and diffusion models, with differentiable constrained optimization layers to build end-to-end pipelines able to produce diverse feasible solutions.

Optimal Differential Privacy Optimization

By observing the price of electricity in smart grids, an adversary can infer power consumption patterns of the individual users. Finding efficient, easily implementable “private” algorithms that offer strong performance is key for this and many other applications. Differential privacy, developed in the ML community, provides a rigorous guarantee that, with high probability, an adversary cannot discover an individual’s data by observing the output of an algorithm. However, other than simple classes of problems, optimal differentially private optimization algorithms are not well understood. For example, it is not clear how public and private data can be combined to solve optimization algorithms and make optimal decisions. Only some recent works study simple classes of such problems (for example, convex smooth i.i.d. empirical risk minimization). An interesting AI/OR research topic is to study and develop private optimization algorithms for various classes of problems (such as integer, non-convex, multi-level, or non-smooth optimization problems).

OR Tools for AI Problems with Binary Decision Variables

Most AI learning models include logical decisions that can be naturally modeled with binary variables in the training problems: Which features to include in the model? Which data points are outliers? Which points should be clustered together? Unfortunately, the inclusion of binary variables substantially increases the difficulty of carrying out the training problems. In practice, these discrete considerations of AI models are either approximated with continuous functions (potentially leading to poor solutions) or tackled via off-the-shelf mixed-integer optimization soft- ware (often leading to prohibitive computational times). An interesting AI/OR research topic is figuring out how to use OR tools (specifically methods from mixed-integer optimization) to design better approaches to AI problems with binary decision variables. The results would include higher-quality continuous ap- proximations to the underlying discrete problems, better algorithms to solve the problems exactly, and a better understanding of the links between statistical techniques and discrete optimization, thus also leading to better teaching paradigms for courses at the AI/OR interface.

Improving Deep Learning Theory

Continuous-time stochastic processes, such as diffusion processes, are widely used in OR to model complex dynamical systems, such as queuing systems and financial markets. There is a recent surge in using stochastic processes to improve the analysis of deep-learning training algorithms or neural network architectures from a theoretical point of view, especially in the identification of proper asymptotic limits as the widths (or depths) of the neural networks tend to infinity or as the learning rate of the training algorithm tends to zero. This type of asymptotic analysis potentially leads to new classes of algorithms and architectures with theoretical foundations. An interesting AI/OR research topic is therefore training neural networks based on ideas in the theory of controlled stochastic processes, widely used for decision-making problems in OR. This could provide principled guidance to improve the stability and efficiency of deep-learning training algorithms.

Causal AI Inference for Decision-Making

OR tools from causal inference can address issues of AI models for effective and reliable decision-making and counterfactual reasoning, but there is often limited control over how the data is collected, which can lead to unobserved confounders and biases in the data. An interesting AI/OR research topic is developing methods that can provably handle unobserved confounders for causal models relevant to ML problems, such as non-linear models. One could, for example, build on tools from ML, such as the method of moments and tensor decomposition algorithms, to get provable guarantees by modeling the data using suitable non-linear structural equation models, showing that the models are identifiable from low-order moments, and subsequently learning the model using efficient tensor decomposition procedures.

Strengths and Weaknesses of Decision-Aware Learning

Traditional approaches to data-driven decision- making under uncertainty follow a two-step procedure: 1) use ML to fit a non-parametric model to the data and 2) solve an optimization problem replacing unknown quantities with predictions from the ML model. Step 1 is typically “blind” to the structure of the downstream optimization. By contrast, decision- aware or “end-to-end” learning tailors Step 1 to this downstream problem. However, despite a wealth of empirical evidence supporting its benefits, current theory suggests it should be worse than conventional approaches, at least in traditional large-sample settings. One possibility for reconciling this gap between theory and practice is that decision-aware learning is most useful in non- traditional data settings (small-data, covariate shift, or severe model misspecification) or for certain classes of optimization problems. An interesting AI/OR research topic is thus developing a better understanding of its strengths and weaknesses in order to identify where it is likely to have the highest impact.

OR Tools for Interpretable AI and ML under Distribution Shifts

Most AI and ML models are trained under the assumption that the historical data and deployment data come from the same distribution. This assumption fails to hold in many high-stakes settings (such as self-reported surveys, observational data, and population/location change), resulting in severe performance deterioration in deployment and in sys- tems susceptible to adversarial attacks. In these settings, interpretable models, which are simple and easy to understand and scrutinize, are needed. As preliminary results show, interesting AI/OR research topics are 1) using tools from OR and specifically Mixed-Integer Distributionally Robust Opti- mization to learn provably optimal interpretable decision rules and ML models that are guaranteed to have the best possible performance in view of realistic distribution shifts between training and testing and 2) developing ways to calibrate the sets of possible distributions (ambiguity sets) against which the models need to be immunized using a variety of information from domain experts.