# Automated Camera Calibration via Homography Estimation with GNNs

Giacomo D’Amicantonio, Egor Bondarev, Peter H.N. De With
Eindhoven University of Technology
{ g.d.amicantonio, e.bondarau, p.h.n.de.with } @tue.nl

###### Abstract

Over the past few decades, a significant rise of camera-based applications for
traffic monitoring has occurred. Governments and local administrations are
increasingly relying on the data collected from these cameras to enhance road
safety and optimize traffic conditions. However, for effective data
utilization, it is imperative to ensure accurate and automated calibration of
the involved cameras. This paper proposes a novel approach to address this
challenge by leveraging the topological structure of intersections.

We propose a framework involving the generation of a set of synthetic
intersection viewpoint images from a bird’s-eye-view image, framed as a graph
of virtual cameras to model these images. Using the capabilities of Graph
Neural Networks, we effectively learn the relationships within this graph,
thereby facilitating the estimation of a homography matrix. This estimation
leverages the neighbourhood representation for any real-world camera and is
enhanced by exploiting multiple images instead of a single match. In turn, the
homography matrix allows the retrieval of extrinsic calibration parameters. As
a result, the proposed framework demonstrates superior performance on both
synthetic datasets and real-world cameras, setting a new state-of-the-art
benchmark.

##  1 Introduction

(a)

(b)

(c)

(d)

(e)

(f)

Figure 1: Intersection images from [8]. Bird’s-eye-views of the semantical
segmentations of the intersections: Red = road, Blue = terrain and Green =
bicycle path. The intersections differ in the complexity of their topology.
Semantic segmentation of the soccer field: Red = goal box, penalty arc and
center circle, Blue = penalty box, Green = rest of the pitch.

Camera calibration is a crucial aspect of computer vision (CV) applications,
enabling the mapping of pixels to real-world coordinates. It serves as a
prerequisite for various CV tasks, including object localization and immersive
imaging. While calibrating cameras with a checkerboard pattern is now
considered straightforward, this method is not always practical in real-world
scenarios, especially when dealing with traffic-control cameras which are
placed in busy intersections or in highways. These cameras are typically
mounted on light posts and traffic lights, making them susceptible to slight
movements caused by environmental factors and movement of large vehicles.
Consequently, the original camera calibration may be affected by these
movements, necessitating frequent and automated re-calibration. However,
accessing these cameras in person is often unfeasible because of their
locations at intersections or highways. While deep learning techniques have
been explored to address this problem, they often demand substantial data and
computational resources, posing limitations for startups and small companies.
As of today, there is no industry standard for achieving cost-effective,
accurate, and reliable automated camera calibration. To this end, this paper
introduces a homography estimation approach that can be easily trained on
synthetic data and performs effectively in real-world settings.
The proposed method leverages the topological structure of intersections by
creating a graph of synthetic templates from virtual cameras. Each template is
generated by warping the bird’s-eye-view (BEV) of the scene with a homography
derived from each virtual camera. Using this graph, we find the best match
between the camera image and a set of synthetic templates. This matching
process is framed as a link-prediction task, executed by a Graph Neural
Network (GNN) [11, 29].
The proposed model predicts a probability score to select the top-k closest
matches for the input image. The embeddings learned by the GNN are then
processed to regress a homography that transforms the input image to the
highest scoring template, whose homography serves as the anchor. The
homography estimation is performed by a Spatial Transformer Network (STN)
[15].
Notably, this framework has two advantages. First, it estimates the homography
between an image and the BEV by leveraging multiple views of the scene, rather
than relying on a single image. Second, the framework is more computationally
efficient than previous approaches, while outperforming them on synthetic
datasets and real-world cameras. To the best of our knowledge, this is the
first work to explore the use of GNNs for homography estimation.
The paper structure is as follows. Section 2 provides an overview of current
camera calibration approaches and the literature on Graph Neural Networks.
Section 3 details the models and the designed pipeline. The results on
multiple intersections and five real-world cameras are presented in Section 4.
Finally, Section 5 concludes the paper and indicates potential future work.

Figure 2: Example of the synthetic training and dictionary images. It is
relevant to notice that in the second hop there can be images that are not
visually similar to the training images or the representation of the
corresponding part of the scene. Figure 3: Reduced representation of a sub-
graph of the generated graph. Each node represents an image and is connected
to the 20 dictionary nodes with the lowest Topological Loss score. Figure 4:
Overview of the proposed framework. In the first part, the features obtained
from the nodes (images) in the sampled sub-graph are fed to the GAT network
with the adjecency matrix of the links. The GAT produces embeddings for each
node and predicts a score for each link. The top-k scoring links for each
training (or testing) nodes are then processed by the STN to estimate the
homography $\bar{\mathbf{H}}$.

##  2 Related Work

###  2.1 Camera Calibration

Homography estimation typically involves exploitation of various image
features and characteristics. The approaches mentioned in related work [21, 2,
4, 35, 22, 27, 31] extract and match these features in images and then
estimate the homography matrix via Direct Linear Transformation (DLT) [13]. To
handle erroneous matches, outlier detectors like RANSAC [10] or the more
recent MAGSAC, [1] are employed. However, these methods are not tailored
specifically for traffic scenes and lack full automation.
In recent years, deep learning-based approaches have emerged as a powerful
alternative. DeTone _et al_. [7] were among the first to propose a simple end-
to-end network for direct homography estimation. Subsequent works have built
further upon this foundation, using deeper and more complex networks to
achieve better performance [9, 18, 36]. The introduction of the Spatial
Transformer Network (STN) [15] sparked the development of new approaches, such
as the works in [25, 30, 8]. Addressing automated camera calibration, Bhardwaj
_et al_. [3] presented a prominent method which exploits the presence of
vehicles on the road, by employing vehicle-detection techniques, key-point
extractors, and prior knowledge of the vehicle’s geometrical properties.
Another significant work in this area is reported in [37], where the authors
propose two camera calibration methods. One method optimizes an energy
function to minimize the 3D re-projection error, while the other leverages
synthetic data. It is worth noting that although the mentioned approaches have
shown success in various settings, none of them are specifically designed to
handle the challenges unique to traffic scenes, _i.e_. the amount of vehicles
in the scene and varying weather conditions.

###  2.2 Graph Neural Networks

Since their introduction in [11, 29], Graph Neural Networks (GNNs) have
demonstrated promising results in various tasks, involving graph-structured
data. For instance, in [17], Graph Convolutional Networks (GCNs) are employed
for graph-level and node-level classification. Kipf and Welling [16] proposed
an auto-encoder version of GNN for unsupervised link prediction. Over the
years, GNNs have been employed for tasks such as nearest-neighbour estimation
[23] and sentiment analysis [20]. Recent years have shown a growing interest
in exploring the application of GNNs in image and video-related tasks. The
graph embeddings learned by GNNs have facilitated various downstream tasks,
including pose estimation [26, 24] and object detection [19]. In [34], the key
points of an image are treated as nodes in a graph, with links connecting
them, and a GNN model is trained to match these key points. Similarly, in
[28], graphs representing key points are used for image matching. The
successes of GNNs in image-related tasks have inspired us to apply this
approach to the specific problem of automated camera calibration in traffic
scenes. By constructing a graph of synthetic templates based on the
topological structure of intersections, we train a GNN model to perform
homography estimation. The use of GNNs sets our work apart from previous
approaches and allows accurate automated camera calibration in traffic
monitoring scenarios.

Figure 5: Overview of the embedding generation process. The features of all
nodes in the mini-batch are generated by the feature extractor. The positive
links are the links between each training node and its dictionary nodes in the
mini-batch, while the negative links are all the links between training nodes
and the other dictionary nodes. Merging positive and negative links creates
the matrix of all possible links in the mini-batch. The GAT produces
embeddings for each node and probability scores for the links, the latter
being used to train both models via Equation (1).

##  3 Method

The proposed framework leverages a GNN to match the input image with a
dictionary of templates, assigning a score to all possible links. A Spatial
Transformer Network (STN) estimates the homography transformation between the
highest scoring template and the input image from the embeddings generated by
the GNN. The images and the templates are generated, starting from the
manually segmented bird’s-eye-view (BEV) of the intersection. Whereas we train
the framework only on synthetic images, its performance is evaluated on a test
set of synthetic images and on five real-world cameras placed in Intersection
3 (see Figure 1(c)).

###  3.1 Data Generation

Following the approach described in [30] and [8], we generate virtual cameras
by randomly sampling intrinsic and extrinsic parameters from a grid. The
semantically segmented BEV of the scene, shown in Figure 1, is warped with the
homography matrices of these virtual cameras, resulting in a set of
approximately 20,000 images per scene. To create the training and testing
splits, images are randomly sampled from the generated set, with an equal
distribution among the two splits. Additionally, a dictionary split is sampled
containing images to be leveraged as anchors for the final homography
estimation task, following [30]. Each split forms a graph, where each image
corresponds to a node connected to the top-k most similar images in the
dictionary (empirically, k=20). The similarity score between images can be
calculated using similarity metrics, such as Topological Loss [8]. During both
training and testing, nodes from the respective graph are sampled to construct
mini-batches. As illustrated in Figure 3, for each node in a mini-batch, we
also sample a number of its neighbours at a 2-hop distance, following the
approach presented in [12]. However, we discard all nodes in the second hop
that are not part of the dictionary to prevent any cross-contamination between
splits. As shown in Figure 2, the images in the second hop can be visually
different from the training image, or representing a different part of the
intersection.

###  3.2 Matching Process

