#  SurCo: Learning Linear SURrogates
for COmbinatorial Nonlinear Optimization Problems

Aaron Ferber  Taoan Huang  Daochen Zha  Martin Schubert  Benoit Steiner
Bistra Dilkina  Yuandong Tian

###### Abstract

Optimization problems with nonlinear cost functions and combinatorial
constraints appear in many real-world applications but remain challenging to
solve efficiently compared to their linear counterparts. To bridge this gap,
we propose SurCo that learns linear $\underline{\text{Sur}}$rogate costs which
can be used in existing $\underline{\text{Co}}$mbinatorial solvers to output
good solutions to the original nonlinear combinatorial optimization problem.
The surrogate costs are learned end-to-end with nonlinear loss by
differentiating through the linear surrogate solver, combining the flexibility
of gradient-based methods with the structure of linear combinatorial
optimization. We propose three SurCo variants: $\texttt{SurCo}-\texttt{zero}$
for individual nonlinear problems, $\texttt{SurCo}-\texttt{prior}$ for problem
distributions, and $\texttt{SurCo}-\texttt{hybrid}$ to combine both
distribution and problem-specific information. We give theoretical intuition
motivating SurCo, and evaluate it empirically. Experiments show that SurCo
finds better solutions faster than state-of-the-art and domain expert
approaches in real-world optimization problems such as embedding table
sharding, inverse photonic design, and nonlinear route planning.

Machine Learning, Combinatorial Optimization, Nonlinear Optimization

Figure 1: Overview of our proposed framework SurCo.

##  1 Introduction

Combinatorial optimization problems with linear objective functions such as
mixed integer linear programming (MILP) (Wolsey, 2007), and occasionally
linear programming (LP) (Chvatal et al., 1983), have been extensively studied
in operations research (OR). The resulting high-performance solvers like
Gurobi (Gurobi Optimization, LLC, 2022) can solve industrial-scale
optimization problems with tens of thousands of variables in a few minutes.

However, even with perfect solvers, one issue remains: the cost functions
$f({\bm{x}})$ in many practical problems are _nonlinear_ , and the highly-
optimized solvers mainly handle linear or convex formulations while real-world
problems have less constrained objectives. For example, in embedding table
sharding (Zha et al., 2022a) one needs to distribute embedding tables to
multiple GPUs for the deployment of recommendation systems. Due to the
batching behaviors within a single GPU and communication cost among different
GPUs, the overall latency (cost function) in this application depends on
interactions of multiple tables and thus can be highly nonlinear (Zha et al.,
2022a).

To obtain useful solutions to real-world problems, one may choose to directly
optimize the nonlinear cost, which can be the black-box output of a simulator
(Gosavi et al., 2015; Ye et al., 2019), or the output of a cost estimator
learned by machine learning techniques (e.g., deep models) from offline data
(Steiner et al., 2021; Koziel et al., 2021; Wang et al., 2021b; Cozad et al.,
2014). However, many of these direct optimization approaches either rely on
human-defined heuristics (e.g., greedy (Korte & Hausmann, 1978; Reingold &
Tarjan, 1981; Wolsey, 1982), local improvement (Voß et al., 2012; Li et al.,
2021)), or resort to general nonlinear optimization techniques like gradient
descent (Ruder, 2016), reinforcement learning (Mazyavkina et al., 2021), or
evolutionary algorithms (Simon, 2013). While these approaches can work in
certain settings, they may lead to a slow optimization process, in particular
when the cost function is expensive to evaluate, and they often ignore the
combinatorial nature of most real-world applications.

In this work, we propose a systematic framework _SurCo_ that leverages
existing efficient combinatorial solvers to find solutions to nonlinear
combinatorial optimization problems arising in real-world scenarios. When only
one nonlinear _differentiable_ cost $f({\bm{x}})$ needs to be minimized, we
propose SurCo-zero that optimizes a _linear surrogate_ cost $\hat{\bm{c}}$ so
that the _surrogate optimizer_ (SO)
$\min_{{\bm{x}}\in\Omega}\hat{\bm{c}}^{\top}{\bm{x}}$ outputs a solution that
is expected to be optimal w.r.t. the _original_ nonlinear cost $f({\bm{x}})$.
Due to its linear nature, SO can be solved efficiently with existing solvers,
and the surrogate cost $\hat{\bm{c}}$ can be optimized in an end-to-end manner
by back-propagating _through_ the solver via methods proposed in previous work
(Pogančić et al., 2019; Niepert et al., 2021; Berthet et al., 2020).

Thus, SurCo is a general-purpose method for solving combinatorial nonlinear
optimization. Off-the-shelf nonlinear optimizers are often not directly
applicable to these problem domains and often require domain-specific solution
methodologies to give high-quality solutions in a reasonable amount of time,
and solution prediction methods fail to give combinatorially feasible
solutions without problem-specific intervention. Here, learning a linear
surrogate problem ensures that the surrogate solver is practically efficient,
yields gradient information for offline training, and generates solutions that
are combinatorially feasible.

When solving a family of nonlinear differentiable functions
$f({\bm{x}};{\bm{y}})$ parameterized by instance description ${\bm{y}}$, the
surrogate _coefficients_ $\hat{\bm{c}}({\bm{y}};\bm{\theta})$ are learned on a
set of optimization instances (called the training set $\\{{\bm{y}}_{i}\\}$),
by optimizing the parameters $\bm{\theta}$. For an unseen held-out instance
${\bm{y}}^{\prime}$, we propose SurCo-prior that directly optimizes linear SO:
$\hat{{\bm{x}}}^{*}({\bm{y}}^{\prime}):=\arg\min_{{\bm{x}}\in\Omega({\bm{y}}^{\prime})}\hat{\bm{c}}^{\top}({\bm{y}}^{\prime};\bm{\theta}){\bm{x}}$
to get the solution, avoiding optimizing the cost
$f({\bm{x}};{\bm{y}}^{\prime})$ from scratch. Based on the solution predicted
by SurCo-prior, we also propose SurCo-hybrid that fine-tunes the surrogate
costs $\hat{\bm{c}}$ with SurCo-zero to leverage both domain knowledge
synthesized offline and information about the specific instance. We provide a
comprehensive description of SurCo in Section 3.

We evaluate SurCo in three settings: embedding table sharding (Zha et al.,
2022a), photonic inverse design (Schubert et al., 2022), and nonlinear route
planning (Fan et al., 2005). In the on-the-fly setting, SurCo-zero achieves
higher quality solutions in comparable or less runtime, thanks to the help of
an efficient combinatorial solver. in SurCo-prior, our method obtains better
solutions in held-out problems compared to other methods that require training
(e.g., reinforcement learning).

We compare SurCo at a high level with related work integrating learning and
optimization at the end of our paper. We additionally present theoretical
intuition that helps motivate why training a model to predict surrogate linear
coefficients may exhibit better sample complexity than previous approaches
that directly predict the optimal solution (Li et al., 2018; Ban & Rudin,
2019).

Symbol | Description
---|---
${\bm{y}}$ | Parametric description of a specific instance.
${\bm{x}}$ | A solution to an instance.
$f({\bm{x}};{\bm{y}})$ |  The nonlinear objective (w.r.t ${\bm{x}}$) for an instance ${\bm{y}}$.
$\Omega({\bm{y}})$ |  The feasible region of an instance ${\bm{y}}$.
$\hat{\bm{x}}^{*}({\bm{y}})$ |  The optimal SO solution to an instance ${\bm{y}}$.
${\bm{c}}({\bm{y}})$ |  The surrogate coefficients for instance ${\bm{y}}$.
Table 1: Notations used in this work.

##  2 Problem Specification

Our goal is to solve the following nonlinear optimization problem describe by
${\bm{y}}$:

$\small\min_{\bm{x}}f({\bm{x}};{\bm{y}})\quad\quad\mathrm{s.t.}\quad{\bm{x}}\in\Omega{({\bm{y}})}$
(1)

where ${\bm{x}}\in\mathbb{R}^{n}$ are the $n$ variables to be optimized,
$f({\bm{x}};{\bm{y}})$ is the nonlinear differentiable cost function to be
minimized, $\Omega{({\bm{y}})}$ is the feasible region, typically specified by
linear (in)equalities and integer constraints, and ${\bm{y}}\in Y$ are the
problem instance parameters drawn from a distribution $\mathcal{D}{}$ over
$Y$. For example, in the traveling salesman problem, ${\bm{y}}$ can be the
distance matrix among cities.

Differentiable cost function. The nonlinear cost function
$f({\bm{x}};{\bm{y}})$ can either be given analytically, or the result of a
simulator made differentiable via finite differencing (e.g., JAX (Bradbury et
al., 2018)). If the cost function $f({\bm{x}};{\bm{y}})$ is not differentiable
as in one of our experimental settings, we can use a cost model that is
learned from an offline dataset, often generated via sampling multiple
feasible solutions within $\Omega({\bm{y}})$, and recording their costs. In
this work, we assume the following property of $f({\bm{x}};{\bm{y}})$:

######  Assumption 2.1 (Differentiable cost function).

During optimization, the cost function $f({\bm{x}};{\bm{y}})$ and its partial
derivative $\partial f/\partial{\bm{x}}$ are accessible.

Learning a good nonlinear cost model $f$ is non-trivial for practical
applications (e.g., AlphaFold (Jumper et al., 2021), Density Functional Theory
(Nagai et al., 2020), cost model for embedding tables (Zha et al., 2022a)) and
is beyond the scope of this work.

Evaluation Metric. We mainly focus on two aspects: the solution quality
evaluated by $f(\hat{\bm{x}};{\bm{y}})$, and the number of queries of $f$
during optimization to achieve the solution $\hat{\bm{x}}$. For both, smaller
measurements are favorable, i.e., fewer query of $f$ to get solutions closer
to global optimum.

When $f({\bm{x}};{\bm{y}})$ is linear w.r.t ${\bm{x}}$, and the feasible
region $\Omega({\bm{y}})$ can be encoded using mixed integer programs or other
mathematical programs, the problem can be solved efficiently using existing
scalable optimization solvers. When $f({\bm{x}};{\bm{y}})$ is nonlinear, we
propose SurCo that learns a surrogate linear objective function, which allow
us to leverage these existing scalable optimization solvers, and which results
in a solution that has high quality with respect to the original hard-to-
encode objective function $f({\bm{x}};{\bm{y}})$.

Methods | Applicable to | Objective can be | Training Set | Generalize to | Built-in handling of
---|---|---|---|---|---
nonlinear objective | free form | unseen instances | combinatorial constraints
Gradient Descent | Yes | Yes | N/A | No | No
Evolutionary Algorithm | Yes | Yes | N/A | No | No
Nonlinear combinatorial solvers | Yes | No | N/A | No | Yes
Learning direct mapping | Yes | Yes | $\\{{\bm{y}}_{i},{\bm{x}}^{*}_{i}\\}$ | Yes | No
Predict-then-optimize | Limited | No | $\\{{\bm{y}}_{i},{\bm{x}}^{*}_{i}\\}$ | Yes | Yes
SurCo (proposed) | Yes | Yes | $\\{{\bm{y}}_{i}\\}$ | Yes | Yes
Table 2: Conceptual comparison of optimizers (both traditional and ML-guided).
Our approach (SurCo) can handle nonlinear objective without a predefined
analytical form, does not require pre-computed optimal solutions in its
training set, can handle combinatorial constraints (via commercial solvers it
incorporates), and can generalize to unseen instances.

##  3 SurCo: Learning Linear Surrogates

###  3.1 SurCo-zero: on-the-fly optimization

We start from the simplest case in which we focus on a single instance with
$f({\bm{x}})=f({\bm{x}};{\bm{y}})$ and $\Omega=\Omega({\bm{y}})$. SurCo-zero
aims to optimize the following objective:

$\small\text{({SurCo}{}-{zero})}:\quad\min_{{\bm{c}}}\mathcal{L}_{\texttt{zero}}({\bm{c}}):=f({\bm{g}}_{\Omega}({\bm{c}}))$
(2)

where the surrogate optimizer
${\bm{g}}_{\Omega}:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ is the output of
certain combinatorial solvers with linear cost weight
${\bm{c}}\in\mathbb{R}^{n}$ and feasible region
$\Omega\subseteq\mathbb{R}^{n}$. For example, ${\bm{g}}_{\Omega}$ can be the
following:

