Ayoub Foussoul

Turning neural-network predictions into decisions often requires downstream optimization over the network’s inputs. Local search can offer a particularly efficient approach to such optimization when the feasible set is discrete and equipped with a simple neighborhood structure. However, theoretical understanding of local-search performance over the input of trained neural-network landscapes remains limited. In this paper, we study how training shapes the discrete input landscapes of multilayer perceptrons over cardinality-constrained binary sets, equipped with the natural exchange neighborhood. In particular, we study the smoothness of such landscapes in the infinite-width neural tangent kernel (NTK) regime (Lee et al., 2020) through their autocorrelation (Weinberger, 1990), a notion particularly relevant to local-search performance. Under natural assumptions, we show that training produces smooth interpolations of the training labels, with expected autocorrelation approaching one as the input dimension grows. We also show that filtering out components of the trained network’s output associated with smaller eigenvalues of the random-walk matrix on the exchange neighborhood can increase autocorrelation while changing the output values little. Motivated by the latter result, we propose a Filtered Local Search (FLS) method and show that it improves average solution quality over ordinary local search both in controlled experiments close to our theoretical model and in applications with neural architectures and feasible sets beyond it.

Neural scaling laws are empirical relationships between the predictive performance of neural networks and the scale of training data, model capacity, or computation. They have been observed across multiple domains, including language modeling, computer vision, and speech recognition. Yet whether comparable scaling laws hold for prediction tasks in operations remains largely unexplored. We study neural scaling laws relating predictive loss to training-data size in customer choice prediction, a central problem in operations that underlies assortment planning, pricing, and product design. In particular, we train a neural network on an Expedia hotel-search interaction dataset to predict customer bookings across a range of training-set sizes. We establish a power-law relationship between prediction loss and training-set size, and provide an explicit functional form for this relationship. We then examine how this law changes when real choice data are supplemented with synthetic choice data generated by a large language model (LLM). We show that synthetic data improve prediction when real data are scarce, but their benefits shrink as real-data scale grows and can reverse when too much synthetic data is added. We provide an explicit joint scaling law that captures how predictive loss changes with the amount of real and synthetic choice data. Together, these laws can help firms anticipate the predictive returns to additional choice data and assess when and how much synthetic data are likely to improve prediction.

In the predict-then-optimize framework, historical data are used to train a model that predicts the outcome of a decision in a given context. Upon observing a new context, the trained model is optimized over the feasible decisions. When decisions are integer-valued, standard predictive models can lead to downstream optimization problems that are difficult to solve. We introduce Deep Flow Networks (DFNs), a new class of predictive models designed to combine strong predictive performance with efficient downstream integer optimization. DFNs are inspired by and generalize the minimum-cost flow value functions that map node imbalances to the optimal flow cost. We establish a universality result for DFNs and prove that trained DFNs satisfy a generalization of the classical M-convex exchange property (Murota, 2003), allowing us to characterize the complexity of optimizing them. Guided by these results, we develop a practical implementation of DFNs for learning from data. We test DFNs on a diverse collection of public datasets spanning revenue management, transportation, resource allocation, public services, and manufacturing, and find that their predictive performance is competitive with multi-layer perceptrons, while their downstream optimization problems are solved substantially faster. We also conduct an end-to-end contextual assortment optimization experiment and find that DFNs are fast to optimize and produce the highest-revenue assortments among the learned models.

We consider a fundamental generalization of the classical newsvendor problem where the seller needs to decide on the inventory of a product jointly for multiple locations on a metric as well as a fulfillment policy to satisfy the uncertain demand that arises sequentially over time after the inventory decisions have been made. To address the distributional ambiguity, we consider a distributionally robust setting where the decision-maker only knows the mean and variance of the demand, and the goal is to make inventory and fulfillment decisions to minimize the worst-case expected inventory and fulfillment cost. We design a near-optimal policy for the problem with theoretical guarantees on its performance. Our policy generalizes the classical solution of Scarf (1957), maintaining its simplicity and interpretability: it identifies a hierarchical set of clusters, assigns a “virtual” underage cost to each cluster, then makes sure that each cluster holds at least the inventory suggested by Scarf's solution if the cluster behaved as a single point with “virtual” underage cost. As demand arrives sequentially, our policy fulfills orders from nearby clusters, minimizing fulfilment costs, while balancing inventory consumption across the clusters to avoid depleting any single one. We show that the policy achieves a poly-logarithmic approximation. To the best of our knowledge, this is the first algorithm with provable performance guarantees. Furthermore, our numerical experiments show that the policy performs well in practice.