In our approach, a light-weight feature extractor derives a feature vector
from each image. In addition to the feature vectors, a matrix is constructed
containing all possible links between nodes in the mini-batch. Both the
feature vectors and the matrix of links serve as inputs to a Graph Attention
Network (GAT) to perform the matching task. The GAT model has been proposed in
[5] and represents an improvement over the preceding design reported in [32].
GATs follow the same principles as GCNs, but with a key difference in the way
they handle neighbourhood features. While a standard GCN normalizes node
features across neighbours during the convolutional operation, a GAT employs a
masked attention mechanism to compute attention coefficients between nodes
within the same neighbourhood, thereby preserving important structural
information.
The feature extractor and the GAT are trained jointly, allowing the former to
learn meaningful representations of the original images for the latter. The
training loss function used for the GAT is the conventional Binary Cross-
Entropy, defined as:

$L_{GAT}=-\sum_{n=0}^{N-1}{\big{(}\,y_{n}\log(p_{n})+(1-y_{n})\log(1-p_{n})\,\big{)}}.$
(1)

Here, $N$ represents the number of possible links, $y_{n}$ is the binary label
for link $n$, and $p_{n}$ is the score predicted by the GAT for that link.
This loss function ensures effective training of both the feature extractor
and the GAT for accurate and robust link prediction.
An overview of the link-prediction task is shown in Figure 5. The final
outputs of the GAT are the embeddings for every node in the batch and a score
for each possible link between these nodes.

Figure 6: Overview of the homography estimation task. For each training node,
the probability scores predicted by the GAT are needed to select the top-k
best nodes, whose embeddings are then used by the STN to predict
$\bar{\mathbf{H}}$. The homography of the node connected to a training node
via the highest scoring link is the anchor for the final estimated homography
that warps the BEV. The resulting warped images are employed to train end-to-
end all models via Equation 2.

###  3.3 Homography Estimation

The GAT predicts a score for every possible link between training and
dictionary nodes in the batch. The top-k scoring links for each training (or
testing) node are utilized to select the neighbours containing the most useful
information for the Spatial Transformer Network (STN). The feature vectors are
concatenated into a two-dimensional feature matrix and passed as input to the
homography estimation component. The homography of the highest-scoring
dictionary node, $\hat{\mathbf{H}}_{k}$, is the anchor for the corresponding
training (or testing) node. In fact, the STN estimates a homography that
transforms the best match found by the GNN to the target image. In other
words, the homography $\bar{\mathbf{H}}$, estimated by the STN, is multiplied
with its anchor $\mathbf{\hat{H}_{k}}$, producing the final homography
$\mathbf{H}=\mathbf{\hat{H}_{k}}\bar{\mathbf{H}}$.
The STN described in [8] is adapted to accept the embeddings produced by the
GAT. Following that work, we adopt the same training strategy: the semantic
BEV is warped by the estimated homography and the resulting warped image is
compared to the synthetic ground truth via a Topological Loss implementation
of the MSE. This is described by Equation (2), where the running indexes
$k,l\in\\{-1,0,+1\\}$ and $i,j\in\\{0,...,\sqrt{N}\\}$, while $Y$ and
$\hat{Y}$ are the ground-truth image and the warped image, respectively.

$\displaystyle\begin{split}\mathcal{L}_{\text{patch}}(\hat{Y},Y)&=\text{MSE}(\hat{Y}_{i,j},Y_{i,j})+\\\
&\alpha\sum_{k}\sum_{l}\max{(0,\text{MSE}(\hat{Y}_{i+k,j+l},Y_{i+k,j+l})-\beta}),\end{split}$
$\text{and}\ \ \mathcal{L}_{\text{Top-
MSE}}=\frac{1}{N}\sum_{i}\sum_{j}\mathcal{L}_{\text{patch}}(\hat{Y}_{i,j},Y_{i,j}).$
(2)

Table 1: Obtained IoU scores by different implementations of the proposed model, using three different GNNs and the baseline models, over the five synthetic intersection datasets and the World Cup 2014 dataset. All values (mean + std) are expressed in %. Model | Intersections | World Cup
---|---|---
| 1 | 2 | 3 | 4 | 5 | 2014
Sha _et al_. [30] | 85.96 | 78.42 | 78.99 | 83.16 | 71.95 | 81.64
D’Amicantonio _et al_. [8] | 87.91 | 87.00 | 86.66 | 84.51 | 73.75 | 84.21
Proposed 1 (GCN [17]) | 92.31$\pm$0.37 | 93.25$\pm$0.16 | 93.58$\pm$0.11 | 88.28$\pm$0.36 | 87.99$\pm$0.21 | 89.91$\pm$0.44
Proposed 2 (GAT [32]) | 95.61$\pm$0.99 |  96.57$\pm$0.68 | 93.98$\pm$1.45 | 88.89$\pm$1.2 | 96.27$\pm$0.24 | 96.89$\pm$0.7
Proposed 3 (GATv2 [5]) |  95.96$\pm$0.84 | 96.56$\pm$0.53 |  95.38$\pm$1.32 |  89.59$\pm$0.14 |  96.86$\pm$0.57 |  97.31$\pm$0.39

(a) Original image.

(b) Ground truth image.

(c) Segmented image.

(d) Warped image generated by the proposed model.

Figure 7: Visual results of segmentation and warping steps for a real-world image. The segmented image obtained from the SegFormer is less precise than the synthetic images on which the model was trained, which partially explains the drop in accuracy between testing images and real-world images. Table 2: Comparison between the proposed model with different feature extractors. All values (mean + std) are expressed in %. Model | Intersections | World Cup
---|---|---
| 1 | 2 | 3 | 4 | 5 | 2014
Proposed (GATv2 + ResNet18) | 95.13$\pm$0.13 | 95.75$\pm$0.37 | 94.45$\pm$0.17 | 87.65$\pm$0.61 | 95.97$\pm$0.07 | 95.41$\pm$0.44
Proposed (GATv2 + 4-Conv) |  95.96$\pm$0.84 |  96.56$\pm$0.53 |  95.38$\pm$1.32 |  89.59$\pm$0.14 |  96.86$\pm$0.57 |  97.31$\pm$0.39
Table 3: Average IoU scores obtained by the proposed models and the baseline models on five real-world cameras located in Intersection 3. All values (mean + std) are expressed in %. Model | Cameras
---|---
Sha _et al_. [30] | 76.44$\pm$3.56
D’Amicantonio _et al_. [8] | 81.12$\pm$2.54
Proposed 1 (GCN [17]) | 85.73$\pm$0.34
Proposed 2 (GAT [32]) | 86.48$\pm$0.85
Proposed 3 (GATv2 [5]) |  87.89$\pm$0.93

##  4 Results

###  4.1 Experimental setup

The GAT and its feature extractor are trained jointly until convergence, using
the loss for link prediction reported in Equation (1). In this way, the GAT
learns the features of the nodes and their neighbours which can be better
exploited by the STN. After this warmup period of 30 epochs, we start training
the full pipeline of feature extractor, GAT and STN, using only the loss
function in Equation (2). Therefore, the GAT may learn to choose nodes outside
the neighbourhood of the training node as more relevant for the training
objective. The IoU scores are measured between the ground-truth images and the
BEV warped with the estimated homographies to evaluate the model. If the IoU
score does not improve for 10 epochs, the learning rates of all models are
halved, and if it does not improve for a further 15 epochs the training is
stopped.
We evaluate the model on five different intersection scenes and the World Cup
2014 dataset [14]. The results shown in Table 1 are averaged over five
training cycles for each dataset and different train/test/dictionary splits
are sampled at every cycle. Table 3 validates the results by evaluating the
model performance on images obtained from five cameras located in Intersection
3. The experimental results are compared to the baselines, reported in [8] and
[30]. Furthermore, the performances are compared with the original GAT model
proposed by [32] and with a standard GCN presented in [17].

###  4.2 Ablation study

Table 1 shows that the proposed method outperforms the state-of-the-art models
with any of the three GNN networks, strongly supporting the idea of a graph-
based approach for this task. The main difference between the proposed work
and the competitors is in the way the structural information of the
intersection is leveraged. In fact, both previous works employed a Siamese
model to perform the matching task, for which the best template from the
dictionary was selected. This approach has two downsides, as listed below.

  * •

Selecting a single match is valid but not optimal: the amount and quality of
topological information that becomes available from a single match is inferior
to the information that can be extracted from multiple matches and the
relationships between them.

  * •

The Siamese network as a matching component is computationally expensive: each
input image is compared to every image in the dictionary, which places a heavy
burden on computational resources and hinders the scaling capabilities of the
model.

Framing the matching process as a link-prediction task in a graph solves both
problems, allowing us to retrieve multiple matches at a lower computational
cost. Furthermore, the GNN learns features for the nodes based on the related
visual features and the relationships between them, which gives the STN a much
richer input. Training the models end-to-end has been proven not effective in
[8], due to the design of the matching process. In this work, training all
models end-to-end provides much more flexibility to the GNN, allowing it to
discard subpar matches directly connected to the training node in favor of
other nodes in the neighbourhood that can be more relevant for the STN.
It should be noticed that the difference between the three types of GNN we
experimented with, do not show a significant difference in performance. The
GCN proves to be the least performing of the three, but it still outperforms
the current state-of-the-art by 10% on average. Moreover, the difference in
performance between GAT and GATv2 is minor.
The employed feature extractor to prepare the images for the GNN models is a
lightweight model, comprising four convolutional layers only. To prove that
such a simple model is not a bottleneck for our framework, Table 2 compares
the performances with a larger and more complex feature extractor such as
ResNet18. The larger feature extractor does not have a positive impact on the
overall performance of the model, as it is outperformed by the much simpler
model on all datasets. We conjecture that because of the much simpler nature
of the semantic images, a more complex model is harder to train due to the
higher amount of parameters.

###  4.3 Evaluation on real camera views