$\small{\bm{g}}_{\Omega}({\bm{c}}):=\arg\min_{\bm{x}}{\bm{c}}^{\top}{\bm{x}}\quad\mathrm{s.t.}\
\ {\bm{x}}\in\Omega:=\\{A{\bm{x}}\leq{\bm{b}},{\bm{x}}\in\mathbb{Z}^{n}\\}$
(3)

which is the output of a MILP solver. Thanks to previous works (Ferber et al.,
2020; Pogančić et al., 2019), we can efficiently compute the partial
derivative $\partial{\bm{g}}_{\Omega}({\bm{c}})/\partial{\bm{c}}$.
Intuitively, this means that ${\bm{g}}_{\Omega}({\bm{c}})$ can be
_backpropagated_ through. Since $f$ is also differentiable with respect to the
solution it is evaluating, we thus can optimize Eqn. 2 in an end-to-end manner
using any gradient-based optimizer:

$\small{\bm{c}}(t+1)={\bm{c}}(t)-\alpha\frac{\partial{\bm{g}}_{\Omega}}{\partial{\bm{c}}}\frac{\partial
f}{\partial{\bm{x}}},$ (4)

where $\alpha$ is the learning rate. The procedure starts from a randomly
initialized ${\bm{c}}(0)$ and converges at a local optimal solution of
${\bm{c}}$. While Eqn. 2 is still nonlinear optimization and there is no
guarantee about the quality of the final solution ${\bm{c}}$, we argue that
optimizing Eqn. 2 is better than optimizing the original nonlinear cost
$\min_{{\bm{x}}\in\Omega}f({\bm{x}})$. Furthermore, while we cannot guarantee
optimality, we guarantee feasibility by leveraging a linear combinatorial
solver.

Intuitively, instead of optimizing directly over the solution space
${\bm{x}}$, we optimize over the space of surrogate costs ${\bm{c}}$, and
delegate the combinatorial feasibility requirements of the nonlinear problem
to SoTA combinatorial solvers. Compared to naive approaches that directly
optimize $f({\bm{x}})$ via general optimization techniques, our method readily
handles complex constraints of the feasible regions, and thus makes the
optimization procedure easier. Furthermore, it also helps escape from local
minima, thanks to the embedded search component of existing combinatorial
solvers (e.g., branch-and-bound (Land & Doig, 2010) in MILP solvers). As we
see in the experiments, this is particularly important when the problem
becomes large-scale with more local optima. This approach works well when we
are optimizing individual instances and may not have access to offline
training data or the training time is cost-prohibitive.

Limitation. Note that due to linear surrogate, our approach will always return
a vertex in the feasible region, while the solution to the original nonlinear
objective may be in the interior. We leave this limitation for future work. In
many real-world settings, such as in the three domains we tested, the
solutions are indeed on the vertices of feasible regions.

###  3.2 SurCo-prior: offline surrogate training

We now consider a more general case where we have $N$ optimization instances,
each parameterized by an instance description ${\bm{y}}_{i}$, $i=1\ldots N$,
and we want to find their solutions to a _collection_ of nonlinear loss
functions $f({\bm{x}};{\bm{y}}_{i})$ simultaneously. Here we write
$\mathcal{D}_{\mathrm{train}}:=\\{{\bm{y}}_{i}\\}_{i=1}^{N}$ as the training
set. A naive approach is just to apply SurCo-zero $N$ times, which leads to
$N$ independent surrogate costs $\\{{\bm{c}}_{i}\\}_{i=1}^{N}$. However, this
approach does not consider two important characteristics. _First_ , it fails
to leverage possible relationship between the instance descriptor
${\bm{y}}_{i}$ and its associated surrogate cost ${\bm{c}}_{i}$, since every
surrogate cost is independently estimated. _Second_ , it fails to learn any
useful knowledge from the $N$ instances after optimization. As a result, for
an unseen instance, the entire optimization process needs to be conducted
again, which is slow. This motivates us to add a surrogate cost _model_
$\hat{\bm{c}}({\bm{y}};\bm{\theta})$ into the optimization as a regularizer:

$\displaystyle\small\text{({SurCo}{}-{prior}-$\lambda$)}:\quad\min_{\bm{\theta},\\{{\bm{c}}_{i}\\}}\mathcal{L}_{\texttt{prior}}(\bm{\theta},\\{{\bm{c}}_{i}\\};\lambda)$
$\displaystyle:=\sum_{i=1}^{N}f({\bm{g}}_{\Omega({\bm{y}}_{i})}({\bm{c}}_{i});{\bm{y}}_{i})+\lambda\|{\bm{c}}_{i}-\hat{\bm{c}}({\bm{y}}_{i};\bm{\theta}))\|_{2}$
(5)

The regressor model $\hat{\bm{c}}({\bm{y}};\bm{\theta})$ directly predicts the
surrogate cost from the instance description. The form of the regressor can be
a neural network, in which $\bm{\theta}$ is its parameters. Note that when
$\lambda=0$, it reduces to $N$ independent optimizations, while when
$\lambda>0$, the surrogate costs $\\{{\bm{c}}_{i}\\}$ interact with each
other. With the regressor, we distill knowledge gained from the optimization
procedure into $\bm{\theta}$, which can be used for an unseen instance
${\bm{y}}^{\prime}$. Indeed, we use the learned regressor model to predict the
surrogate cost
${\bm{c}}^{\prime}=\hat{\bm{c}}({\bm{y}}^{\prime};\bm{\theta})$, and directly
solve the _surrogate optimization_ (SO):

$\small\hat{\bm{x}}^{*}({\bm{y}}^{\prime})=\arg\min_{{\bm{x}}\in\Omega({\bm{y}})}\hat{\bm{c}}^{\top}({\bm{y}}^{\prime};\bm{\theta}){\bm{x}}$
(6)

A special case is when $\lambda\rightarrow+\infty$, we directly learn the
network parameters $\bm{\theta}$ instead of individual surrogate costs:

$\displaystyle\small\text{({SurCo}{}-{prior})}:\quad\min_{\bm{\theta}}\mathcal{L}_{\texttt{prior}}(\bm{\theta})$
$\displaystyle:=\sum_{i=1}^{N}f({\bm{g}}_{\Omega({\bm{y}}_{i})}(\hat{\bm{c}}({\bm{y}}_{i};\bm{\theta}));{\bm{y}}_{i})$
(7)

This approach is useful when the goal is to find high-quality solutions for
unseen instances of a problem distribution when the upfront cost of offline
training is acceptable but the cost of optimizing on-the-fly is prohibitive.
Here, we require access to a distribution of training optimization problems,
but at test time only require the feasible region and not the nonlinear
objective. Different from predict-then-optimize (Elmachtoub & Grigas, 2022a;
Ferber et al., 2020) or ML optimizers (Ban & Rudin, 2019), we do not require
the optimal solution $\\{{\bm{x}}^{*}_{i}\\}_{i=1}^{N}$ as part of the
training set.

###  3.3 SurCo-hybrid: fine-tuning a predicted surrogate

Naturally, we consider SurCo-hybrid, a hybrid approach which initializes the
coefficients of SurCo-zero with the coefficients predicted from SurCo-prior
which was trained on offline data. This allows SurCo-hybrid to start out
optimization from an initial prediction that has good performance for the
distribution at large but which is then fine-tuned for the specific instance.
Formally, we initialize ${\bm{c}}(0)=\hat{\bm{c}}({\bm{y}}_{i};\bm{\theta})$
and then continue optimizing ${\bm{c}}$ based on the update from SurCo-zero.
This approach is geared towards optimizing the nonlinear objective using a
high-quality initial prediction that is based on the problem distribution and
then fine-tuning the objective coefficients based on the specific problem
instance at test time. Here, high performance comes at the runtime cost of
both having to train offline on a problem distribution as well as performing
fine-tuning steps on-the-fly. However, this additional cost is often
worthwhile when the main goal is to find the best possible solutions by
leveraging synthesized domain knowledge in combination with individual problem
instances as arises in chip design (Mirhoseini et al., 2021) and compiler
optimization (Zhou et al., 2020).

##  4 Is Predicting Surrogate Cost better than Predicting Solution? A
Theoretical Analysis

One of the key ingredient of our proposed methods (SurCo-prior and SurCo-
hybrid) is to learn a model to predict surrogate cost ${\bm{c}}$ from instance
description ${\bm{y}}$, which is in contrast with previous solution regression
approaches that directly learn a mapping from problem description ${\bm{y}}$
to the solution ${\bm{x}}^{*}({\bm{y}})$ (Ban & Rudin, 2019). A natural
question arise: which one is better?

In this section, we give theoretical intuition to compare the two approaches
using a simple 1-nearest-neighbor (1-NN) solution regressor (Fix, 1985). We
first relate the number of samples needed to learn any mapping to its
_Lipschitz constant_ $L$, and then show that for the direct mapping
${\bm{y}}\mapsto{\bm{x}}^{*}({\bm{y}})$, $L$ can be very large. Therefore,
there exist fundamental difficulties to learn such a mapping. When this
happens, we can still find surrogate cost mapping
${\bm{y}}\mapsto{\bm{c}}^{*}({\bm{y}})$ with finite $L$ that leads to the
optimal solution ${\bm{x}}^{*}({\bm{y}})$ of the original nonlinear problems.

###  4.1 Lipschitz constant and sample complexity

Formally, consider fitting any mapping $\bm{\phi}:\mathbb{R}^{d}\supseteq
Y\mapsto\mathbb{R}^{m}$ with a dataset
$\mathcal{C}:=\\{{\bm{y}}_{i},\bm{\phi}_{i}\\}$. Here $Y$ is a compact region
with finite volume $\mathrm{vol}(Y)$. The Lipschitz constant $L$ is the
smallest number so that
$\|\bm{\phi}({\bm{y}}_{1})-\bm{\phi}({\bm{y}}_{2})\|_{2}\leq
L\|{\bm{y}}_{1}-{\bm{y}}_{2}\|_{2}$ holds for any
${\bm{y}}_{1},{\bm{y}}_{2}\in Y$. The following theorem shows that if the
dataset covers the space $Y$, we could achieve high accuracy prediction:
$\|\bm{\phi}({\bm{y}})-\hat{\bm{\phi}}({\bm{y}})\|_{2}\leq\epsilon$ for any
${\bm{y}}\in Y$.

######  Definition 4.1 ($\delta$-cover).

A dataset $\mathcal{C}:=\\{({\bm{y}}_{i},\bm{\phi}_{i})\\}_{i=1}^{N}$
$\delta$-covers the space $Y$, if for any ${\bm{y}}\in Y$, there exists at
least one ${\bm{y}}_{i}$ so that $\|{\bm{y}}-{\bm{y}}_{i}\|_{2}\leq\delta$.

######  Lemma 4.2 (Sufficient condition of prediction with
$\epsilon$-accuracy).

If the dataset $\mathcal{C}$ can $(\epsilon/L)$-cover $Y$, then for any
${\bm{y}}\in Y$, a 1-nearest-neighbor regressor $\hat{\bm{\phi}}$ leads to
$\|\hat{\bm{\phi}}({\bm{y}})-\bm{\phi}({\bm{y}})\|_{2}\leq\epsilon$.

######  Lemma 4.3 (Lower bound of sample complexity for $\epsilon/L$-cover).

To achieve $\epsilon/L$-cover of $Y$, the size of the dataset set $N\geq
N_{0}(\epsilon):=\frac{\mathrm{vol}(Y)}{\mathrm{vol}_{0}}\left(\frac{L}{\epsilon}\right)^{d}$,
where $\mathrm{vol}_{0}$ is the volume of unit ball in $d$-dimension.

Please find all proofs in the Appendix. While we do not rule out a more
advanced regressor than 1-nearest-neighbor that could lead to better sample
complexity, the lemmas demonstrate that the Lipschitz constant $L$ plays an
important role in sample complexity.

Figure 2: Table placement plan latency (left) and solver runtime (right). We
evaluate SurCo against Dreamshard (Zha et al., 2022b), a SoTA offline RL
sharding tool, a domain-heuristic of assigning tables based on dimension, and
a greedy heuristic based on the estimated runtime increase. Striped approaches
require pre-training.

###  4.2 Difference between Cost and Solution Regression

In the following we will show that in certain cases, the direct prediction
${\bm{y}}\mapsto{\bm{x}}^{*}({\bm{y}})$ could have an infinitely large
Lipschitz constant $L$. To show this, let us consider a general mapping
$\bm{\phi}:\mathbb{R}^{d}\supseteq Y\mapsto\mathbb{R}^{m}$. Let $\bm{\phi}(Y)$
be the image of $Y$ under mapping $\bm{\phi}$ and $\kappa(Y)$ be the number of
connected components for region $Y$.

