# Notes on: Srinivasa, C., Givoni, I., Ravanbakhsh, S., & Frey, B. J. (2017): Min-Max Propagation

## Overview

• min-max propagation for approximate min-max inference in factor graphs
• min-max problems that can be efficiently factored into a group of more simple functions

## Terminology

FG
factor graph
CSP
Constraint Satisfaction Problems
high-order factors
factors which has "a lot" of variables

## Notation

• variables to minimize over
• variables to maximize over
• is the factorizable min-max problem
• to index the values of
• to denote the subset of variables that depends on when
• denotes the variable indices
• denotes the factor indices
• denotes the set of neighbouring factor indices for variable
• denote the index set of variables connected to factor
• Variable-to-Factor messages: The messsage sent from variable to function is:

where is the message sent from function to variable and is the set of all neighbouring factors of variable , with removed.

• Factor-to-Variables Messages: The message sent from function to variable is computed using

• Initialization Using the Identity:

## Min-Max Optimization on Factor Graphs

• Consider min-max problems that can be efficiently factored into a group of more simple functions
• These min-max problems the following properties:
1. Cardinality of either or is linear in available computing resources (e.g. is an indexing variable which is linear in the number of indices)
2. Other variable can be decomposed, so that
3. Given , the function depends only on a subset of the variables (a clique) and / or exhibits a form which is easier to minimze individually than when combined with
• Can formulate a factorizable min-max problem as:

## Min-Max Propagation

### Initialization using the Identity

In the sum-product algorithm:

• messages are usually initialized using knowledge of the identity of the product operation.

Consider the case where the FG is a tree with some node chosen as a root, messages can be passed from the leaves to the root and back to the leaves, then:

• Initial message sent from a variable that is a leaf involves taking the product of an empty set of incoming messages, and therefore the message is initialized to the identity of the group , which is
• Need the identity of the semi-group, where

that is

## Efficient Update for High-Order Factors

### Notation

• are binary variables
• drop in factors and messages when context is obvious
• is the largest value that is obtained at some index , for some value :

i.e. denotes the index of the in the above expression, and simply denotes if it takes on 0 or 1 value. Further, is the index of the next largest message indices up to the largest ones, and be their corresponding assignment

### Procedure

Make the following assumptions:

1. The function can be minimized in time with any subset of its variables fixed