To validate the results obtained by the proposed model on synthetic images,
the models are executed on images obtained from five cameras located in
Intersection 3. The images are segmented by SegFormer [33], which is trained
on Cityscapes [6]. Given that Cityscapes has 30 classes while our application
only needs 4 (terrain, road, bicycle path and background), we discard or merge
the additional classes in one of the four classes. While the merging strategy
heavily depends on the individual scene, it is fair to assume that e.g. the
car class can be merged with the road class and the bicycle class with the
bicycle-path class.
In Table 3, the proposed model is compared with the previous baseline model.
With each of the three GNNs, the proposed model outperforms the baseline
models by up to 8%. It is worth noting that the segmented images are not as
precise as the synthetic images, which may cause the drop in accuracy w.r.t.
the testing dataset. Furthermore, we do not account for any distortion while
generating the synthetic images, which may be a factor for real-world cameras,
especially fish-eye cameras. As shown in Figures 7(c) and 7(b), the
segmentation obtained from the SegFormer model is not very precise in some
areas, such as the bicycle path at the right or the poles and trees at the
left. We conjecture that fine-tuning a segmentation model to discard
obstructing objects may lead to even better results with the same model. We
leave this for future work, as it is not in the scope of this paper.

##  5 Conclusions

In this work, we have proposed a homography estimation framework based on
Graph Neural Networks. It is shown that framing multiple synthetic views of an
intersection as a graph and training a GNN to learn the relationships between
them, leads to the generation of rich embeddings which can be useful to
estimate the homography of a given image. The framework is completely
automated and requires fewer computational resources and training data w.r.t.
comparable methods in literature. The proposed framework has been tested on
five different intersections, five real-world cameras and a real-world dataset
with three different types of GNNs. In all settings, the framework outperforms
the current state-of-the-art by a significant margin, proving to be also very
effective in real-world applications. In future work, it can be interesting to
focus on improving the scoring mechanism for the matches retrieved by the GNN
and refining the segmentation of camera images.

## References

  * [1] Dániel Baráth, Jana Noskova, Maksym Ivashechkin, and Jiri Matas.  Magsac++, a fast, reliable and accurate robust estimator.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 1301–1309. Computer Vision Foundation / IEEE, 2020.
  * [2] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool.  Surf: Speeded up robust features.  In Aleš Leonardis, Horst Bischof, and Axel Pinz, editors, Computer Vision – ECCV 2006, pages 404–417, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [3] Romil Bhardwaj, Gopi Krishna Tummala, Ganesan Ramalingam, Ramachandran Ramjee, and Prasun Sinha.  Autocalib: Automatic traffic camera calibration at scale.  ACM Trans. Sen. Netw., 14(3–4), nov 2018.
  * [4] Jia-Wang Bian, Wen-Yan Lin, Yun Liu, Le Zhang, Sai-Kit Yeung, Ming-Ming Cheng, and Ian Reid.  GMS: Grid-based motion statistics for fast, ultra-robust feature correspondence.  International Journal of Computer Vision (IJCV), 2020.
  * [5] Shaked Brody, Uri Alon, and Eran Yahav.  How attentive are graph attention networks?  arXiv preprint arXiv:2105.14491, 2021.
  * [6] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  * [7] Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich.  Deep image homography estimation.  CoRR, 06 2016.
  * [8] Giacomo D’Amicantonio, Egor Bondarau, and Peter H.N. De With.  Homography estimation for camera calibration in complex topological scenes.  In 2023 IEEE Intelligent Vehicles Symposium (IV), pages 1–8, 2023\.
  * [9] Farzan Erlik Nowruzi, Robert Laganiere, and Nathalie Japkowicz.  Homography estimation from image pairs with hierarchical convolutional networks.  In Proceedings of the IEEE international conference on computer vision workshops, pages 913–920, 2017.
  * [10] Martin A. Fischler and Robert C. Bolles.  Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography.  Commun. ACM, 24(6):381–395, jun 1981.
  * [11] Marco Gori, Gabriele Monfardini, and Franco Scarselli.  A new model for learning in graph domains.  Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., 2:729–734 vol. 2, 2005.
  * [12] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * [13] Richard Hartley and Andrew Zisserman.  Multiple View Geometry in Computer Vision.  Cambridge University Press, New York, NY, USA, 2 edition, 2003.
  * [14] Namdar Homayounfar, Sanja Fidler, and Raquel Urtasun.  Sports field localization via deep structured models.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [15] Max Jaderberg, Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu.  Spatial transformer networks.  CoRR, abs/1506.02025, 2015.
  * [16] Thomas N. Kipf and Max Welling.  Variational graph auto-encoders, 2016.
  * [17] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations (ICLR), 2017\.
  * [18] Hoang Le, Feng Liu, Shu Zhang, and Aseem Agarwala.  Deep homography estimation for dynamic scenes.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7652–7661, 2020.
  * [19] Kejie Li, Daniel DeTone, Yu Fan (Steven) Chen, Minh Vo, Ian Reid, Hamid Rezatofighi, Chris Sweeney, Julian Straub, and Richard Newcombe.  Odam: Object detection, association, and mapping using posed rgb video.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 5998–6008, October 2021.
  * [20] Wenxiong Liao, Bi Zeng, Jianqi Liu, Pengfei Wei, Xiaochun Cheng, and Weiwen Zhang.  Multi-level graph neural network for text sentiment analysis.  Computers & Electrical Engineering, 92:107096, 2021.
  * [21] David G. Lowe.  Distinctive image features from scale-invariant keypoints.  Int. J. Comput. Vision, 60(2):91–110, Nov. 2004.
  * [22] Jiayi Ma, Ji Zhao, Hanqi Guo, Junjun Jiang, Huabing Zhou, and Yuan Gao.  Locality preserving matching.  In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 4492–4498, 2017.
  * [23] Federico Monti, Michael Bronstein, and Xavier Bresson.  Geometric matrix completion with recurrent multi-graph neural networks.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [24] Negar Nejatishahidin, Will Hutchcroft, Manjunath Narayana, Ivaylo Boyadzhiev, Yuguang Li, Naji Khosravan, Jana Košecká, and Sing Bing Kang.  Graph-covis: Gnn-based multi-view panorama global pose estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, pages 6458–6467, June 2023.
  * [25] Ty Nguyen, Steven W. Chen, Shreyas S. Shivakumar, Camillo J. Taylor, and Vijay Kumar.  Unsupervised deep homography: A fast and robust homography estimation model.  CoRR, abs/1709.03966, 2017.
  * [26] Barbara Roessle and Matthias Nießner.  End2end multi-view feature matching using differentiable pose optimization, 2022.
  * [27] Ethan Rublee, Vincent Rabaud, Kurt Konolige, and Gary Bradski.  Orb: An efficient alternative to sift or surf.  In 2011 International Conference on Computer Vision, pages 2564–2571, 2011.
  * [28] Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich.  Superglue: Learning feature matching with graph neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [29] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  IEEE Transactions on Neural Networks, 20(1):61–80, 2009.
  * [30] Long Sha, Jennifer Hobbs, Panna Felsen, Xinyu Wei, Patrick Lucey, and Sujoy Ganguly.  End-to-end camera calibration for broadcast videos.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 13624–13633, 2020.
  * [31] Yurun Tian, Xin Yu, Bin Fan, Fuchao Wu, Huub Heijnen, and Vassileios Balntas.  Sosnet: Second order similarity regularization for local descriptor learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11016–11025, 2019.
  * [32] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [33] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, José M. Álvarez, and Ping Luo.  Segformer: Simple and efficient design for semantic segmentation with transformers.  CoRR, abs/2105.15203, 2021.
  * [34] Nancy Xu, Giannis Nikolentzos, Michalis Vazirgiannis, and Henrik Boström.  Image keypoint matching using graph neural networks.  In Complex Networks & Their Applications X, pages 441–451, Cham, 2022. Springer International Publishing.
  * [35] Kwang Moo Yi, Eduard Trulls, Vincent Lepetit, and Pascal Fua.  LIFT: learned invariant feature transform.  CoRR, abs/1603.09114, 2016.
  * [36] Jirong Zhang, Chuan Wang, Shuaicheng Liu, Lanpeng Jia, Jue Wang, and Ji Zhou.  Content-aware unsupervised deep homography estimation.  CoRR, abs/1909.05983, 2019.
  * [37] Wentao Zhang, Huansheng Song, Lichen Liu, Congliang Li, Bochen Mu, and Qian Gao.  Vehicle localisation and deep model for automatic calibration of monocular camera in expressway scenes.  IET Intelligent Transport Systems, 16, 04 2022.


# Robust Optimization for Local Differential Privacy

Jasper Goseling  University of Twente,
the Netherlands  Milan Lopuhaä-Zwakenberg  University of Twente,
the Netherlands

(June 2022)

###### Abstract

We consider the setting of publishing data without leaking sensitive
information. We do so in the framework of Robust Local Differential Privacy
(RLDP). This ensures privacy for all distributions of the data in an
uncertainty set. We formulate the problem of finding the optimal data release
protocol as a robust optimization problem. By deriving closed-form expressions
for the duals of the constraints involved we obtain a convex optimization
problem. We compare the performance of four possible optimization problems
depending on whether or not we require robustness in i) utility and ii)
privacy.

##  I Introduction

We consider a setting in which users have data $(S,U)$ with $U\in\mathbb{R}$.
A user wants to publish $U$, but does not want to disclose information about
their sensitive data $S$, which may be correlated with $U$. Therefore, the
users release an obfuscated version $Y$ of $U$, such that $Y$ is as close to
$U$ as possible, measured by mean squared distortion, without leaking too much
information about $S$. This scenario and closely related ones have been
studied in, for instance, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

To measure the information leakage about $S$ in $Y$ we use a form of Local
Differential Privacy [11] that was introduced in [12], which states that for
each possible $s_{1},s_{2}$ and $y$ the following should hold:

$\mathbb{P}(Y=y|S=s_{1})\leq\textrm{e}^{\varepsilon}\mathbb{P}(Y=y|S=s_{2}).$
(1)

This condition is less strict than regular LDP, reflecting the fact that only
$S$, and not $U$ itself, needs to be protected. Note that (1) depends on the
joint probability distribution $P_{SU}$. A privacy protocol is given by the
conditional probability distribution $P_{Y|SU}$, and given such a protocol,
the distortion is measured by $\mathbb{E}(U-Y)^{2}$, which also depends on
$P_{SU}$.

Thus both privacy and utility depend on the distribution of the data. However,
a user may not know this distribution exactly and needs to estimate it. The
odds ratio interpretation of differential privacy [13] tells us that an
attacker with a better estimate may obtain more information about $S$ than the
privacy protocol that is developed based on this estimate would indicate.
Furthermore, a good utility under the estimated distribution may not imply a
good utility under the actual distribution.

In this paper, therefore, we demand stronger, _robust_ privacy and utility
guarantees. More concretely, we assume that there exists a publicly available
dataset from which the users produce an estimate distribution $\hat{P}_{SU}$,
and a set $\mathcal{F}$ of probability distributions that do not differ
significantly from $\hat{P}_{S,U}$ (for a chosen significance level). Then
robustness can be incorporated in the following two ways:

  1. 1.

We demand robust privacy by requiring (1) to hold for all
$P_{SU}\in\mathcal{F}$;

  2. 2.

We obtain robust utility by minimising
$\max_{P_{SU}\in\mathcal{F}}\mathbb{E}(U-Y)^{2}$.

Robustness allows us to guarantee privacy and utility for all probability
distributions one can reasonably expect, without sacrificing too much utility
to account for unlikely distributions. It is important to note that: i)
robustness in utility is w.r.t. our own uncertainty about $P_{S,U}$ and ii)
robustness in privacy is w.r.t. our uncertainty about current knowledge by an
attacker. The robustness of privacy and utility can be incorporated
independently, leaving us with four possible optimization problems depending
on for which of the two we want robust guarantees.

$\overrightarrow{(s,u)}$$s_{1},u_{1}$$s_{2},u_{2}$$s_{n},u_{n}$known
dataprobability spacenew
data$\mathcal{P}_{\mathcal{S}\times\mathcal{U}}$$\mathcal{F}$$\hat{P}$$P^{*}$frequencies$(s_{i},u_{i})\sim
P^{*}$$(S,U)\sim P^{*}$$S,U$$P_{Y|SU}$$Y$ Figure 1: Overview. For clarity we
write $P^{*}=P^{*}_{SU}$ and $\hat{P}=\hat{P}_{SU}$. Since $\mathcal{F}$ is a
confidence interval $P^{*}$ may or may not be an element of $\mathcal{F}$.

In recent work [9, 10] we introduced the robust privacy framework that we also
use here. An important difference is that in [9, 10] the utility measure is
$\operatorname{I}(S,U;Y)$, leading to an optimization problem is not convex.
Therefore, similar to [2], the resulting techniques for analysis in [9, 10]
are combinatorial in nature and heuristics are developed. In the current work
the utility measure is the mean-squared error, leading to a non-robust
optimization problem that is convex.

One of the main contributions of this paper is to provide convex formulations
of the corresponding robust optimization problems. These formulations can be
handled by standard convex optimization solvers in order to obtain privacy
protocols that are provably optimal. Our numerical results demonstrate that:
i) without including robustness on the privacy constraints the effective
privacy guarantees that are obtained are very weak, ii) including robustness
on privacy leads to a significant penalty on utility, and iii) including a
robustness constraint on utility does not have a large impact if privacy
robustness is already imposed.

Our techniques are rooted in robust optimization [14, 15], an important aspect
of which is to use Fenchel duality on constraints like (1) that need to hold
for all distributions in $\mathcal{F}$. In [16] and [17] duals are derived for
constraints involving probabilities and uncertainty sets based on the
$\chi^{2}$-test. A major difference in the current work, and a contribution on
the technical side, is that (1) involves two conditional distributions from
$\mathcal{F}$.

The structure of this paper is as follows. In Section II we present the
details of our model. We provide background on robust optimization in Section
III and present our analytical results in Section IV. Insights obtained by
numerical experiments are given Section V. Finally, in Section VI we provide a
discussion and outlook on future work. PRoofs are presented in the appendix.

##  II Model

An overview of our model, the details of which are given in this section, is
given in Figure 1. There is a publicly accessible dataset
$\overrightarrow{(s,u)}$ of size $n$, in which each entry $(s_{i},u_{i})$ is
drawn independently from a probability distribution $P_{SU}^{*}$ on a set
$\mathcal{S}\times\mathcal{U}$, where $\mathcal{S}$ and
$\mathcal{U}\subset\mathbb{R}$ are finite alphabets. New data items $(S,U)$
are also drawn from $P_{SU}^{*}$. The user’s aim is to create a release
protocol $P_{Y|SU}$ such that $Y\in\mathcal{U}$ is as close as possible to
$U$, while not leaking too much information about $S$. More precisely, the
goal is to minimize the distortion, measured as $\mathbb{E}[d(U,Y)]$, where
$d$ is any distance function on $\mathcal{U}$.

The distribution $P_{SU}^{*}$ is not known exactly. The uncertainty set
$\mathcal{F}\subset\mathcal{P}_{\mathcal{S}\times\mathcal{U}}$, where
$\mathcal{P}_{\mathcal{S}\times\mathcal{U}}$ denotes the probability simplex
over $\mathcal{S}\times\mathcal{U}$, captures the user’s uncertainty about
$P_{SU}^{*}$. It is constructed from the dataset $\overrightarrow{(s,u)}$.
More specifically, we let $\mathcal{F}_{B}$ be the $(1-\alpha)$-confidence set
for $P_{SU}$ in a $\chi^{2}$-test, i.e.,

$\mathcal{F}_{B}=\left\\{P_{SU}\in\mathcal{P}_{\mathcal{S}\times\mathcal{U}}\middle|\sum_{\begin{subarray}{c}s\in\mathcal{S},\\\
u\in\mathcal{U}\end{subarray}}\frac{(\hat{P}_{s,u}-P_{s,u})^{2}}{P_{s,u}}\leq
B\right\\},$ (2)

where

$B=\frac{F^{-1}_{|\mathcal{S}\times\mathcal{U}|-1}(1-\alpha)}{n},$ (3)

$\hat{P}_{SU}$ is the empirical probability distribution of $(S,U)$ and
$F_{d}$ is the CDF of the $\chi^{2}$-distribution with $d$ degrees of freedom.
For the remainder of this paper we fix $B$ and write
$\mathcal{F}:=\mathcal{F}_{B}$.

The user creates $P_{Y|SU}$ in such a way that a Local Differential Privacy-
like privacy standard is guaranteed when $P_{SU}\in\mathcal{F}$. We will
denote this as robust local differential privacy (RLDP) [10]; it is defined as
follows.

######  Definition 1.

Let $\varepsilon\geq 0$ and
$\mathcal{F}\subset\mathcal{P}_{\mathcal{S}\times\mathcal{U}}$. We say that
$P_{Y|SU}$ satisfies $(\varepsilon,\mathcal{F})$-RLDP if for all
$s_{1},s_{2}\in\mathcal{S}$, all $y\in\mathcal{Y}$, and all
$P_{SU}\in\mathcal{F}$ we have

$\mathbb{P}(Y=y|S=s_{1})\leq\textrm{\emph{e}}^{\varepsilon}\mathbb{P}(Y=y|S=s_{2}).$
(4)

This is less strict than regular LDP [11], which requires that not just $S$
but also $U$ be protected. Unlike regular LDP it depends on $P_{SU}$, which is
why we demand robustness. In terms of coefficients we can write (4) as

$\displaystyle\forall y,s_{1},s_{2}\forall P_{SU}\in\mathcal{F}\colon
L_{y,s_{1},s_{2}}(P_{SU},P_{Y|SU})\leq 0,$ (5) $\displaystyle
L_{y,s_{1},s_{2}}(P_{SU},P_{Y|SU})$
$\displaystyle=\sum_{u\in\mathcal{U}}(P_{u|s_{1}}P_{y|s_{1},u}-\textrm{e}^{\varepsilon}P_{u|s_{2}}P_{y|s_{2},u}).$
(6)

We distinguish four possible optimization problems depending on whether or not
we require robustness in i) utility and ii) privacy. This gives:

NUNP: $\displaystyle\text{minimize}\
\mathbb{E}_{(S,U)\sim\hat{P}_{SU}}[d(U,Y)]$ (7) subject to $\displaystyle
L_{y,s_{1},s_{2}}(\hat{P}_{SU},P_{Y|SU})\leq 0,\forall y,s_{1},s_{2},$ NURP:
$\displaystyle\text{minimize}\ \mathbb{E}_{(S,U)\sim\hat{P}_{SU}}[d(U,Y)]$ (8)
subject to $\displaystyle L_{y,s_{1},s_{2}}(P_{SU},P_{Y|SU})\leq 0,$
$\displaystyle\qquad\forall P_{SU}\in\mathcal{F},\forall y,s_{1},s_{2},$ RUNP:
$\displaystyle\text{minimize}\ D$ (9) subject to
$\displaystyle\mathbb{E}_{(S,U)\sim P_{SU}}[d(U,Y)]\leq D,\quad\forall
P_{SU}\in\mathcal{F},$ $\displaystyle
L_{y,s_{1},s_{2}}(\hat{P}_{SU},P_{Y|SU})\leq 0,\forall y,s_{1},s_{2},$ RURP:
$\displaystyle\text{minimize}\ D$ (10) subject to
$\displaystyle\mathbb{E}_{(S,U)\sim P_{SU}}[d(U,Y)]\leq D,\quad\forall
P_{SU}\in\mathcal{F},$ $\displaystyle L_{y,s_{1},s_{2}}(P_{SU},P_{Y|SU})\leq
0,\forall P_{SU}\in\mathcal{F},\forall y,s_{1},s_{2}.$