######  Theorem 4.4 (A case of infinite Lipschitz constant).

If the minimal distance $d_{\min}$ for different connected components of
$\bm{\phi}(Y)$ is strictly positive, and $\kappa(\bm{\phi}(Y))>\kappa(Y)$,
then the Lipschitz constant of the mapping $\bm{\phi}$ is infinite.

Note that this theorem applies to a wide variety of combinatorial optimization
problems. For example, when $Y$ is a connected region and the optimization
problem can be formulated as an integer programming, the optimal solution set
${\bm{x}}^{*}(Y):=\\{{\bm{x}}^{*}({\bm{y}}):{\bm{y}}\in Y\\}$ is a discrete
set of integral vertices, so the theorem applies. Combined with analysis in
Sec. 4.1, we know the mapping ${\bm{y}}\mapsto{\bm{x}}^{*}({\bm{y}})$ is hard
to learn even with a lot of samples.

We can see this more clearly with a concrete example in 2D space. Let the 1D
instance description $y\in[0,\pi/2]$, and the feasible region is a convex hull
of 3 vertices $\\{(0,0),(0,1),(1,0)\\}$. The nonlinear objective is simply
$f({\bm{x}};y):=(x_{1}\cos(y)+x_{2}\sin(y))^{2}$, in which
${\bm{x}}=(x_{1},x_{2})$ is the 2D solution vector. The direct mapping
$y\rightarrow{\bm{x}}^{*}$ maps a continuous region of instance descriptions
(i.e., $y\in[0,\pi/2]$) into 2 disjoint regions points (${\bm{x}}^{*}=(0,1)$
and ${\bm{x}}^{*}=(1,0)$), and thus according to Theorem 4.4, its Lipschitz
constant must be infinite. In contrast, there exists a surrogate cost mapping
${\bm{c}}(y)=[\cos(y),\sin(y)]^{\top}$, and the mapping $y\rightarrow{\bm{c}}$
has finite Lipschitz constant (actually $L\leq 1$) and can be learned easily.

##  5 Empirical Evaluation

We evaluate the variants of SurCo on three settings, embedding table sharding,
inverse photonic design, and nonlinear route planning, with the first two
being real-world industrial settings. Each setting consists of a family of
problem instances with varying feasible region and nonlinear objective
function. Additionally, both table sharding and inverse photonic design lack
analytical formulations of the objective function which prevents them from
being used by many off-the-shelf nonlinear solvers like SCIP (Achterberg,
2009).

Figure 3: Left The solution loss (% of failed instances when the design loss
is not 0), and right test time solver runtime in log scale. For both, lower is
better. We compare against the Pass-Through gradient approach proposed in
(Schubert et al., 2022). We observe that SurCo-prior achieves similar success
rates to the previous approach Pass-Through with a substantially improved
runtime. Additionally, SurCo-zero runs comparably or faster, while finding
more valid solutions than Pass-Through. SurCo-hybrid obtains valid solutions
most often and is faster than SurCo-zero at the expense of pretraining.
Striped approaches use pretraining.

###  5.1 Embedding Table Sharding

The task of sharding embedding tables arises in the deployment of large-scale
neural network models which operate over both sparse and dense inputs (e.g.,
in recommendation systems (Zha et al., 2022a, b, 2023; Sethi et al., 2022)).
Given $T$ embedding tables and $D$ homogeneous devices, the goal is to
distribute the tables among the devices such that no device’s memory limit is
exceeded, while the tables are processed efficiently. Formally, let $x_{t,d}$
be the binary variable indicating whether table $t$ is assigned to device $d$,
and ${\bm{x}}:=\\{x_{t,d}\\}\in\\{0,1\\}^{TD}$ be the collection of the
variables. The optimization problem is
$\min_{{\bm{x}}\in\Omega}f({\bm{x}};{\bm{y}})$ where
$\Omega({\bm{y}}):=\left\\{{\bm{x}}:\forall t,\sum_{t}x_{t,d}=1,\forall
d,\sum_{t}m_{t}x_{t,d}\leq M\right\\}$.

Here the problem description ${\bm{y}}$ includes table memory usage
$\\{m_{t}\\}$, and capacity $M$ of each device. $\sum_{d}x_{t,d}=1$ means each
table $t$ should be assigned to exactly one device, and
$\sum_{d}m_{t}x_{t,d}\leq M$ means the memory consumption at each device $d$
should not exceed its capacity. The nonlinear cost function
$f({\bm{x}};{\bm{y}})$ is the _latency_ , i.e., the runtime of the longest-
running device. Due to shared computation (e.g., batching) among the group of
assigned tables, and communication costs across devices, the objective is
highly nonlinear. $f({\bm{x}};{\bm{y}})$ is well-approximated by a sharding
plan runtime estimator proposed by Dreamshard (Zha et al., 2022b). Note that
here, the runtime is approximated by a differentiable function since the real
world deployment runtime isn’t differentiable.

SurCo learns to predict $T\times D$ surrogate cost $\hat{c}{}_{t,d}$, one for
each potential table-device assignment. During training, the gradients through
the combinatorial solver $\partial{\bm{g}}/\partial{\bm{c}}$ are computed via
CVXPYLayers (Agrawal et al., 2019a), and the integrality constraints are
relaxed. In practice, we obtained mostly integral solutions in that only one
table on any given device was fractional. At test time, we solve for the
integer solution using SCIP (Achterberg, 2009), a branch and bound MILP
solver.

Settings. We evaluate SurCo on the public Deep Learning Recommendation Model
(DLRM) dataset (Naumov et al., 2019). We consider 6 settings placing 10, 20,
30, 40, 50, and 60 tables on 4 devices, with a 5GB memory limit on GPU devices
and 100 instances each (50 train, 50 test).

Baselines. For impromptu baselines, Greedy allocates tables to devices based
on predicted latency increase $f$, and the domain-expert algorithm Domain-
Heuristic balances the aggregate dimension (Zha et al., 2022b). For SurCo-
prior, we use Dreamshard, the SoTA embedding table sharding algorithm using
offline RL.

Results. Fig. 2, SurCo-zero finds lower latency sharding plans than the
baselines, while it takes slightly longer than Domain-Heuristic and DreamShard
due to taking optimization steps rather than building a solution from a
heuristic feature or reinforcement learned policy. SurCo-prior obtains lower
latency solutions in about the same time as DreamShard with a slight runtime
increase from SCIP. Lastly, SurCo-hybrid obtains the best solutions and has
runtime comparable to SurCo-zero. In smaller instances ($T\leq 40$), SurCo-
prior finds better solutions than its impromptu counterpart, SurCo-zero,
likely by escaping local optima by training on a variety of examples. For
larger instances with more tables available for placement, SurCo-zero performs
better by optimizing for the test instances as opposed to SurCo-prior which
only uses training data. Using SurCo-hybrid, we obtain the best solutions but
incur the upfront pretraining cost and the deployment-time optimization cost.

###  5.2 Inverse Photonic Design

Figure 4: Inverse photonic design settings from the ceviche challenges
(Schubert et al., 2022) along with SurCo-zero solution designs and wavelength
intensities. Light is fed in on the left and is routed at desired intensities
to the output by designing the intermediate region. In the Wavelength
Multiplexer setting, two wavelengths of interest are visualized as they are
routed to different locations.

Photonic devices play an essential role in high-speed communication (Marpaung
et al., 2019), quantum computing (Arrazola et al., 2021), and machine learning
hardware acceleration (Wetzstein et al., 2020). The photonic components can be
encoded as a binary 2D grid, with each cell being filled or void. There are
constraints on which binary patterns are physically manufacturable: only those
that can be drawn by a physical brush instrument with a specific cross shape
can be manufactured. It remains challenging to find manufacturable designs
that satisfy design specifications like splitting beams of light. An example
solution developed by SurCo is shown in Figure 5(b): coming from the top,
beams are routed to the left or right, depending on wavelength. The solution
is also manufacturable: a 3-by-3 brush cross can fit in all filled and void
space. Given the design, existing work (Hughes et al., 2019) enables
differentiation of the design misspecification cost, evaluated as how far off
the transmission intensity of the wavelengths are from the desired output
locations, with zero design loss meaning that the specification is satisfied.
Researchers also develop the Ceviche Challenges (Schubert et al., 2022) a
standard benchmark of inverse photonic design problems. Formally, a feasible
design is a rectangle of pixels which are either filled or void where both the
filled and void pixels can be expressed as a unions of the brush shape. Please
see (Schubert et al., 2022) for an in depth description of the nonlinear
objective and feasible region.

(a) Loss Convergence (b) Device (c) Wave Mangitude

Figure 5: Inverse photonic design convergence example (Schubert et al., 2022).
In (a), SurCo-zero smoothly lowers the loss while the pass-through baseline
converges noisily. Also, SurCo-hybrid quickly fine-tunes an already high-
quality solution. (b) visualizes the SurCo-zero solution and (c) visualizes
the two wavelengths of interest which are successfully routed from the top to
the bottom.

Settings. We compare our approaches against the Pass-Through method (Schubert
et al., 2022) on randomly generated instances of the four types of problems in
(Schubert et al., 2022): Waveguide Bend, Mode Converter, Wavelengths Division
Multiplexer, and Beam Splitter. We generate 50 instances in each setting (25
training/25 test), randomly sampling the location of input and output
waveguides, or “pipes” where we are taking in light and desire light to
output. We fix the wavelengths themselves and so the problem description
${\bm{y}}$ contains an image description of the problem instance, where each
pixel is either “fixed” or “designable”. Further generation details are in the
appendix. We evaluated several algorithms described in the appendix, such as
genetic algorithms and derivative-free optimization, which failed to find
physically feasible solutions. We consider two wavelengths (1270nm/1290nm),
and optimize at a resolution of 40nm, visualizing the test results in Fig. 3.

Results. Fig. 3, SurCo-zero consistently finds as many or more valid devices
compared to the Pass-Through baseline (Schubert et al., 2022). Additionally,
since the on-the-fly solvers stop when they either find a valid solution, or
reach a maximum of 200 steps, the runtime of SurCo-zero is slightly lower than
the Pass-Through baseline. SurCo-prior obtains similar success rates as Pass-
Through while taking two orders of magnitude less time as it does not require
expensive impromptu optimization, making SurCo-prior a promising approach for
large-scale settings or when solving many slightly-varied instances. Lastly,
SurCo-hybrid performs best in terms of solution loss, finding valid solutions
more often than the other approaches. It also takes less runtime than the
other on-the-fly approaches since it is able to reach valid solutions faster,
although it still requires optimization on-the-fly so it takes longer than
SurCo-prior. We visualize impromptu solver convergence in Fig. 5(a) where
SurCo-zero has smoother and faster convergence than Pass-Through.

###  5.3 Nonlinear Route Planning

Figure 6: Nonlinear route planning visualization. The goal is to route from
the top left to bottom right corner, with the edge weights being normally
distributed, maximizing the probability of arriving before a set deadline.

Nonlinear route planning can arise where one wants to maximize the probability
of arrival before a set time in graphs with random edges (Fan et al., 2005;
Nikolova et al., 2006; Lim et al., 2013). These problems occur in risk-aware
settings such as emergency services operators who need to maximize the
probability of arriving before a critical time, or where driver reward is
determined by deadlines.

Given a graph $G$ with edge lengths coming from a random distribution, a pair
of source and destination nodes $s,t$, and a time limit $T$ that we would like
to arrive before, we select a feasible $s-t$ path $P_{s,t}$ that maximizes the
probability of arriving before the deadline $P[\text{length}(P_{s,t})\leq T]$.
If we assume that edge times are distributed according to a random normal
distribution $t_{e}\sim{\mathcal{N}}(\mu_{e},\sigma_{e}^{2})$, then we could
write the objective as maximizing $f(x;y)=\Phi\left((T-\sum_{e\in
P_{s,t}}\mu_{e})/\sqrt{\sum_{e\in P_{s,t}}\sigma^{2}_{e}}\right)$, with $\Phi$
being the cumulative distribution function of a standard Gaussian
distribution, with the feasible region $\Omega(y)$ being the set of $s-t$
paths in the graph from origin to destination. Explicitly, the problem
parameters ${\bm{y}}$ are the graph $G$, source and destination nodes $s,t$,
time limit $T$, and the edge weight distributions specified by the edge means
and variances $\mu_{e},\sigma_{e}^{2}$. We only consider the zero-shot setting
without training examples since we need to solve the problem on-the-fly. SurCo
trains surrogate edge costs $\hat{c}_{e}$ and finds the shortest path using
Bellman-Ford (Bellman, 1958), and differentiate using blackbox differentiation
(Pogančić et al., 2019).

