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

## Table of Contents

## 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:
- Cardinality of either or is linear in available computing resources (e.g. is an indexing variable which is linear in the number of indices)
- Other variable can be decomposed, so that
- 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 isNeed 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:

- The function can be
*minimized*in time with any subset of its variables fixed