In all these problems the optimization variable is $P_{Y|SU}$. Note that NUNP
corresponds to the ‘naive’ approach of assuming $P^{*}_{SU}=\hat{P}_{SU}$ and
doing nonrobust optimization.

We note that one can make different choices for the utility [9], privacy [3,
12], and uncertainty set [17]. As we will see below, robust optimization is a
general framework that works for many choices, but one needs problem-specific
analytic results (Theorems 2 & 4 and Lemmas 1 & 2 below) in order to
reformulate (7)–(10) as convex optimization problems, which can be fed to a
solver.

##  III Robust optimization

Problems (8)–(10) are robust optimization problems [14, 15]. In this section
we provide some background on robust optimization.

Let $f:\mathbb{R}^{m}\times\mathbb{R}^{n}\to\bar{\mathbb{R}}$ be defined on
the extended real line $\bar{\mathbb{R}}=\mathbb{R}\cup\\{-\infty,\infty\\}$
and for a given $x\in\mathbb{R}^{n}$ define $\operatorname{dom}(f(\cdot\
,x))=\\{a|\ f(a,x)>-\infty\\}$. Consider an optimization problem with
constraint

$f(a,x)\leq 0,\forall a\in\mathcal{A},$ (11)

where $x\in\mathbb{R}^{n}$ is the optimization variable, $a\in\mathbb{R}^{m}$
is an uncertain parameter and $\mathcal{A}$ is the uncertainty set for which
we need the constraint to hold. The robustness constraints in (8)–(10) are of
the form (11) with $P_{SU}$ and $P_{Y|SU}$ in the roles of $a$ and $x$,
respectively.

The main tool that is used in this paper is based on Fenchel duality. In order
to present this, let

$f_{*}(v,x)=\inf_{a\in\mathbb{R}^{m}}v^{T}a-f(a,x)$ (12)

and

$\delta^{*}(v\,|\,\mathcal{A})=\sup_{a\in\mathcal{A}}v^{T}a,$ (13)

which are known as the partial concave conjugate of $f$ and the support set of
$\mathcal{A}$, respectively. Also, let $\operatorname{ri}(\cdot)$ denote the
relative interior of a set. We will extensively use the following result.

######  Theorem 1 ([15]).

Let $x\in\mathbb{R}^{n}$. If $f(a,x)$ is closed concave in $a$ and
$\operatorname{ri}(\mathcal{A})\cap\operatorname{ri}(\operatorname{dom}(f(\cdot\
,x)))\neq\emptyset$, then $x$ satisfies (11) if and only if

$\exists v\in\mathbb{R}^{m}\text{ s.t. }\delta^{*}(v\,|\,\mathcal{A})\leq
f_{*}(v,x).$ (14)

Since $\delta^{*}(v\,|\,\mathcal{A})$ and $f_{*}(v,x)$ are convex and concave
functions, respectively, Theorem 1 provides a means to efficiently solve
robust optimization problems once these functions are found in closed form.
Another result we use is that Theorem 1 can be applied independently to each
uncertain constraint [14], and so we can handle robust utility and robust
privacy separately.

##  IV Closed-form expressions for robustness

While Theorem 1 is a powerful tool to deal with the universal quantifiers in
the robust constraints, the downside is that one has to find closed forms of
the functions $\delta^{*}(\bullet|\mathcal{A})$ and $f_{*}(\bullet,x)$. In
this section, we show how to do this for the robust utility and privacy
constraints of (7)–(10). As will become apparent from the discussion below,
the solutions we find are specific to our choice of privacy, utility, and
uncertainty set.

###  IV-A Robust utility

The robust utility constraint in RUNP and RURP is of the form

$\mathbb{E}_{(S,U)\sim P_{SU}}[d(U,Y)]\leq D,\quad\forall
P_{SU}\in\mathcal{F}.$ (15)

We can write this as

$\displaystyle E_{D}(P_{SU},P_{Y|SU})$ $\displaystyle\leq 0,\quad\forall
P_{SU}\in\mathcal{F},$ (16) $\displaystyle E_{D}(P_{SU},P_{Y|SU})$
$\displaystyle=\mathbb{E}[d(U,Y)]-D$ (17)
$\displaystyle=\sum_{y,s,u}P_{s,u}P_{y|s,u}d(u,y)-D.$ (18)

Using Theorem 1 we can write this as

$\exists
v\in\mathbb{R}^{|\mathcal{S}\times\mathcal{U}|}\colon\delta^{*}(v|\mathcal{F})\leq
E_{D*}(v,P_{Y|SU}).$ (19)

Thus we need to find expressions for $\delta^{*}(v|\mathcal{F})$ and
$E_{D*}(v,P_{Y|SU})$. Since $E_{D}$ is linear in $P_{SU}$, one easily derives
the following [14]:

######  Lemma 1.

Let $E_{D}(P_{SU},P_{Y|SU})=\mathbb{E}[d(U,Y)]-D$, with uncertain parameter
$P_{SU}$ and optimization variable $P_{Y|SU}$. Then

$\displaystyle E_{D*}(v,P_{Y|SU})$ $\displaystyle=\begin{cases}D,&\text{if
}\forall s,u\colon v_{s,u}=\sum_{y}P_{y|s,u}d(y,u),\\\
-\infty,\quad&\text{otherwise.}\end{cases}$ (20)

The expression for $\delta^{*}(v|\mathcal{F})$ is a little bit more work, but
can be found using established results in convex analysis [15]. A related
result is found in [17, Thm. 5].

######  Theorem 2.

$\delta^{*}(v|\mathcal{F})=\min_{w\geq v,c\geq
0}\Bigg{\\{}-2\sqrt{c}\sum_{s,u}\hat{P}_{s,u}\sqrt{w_{s,u}-v_{s,u}}\\\
+\max_{s,u}w_{s,u}+c(B+1)\Bigg{\\}}.$ (21)

Combining these results, we can write the robust utility constraint (15) as

$\delta^{*}\left(\left(\sum_{y}P_{y|s,u}d(y,u)\right)_{s\in\mathcal{S},u\in\mathcal{U}}\middle|\mathcal{F}\right)\leq
D,$ (22)

where $\delta^{*}(\bullet|\mathcal{F})$ is as in Theorem 2.

###  IV-B Robust privacy

Fix $y,s_{1},s_{2}$. The robust privacy constraint in NURP and RURP is of the
form

$L_{y,s_{1},s_{2}}(P_{SU},P_{Y|SU})\leq 0,\forall P_{SU}\in\mathcal{F}.$ (23)

One would like to apply Theorem 1; however, $L_{y,s_{1}.s_{2}}$ is not convex
in $P_{SU}$. Therefore we rewrite it as follows. Let
$\mathcal{F}_{U|s_{1},s_{2}}$ be the projection of $\mathcal{F}$ onto
$\mathcal{P}_{\mathcal{U}}\times\mathcal{P}_{\mathcal{U}}$ by the map
$P\mapsto(P_{U|s_{1}},P_{U|s_{2}})$. We can write (23) as

$\displaystyle\forall(P_{U|s_{1}},P_{U|s_{2}})\in\mathcal{F}_{U|s_{1},s_{2}}\colon$
$\displaystyle\tilde{L}_{y,s_{1},s_{2}}(P_{U|s_{1}},P_{U|s_{2}},P_{Y|SU})\leq
0,$ (24)

where

$\displaystyle\tilde{L}_{y,s_{1},s_{2}}(P_{U|s_{1}},P_{U|s_{2}},P_{Y|SU})$
$\displaystyle=\sum_{u\in\mathcal{U}}(P_{u|s_{1}}P_{y|s_{1},u}-\textrm{e}^{\varepsilon}P_{u|s_{2}}P_{y|s_{2},u}).$
(25)

Again we use Theorem 1 to write this as

$\exists
v_{1},v_{2}\in\mathbb{R}^{|\mathcal{U}|}\colon\delta^{*}(v_{1},v_{2}|\mathcal{F}_{U|s_{1},s_{2}})\leq\tilde{L}_{y,s_{1},s_{2}*}(v_{1},v_{2},P_{Y|SU}).$
(26)

Thus we need to find expressions for these functions. As
$\tilde{L}_{y,s_{1},s_{2}}(P_{U|s_{1}},P_{U|s_{2}},P_{Y|SU})$ is linear in its
first two arguments, we find the following:

######  Lemma 2.

One has

$\displaystyle\tilde{L}_{y,s_{1},s_{2}*}(v_{1},v_{2},P_{Y|SU})$
$\displaystyle=\begin{cases}0,&\text{if }\forall u\colon
v_{1,u}=P_{y|s_{1},u},\\\ &\quad\text{and
}v_{2,u}=-\textrm{\emph{e}}^{\epsilon}P_{y|s_{2},u},\\\ -\infty,\
&\text{otherwise.}\end{cases}$ (27)

The expression for $\delta^{*}(v_{1},v_{2}|\mathcal{F}_{U|s_{1},s_{2}})$ takes
considerably more effort, in part because we first have to find a closed
expression for $\mathcal{F}_{U|s_{1},s_{2}}$. This is given in the following
result:

######  Theorem 3.

$\mathcal{F}_{U|s_{1},s_{2}}=\Bigg{\\{}\left(R_{U|s_{1}},R_{U|s_{2}}\right)\in\mathcal{P}_{\mathcal{U}}^{2}\
\Bigg{|}\\\
\sum_{i=1}^{2}\sqrt{\sum_{u}\frac{\hat{P}_{s_{i},u}^{2}}{R_{u|s_{i}}}}\leq\sqrt{B+1}-1+\sum_{i=1}^{2}\hat{P}_{s_{i}}\Bigg{\\}}.$
(28)