Settings. We run on a 5x5 grid graph with 25 draws of edge parameters
$\mu_{e}\sim U(0.1,1)$ and $\sigma^{2}_{e}\sim U(0.1,0.3)*(1-\mu_{e})$, with
$U(a,b)$ being the uniform random distribution between $a$ and $b$. We have
deadline settings based on the length of the least expected time path (LET)
which is simply the shortest path using $\mu_{e}$ as weights. We use loose,
normal, and tight deadlines of 1.1 LET, 1 LET, and 0.9 LET respectively. The
source and destination are oppose corners of the grid graph.

Figure 7: Comparison of nonlinear route planning probability of arriving on
time. We compare against a domain heuristic (Nikolova et al., 2006) and SCIP
(Achterberg, 2009). SurCo-zero outperforms the domain heuristic, and is
similar to SCIP using less time. SCIP-1s fails to find feasible solutions.

Results. Fig. 7, we compare SurCo-zero against a domain-specific approach that
minimizes a linear combination of mean and variance (Nikolova et al., 2006),
and SCIP (Achterberg, 2009). In this setting, we focus on the zero-shot
performance of SurCo, comparing it against two other zero-shot approaches.
Furthermore, here we are able to encode the objective analytically into SCIP
whereas the objectives of the other settings do not have readily-encodeable
formulations, relying on neural networks or physical simulation. Since SurCo-
zero and the domain approach take much less than 1 second, we use SCIP-1s and
find that SCIP cannot find feasible solutions at that time scale. SCIP-30min
demonstrates how well a general-purpose method can do given enough time, with
SCIP timing out on all instances. We also find that SurCo-zero is able to
obtain comparable solutions to SCIP-30min. Furthermore, SurCo-zero
consistently outperforms the domain heuristic, finding paths that reach the
deadline with $4.5\%,6.5\%,8.5\%$ times higher success rates in loose, normal,
and tight deadlines. Finally, we found only 2 instances where the domain
heuristic beat SurCo-zero.

##  6 Related Work

##### Differentiable Optimization

OptNet (Amos & Kolter, 2017) proposed implicitly differentiating through KKT
conditions, a set of linear equations that determine the optimal solution.
Followup work differentiated through linear programs (Wilder et al., 2019a),
submodular optimization problems (Djolonga & Krause, 2017; Wilder et al.,
2019a), cone programs (Agrawal et al., 2019a, b), MaxSAT (Wang et al., 2019),
Mixed Integer Linear Programming (Ferber et al., 2020; Mandi et al., 2020),
Integer Linear Programming (Mandi et al., 2020), dynamic programming
(Demirovic et al., 2020), blackbox discrete linear optimizers (Pogančić et
al., 2019; Rolínek et al., 2020a, b), maximum likelihood estimation (Niepert
et al., 2021), kmeans clustering (Wilder et al., 2019b), knapsack (Guler et
al., 2022; Demirović et al., 2019), the cross-entropy method (Amos & Yarats,
2020), Nonlinear Least Squares (Pineda et al., 2022), SVM training (Lee et
al., 2019), and combining LP variables (Wang et al., 2020a). SurCo can
leverage these differentiable surrogates for different problem domains.

##### Task Based Learning

Task-based learning solves distributions of linear or quadratic optimization
problems with the true objective hidden at test time but available for
training (Elmachtoub & Grigas, 2022b; Donti et al., 2017; El Balghiti et al.,
2019; Liu & Grigas, 2021; Hu et al., 2022). (Donti et al., 2021) predicts and
corrects solutions for continuous nonlinear optimization. Bayesian
optimization (BO) (Shahriari et al., 2016), optimizes blackbox functions by
approximating the objective with a learned model that can be optimized over.
Recent work optimizes individual instances over discrete spaces like
hypercubes (Baptista & Poloczek, 2018), graphs (Deshwal et al., 2021), and
MILP (Papalexopoulos et al., 2022). Data reuse from previous runs is proposed
to optimize multiple correlated instances (Swersky et al., 2013; Feurer et
al., 2018). However, the surrogate Gaussian Process (GP) models are memory and
time intensive in high-dimensional settings. Recent work has addressed GP
scalability via gradient updates (Ament & Gomes, 2022); however, it is unclear
whether GP can scale in conjunction with combinatorial solvers. Machine
learning is also used to guide combinatorial algorithms. Several approaches
produce combinatorial solutions (Zhang & Dietterich, 1995; Khalil et al.,
2017; Kool et al., 2018; Nazari et al., 2018; Zha et al., 2022a, b). Here,
approaches are limited to simple feasible regions by iteratively building
solutions for problems like routing, assignment, or covering. However, these
approaches fail to handle more complex constraints. Other approaches set
parameters that improve solver runtime (Khalil et al., 2016; Bengio et al.,
2021). Similarly, a neural diving approach has been proposed for finding fast
MILP solutions (Nair et al., 2020). This approach requires iteratively solving
a subproblem which in the nonlinear setting may still be hard to solve or even
encode.

##### Learning Latent Space for Optimization

We learn latent linear objectives to optimize nonlinear functions while other
approaches learn latent embeddings for faster solving. FastMap (Faloutsos &
Lin, 1995) learns latent object embeddings for efficient search, and variants
of FastMap are used in graph optimization and shortest path (Cohen et al.,
2018; Hu et al., 2022; Li et al., 2019). (Wang et al., 2020b, 2021a; Yang et
al., 2021; Zhao et al., 2022) use Monte Carlo Tree Search to perform single
and multi-objective optimization by learning to split the search space.

##### Mixed Integer Nonlinear Programming (MINLP)

SurCo-zero operates as a MINLP solver, optimizing nonlinear and nonconvex
objectives over discrete linear feasible regions. Specialized solvers handle
some MINLP variants (Burer & Letchford, 2012; Belotti et al., 2013); however,
scalability in nonconvex settings usually requires problem-specific techniques
like piecewise linear approximation, objective convexification, or exploiting
special structure.

##  7 Conclusion

We introduced SurCo, a method for learning linear surrogates for combinatorial
nonlinear optimization problems. SurCo learns linear objective coefficients
for a surrogate solver which results in solutions that minimize the nonlinear
loss via gradient descent. At its core, SurCo differentiates through the
surrogate solver which maps the predicted coefficients to a combinatorially
feasible solution, combining the flexibility of gradient-based optimization
with the structure of combinatorial solvers. Our theoretical intuition for
SurCo poses promising directions for future work in proving convergence
guarantees or generalization bounds. Additionally, improvements of SurCo may
enable scalable solving for settings in stochastic optimization, game theory,
combinatorial reinforcement learning, and more. We presented three variants of
SurCo, SurCo-zero which optimizes individual instances, SurCo-prior which
trains a coefficient prediction model offline, and SurCo-hybrid which fine-
tunes the coefficients predicted by SurCo-prior on individual test instances.
While SurCo’s performance is somewhat limited to binary problems due to the
lack of interior integer points, we find that many real-world domains operate
on binary decision variables. We evaluated variants of SurCo against the
state-of-the-art approaches on three domains, with two used in industry,
obtaining better solution quality for similar or better runtime in the
embedding table sharding domain, quickly identifying viable photonic devices,
and finding successful routes in stochastic path planning. Overall, SurCo
trains linear surrogate coefficients to point the solver towards high-quality
solutions, becoming a general-purpose method that aims to tackle a broad class
of combinatorial problems with nonlinear objectives when off-the-shelf solvers
fail.

## Acknowledgements.

This paper reports on research done while Aaron Ferber, Taoan Huang, and
Daochen Zha were interns at Meta AI (FAIR). The research at the University of
Southern California was supported by the National Science Foundation (NSF)
under grant number 2112533. We also thank the anonymous reviewers for helpful
feedback.