We consider the class of disjoint bilinear programs $\max \, \{ {\textbf{x}}^T{\textbf{y}} \mid {\textbf{x}} \in {\mathcal {X}}, \;{\textbf{y}} \in {\mathcal {Y}}\}$ where ${\mathcal {X}}$ and ${\mathcal {Y}}$ are packing polytopes. We present an $O\left(\frac{\log \log m_1}{\log m_1} \frac{\log \log m_2}{\log m_2}\right)$-approximation algorithm for this problem where $m_1$ and $m_2$ are the number of packing constraints in ${\mathcal {X}}$ and ${\mathcal {Y}}$ respectively. In particular, we show that there exists a near-optimal solution $(\tilde{{\textbf{x}}}, \tilde{{\textbf{y}}})$ such that $\tilde{{\textbf{x}}}$ and $\tilde{{\textbf{y}}}$ are “near-integral”. We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique. As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an $O\left(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L}\right)$-approximation where L is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an $O\left(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L}\right)$-approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance.

We introduce and study a two-stage stochastic stable matching problem between students and schools. A decision maker chooses a stable matching in a marriage instance; then, after some agents enter or leave the market following a probability distribution $\mathcal{D}$, chooses a stable matching in the new instance. The goal is, roughly speaking, to maximize the expected quality of the matchings across the two stages and minimize the expected students’ discontent for being downgraded to a less preferred school in the second-stage. We consider both the case when $\mathcal{D}$ is given explicitly and when it is accessed via a sampling oracle. In the former case, we give a polynomial time algorithm. In the latter case, we show that, unless P = NP, no algorithm can find the optimal value or the optimal solution of the problem in polynomial-time. On the positive side, we give a pseudopolynomial algorithm that computes a solution of arbitrarily small additive error. Our techniques include the use of a newly defined poset of stable pairs, which may be of independent interest.

We introduce and study Minimum Cut Representability, a framework to solve optimization and feasibility problems over stable matchings by representing them as minimum s-t cut problems on digraphs over rotations. We provide necessary and sufficient conditions on objective functions and feasibility sets for problems to be minimum cut representable. In particular, we define the concepts of first and second order differentials of a function over stable matchings and show that a problem is minimum cut representable if and only if, roughly speaking, the objective function can be expressed solely using these differentials, and the feasibility set is a sublattice of the stable matching lattice. To demonstrate the practical relevance of our framework, we study a range of real-world applications, including problems involving school choice with siblings and a two-stage stochastic stable matching problem. We show how our framework can be used to help solving these problems.

We study the classical load balancing problem in a fully dynamic setting where jobs both arrive and depart. Each job can only be assigned to a subset of machines and can be reassigned at any time step. The goal is to maintain a near-optimal maximum load at all time steps with a small total number of reassignments. We consider the setting where the degree of the jobs (number of machines they can be assigned to) is bounded. This is motivated by natural settings where jobs can only be locally assigned to a small number of machines (e.g., bike sharing [12], map-reduce settings [23]) and generalizes the classical EdgeOrientation problem. We give a constant competitive algorithm with amortized constant number of reassignments. We also consider the generalizations of our problem to arbitrary reassignment costs and arbitrary job sizes. The generalizations require different techniques and we give a different randomized algorithm for these.

In a recent work, Laforgue et al. introduce the model of last switch dependent (LSD) bandits, in an attempt to capture nonstationary phenomena induced by the interaction between the player and the environment. Examples include satiation, where consecutive plays of the same action lead to decreased performance, or deprivation, where the payoff of an action increases after an interval of inactivity. In this work, we take a step towards understanding the approximability of planning LSD bandits, namely, the (NP-hard) problem of computing an optimal arm-pulling strategy under complete knowledge of the model. In particular, we design the first efficient constant approximation algorithm for the problem and show that, under a natural monotonicity assumption on the payoffs, its approximation guarantee (almost) matches the state-of-the-art for the special and well-studied class of recharging bandits (also known as delay-dependent). In this attempt, we develop new tools and insights for this class of problems, including a novel higher-dimensional relaxation and the technique of mirroring the evolution of virtual states. We believe that these novel elements could potentially be used for approaching richer classes of action-induced nonstationary bandits (e.g., special instances of restless bandits). In the case where the model parameters are initially unknown, we develop an online learning adaptation of our algorithm for which we provide sublinear regret guarantees against its full-information counterpart.

In this paper, we study the MNL-Bandit problem in a non-stationary environment and present an algorithm with a worst-case expected regret of $\tilde{O}\left( \min \left\{ \sqrt{NTL}\;,\; N^{\frac{1}{3}}(\Delta_{\infty}^{K})^{\frac{1}{3}} T^{\frac{2}{3}} + \sqrt{NT}\right\}\right)$. Here $N$ is the number of arms, $L$ is the number of changes and $\Delta_{\infty}^{K}$ is a variation measure of the unknown parameters. Furthermore, we show matching lower bounds on the expected regret (up to logarithmic factors), implying that our algorithm is optimal. Our approach builds upon the epoch-based algorithm for stationary MNL-Bandit in Agrawal et al. 2016. However, non-stationarity poses several challenges and we introduce new techniques and ideas to address these. In particular, we give a tight characterization for the bias introduced in the estimators due to non stationarity and derive new concentration bounds.