Similar to, but more in a more complicated way than, Theorem 2, one can prove:

######  Theorem 4.

The support function of $\mathcal{F}_{U|s_{1},s_{2}}$ is given by

$\delta^{*}(v_{1},v_{2}|\mathcal{F}_{U|s_{1},s_{2}})=\min_{c\geq 0,w_{1}\geq
v_{1},w_{2}\geq v_{2}}\Bigg{\\{}\\\
-(2^{-2/3}+2^{1/3})c^{2/3}\sum_{i=1}^{2}\left(\sum_{u}\hat{P}_{s_{i},u}\sqrt{w_{i}(u)-v_{i}(u)}\right)^{2/3}\\\
+\sum_{i=1}^{2}\max_{u}w_{i}(u)+c\bigg{(}\sqrt{B+1}-1+\sum_{i=1}^{2}\hat{P}_{s_{i}}\bigg{)}\Bigg{\\}}.$
(29)

Thus we can write (23) as

$\delta^{*}\left((P_{y|s_{1},u})_{u\in\mathcal{U}},(P_{y|s_{2},u})_{u\in\mathcal{U}}\middle|\mathcal{F}_{\mathcal{U}|s_{1},s_{2}}\right)\leq
0,$ (30)

where $\delta^{*}(\bullet|\mathcal{F}_{\mathcal{U}|s_{1},s_{2}})$ is as in
Theorem 4. Replacing (15) by (22), and (23) by (30) allows us to provide
convex formulations of (7)–(10). In the next section we provide some insights
that are obtained through numerical experiments.

$0$$2$$4$$6$$0$$1$$2$$3$$\varepsilon^{*}$$D^{*}$NUNPNURPRUNPRURP (a) Impact of
robustness on utility ($K=30$, $n=75$).

$0.5$$1$$1.5$$2$$0$$0.5$$1$$1.5$$\varepsilon^{*}$$D^{*}$NUNPNURPRUNPRURP (b)
Impact of robustness on utility ($K=30$, $n=15,000$).

$10^{1}$$10^{2}$$10^{3}$$0$$0.5$$1$$1.5$$2$$N$$\varepsilon^{*}$NUNPNURPRUNPRURP
(c) This figure depicts $\varepsilon^{*}$ as a function of
$n=N\cdot|\mathcal{S}||\mathcal{U}|$.

$10^{1}$$10^{2}$$10^{3}$$0$$0.5$$1$$1.5$$2$$N$$D^{*}$NUNPNURPRUNPRURP (d) This
figure depicts $D^{*}$ as a function of $n=N\cdot|\mathcal{S}||\mathcal{U}|$.

Figure 2: Experimental results on $K$ instances for optimization under
Nonrobust/Robust Utility and Nonrobust/Robust Privacy. ($\alpha=0.05$,
$\varepsilon=0.5$, $|\mathcal{S}|=3$, $|\mathcal{U}|=5$)

##  V Numerical experiments

The performance measures that we consider are

$D^{*}=\mathbb{E}_{(S,U)\sim P^{*}_{SU}}[d(U,Y)]$ (31)

and

$\varepsilon^{*}=\log\max_{y,s_{1},s_{2}}\frac{P_{y|s_{1}}}{P_{y|s_{2}}},$
(32)

interpreting $0/0$ as $1$ and with $\varepsilon^{*}=\infty$ if there exist
$y$, $s_{1}$ and $s_{2}$ for which $P_{y|s_{2}}=0$ and $P_{y|s_{1}}>0$. These
measures give the performance of the $P_{Y|SU}$ that is obtained from
optimization under the actual distribution $P_{SU}^{*}$.

In all experiments we use $\mathcal{S}=\\{0,1,2\\}$,
$\mathcal{U}=\\{0,1,2,3,4\\}$, $d(x,y)=(x-y)^{2}$, $\alpha=0.05$ and
$\varepsilon=0.5$. We draw $P_{SU}^{*}$ according to the Jeffreys prior on
$\mathcal{P}_{\mathcal{S}\times\mathcal{U}}$, i.e., the symmetric Dirichlet
distribution with parameter $\tfrac{1}{2}$ [18].

In our first experiment we draw $K=30$ instances of $P_{SU}^{*}$. For each
instance, we draw $n$ samples $(s,u)$ from which we estimate $\hat{P}_{SU}$.
For each of the $K=30$ instances we report $\varepsilon^{*}$ and $D^{*}$ in a
scatter plot. We do so for each combination of nonrobust/robust utility and
privacy (nomenclature in (7)–(10)). In Figures 2(a) and 2(b) the results are
depicted for $n=5|\mathcal{S}||\mathcal{U}|=75$ and for
$n=10^{3}|\mathcal{S}||\mathcal{U}|=15,000$, respectively. Instances that have
$\epsilon^{*}=\infty$ are omitted from the figures.

We observe that without robustness in privacy, i.e., NUNP and RUNP, almost all
instances have significantly lower privacy performance than what they are
designed for, i.e., $\varepsilon^{*}\gg\varepsilon$. Also, by introducing
robustness in privacy as a hard constraint, we significantly suffer in terms
of utility. Note though that even with robust privacy we do not always get
$\varepsilon^{*}\leq\varepsilon$; this is because $P^{*}\in\mathcal{F}$ only
with probability $1-\alpha$. In Figure 2(a) NURP has more than the expected
number of outliers, which can be explained from the fact that the $\chi^{2}$
test only asymptotically gives a confidence interval as $n\rightarrow\infty$.
Another interesting observation (which will be confirmed by the next
experiments) is that once we have imposed robust privacy, imposing robust
utility does not make much difference, i.e., NURP and RURP are very similar.
This shows that the utility cost of demanding robust privacy is considerably
greater than the utility benefit of demanding robust utility. Note, that by
comparing to Figure 2(b), some of the large $\varepsilon^{*}$ values for NURP
in Figure 2(a) seem to be small sample artifacts. A final observation is that
in both figures there are outliers, especially in $\varepsilon^{*}$.

Our second experiment illustrates the influence of $n$. We give the mean
$D^{*}$ and $\varepsilon^{*}$ over $K=10^{3}$ instances as a function of $n$
in Figures 2(c) and 2(d), respectively. In addition to the mean we report the
standard deviation. Thick lines depict the mean over $K=10^{3}$ samples, the
width of the bands correspond to $\pm 1$ standard deviation. Both are computed
by first removing outliers based on the $1.5\text{IQR}$ rule.

We observe that for small $n$, due to the large uncertainty on $P_{SU}$, RURP
is very conservative with $\varepsilon^{*}\ll\epsilon$. The figures also
confirm that imposing robustness in utility has relatively little impact.

Our implementations are in CVX [19] and are solved using Mosek [20].

##  VI Discussion

We have given convex formulations of optimization problems for finding robust
data release protocols $P_{Y|SU}$. In addition we also studied the non-robust
form. Numerical experiments revealed that the non-robust forms achieve privacy
levels that are much worse than anticipated. In particular, the naive approach
of assuming $P^{*}_{SU}=\hat{P}_{SU}$ leads to undesirable privacy leakage.

Our convex formulations and corresponding implementations have a number of
variables and constraints that grows exponentially in $|\mathcal{S}|$ and
$|\mathcal{U}|$. It would be of great interest to develop bounding methods
that have reduced complexity, but that still provide strong guarantees.

The current model imposes that the output alphabet of $P_{Y|SU}$ is equal to
the input alphabet $\mathcal{U}$. It would be of interest to leverage this
assumption.

## References

  * [1] D. Rebollo-Monedero, J. Forne, and J. Domingo-Ferrer, “From t-closeness-like privacy to postrandomization via information theory,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 22, no. 11, pp. 1623–1636, 2010.
  * [2] P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 492–542, 2016.
  * [3] A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard, “From the information bottleneck to the privacy funnel,” in _2014 IEEE Information Theory Workshop (ITW 2014)_. IEEE, 2014, pp. 501–505.
  * [4] S. Salamatian, A. Zhang, F. du Pin Calmon, S. Bhamidipati, N. Fawaz, B. Kveton, P. Oliveira, and N. Taft, “Managing your private and public data: Bringing down inference attacks against your privacy.” _J. Sel. Topics Signal Processing_ , vol. 9, no. 7, pp. 1240–1255, 2015.
  * [5] S. Asoodeh, M. Diaz, F. Alajaji, and T. Linder, “Information extraction under privacy constraints,” _Information_ , vol. 7, no. 1, p. 15, 2016.
  * [6] S. Kung, “A compressive privacy approach to generalized information bottleneck and privacy funnel problems,” _Journal of the Franklin Institute_ , vol. 355, no. 4, pp. 1846–1872, 2018.
  * [7] N. Ding and P. Sadeghi, “A submodularity-based clustering algorithm for the information bottleneck and privacy funnel,” in _2019 IEEE Information Theory Workshop (ITW)_. IEEE, 2019, pp. 1–5.
  * [8] S. Salamatian, F. P. Calmon, N. Fawaz, A. Makhdoumi, and M. Médard, “Privacy-utility tradeoff and privacy funnel,” 2020, preprint.
  * [9] M. Lopuhaä-Zwakenberg and J. Goseling, “The privacy-utility tradeoff of robust local differential privacy,” _arXiv:2101.09139_ , 2021, preprint.
  * [10] ——, “Robust local differential privacy,” in _2021 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2021, pp. 557–562.
  * [11] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” _SIAM Journal on Computing_ , vol. 40, no. 3, pp. 793–826, 2011.
  * [12] M. Lopuhaä-Zwakenberg, H. Tong, and B. Škorić, “Data sanitisation for the privacy funnel with differential privacy guarantees,” _arXiv:2008.13151_ , 2020.
  * [13] D. Kifer and A. Machanavajjhala, “Pufferfish: A framework for mathematical privacy definitions,” _ACM Transactions on Database Systems (TODS)_ , vol. 39, no. 1, pp. 1–36, 2014.
  * [14] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, _Robust optimization_. Princeton university press, 2009.
  * [15] A. Ben-Tal, D. Den Hertog, and J.-P. Vial, “Deriving robust counterparts of nonlinear uncertain inequalities,” _Mathematical programming_ , vol. 149, no. 1-2, pp. 265–299, 2015.
  * [16] A. Ben-Tal, D. Den Hertog, A. De Waegenaere, B. Melenberg, and G. Rennen, “Robust solutions of optimization problems affected by uncertain probabilities,” _Management Science_ , vol. 59, no. 2, pp. 341–357, 2013\.
  * [17] D. Bertsimas, V. Gupta, and N. Kallus, “Data-driven robust optimization,” _Mathematical Programming_ , vol. 167, no. 2, pp. 235–292, 2018.
  * [18] C. P. Robert, N. Chopin, and J. Rousseau, “Harold jeffreys’s theory of probability revisited,” _Statistical Science_ , vol. 24, no. 2, pp. 141–172, 2009.
  * [19] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
  * [20] MOSEK ApS, _MOSEK Optimization Suite version 9.2_ , 2019. [Online]. Available: https://docs.mosek.com/9.2/intro/index.html