## References

  * Achterberg (2009) Achterberg, T.  Scip: solving constraint integer programs.  _Mathematical Programming Computation_ , 1(1):1–41, 2009.
  * Agrawal et al. (2019a) Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z.  Differentiable convex optimization layers.  _Advances in neural information processing systems_ , 32, 2019a.
  * Agrawal et al. (2019b) Agrawal, A., Barratt, S., Boyd, S., Busseti, E., and Moursi, W. M.  Differentiating through a cone program.  _J. Appl. Numer. Optim_ , 1(2):107–115, 2019b.
  * Ament & Gomes (2022) Ament, S. E. and Gomes, C. P.  Scalable first-order bayesian optimization via structured automatic differentiation.  In _International Conference on Machine Learning_ , pp. 500–516. PMLR, 2022.
  * Amos & Kolter (2017) Amos, B. and Kolter, J. Z.  Optnet: Differentiable optimization as a layer in neural networks.  In _International Conference on Machine Learning_ , pp. 136–145. PMLR, 2017.
  * Amos & Yarats (2020) Amos, B. and Yarats, D.  The differentiable cross-entropy method.  In _International Conference on Machine Learning_ , pp. 291–302. PMLR, 2020.
  * Arrazola et al. (2021) Arrazola, J. M., Bergholm, V., Brádler, K., Bromley, T. R., Collins, M. J., Dhand, I., Fumagalli, A., Gerrits, T., Goussev, A., Helt, L. G., et al.  Quantum circuits with many photons on a programmable nanophotonic chip.  _Nature_ , 591(7848):54–60, 2021.
  * Ban & Rudin (2019) Ban, G.-Y. and Rudin, C.  The big data newsvendor: Practical insights from machine learning.  _Operations Research_ , 67(1):90–108, 2019.
  * Baptista & Poloczek (2018) Baptista, R. and Poloczek, M.  Bayesian optimization of combinatorial structures.  In _International Conference on Machine Learning_ , pp. 462–471. PMLR, 2018.
  * Bellman (1958) Bellman, R.  On a routing problem.  _Quarterly of applied mathematics_ , 16(1):87–90, 1958.
  * Belotti et al. (2013) Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., and Mahajan, A.  Mixed-integer nonlinear optimization.  _Acta Numerica_ , 22:1–131, 2013.
  * Bengio et al. (2021) Bengio, Y., Lodi, A., and Prouvost, A.  Machine learning for combinatorial optimization: a methodological tour d’horizon.  _European Journal of Operational Research_ , 290(2):405–421, 2021.
  * Berthet et al. (2020) Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F.  Learning with differentiable pertubed optimizers.  _Advances in neural information processing systems_ , 33:9508–9519, 2020.
  * Bradbury et al. (2018) Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., and Zhang, Q.  JAX: composable transformations of Python+NumPy programs, 2018\.  URL http://github.com/google/jax.
  * Burer & Letchford (2012) Burer, S. and Letchford, A. N.  Non-convex mixed-integer nonlinear programming: A survey.  _Surveys in Operations Research and Management Science_ , 17(2):97–106, 2012.
  * Chvatal et al. (1983) Chvatal, V., Chvatal, V., et al.  _Linear programming_.  Macmillan, 1983.
  * Cohen et al. (2018) Cohen, L., Uras, T., Jahangiri, S., Arunasalam, A., Koenig, S., and Kumar, T. S.  The fastmap algorithm for shortest path computations.  In _IJCAI_ , 2018.
  * Cozad et al. (2014) Cozad, A., Sahinidis, N. V., and Miller, D. C.  Learning surrogate models for simulation-based optimization.  _AIChE Journal_ , 60(6):2211–2227, 2014.
  * Demirović et al. (2019) Demirović, E., J Stuckey, P., Bailey, J., Chan, J., Leckie, C., Ramamohanarao, K., and Guns, T.  Predict+ optimise with ranking objectives: Exhaustively learning linear functions.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019_ , pp. 1078–1085. International Joint Conferences on Artificial Intelligence, 2019.
  * Demirovic et al. (2020) Demirovic, E., J Stuckey, P., Guns, T., Bailey, J., Leckie, C., Ramamohanarao, K., and Chan, J.  Dynamic programming for predict+ optimise.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pp. 1444–1451. AAAI Press, 2020.
  * Deshwal et al. (2021) Deshwal, A., Belakaria, S., and Doppa, J. R.  Mercer features for efficient combinatorial bayesian optimization.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(8):7210–7218, May 2021.  doi: 10.1609/aaai.v35i8.16886.  URL https://ojs.aaai.org/index.php/AAAI/article/view/16886.
  * Djolonga & Krause (2017) Djolonga, J. and Krause, A.  Differentiable learning of submodular models.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Donti et al. (2017) Donti, P., Amos, B., and Kolter, J. Z.  Task-based end-to-end model learning in stochastic optimization.  _Advances in neural information processing systems_ , 30, 2017.
  * Donti et al. (2021) Donti, P. L., Rolnick, D., and Kolter, J. Z.  DC3: A learning method for optimization with hard constraints.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=V1ZHVxJ6dSS.
  * El Balghiti et al. (2019) El Balghiti, O., Elmachtoub, A. N., Grigas, P., and Tewari, A.  Generalization bounds in the predict-then-optimize framework.  _Advances in neural information processing systems_ , 32, 2019.
  * Elmachtoub & Grigas (2022a) Elmachtoub, A. N. and Grigas, P.  Smart “predict, then optimize”.  _Management Science_ , 68(1):9–26, 2022a.
  * Elmachtoub & Grigas (2022b) Elmachtoub, A. N. and Grigas, P.  Smart “predict, then optimize”.  _Management Science_ , 68(1):9–26, 2022b.
  * Faloutsos & Lin (1995) Faloutsos, C. and Lin, K.-I.  Fastmap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets.  In _Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data_ , SIGMOD ’95, pp. 163–174, New York, NY, USA, 1995. Association for Computing Machinery.  ISBN 0897917316.  doi: 10.1145/223784.223812.  URL https://doi.org/10.1145/223784.223812.
  * Fan et al. (2005) Fan, Y., Kalaba, R. E., and Moore, J. E.  Arriving on time.  _Journal of Optimization Theory and Applications_ , 127:497–513, 2005.
  * Ferber et al. (2020) Ferber, A., Wilder, B., Dilkina, B., and Tambe, M.  Mipaal: Mixed integer program as a layer.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 1504–1511, 2020.
  * Feurer et al. (2018) Feurer, M., Letham, B., and Bakshy, E.  Scalable meta-learning for bayesian optimization.  _stat_ , 1050(6), 2018.
  * Fix (1985) Fix, E.  _Discriminatory analysis: nonparametric discrimination, consistency properties_ , volume 1.  USAF school of Aviation Medicine, 1985.
  * Gad (2021) Gad, A. F.  Pygad: An intuitive genetic algorithm python library, 2021.
  * Gosavi et al. (2015) Gosavi, A. et al.  _Simulation-based optimization_.  Springer, 2015.
  * Guler et al. (2022) Guler, A. U., Demirović, E., Chan, J., Bailey, J., Leckie, C., and Stuckey, P. J.  A divide and conquer algorithm for predict+ optimize with non-convex problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 3749–3757, 2022.
  * Gurobi Optimization, LLC (2022) Gurobi Optimization, LLC.  Gurobi Optimizer Reference Manual, 2022.  URL https://www.gurobi.com.
  * Hu et al. (2022) Hu, Y., Kallus, N., and Mao, X.  Fast rates for contextual linear optimization.  _Management Science_ , 2022.
  * Hughes et al. (2019) Hughes, T. W., Williamson, I. A., Minkov, M., and Fan, S.  Forward-mode differentiation of maxwell’s equations.  _ACS Photonics_ , 6(11):3010–3016, 2019.
  * Jumper et al. (2021) Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Khalil et al. (2016) Khalil, E., Le Bodic, P., Song, L., Nemhauser, G., and Dilkina, B.  Learning to branch in mixed integer programming.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Khalil et al. (2017) Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L.  Learning combinatorial optimization algorithms over graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * Kool et al. (2018) Kool, W., van Hoof, H., and Welling, M.  Attention, learn to solve routing problems!  In _International Conference on Learning Representations_ , 2018.
  * Korte & Hausmann (1978) Korte, B. and Hausmann, D.  An analysis of the greedy heuristic for independence systems.  In _Annals of Discrete Mathematics_ , volume 2, pp. 65–74. Elsevier, 1978.
  * Koziel et al. (2021) Koziel, S., Çalık, N., Mahouti, P., and Belen, M. A.  Accurate modeling of antenna structures by means of domain confinement and pyramidal deep neural networks.  _IEEE Transactions on Antennas and Propagation_ , 70(3):2174–2188, 2021.
  * Land & Doig (2010) Land, A. H. and Doig, A. G.  An automatic method for solving discrete programming problems.  In _50 Years of Integer Programming 1958-2008_ , pp. 105–132. Springer, 2010.
  * Lee et al. (2019) Lee, K., Maji, S., Ravichandran, A., and Soatto, S.  Meta-learning with differentiable convex optimization.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 10657–10665, 2019.
  * Li et al. (2019) Li, J., Felner, A., Koenig, S., and Kumar, T. S.  Using fastmap to solve graph problems in a euclidean space.  In _Proceedings of the international conference on automated planning and scheduling_ , volume 29, pp. 273–278, 2019.
  * Li et al. (2021) Li, S., Yan, Z., and Wu, C.  Learning to delegate for large-scale vehicle routing.  _Advances in Neural Information Processing Systems_ , 34:26198–26211, 2021.
  * Li et al. (2018) Li, Z., Chen, Q., and Koltun, V.  Combinatorial optimization with graph convolutional networks and guided tree search.  _Advances in neural information processing systems_ , 31, 2018.
  * Lim et al. (2013) Lim, S., Sommer, C., Nikolova, E., and Rus, D.  Practical route planning under delay uncertainty: Stochastic shortest path queries.  In _Robotics: Science and Systems_ , volume 8, pp. 249–256. United States, 2013.
  * Liu & Grigas (2021) Liu, H. and Grigas, P.  Risk bounds and calibration for a smart predict-then-optimize method.  _Advances in Neural Information Processing Systems_ , 34:22083–22094, 2021.
  * Liuzzi et al. (2015) Liuzzi, G., Lucidi, S., and Rinaldi, F.  Derivative-free methods for mixed-integer constrained optimization problems.  _Journal of Optimization Theory and Applications_ , 164(3):933–965, 2015.
  * Mandi et al. (2020) Mandi, J., Stuckey, P. J., Guns, T., et al.  Smart predict-and-optimize for hard combinatorial optimization problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 1603–1610, 2020.
  * Marpaung et al. (2019) Marpaung, D., Yao, J., and Capmany, J.  Integrated microwave photonics.  _Nature photonics_ , 13(2):80–90, 2019.
  * Mazyavkina et al. (2021) Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, E.  Reinforcement learning for combinatorial optimization: A survey.  _Computers & Operations Research_, 134:105400, 2021.
  * Mirhoseini et al. (2021) Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang, S., Lee, Y.-J., Johnson, E., Pathak, O., Nazi, A., et al.  A graph placement methodology for fast chip design.  _Nature_ , 594(7862):207–212, 2021.
  * Nagai et al. (2020) Nagai, R., Akashi, R., and Sugino, O.  Completing density functional theory by machine learning hidden messages from molecules.  _npj Computational Materials_ , 6(1):1–8, 2020\.
  * Nair et al. (2020) Nair, V., Bartunov, S., Gimeno, F., Von Glehn, I., Lichocki, P., Lobov, I., O’Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., et al.  Solving mixed integer programs using neural networks.  _arXiv preprint arXiv:2012.13349_ , 2020.
  * Naumov et al. (2019) Naumov, M., Mudigere, D., Shi, H. M., Huang, J., Sundaraman, N., Park, J., Wang, X., Gupta, U., Wu, C., Azzolini, A. G., Dzhulgakov, D., Mallevich, A., Cherniavskii, I., Lu, Y., Krishnamoorthi, R., Yu, A., Kondratenko, V., Pereira, S., Chen, X., Chen, W., Rao, V., Jia, B., Xiong, L., and Smelyanskiy, M.  Deep learning recommendation model for personalization and recommendation systems.  _CoRR_ , abs/1906.00091, 2019.  URL https://arxiv.org/abs/1906.00091.
  * Nazari et al. (2018) Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M.  Reinforcement learning for solving the vehicle routing problem.  _Advances in neural information processing systems_ , 31, 2018.
  * Niepert et al. (2021) Niepert, M., Minervini, P., and Franceschi, L.  Implicit mle: backpropagating through discrete exponential family distributions.  _Advances in Neural Information Processing Systems_ , 34:14567–14579, 2021.
  * Nikolova et al. (2006) Nikolova, E., Kelner, J. A., Brand, M., and Mitzenmacher, M.  Stochastic shortest paths via quasi-convex maximization.  In _European Symposium on Algorithms_ , pp. 552–563. Springer, 2006\.
  * Papalexopoulos et al. (2022) Papalexopoulos, T. P., Tjandraatmadja, C., Anderson, R., Vielma, J. P., and Belanger, D.  Constrained discrete black-box optimization using mixed-integer programming.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 17295–17322. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/papalexopoulos22a.html.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  Pytorch: An imperative style, high-performance deep learning library.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Pineda et al. (2022) Pineda, L., Fan, T., Monge, M., Venkataraman, S., Sodhi, P., Chen, R. T., Ortiz, J., DeTone, D., Wang, A., Anderson, S., et al.  Theseus: A library for differentiable nonlinear optimization.  _Advances in Neural Information Processing Systems_ , 35:3801–3818, 2022.
  * Pogančić et al. (2019) Pogančić, M. V., Paulus, A., Musil, V., Martius, G., and Rolinek, M.  Differentiation of blackbox combinatorial solvers.  In _International Conference on Learning Representations_ , 2019.
  * Rapin & Teytaud (2018) Rapin, J. and Teytaud, O.  Nevergrad - A gradient-free optimization platform.  https://GitHub.com/FacebookResearch/Nevergrad, 2018.
  * Reingold & Tarjan (1981) Reingold, E. M. and Tarjan, R. E.  On a greedy heuristic for complete matching.  _SIAM Journal on Computing_ , 10(4):676–681, 1981\.
  * Rolínek et al. (2020a) Rolínek, M., Musil, V., Paulus, A., Vlastelica, M., Michaelis, C., and Martius, G.  Optimizing rank-based metrics with blackbox differentiation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7620–7630, 2020a.
  * Rolínek et al. (2020b) Rolínek, M., Swoboda, P., Zietlow, D., Paulus, A., Musil, V., and Martius, G.  Deep graph matching via blackbox differentiation of combinatorial solvers.  In _European Conference on Computer Vision_ , pp. 407–424. Springer, 2020b.
  * Ruder (2016) Ruder, S.  An overview of gradient descent optimization algorithms.  _arXiv preprint arXiv:1609.04747_ , 2016.
  * Schubert et al. (2022) Schubert, M. F., Cheung, A. K. C., Williamson, I. A. D., Spyra, A., and Alexander, D. H.  Inverse design of photonic devices with strict foundry fabrication constraints.  _ACS Photonics_ , 9(7):2327–2336, 2022.  doi: 10.1021/acsphotonics.2c00313.
  * Sethi et al. (2022) Sethi, G., Acun, B., Agarwal, N., Kozyrakis, C., Trippel, C., and Wu, C.-J.  Recshard: statistical feature-based memory optimization for industry-scale neural recommendation.  In _Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , pp. 344–358, 2022.
  * Shahriari et al. (2016) Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and de Freitas, N.  Taking the human out of the loop: A review of bayesian optimization.  _Proceedings of the IEEE_ , 104(1):148–175, 2016\.  doi: 10.1109/JPROC.2015.2494218.
  * Simon (2013) Simon, D.  _Evolutionary optimization algorithms_.  John Wiley & Sons, 2013.
  * Steiner et al. (2021) Steiner, B., Cummins, C., He, H., and Leather, H.  Value learning for throughput optimization of deep learning workloads.  In Smola, A., Dimakis, A., and Stoica, I. (eds.), _Proceedings of Machine Learning and Systems_ , volume 3, pp. 323–334, 2021.  URL https://proceedings.mlsys.org/paper/2021/file/73278a4a86960eeb576a8fd4c9ec6997-Paper.pdf.
  * Swersky et al. (2013) Swersky, K., Snoek, J., and Adams, R. P.  Multi-task bayesian optimization.  In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.  URL https://proceedings.neurips.cc/paper/2013/file/f33ba15effa5c10e873bf3842afb46a6-Paper.pdf.
  * Van Rossum & Drake (2009) Van Rossum, G. and Drake, F. L.  _Python 3 Reference Manual_.  CreateSpace, Scotts Valley, CA, 2009.  ISBN 1441412697.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Voß et al. (2012) Voß, S., Martello, S., Osman, I. H., and Roucairol, C.  _Meta-heuristics: Advances and trends in local search paradigms for optimization_.  Springer Science & Business Media, 2012.
  * Wang et al. (2020a) Wang, K., Wilder, B., Perrault, A., and Tambe, M.  Automatically learning compact quality-aware surrogates for optimization problems.  _Advances in Neural Information Processing Systems_ , 33:9586–9596, 2020a.
  * Wang et al. (2020b) Wang, L., Fonseca, R., and Tian, Y.  Learning search space partition for black-box optimization using monte carlo tree search.  _Advances in Neural Information Processing Systems_ , 33:19511–19522, 2020b.
  * Wang et al. (2021a) Wang, L., Xie, S., Li, T., Fonseca, R., and Tian, Y.  Sample-efficient neural architecture search by learning actions for monte carlo tree search.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021a.
  * Wang et al. (2019) Wang, P.-W., Donti, P., Wilder, B., and Kolter, Z.  Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.  In _International Conference on Machine Learning_ , pp. 6545–6554. PMLR, 2019.
  * Wang et al. (2021b) Wang, X., Liu, Y., Zhao, J., Liu, C., Liu, J., and Yan, J.  Surrogate model enabled deep reinforcement learning for hybrid energy community operation.  _Applied Energy_ , 289:116722, 2021b.
  * Wetzstein et al. (2020) Wetzstein, G., Ozcan, A., Gigan, S., Fan, S., Englund, D., Soljačić, M., Denz, C., Miller, D. A., and Psaltis, D.  Inference in artificial intelligence with deep optics and photonics.  _Nature_ , 588(7836):39–47, 2020.
  * Wilder et al. (2019a) Wilder, B., Dilkina, B., and Tambe, M.  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 1658–1665, 2019a.
  * Wilder et al. (2019b) Wilder, B., Ewing, E., Dilkina, B., and Tambe, M.  End to end learning and optimization on graphs.  _Advances in Neural Information Processing Systems_ , 32, 2019b.
  * Wolsey (1982) Wolsey, L. A.  An analysis of the greedy algorithm for the submodular set covering problem.  _Combinatorica_ , 2(4):385–393, 1982.
  * Wolsey (2007) Wolsey, L. A.  Mixed integer programming.  _Wiley Encyclopedia of Computer Science and Engineering_ , pp. 1–10, 2007.
  * Yang et al. (2021) Yang, K., Zhang, T., Cummins, C., Cui, B., Steiner, B., Wang, L., Gonzalez, J. E., Klein, D., and Tian, Y.  Learning space partitions for path planning.  _Advances in Neural Information Processing Systems_ , 34:378–391, 2021.
  * Ye et al. (2019) Ye, Y., Zhang, X., and Sun, J.  Automated vehicle’s behavior decision making using deep reinforcement learning and high-fidelity simulation environment.  _Transportation Research Part C: Emerging Technologies_ , 107:155–170, 2019.
  * Zha et al. (2022a) Zha, D., Feng, L., Bhushanam, B., Choudhary, D., Nie, J., Tian, Y., Chae, J., Ma, Y., Kejariwal, A., and Hu, X.  Autoshard: Automated embedding table sharding for recommender systems.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pp. 4461–4471, 2022a.
  * Zha et al. (2022b) Zha, D., Feng, L., Tan, Q., Liu, Z., Lai, K.-H., Bhargav, B., Tian, Y., Kejariwal, A., and Hu, X.  Dreamshard: Generalizable embedding table placement for recommender systems.  In _Advances in Neural Information Processing Systems_ , 2022b.
  * Zha et al. (2023) Zha, D., Feng, L., Luo, L., Bhushanam, B., Liu, Z., Hu, Y., Nie, J., Huang, Y., Tian, Y., Kejariwal, A., et al.  Pre-train and search: Efficient embedding table sharding with pre-trained neural cost models.  In _Sixth Conference on Machine Learning and Systems_ , 2023.
  * Zhang & Dietterich (1995) Zhang, W. and Dietterich, T. G.  A reinforcement learning approach to job-shop scheduling.  In _IJCAI_ , volume 95, pp. 1114–1120. Citeseer, 1995.
  * Zhao et al. (2022) Zhao, Y., Wang, L., Yang, K., Zhang, T., Guo, T., and Tian, Y.  Multi-objective optimization by learning space partition.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=FlwzVjfMryn.
  * Zhou et al. (2020) Zhou, Y., Roy, S., Abdolrashidi, A., Wong, D., Ma, P., Xu, Q., Liu, H., Phothilimtha, P., Wang, S., Goldie, A., et al.  Transferable graph optimizers for ml compilers.  _Advances in Neural Information Processing Systems_ , 33:13844–13855, 2020.

##  Appendix A Proofs

See 4.2

###### Proof.

Since the dataset is a $\epsilon/L$-cover, for any ${\bm{y}}\in Y$, there
exists at least one ${\bm{y}}_{i}$ so that
$\|{\bm{y}}-{\bm{y}}_{i}\|_{2}\leq\epsilon/L$. Let ${\bm{y}}_{\mathrm{nn}}$ be
the nearest neighbor of ${\bm{y}}$, and we have:

$\|{\bm{y}}-{\bm{y}}_{\mathrm{nn}}\|_{2}\leq\|{\bm{y}}-{\bm{y}}_{i}\|_{2}\leq\epsilon/L$
(8)

From the Lipschitz condition and the definition of 1-nearest-neighbor
classifier ($\hat{\bm{\phi}}({\bm{y}})=\bm{\phi}({\bm{y}}_{\mathrm{nn}})$), we
know that

$\|\bm{\phi}({\bm{y}})-\hat{\bm{\phi}}({\bm{y}})\|_{2}=\|\bm{\phi}({\bm{y}})-\bm{\phi}({\bm{y}}_{\mathrm{nn}})\|_{2}\leq
L\|{\bm{y}}-{\bm{y}}_{\mathrm{nn}}\|_{2}\leq\epsilon$ (9)

∎

See 4.3

###### Proof.

We prove by contradiction. If $N<N_{0}(\epsilon)$, then for each training
sample $({\bm{y}}_{i},\bm{\phi}_{i})$, we create a ball
$B_{i}:=B\left({\bm{y}}_{i},\epsilon/L\right)$. Since

$\mathrm{vol}\left(\bigcup_{i=1}^{N}B_{i}\cap
Y\right)\leq\mathrm{vol}\left(\bigcup_{i=1}^{N}B_{i}\right)\leq\sum_{i=1}^{N}\mathrm{vol}(B_{i})=N\mathrm{vol}_{0}\left(\frac{\epsilon}{L}\right)^{d}<\mathrm{vol}(Y)$
(10)

Therefore, there exists at least one ${\bm{y}}\in Y$ so that ${\bm{y}}\notin
B_{i}$ for any $1\leq i\leq N$. This means that ${\bm{y}}$ is not
$\epsilon/L$-covered. ∎

See 4.4

###### Proof.

Let $R_{1},R_{2},\ldots,R_{K}$ be the $K=\kappa(\bm{\phi}(Y))$ connected
components of $\bm{\phi}(Y)$, and $Y_{1},Y_{2},\ldots,Y_{J}$ be the
$J=\kappa(Y)$ connected components of $Y$. From the condition, we know that
$\min_{k\neq k^{\prime}}\mathrm{dist}(R_{k},R_{k^{\prime}})=d_{\min}>0$.

We have $R_{k}\cap R_{k^{\prime}}=\emptyset$ for $k\neq k^{\prime}$. Each
$R_{k}$ has a pre-image $S_{k}:=\bm{\phi}^{-1}(R_{k})\subseteq Y$. These pre-
images $\\{S_{k}\\}_{k=1}^{K}$ form a partition of $Y$ since

  * •

$S_{k}\cap S_{k^{\prime}}=\emptyset$ for $k\neq k^{\prime}$ since any
${\bm{y}}\in Y$ cannot be mapped to more than one connected components;

  * •

$\bigcup_{k=1}^{K}S_{k}=\bigcup_{k=1}^{K}\bm{\phi}^{-1}(R_{k})=\bm{\phi}^{-1}\left(\bigcup_{k=1}^{K}R_{k}\right)=\bm{\phi}^{-1}(\bm{\phi}(S))=S$.

Since $K=\kappa(\bm{\phi}(Y))>\kappa(Y)$, by pigeonhole principle, there
exists one $Y_{j}$ that contains at least part of the two pre-images $S_{k}$
and $S_{k^{\prime}}$ with $k\neq k^{\prime}$. This means that

$S_{k}\cap Y_{j}\neq\emptyset,\quad S_{k^{\prime}}\cap Y_{j}\neq\emptyset$
(11)

Then we pick ${\bm{y}}\in S_{k}\cap Y_{j}$ and ${\bm{y}}^{\prime}\in
S_{k^{\prime}}\cap Y_{j}$. Since ${\bm{y}},{\bm{y}}^{\prime}\in Y_{j}$ and
$Y_{j}$ is a connected component, there exists a continuous path
$\gamma:[0,1]\mapsto Y_{j}$ so that $\gamma(0)={\bm{y}}$ and
$\gamma(1)={\bm{y}}^{\prime}$. Therefore, we have $\bm{\phi}(\gamma(0))\in
R_{k}$ and $\bm{\phi}(\gamma(1))\in R_{k^{\prime}}$. Let
$t_{0}:=\sup\\{t:t\in[0,1],\bm{\phi}(\gamma(t))\in R_{k}\\}$, then $0\leq
t_{0}<1$. For any sufficiently small $\epsilon>0$, we have:

  * •

By the definition of $\sup$, we know there exists $t_{0}-\epsilon\leq
t^{\prime}\leq t_{0}$ so that $\bm{\phi}(\gamma(t^{\prime}))\in R_{k}$.

  * •

Picking $t^{\prime\prime}=t_{0}+\epsilon<1$, then
$\bm{\phi}(\gamma(t^{\prime\prime}))\in R_{k^{\prime\prime}}$ with some
$k^{\prime\prime}\neq k$.

On the other hand, by continuity of the curve $\gamma$, there exists a
constant $C(t_{0})$ so that
$\|\gamma(t^{\prime})-\gamma(t^{\prime\prime})\|_{2}\leq
C(t_{0})\|t^{\prime}-t^{\prime\prime}\|_{2}\leq 2C(t_{0})\epsilon$. Then we
have

$L=\max_{{\bm{y}},{\bm{y}}^{\prime}\in
Y}\frac{\|\bm{\phi}({\bm{y}})-\bm{\phi}({\bm{y}}^{\prime})\|_{2}}{\|{\bm{y}}-{\bm{y}}^{\prime}\|_{2}}\geq\frac{\|\bm{\phi}(\gamma(t^{\prime}))-\bm{\phi}(\gamma(t^{\prime\prime}))\|_{2}}{\|\gamma(t^{\prime})-\gamma(t^{\prime\prime})\|_{2}}\geq\frac{d_{\min}}{2C(t_{0})\epsilon}\rightarrow+\infty$
(12)

∎

##  Appendix B Experiment Details

###  B.1 Setups

Experiments are performed on a cluster of identical machines, each with 4
Nvidia A100 GPUs and 32 CPU cores, with 1T of RAM and 40GB of GPU memory.
Additionally, we perform all operations in Python (Van Rossum & Drake, 2009)
using Pytorch (Paszke et al., 2019). For embedding table placement, the
nonlinear cost estimator is trained for 200 iterations and the offline-trained
models of Dreamshard and SurCo-prior are trained against the pretrained cost
estimator for 200 iterations. The DLRM Dataset (Naumov et al., 2019) is
available at https://github.com/facebookresearch/dlrm_datasets, and the
dreamshard (Zha et al., 2022b) code is available at
https://github.com/daochenzha/dreamshard. Additional details on dreamshard’s
model architecture and features can be obtained in the paper and codebase.
Training time for the networks used in SurCo-prior and SurCo-hybrid are on
average 8 hours for the inverse photonic design settings and 6, 21, 39, 44,
50, 63 minutes for DLRM 10, 20, 30, 40, 50, 60 settings respectively.