##  Appendix A Proof of Theorem 3

###### Proof:

Denote the RHS of (28) by $\overline{\mathcal{F}}_{U|s_{1},s_{2}}$. Let
$\left(R_{U|s_{1}},R_{U|s_{2}}\right)\in\overline{\mathcal{F}}_{U|s_{1},s_{2}}$
and define $P_{SU}\in\mathbb{R}^{\mathcal{S}}\times\mathbb{R}^{\mathcal{U}}$
as

$P_{s,u}=\begin{cases}\frac{\kappa_{1}}{\kappa_{1}+\kappa_{2}+\kappa_{3}}R_{u|s_{1}},\quad&\text{
if }s=s_{1},\\\
\frac{\kappa_{2}}{\kappa_{1}+\kappa_{2}+\kappa_{3}}R_{u|s_{2}},\quad&\text{ if
}s=s_{2},\\\
\frac{1}{\kappa_{1}+\kappa_{2}+\kappa_{3}}\hat{P}_{s,u},\quad&\text{ if }s\neq
s_{1},s_{2},\\\ \end{cases}$ (33)

with

$\kappa_{1}=\hat{P}_{s_{1}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{1}}^{2}}{R_{u|s_{1}}}},\quad\kappa_{2}=\hat{P}_{s_{2}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{2}}^{2}}{R_{u|s_{2}}}},$
(34)

and $\kappa_{3}=1-\hat{P}_{s_{1}}-\hat{P}_{s_{2}}$. Then

$\displaystyle\sum_{s,u}P_{s,u}$
$\displaystyle=\tfrac{1}{\kappa_{1}+\kappa_{2}+\kappa_{3}}\Bigg{(}$ (35)
$\displaystyle\kappa_{1}\sum_{u}R_{u|s_{1}}+\kappa_{2}\sum_{u}R_{u|s_{2}}+\sum_{s\notin\\{s_{1},s_{2}\\},u}\hat{P}_{s,u}\Bigg{)}$
$\displaystyle=\tfrac{1}{\kappa_{1}+\kappa_{2}+\kappa_{3}}(\kappa_{1}+\kappa_{2}+\kappa_{3})=1,$
(36)

so $P_{SU}\in\mathcal{P}_{\mathcal{S}\times\mathcal{U}}$. Furthermore,

$\displaystyle\sum_{s,u}\frac{P_{s,u}^{2}}{P_{s,u}}$
$\displaystyle=(\kappa_{1}+\kappa_{2}+\kappa_{3})\Bigg{(}$ (37)
$\displaystyle\sum_{u}\frac{\hat{P}_{s,u}^{2}}{\kappa_{1}R_{u|s_{1}}}+\frac{\hat{P}_{s,u}^{2}}{\kappa_{2}R_{u|s_{2}}}+\sum_{s\notin\\{s_{1},s_{2}\\},u}\hat{P}_{s,u}\Bigg{)}$
$\displaystyle=(\kappa_{1}+\kappa_{2}+\kappa_{3})^{2}.$ (38)

Since $(R_{U|s_{1}},R_{U|s_{2}}\in\overline{\mathcal{F}}_{U|s_{1},s_{2}}$, one
has $\kappa_{1}+\kappa_{2}+\kappa_{3}\leq\sqrt{B+1}$. It follows that

$\displaystyle\sum_{s,u}\frac{(P_{s,u}-\hat{P}_{s,u})^{2}}{P_{s,u}}$
$\displaystyle=\sum_{s,u}(P_{s,u}-2\hat{P}_{s,u})+\sum_{s,u}\frac{P_{s,u}^{2}}{P_{s,u}}$
(39) $\displaystyle=(\kappa_{1}+\kappa_{2}+\kappa_{3})^{2}-1$ (40)
$\displaystyle\leq B,$ (41)

which shows that $P_{SU}\in\mathcal{F}$. It is clear that $P_{SU}$ projects to
$\left(R_{U|s_{1}},R_{U|s_{2}}\right)$. This shows that
$\overline{\mathcal{F}}_{U|s_{1},s_{2}}\subset\mathcal{F}_{U|s_{1},s_{2}}$.

Next, let $P_{SU}\in\mathcal{F}$. From (2) it follows that

$\displaystyle\frac{\hat{P}_{s_{1}}^{2}}{P_{s_{1}}}\sum_{u}\frac{\hat{P}_{u|s_{1}}^{2}}{P_{u|s_{1}}}+\frac{\hat{P}_{s_{2}}^{2}}{P_{s_{2}}}\sum_{u}\frac{\hat{P}_{u|s_{2}}^{2}}{P_{u|s_{2}}}+$
$\displaystyle\frac{\left(1-\hat{P}_{s_{1}}-\hat{P}_{s_{2}}\right)^{2}}{1-P_{s_{1}}-P_{s_{2}}}$
$\displaystyle\leq B+1.$ (42)

Application of the Cauchy-Schwartz inequality on the vectors

$\left(\frac{\hat{P}_{s_{1}}}{\sqrt{P_{s_{1}}}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{1}}^{2}}{P_{u|s_{1}}}},\frac{\hat{P}_{s_{2}}}{\sqrt{P_{s_{2}}}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{2}}^{2}}{P_{u|s_{2}}}},\frac{1-\hat{P}_{s_{1}}-\hat{P}_{s_{2}}}{\sqrt{1-P_{s_{1}}-P_{s_{2}}}}\right)$

and

$\left(\sqrt{P_{s_{1}}},\sqrt{P_{s_{2}}},\sqrt{1-P_{s_{1}}-P_{s_{2}}}\right),$

gives

$\displaystyle\left(\hat{P}_{s_{1}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{1}}^{2}}{P_{u|s_{1}}}}+\hat{P}_{s_{2}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{2}}^{2}}{P_{u|s_{2}}}}+1-\hat{P}_{s_{1}}-\hat{P}_{s_{2}}\right)^{2}$
$\displaystyle\leq\frac{\hat{P}_{s_{1}}^{2}}{P_{s_{1}}}\sum_{u}\frac{\hat{P}_{u|s_{1}}^{2}}{P_{u|s_{1}}}+\frac{\hat{P}_{s_{2}}^{2}}{P_{s_{2}}}\sum_{u}\frac{\hat{P}_{u|s_{2}}^{2}}{P_{u|s_{2}}}$
(43)
$\displaystyle\quad+\frac{\left(1-\hat{P}_{s_{1}}-\hat{P}_{s_{2}}\right)^{2}}{1-P_{s_{1}}-P_{s_{2}}},$

which together with (42) yields

$\displaystyle\hat{P}_{s_{1}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{1}}^{2}}{P_{u|s_{1}}}}+\hat{P}_{s_{2}}\sqrt{\sum_{u}\frac{\hat{P}_{u|s_{2}}^{2}}{P_{u|s_{2}}}}$
$\displaystyle+1-\hat{P}_{s_{1}}-\hat{P}_{s_{2}}$
$\displaystyle\leq\sqrt{B+1},$ (44)

which shows that
$\mathcal{F}_{U|s_{1},s_{2}}\subset\overline{\mathcal{F}}_{U|s_{1},s_{2}}$.
This completes the proof. ∎

##  Appendix B Concave conjugates

In this section we prove Lemmas 1 and 2. Since both $E_{D}$ and
$\tilde{L}_{y,s_{1},s_{2}}$ are linear in the uncertain variable, they both
follow directly from the following result:

######  Lemma 3.

Let $f$ be a convex function, and let $x$ be such that $f(a,x)$ is linear in
$v$; write $f(v,x)=b_{x}^{T}a+c_{x}$. Then

$f_{*}(v,x)=\begin{cases}-c_{x},&\text{ if }v=b_{x},\\\ -\infty,&\text{
otherwise.}\end{cases}$ (45)

###### Proof:

By definition

$f_{*}(v,x)=\inf_{a}(v-b_{x})^{T}a-c_{x}.$ (46)

If $v-b_{x}\neq 0$, then the inner product can become arbitrarily negative,
and so $f_{*}(v,x)=-\infty$. If $v=b_{x}$, however, then the RHS is equal to
$-c_{x}$ no matter the choice of $a$. ∎

‘

##  Appendix C Support functions