###  B.2 Network Architectures

####  B.2.1 Embedding Table Sharding

The table features are the same used in (Zha et al., 2022b), and sinusoidal
positional encoding (Vaswani et al., 2017) is used as device features so that
the learning model is able to break symmetries between the different tables
and effectively group them onto homogeneous devices. The table and device
features are concatenated and then fed into Dreamshard’s initial fully-
connected table encoding module to obtain scalar predictions $\hat{c}{}_{t,d}$
for each desired objective coefficient. The architecture is trained with the
Adam optimizer with learning rate 0.0005. Here, we use the dreamshard backbone
to predict coefficients for each table-device pair. We add more output
dimensions to the dreamshard backbone, ensuring that we output the desired
number of coefficients.

####  B.2.2 Inverse Photonic Design

Network architectures. The input design specification (a 2D image) is passed
through a 3 layer convolutional neural network with ReLU activations and a
final layer composed of filtering with the known brush shape. Then a tanh
activation is used to obtain surrogate coefficients $\hat{\bm{c}}$, one
component for each binary input variable. The architecture is trained with the
Adam optimizer with learning rate 0.001.

This is motivated by previous work (Schubert et al., 2022) that also uses the
fixed brush shape filter and tanh operation to transform the latent parameters
into a continuous solution that is projected onto the space of physically
feasible solutions.

In each setting, optimization is done on a binary grid of different sizes to
meet fabrication constraints, namely that a 3 by 3 cross must fit inside each
fixed and void location. In the beam splitter the design is an $80\times 60$
grid, in mode converter it is a $40\times 40$ grid, in waveguide bend it is a
$40\times 40$ grid, in wavelength division multiplexer it is an $80\times 80$
grid.

Task | Randomization
---|---
mode converter | randomize the right and left waveguide width
bend setting | randomize the waveguide width and length
beam splitter | randomize the waveguide separation, width and length
wavelength division multiplexer | randomize the input and output waveguide locations
Table 3: Task randomization of 4 different tasks in inverse photonic design.

Previous work formulated the projection as finding a discrete solution that
minimized the dot product of the input continuous solution and proposed
discrete solution. The authors then updated the continuous solution by
computing gradients of the loss with respect to the discrete solution and
using pass-through gradients to update the continuous solution. By comparison,
our approach treats the projection as an optimization problem and updates the
objective coefficients so that the resulting projected solution moves in the
direction of the desired gradient.

To compute the gradient of this blackbox projection solver, we leverage the
approach suggested by (Pogančić et al., 2019) which calls the solver twice,
once with the original coefficients, and again with coefficients that are
perturbed in the direction of the incoming solution gradient as being an
“improved solution”. The gradient with respect to the input coefficients are
then the difference between the “improved solution” and the solution for the
current objective coefficients.

##  Appendix C Pseudocode

Here is the pseudocode for the different variants of our algorithm. Each of
these leverage a differentiable optimization solver to differentiate through
the surrogate optimization problem.

Algorithm 1 SurCo-zero

Input: feasible region $\Omega{}$, data ${\bm{y}}$, objective $f$

${\bm{c}}\leftarrow$ init_surrogate_coefs$({\bm{y}})$

while not converged do

${\bm{x}}\leftarrow\arg\min_{{\bm{x}}\in\Omega({\bm{y}})}{\bm{c}}^{\top}{\bm{x}}$

loss $\leftarrow f({\bm{x}};{\bm{y}})$

${\bm{c}}\leftarrow$grad_update$({\bm{c}},\nabla_{{\bm{c}}}\text{loss})$

end while

Return ${\bm{x}}$

Algorithm 2 SurCo-prior Training

Input: feasible region $\Omega{}$, data
$\mathcal{D}_{\mathrm{train}}=\\{{\bm{y}}_{i}\\}_{i=1}^{N}$, objective $f$

$\theta\leftarrow$ init_surrogate_model$()$

while not converged do

Sample batch $B=\\{{\bm{y}}_{i}\\}_{i}^{k}\sim\mathcal{D}_{\mathrm{train}}$

for ${\bm{y}}\in B$ do

$\hat{{\bm{c}}}\leftarrow\hat{{\bm{c}}}({\bm{y}};\theta)$

${\bm{x}}\leftarrow\arg\min_{{\bm{x}}\in\Omega({\bm{y}})}{\bm{c}}^{\top}{\bm{x}}$

loss $\mathrel{+}=f({\bm{x}};{\bm{y}})$

end for

$\theta\leftarrow$grad_update$(\theta,\nabla_{\theta}\text{loss})$

end while

Return $\theta$

Algorithm 3 SurCo-prior Deployment

1: Input: feasible region $\Omega{}$, data
$\mathcal{D}_{\mathrm{train}}=\\{{\bm{y}}_{i}\\}_{i=1}^{N}$, objective $f$,
test instance ${\bm{y}}_{\text{test}}$

2: $\theta\leftarrow$ train SurCo-
prior$(\Omega{},\mathcal{D}_{\mathrm{train}},f)$

3: ${\bm{c}}\leftarrow\hat{{\bm{c}}}({\bm{y}};\theta)$

4:
${\bm{x}}\leftarrow\arg\min_{{\bm{x}}\in\Omega({\bm{y}})}{\bm{c}}^{\top}{\bm{x}}$

5: Return ${\bm{x}}$

Algorithm 4 SurCo-hybrid

1: Input: feasible region $\Omega{}$, data
$\mathcal{D}_{\mathrm{train}}=\\{{\bm{y}}_{i}\\}_{i=1}^{N}$, objective $f$,
test instance ${\bm{y}}_{\text{test}}$

2: $\theta\leftarrow$ train SurCo-
prior$(\Omega{},\mathcal{D}_{\mathrm{train}},f)$

3: ${\bm{c}}\leftarrow\hat{{\bm{c}}}({\bm{y}};\theta)$

4: while not converged do

5:
${\bm{x}}\leftarrow\arg\min_{{\bm{x}}\in\Omega({\bm{y}})}{\bm{c}}^{\top}{\bm{x}}$

6: loss $\leftarrow f({\bm{x}};{\bm{y}})$

7: ${\bm{c}}\leftarrow$grad_update$({\bm{c}},\nabla_{{\bm{c}}}\text{loss})$

8: end while

9: Return ${\bm{x}}$

##  Appendix D Additional Failed Baselines

##### SOGA - Single Objective Genetic Algorithm

Using PyGAD (Gad, 2021), we attempted several approaches for both table
sharding and inverse photonics settings. While we were able to obtain feasible
table sharding solutions, they underperformed the greedy baseline by $20\%$.
Additionally, they were unable to find physically feasible inverse photonics
solutions. We varied between random, swap, inversion, and scramble mutations
and used all parent selection methods but were unable to find viable
solutions.

##### DFL - A Derivative-Free Library

We could not easily integrate DFLGEN (Liuzzi et al., 2015) into our pipelines
since it operates in fortran and we needed to specify the feasible region with
python in the ceviche challenges. DFLINT works in python but took more than 24
hours to run on individual instances which reached a timeout limit. We found
that the much longer runtime made this inapplicable for the domains of
interest.

##### Nevergrad

We enforced integrality in Nevergrad (Rapin & Teytaud, 2018) using choice
variables which selected between 0 and 1. This approach was unable to find
feasible solutions for inverse photonics in less than 10 hours. For table
sharding we obtained solutions by using a choice variable for each table,
selecting one of the available devices. This approach was not able to
outperform the greedy baseline and took longer time so it was strictly
dominated by the greedy approach.

##### Solution Prediction

We made several attempts at training solution predictors for each of our
domains. We label each problem instance with the best-known solution obtained
(including those obtained via SurCo). Note that predicting feasible solutions
to combinatorial optimization problems is nontrivial for general settings.

We evaluate solution prediction architectures in each setting. The models here
match the architecture of SurCo-prior but the output is fed through a sigmoid
transformation to get predictions in [0,1]. In nonlinear shortest path we use
a GCN architecture and predict [0,1] whether edges are in the shortest s-t
path. Not surprisingly, we found that predicting solutions to combinatorial
problems is a nontrivial problem, further motivating the use of SurCo which
ensures combinatorial feasibility of the generated solution.

Note that the solutions predicted by the networks may not be binary (and thus
not feasible). We then round the individual decision variables to get binary
predictions. Empirically, we found that our predictions are very close to
binary, indicating that rounding is more a numerical exactness operation than
an algorithmic decision, with the largest distance from any original to
rounded value being 0.0008 for inverse photonics, 0.0001 for nonlinear
shortest path, and 0.0007 for the assignment problem of table sharding.

We evaluate the results on unseen test instances in Table 4 and find that
these solution prediction approaches don’t yield combinatorially feasible
solutions. We present machin learning performance in the table below to verify
that the predictive models perform “well” in terms of standard machine
learning evaluation even though they fail to generate feasible solutions.

Setting | Decision Variable Accuracy Average | Solution Accuracy | Solution Feasibility Rate
---|---|---|---
Inverse Photonics - Sigmoid | 87% | 0% | 0%
Nonlinear Shortest Path - Sigmoid | 95% | 0% | 0%
Table Sharding - Sigmoid | 92% | 0% | 0%
Table Sharding - Softmax | 88% | 0% | 0%
Table Sharding - Softmax + Iterative | 70% | 0% | 100%
Table 4: Solution prediction results, most methods give infeasible solutions. Setting | % Latency Increase vs Domain Heuristic (worst baseline)
---|---
DLRM-10 | 6%
DLRM-20 | 5%
DLRM-30 | 9%
DLRM-40 | 7%
DLRM-50 | 3%
DLRM-60 | 11%
Table 5: Comparison of only feasible solution prediction method against worst
baseline.

We also iterate on table sharding to produce two more domain-specific
approaches. We evaluate a model variant which assigns each table into one of
the 4 devices using softmax, which empirically fails to yield feasible
solutions that meet device memory limits for any of our instances. We further
develop a method called Softmax + Iterative which iteratively assigns the most
likely table-device assignment as long as the device has enough memory to hold
the device. Luckily, this Softmax + Iterative method empirically yields
feasible solutions in this setting but we note that this approach is not
guaranteed to terminate in feasible solutions, unlike SurCo. To see why
Softmax + Iterative does not necessarily guarantee feasible termination,
consider assigning 3 tables (2 small and 1 large) to 2 devices each with
memory limit of 2, the small tables have memory 1 and the large table has
memory 2. If the model’s highest assignment probability is on the small tables
being evenly distributed across devices, the algorithm will first assign the
small tables to devices 1 and 2 but stall because it is unable to assign the
large table since neither device has enough remaining capacity. We present
results for this Softmax + Iterative approach compared to our domain heuristic
which is the worst performing baseline in Table 5.

For each setting, we evaluate the three metrics:

  * •

Decision Variable Accuracy Average, is the average percent of variables which
are correctly predicted.

  * •

The solution accuracy, is the rate of predicting the full solution correctly
(all decision variables predicted correctly).

  * •

The solution feasibility rate, is the percent of instances for which the
predicted solution satisfies the constraints.


SRT3D: A Sparse Region-Based 3D Object Tracking Approach for the Real World

Manuel Stoiber Martin Pfanne Klaus H. Strobl Rudolph Triebel Alin Albu-Schäffer

M. Stoiber German Aerospace Center, 82234 Wessling, Germany

Technical University of Munich, 80333 Munich, Germany

M. Pfanne German Aerospace Center, 82234 Wessling, Germany

K. H. Strobl German Aerospace Center, 82234 Wessling, Germany

R. Triebel German Aerospace Center, 82234 Wessling, Germany

Technical University of Munich, 80333 Munich, Germany

A. Albu-Schäffer German Aerospace Center, 82234 Wessling, Germany

Technical University of Munich, 80333 Munich, Germany

International Journal of Computer Vision
This is a pre-peer review, pre-print version of the article

ICP[ICP]Iterative Closest Point
PDF[PDF]probability density function
AUC[AUC]area under curve
OPT[OPT]Object Pose Tracking
RBOT[RBOT]Region-Based Object Tracking
6DoF[6DoF]six degrees of freedom
SLAM[SLAM]Simultaneous Localization and Mapping
CNN[CNN]convolutional neural network

[Besl and McKay, 1992]
Besl PJ, McKay ND (1992) A method for registration of 3-D shapes. IEEE
Transactions on Pattern Analysis and Machine Intelligence 14(2):239–256