In this appendix we prove Theorems 2 and 4. We first state a number of
standard results of convex analysis, which can be found, for instance, in
[15]. For a closed convex function
$f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{\pm\infty\\}$ and
$v\in\mathbb{R}^{n}$ we write

$f^{*}(v)=\sup_{x\in\mathbb{R}^{n}}v^{T}x-f(x).$ (47)

######  Lemma 4 ([15]).

For $C\in\mathbb{R}$ one has $(f+C)^{*}(v)=f^{*}(v)-C$.

######  Lemma 5 ([15]).

Let
$h_{1},\ldots,h_{k}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\pm{\infty}$
be closed convex functions, and let

$\mathcal{A}=\left\\{(x_{1},\ldots,x_{k})\in\mathbb{R}^{2n}\middle|\sum_{j}h_{j}(x_{j})\leq
0\right\\}.$ (48)

Then

$\delta^{*}(v_{1},\ldots,v_{k}|\mathcal{A})=\min_{c\geq
0}\left\\{c\sum_{j}h_{j}^{*}\left(\tfrac{v_{j}}{c}\right)\right\\}.$ (49)

######  Lemma 6 ([15]).

One has
$\delta^{*}(v_{1},v_{2}|\mathcal{A}\times\mathcal{B})=\delta^{*}(v_{1}|\mathcal{A})+\delta^{*}(v_{2}|\mathcal{B})$.

######  Lemma 7 ([15]).

Let $\mathcal{A},\mathcal{B}$ be closed sets such that
$\operatorname{ri}(\mathcal{A})\cap\operatorname{ri}(\mathcal{B})\neq\varnothing$.
Then

$\delta^{*}(v|\mathcal{A}\cap\mathcal{B})=\min_{t,w}\left\\{\delta^{*}(t|\mathcal{A})+\delta^{*}(w|\mathcal{B})\middle|t+w=v\right\\}.$
(50)

###### Proof:

We can write

$\displaystyle\delta^{*}(v|\mathcal{F})$
$\displaystyle=\delta^{*}(v|\mathcal{P}_{\mathcal{S}\times\mathcal{U}}\cap\mathcal{B}),$
(51) $\displaystyle\mathcal{B}$
$\displaystyle=\\{R\in\mathbb{R}^{|\mathcal{S}\times\mathcal{U}|}|g(R)-B-1\leq
0\\},$ (52) $\displaystyle g(R)$ $\displaystyle=\sum_{s,u}g_{s,u}(R_{s,u}),$
(53) $\displaystyle g_{s,u}(R_{s,u})$
$\displaystyle=\frac{\hat{P}_{s,u}^{2}}{R_{s,u}}.$ (54)

Then by Lemma 7

$\displaystyle\delta^{*}(v|\mathcal{F})=\min_{t,v}\\{\delta^{*}(t|\mathcal{B})+\delta^{*}(w|\mathcal{P}_{\mathcal{S}\times\mathcal{U}})\mid
t+w=v\\}.$ (55)

For the second term on the RHS have

$\displaystyle\delta^{*}(w|\mathcal{P}_{\mathcal{S}\times\mathcal{U}})$
$\displaystyle=\max_{P_{SU}\in\mathcal{P}_{\mathcal{S}\times\mathcal{U}}}\sum_{s,u}P_{s,u}w_{s,u}$
$\displaystyle=\max_{s,u}w_{s,u}.$ (56)

Furthermore it follows from Lemmas 4 and 5 that

$\displaystyle\delta^{*}(t|\mathcal{B})$ $\displaystyle=\min_{c\geq
0}\left\\{c\sum_{s,u}g^{*}_{s,u}\left(\tfrac{t_{s,u}}{c}\right)+c(B+1)\right\\},$
(57)

so it remains to determine

$\displaystyle g^{*}_{s,u}(z)=\sup_{x}xz-\frac{\hat{P}_{s,u}^{2}}{x}.$ (58)

for $z\in\mathbb{R}$. We find this by taking the derivative w.r.t. $x$, and we
have to solve

$z+\frac{\hat{P}_{s,u}^{2}}{x^{2}}=0$ (59)

hence $x=\frac{\hat{P}_{s,u}^{2}}{\sqrt{-z}}$ (if $z>0$, then the maximum does
not exist and $g^{*}_{s,u}(z)=\infty$). Substituting this we find

$g^{*}_{s,u}(z)=-2\sqrt{-z}\hat{P}_{s,u}.$ (60)

Combining this with (55) and (56), and substituting $t=w-v$, now proves the
Theorem. ∎

###### Proof:

We have

$\displaystyle\delta^{*}(v_{1},v_{2}|\mathcal{F}_{U|s_{1},s_{2}})=\delta^{*}(v_{1},v_{2}|(\mathcal{P}_{\mathcal{U}}\times\mathcal{P}_{\mathcal{U}})\cap\mathcal{A}),$
(61)

where

$\mathcal{A}=\left\\{(R_{1},R_{2})\in\mathbb{R}^{|\mathcal{U}|}\times\mathbb{R}^{|\mathcal{U}|}\middle|h(R_{1},R_{2})\leq
0\right\\},\\\ $ (62) $\displaystyle h(R_{1},R_{2})$
$\displaystyle=h_{1}(R_{1})+h_{2}(R_{2})-C,$ (63) $\displaystyle h_{1}(R_{1})$
$\displaystyle=\sqrt{\sum_{u}\frac{\hat{P}_{s_{1},u}^{2}}{R_{u|s_{1}}}},$ (64)
$\displaystyle h_{1}(R_{2})$
$\displaystyle=\sqrt{\sum_{u}\frac{\hat{P}_{s_{2},u}^{2}}{R_{u|s_{2}}}},$ (65)
$\displaystyle C$
$\displaystyle=\sqrt{B+1}-1+\hat{P}_{s_{1}}+\hat{P}_{s_{2}}.$ (66)

By Lemma 7 one has

$\displaystyle\delta^{*}(v_{1},v_{2}|\mathcal{F}_{U|s_{1},s_{2}})$ (67)
$\displaystyle=\min_{t_{1},t_{2},w_{1},w_{2}}\left\\{\delta^{*}(t_{1},t_{2}|\mathcal{A})+\delta^{*}(w_{1},w_{2}|\mathcal{P}_{U}\times\mathcal{P}_{U})\right\\}.$

By Lemma 6 we have

$\delta^{*}(w_{1},w_{2}|\mathcal{P}_{\mathcal{U}}\times\mathcal{P}_{\mathcal{U}})=\delta^{*}(w_{1}|\mathcal{P}_{\mathcal{U}})+\delta^{*}(w_{2}|\mathcal{P}_{\mathcal{U}}).$
(68)

As in (56)

$\displaystyle\delta^{*}(w|\mathcal{P}_{U})$
$\displaystyle=\max_{P\in\mathcal{P}_{\mathcal{U}}}P^{T}w$ (69)
$\displaystyle=\max_{u}w_{u}.$ (70)

Now let us consider $\delta^{*}(t_{1},t_{2}|\mathcal{A})$. Applying Lemmas 4
and 5, we get

$\displaystyle\delta^{*}(t_{1},t_{2}|\mathcal{A})=\min_{c\geq
0}\left\\{h_{1}^{*}\left(\tfrac{t_{1}}{c}\right)+h_{2}^{*}\left(\tfrac{t_{2}}{c}\right)+cC\right\\},$
(71)

so it remains to find expressions for the $h_{i}^{*}$. This is done in Lemma 8
below; combining this with equations (67)–(71) now proves the Theorem. ∎

######  Lemma 8.

Let $h:\mathbb{R}^{k}\to\mathbb{R}$,
$h(x)=\sqrt{\sum_{i=1}^{k}\frac{\kappa^{2}_{i}}{x_{i}}}$, with $\kappa_{i}>0$.
Let $\lambda=\sum_{i=1}^{k}\kappa_{i}\sqrt{-v_{i}}$. Then

$h^{*}(v)=\begin{cases}-(2^{-2/3}+2^{1/3})\lambda^{2/3},\quad&\text{if
}\max_{i}v_{i}\leq 0,\\\ \infty,\quad&\text{otherwise}.\end{cases}$ (72)

###### Proof:

By definition

$h^{*}(v)=\sup_{x\in\mathbb{R}^{k}}\left(\sum_{i=1}^{k}v_{i}x_{i}-\sqrt{\sum_{i=1}^{k}\frac{\kappa^{2}_{i}}{x_{i}}}\right).$
(73)

Note, that if any of the $v_{i}$ are positive, then $h^{*}(v)$ is unbounded.
Furthermore, for those $i\in\\{1,\dots,k\\}$ for which $v_{i}=0$, we get
$x_{i}\to\infty$ and $0=\kappa_{i}\sqrt{-v_{i}}$ contribution to $h^{*}(v)$.
Therefore, only need to consider $\max_{i}v_{i}<0$ in the remainder. The
partial derivative w.r.t. $x_{i}$ of the expression that is optimized is

$v_{i}+\frac{1}{2\sqrt{\sum_{j=1}^{k}\frac{\kappa^{2}_{j}}{x_{j}}}}\frac{\kappa^{2}_{i}}{x_{i}^{2}}.$
(74)

This means that all partial derivatives are zero if $x$ is of the form

$x_{i}=c\frac{\kappa_{i}}{\sqrt{-v_{i}}},$ (75)

for some constant $c>0$. This gives

$h^{*}(v)=\sup_{c>0}\left(-c\lambda-\sqrt{\frac{\lambda}{c}}\right),$ (76)

where $\lambda=\sum_{i=1}^{k}\kappa_{i}\sqrt{-v_{i}}$. This supremum is
attained at

$c=2^{-2/3}\lambda^{-1/3}.$ (77)

Substituting this into (76) completes the proof. ∎