[Bibby and Reid, 2008]
Bibby C, Reid I (2008) Robust real-time visual tracking using pixel-wise
posteriors. In: European Conference on Computer Vision, pp 831–844

[Brachmann et al., 2016]
Brachmann E, Michel F, Krull A, Yang MY, Gumhold S, Rother C (2016)
Uncertainty-driven 6D pose estimation of objects and scenes from a single
RGB image. In: IEEE Conference on Computer Vision and Pattern Recognition,
pp 3364–3372

[Brox et al., 2010]
Brox T, Rosenhahn B, Gall J, Cremers D (2010) Combined region and
motion-based 3D tracking of rigid and articulated objects. IEEE
Transactions on Pattern Analysis and Machine Intelligence 32(3):402–415

[Bugaev et al., 2018]
Bugaev B, Kryshchenko A, Belov R (2018) Combining 3D model contour energy and
keypoints for object tracking. In: European Conference on Computer Vision, pp

[Comport et al., 2006]
Comport AI, Marchand E, Pressigout M, Chaumette F (2006) Real-time
markerless tracking for augmented reality: The virtual visual servoing
framework. IEEE Transactions on Visualization and Computer Graphics

[Crivellaro and Lepetit, 2014]
Crivellaro A, Lepetit V (2014) Robust 3D tracking with descriptor fields.
In: IEEE Conference on Computer Vision and Pattern Recognition, pp 3414–3421

[Dambreville et al., 2008]
Dambreville S, Sandhu R, Yezzi A, Tannenbaum A (2008) Robust 3D pose
estimation and efficient 2D region-based segmentation from a 3D shape
prior. In: European Conference on Computer Vision, pp 169–182

[Deng et al., 2021]
Deng X, Mousavian A, Xiang Y, Xia F, Bretl T, Fox D (2021) PoseRBPF: A
Rao–Blackwellized particle filter for 6-D object pose tracking. IEEE
Transactions on Robotics 37(5):1328–1342

[Drummond and Cipolla, 2002]
Drummond T, Cipolla R (2002) Real-time visual tracking of complex
structures. IEEE Transactions on Pattern Analysis and Machine Intelligence

[Engel et al., 2018]
Engel J, Koltun V, Cremers D (2018) Direct sparse odometry. IEEE
Transactions on Pattern Analysis and Machine Intelligence 40(3):611–625

[Garon and Lalonde, 2017]
Garon M, Lalonde JF (2017) Deep 6-DOF tracking. IEEE Transactions on
Visualization and Computer Graphics 23(11):2410–2418

[Harris and Stennett, 1990]
Harris C, Stennett C (1990) RAPID - A video rate object tracker. In:
Proceedings of the British Machine Vision Conference, pp 15.1–15.6

[Hexner and Hagege, 2016]
Hexner J, Hagege RR (2016) 2D-3D pose estimation of heterogeneous objects
using a region based approach. International Journal of Computer Vision

[Hinterstoisser et al., 2013]
Hinterstoisser S, Lepetit V, Ilic S, Holzer S, Bradski G, Konolige K, Navab N
(2013) Model based training, detection and pose estimation of texture-less
3D objects in heavily cluttered scenes. In: Asian Conference on Computer
Vision, pp 548–562

[Huang et al., 2020]
Huang H, Zhong F, Sun Y, Qin X (2020) An occlusion-aware edge-based method for
monocular 3d object tracking using edge confidence. Computer Graphics Forum

[Kehl et al., 2017]
Kehl W, Tombari F, Ilic S, Navab N (2017) Real-time 3D model tracking in
color and depth on a single CPU core. In: IEEE Conference on Computer
Vision and Pattern Recognition, pp 465–473

[Krainin et al., 2011]
Krainin M, Henry P, Ren X, Fox D (2011) Manipulator and object tracking for
in-hand 3D object modeling. International Journal of Robotics Research

[Krull et al., 2015]
Krull A, Michel F, Brachmann E, Gumhold S, Ihrke S, Rother C (2015) 6-DOF
model based tracking via object coordinate regression. In: Asian Conference
on Computer Vision, pp 384–399

[Lankton and Tannenbaum, 2008]
Lankton S, Tannenbaum A (2008) Localizing region-based active contours.
IEEE Transactions on Image Processing 17(11):2029–2039

[Lepetit and Fua, 2005]
Lepetit V, Fua P (2005) Monocular Model-Based 3D Tracking of Rigid Objects:
A Survey, vol 1. Foundations and Trends in Computer Graphics and Vision

[Leutenegger et al., 2011]
Leutenegger S, Chli M, Siegwart RY (2011) BRISK: Binary robust
invariant scalable keypoints. In: IEEE International Conference on Computer
Vision, pp 2548–2555

[Li et al., 2021]
Li JC, Zhong F, Xu SH, Qin XY (2021) 3D object tracking with adaptively
weighted local bundles. Journal of Computer Science and Technology

[Li et al., 2018]
Li Y, Wang G, Ji X, Xiang Y, Fox D (2018) DeepIM: Deep iterative matching
for 6D pose estimation. In: European Conference on Computer Vision, pp

[Liu et al., 2021]
Liu F, Wei Z, Zhang G (2021) An off-board vision system for relative attitude
measurement of aircraft. IEEE Transactions on Industrial Electronics

[Liu et al., 2020]
Liu Y, Sun P, Namiki A (2020) Target tracking of moving and rotating
object by high-speed monocular active vision. IEEE Sensors Journal

[Lowe, 2004]
Lowe DG (2004) Distinctive image features from scale-invariant keypoints.
International Journal of Computer Vision 60(2):91–110

[Lucas and Kanade, 1981]
Lucas BD, Kanade T (1981) An iterative image registration technique with an
application to stereo vision. In: Proceedings of the 7th International Joint
Conference on Artificial Intelligence, vol 2, pp 674–679

[Mur-Artal and Tardós, 2017]
Mur-Artal R, Tardós JD (2017) ORB-SLAM2: An open-source SLAM system
for monocular, stereo, and RGB-D cameras. IEEE Transactions on Robotics

[Pauwels et al., 2013]
Pauwels K, Rubio L, Díaz J, Ros E (2013) Real-time model-based rigid
object pose estimation and tracking combining dense and sparse visual cues.
In: IEEE Conference on Computer Vision and Pattern Recognition, pp 2347–2354

[Prisacariu and Reid, 2012]
Prisacariu VA, Reid ID (2012) PWP3D: Real-time segmentation and tracking of
3D objects. International Journal of Computer Vision 98(3):335–354

[Prisacariu et al., 2015]
Prisacariu VA, Kähler O, Murray DW, Reid ID (2015) Real-time 3D tracking and
reconstruction on mobile phones. IEEE Transactions on Visualization and
Computer Graphics 21(5):557–570

[Ren et al., 2017]
Ren CY, Prisacariu VA, Kähler O, Reid ID, Murray DW (2017) Real-time
tracking of single and multiple objects from depth-colour imagery using 3D
signed distance functions. International Journal of Computer Vision

[Rosenhahn et al., 2007]
Rosenhahn B, Brox T, Weickert J (2007) Three-dimensional shape knowledge for
joint image segmentation and pose tracking. International Journal of Computer
Vision 73(3):243–262

[Rublee et al., 2011]
Rublee E, Rabaud V, Konolige K, Bradski G (2011) ORB: An efficient
alternative to SIFT or SURF. In: IEEE International Conference on
Computer Vision, pp 2564–2571

[Sarlin et al., 2020]
Sarlin PE, DeTone D, Malisiewicz T, Rabinovich A (2020) SuperGlue:
Learning feature matching with graph neural networks. In: IEEE/CVF
Conference on Computer Vision and Pattern Recognition, pp 4937–4946

[Schmaltz et al., 2012]
Schmaltz C, Rosenhahn B, Brox T, Weickert J (2012) Region-based pose tracking
with occlusions using 3D models. Machine Vision and Applications

[Seo et al., 2014]
Seo B, Park H, Park J, Hinterstoisser S, Ilic S (2014) Optimal local
searching for fast and robust textureless 3D object tracking in highly
cluttered backgrounds. IEEE Transactions on Visualization and Computer
Graphics 20(1):99–110

[Seo and Wuest, 2016]
Seo BK, Wuest H (2016) A direct method for robust model-based 3D object
tracking from a monocular RGB image. In: European Conference on Computer
Vision Workshop, pp 551–562

[Stoiber et al., 2020]
Stoiber M, Pfanne M, Strobl KH, Triebel R, Albu-Schaeffer A (2020) A sparse
gaussian approach to region-based 6DoF object tracking. In: Asian
Conference on Computer Vision, pp 666–682

[Sun et al., 2021]
Sun X, Zhou J, Zhang W, Wang Z, Yu Q (2021) Robust monocular pose
tracking of less-distinct objects based on contour-part model. IEEE
Transactions on Circuits and Systems for Video Technology

[Tan et al., 2017]
Tan DJ, Navab N, Tombari F (2017) Looking beyond the simple scenarios:
Combining learners and optimizers in 3D temporal tracking. IEEE
Transactions on Visualization and Computer Graphics 23(11):2399–2409

[Tjaden et al., 2018]
Tjaden H, Schwanecke U, Schömer E, Cremers D (2018) A region-based
Gauss-Newton approach to real-time monocular multiple object tracking. IEEE
Transactions on Pattern Analysis and Machine Intelligence 41(8):1797–1812

[Vacchetti et al., 2004]
Vacchetti L, Lepetit V, Fua P (2004) Stable real-time 3D tracking using
online and offline information. IEEE Transactions on Pattern Analysis and
Machine Intelligence 26(10):1385–1391

[Wagner et al., 2010]
Wagner D, Reitmayr G, Mulloni A, Drummond T, Schmalstieg D (2010)
Real-time detection and tracking for augmented reality on mobile phones. IEEE
Transactions on Visualization and Computer Graphics 16(3):355–368

[Wang et al., 2019]
Wang C, Xu D, Zhu Y, Martín-Martín R, Lu C, Fei-Fei L, Savarese
S (2019) DenseFusion: 6D object pose estimation by iterative dense
fusion. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition,
pp 3338–3347

[Wen et al., 2020]
Wen B, Mitash C, Ren B, Bekris KE (2020) se(3)-TrackNet: Data-driven 6D
pose tracking by calibrating image residuals in synthetic domains. In:
IEEE/RSJ International Conference on Intelligent Robots and Systems, pp

[Whelan et al., 2015]
Whelan T, Leutenegger S, Moreno RS, Glocker B, Davison A (2015)
ElasticFusion: Dense SLAM without a pose graph. In: Robotics: Science
and Systems

[Wu et al., 2017]
Wu PC, Lee YY, Tseng HY, Ho HI, Yang MH, Chien SY (2017) A benchmark dataset
for 6DoF object pose tracking. In: IEEE International Symposium on Mixed
and Augmented Reality, pp 186–191

[Xiang et al., 2018]
Xiang Y, Schmidt T, Narayanan V, Fox D (2018) PoseCNN: A convolutional
neural network for 6D object pose estimation in cluttered scenes. In:
Robotics: Science and Systems

[Yi et al., 2016]
Yi KM, Trulls E, Lepetit V, Fua P (2016) LIFT: Learned invariant feature
transform. In: European Conference on Computer Vision, pp 467–483

[Yilmaz et al., 2006]
Yilmaz A, Javed O, Shah M (2006) Object tracking: A survey. ACM Computing
Surveys 38(4):13

[Zhao et al., 2014]
Zhao S, Wang L, Sui W, Wu H, Pan C (2014) 3D object tracking via
boundary constrained region-based model. In: IEEE International Conference on
Image Processing, pp 486–490

[Zhong and Zhang, 2019]
Zhong L, Zhang L (2019) A robust monocular 3D object tracking method
combining statistical and photometric constraints. International Journal of
Computer Vision 127(8):973–992

[Zhong et al., 2020]
Zhong L, Zhang Y, Zhao H, Chang A, Xiang W, Zhang S, Zhang L
(2020a) Seeing through the occluders: Robust monocular 6-DOF
object pose tracking via model-guided video object segmentation. IEEE
Robotics and Automation Letters 5(4):5159–5166

[Zhong et al., 2020]
Zhong L, Zhao X, Zhang Y, Zhang S, Zhang L (2020b)
Occlusion-aware region-based 3D pose tracking of objects with temporally
consistent polar-based local partitioning. IEEE Transactions on Image
Processing 29:5065–5078