Ejemplos de juguetes para solucionadores de Plotkin-Shmoys-Tardos y Arora-Kale

Me gustaría entender cómo el solucionador Arora-Kale SDP se aproxima a la relajación Goemans-Williamson en un tiempo casi lineal, cómo el solucionador Plotkin-Shmoys-Tardos aproxima los problemas de "empaquetamiento" y "cubrimiento" fraccionales en un tiempo casi lineal, y cómo los algoritmos son instancias del marco abstracto "aprender de los expertos".

La tesis de Kale tiene una excelente presentación, pero me resulta muy difícil saltar directamente al marco abstracto, y preferiría comenzar con un ejemplo de un problema simple por el cual es absolutamente obvio qué hacer, y luego pasar a problemas más generales , agregando progresivamente "características" al algoritmo y a su análisis.

Por ejemplo:

¿Cómo resuelve Plotkin-Shmoys la relajación de programación lineal de la cubierta de vértice no ponderada? ¿Cubierta de vértice ponderada? Establecer cubierta? Coincidencia bipartita?

¿Cuál es el ejemplo más simple en el que el algoritmo Arora-Kale está haciendo algo interesante? ¿Cómo calcula el mayor valor propio del laplaciano de un gráfico?

(Calcular el valor propio más grande del Laplaciano es equivalente al problema de resolver una versión más débil de la relajación Goemans-Williamson SDP de Max Cut, en la que, en lugar de requerir que cada vector sea de longitud uno, desea la suma de los cuadrados de las normas para ser | V |.)

Luca, ya que ha pasado un año, probablemente hayas investigado tu propia respuesta. Estoy respondiendo algunas de sus preguntas aquí solo para el registro. Reviso algunos algoritmos de relajación lagrangiana para los problemas que menciona, y bosquejo la conexión con el aprendizaje (en particular, siguiendo el consejo de expertos). No comento aquí sobre algoritmos SDP.

Tenga en cuenta que los algoritmos particulares que menciona no se ejecutan en un tiempo casi lineal. (Existe un algoritmo de tiempo casi lineal para problemas de empaque o cobertura dados explícitamente . Ver Beating Simplex para programas lineales de empaque fraccionado y cobertura ). Los algoritmos que tiene en mente generalmente tienen variantes que se ejecutan en un número casi lineal de iteraciones , pero cada una La iteración generalmente requiere al menos tiempo lineal también. Discuto algunos de estos algoritmos a continuación.

Algunas funciones útiles

Antes de comenzar, aquí hay algunas funciones que usaremos en los bocetos de prueba. (Si está interesado en los algoritmos, pero no en los detalles de la prueba, puede saltar adelante). Para cualquier vector $y$ , defina $\mbox{Lmax}(y)$ como $\ln \sum_i \exp(y_i)$ . Esta función es un límite superior en : Análogamente, defina como , un límite inferior en .$\max_i y_i$

$$\max_i y_i ~\le~ \mbox{Lmax}(y) ~\le~ \max_i y_i + \ln m.$$ $\mbox{Lmin}(y)$$-\mbox{Lmax}(-y)$$\min_i y_i$

Por conveniencia en lo que sigue, usamos para denotar el gradiente de Lmin. Usamos para denotar el gradiente de Lmax.$g(y)$$\nabla \mbox{Lmin}(y)$$G(y)$$\nabla \mbox{Lmax}(y)$

Explícitamente, es mientras que es .$g_i(y)$$\exp(-y_i)/\sum_{i'} \exp(-y_{i'})$$G_i(y)$$\exp(y_i)/\sum_{i'} \exp(y_{i'})$

Lmin y Lmax son suaves en el siguiente sentido: para cualquier vector e , y $d\in[0,\varepsilon]^n$$y\in R^n$

$$\mbox{Lmin}(y+d) ~\ge~ \mbox{Lmin}(y) ~+~ (1-O(\varepsilon))\, d \cdot g(y)$$ $$\mbox{Lmax}(y+d) ~\le~ \mbox{Lmax}(y) ~+~ (1+O(\varepsilon))\, d \cdot G(y).$$

Tenga en cuenta que ambos gradientes tienen una norma igual a 1: . (En todo momento usamos para denotar la norma 1).$|G(y)| = |g(y)| = 1$$|z|$

Tenga en cuenta también que, para una matriz , el gradiente de la función con respecto a es (por la regla de la cadena) . Más explícitamente, la derivada parcial de la función con respecto a es . Asimismo, la derivada parcial de Lmax con respecto a es .$A$$x\mapsto \mbox{Lmin}(Ax)$$x$$(g(Ax))^T A$$x_j$$\sum_i A_{ij} \exp(-A_i x) / \sum_i \exp(-A_i x)$$(Ax)$$x_j$$\sum_i A_{ij} \exp(A_i x)/\sum_i \exp(A_i x)$

Tapa de conjunto fraccional

Arreglar una instancia de Set-Cover. Deje denotar la matriz de incidencia elemento / conjunto. Por lo tanto, si , si no 0, y es el grado en que la cobertura fraccional cubre el elemento .$A$$A_{es} = 1$$e\in s$$A_e x$$x$$e$

El LP es . Dado , el algoritmo es$\min\{ |x| : A x \ge 1; x \ge 0\}$$\varepsilon\in (0,1)$

---

1. Inicialice todos . Deje . $x_s = 0$$N=\log(n)/\varepsilon$

2. Repita hasta : $\min_e A_e x \ge N$

   2.1. Elija maximizando la derivada parcial de Lmin wrt . (Explícitamente, elija maximizing .) $s$$(Ax)$$x_s$ s ∑ e ∈ s exp ( - ∑ s ′ ∋ e x s ′
   $s$$\sum_{e\in s} \exp(-\sum_{s'\ni e} x_{s'})$

   2.2. Aumente en . $x_s$$\varepsilon$

3. Devuelve .$x/\min_{e} A_e x$

---

El algoritmo devuelve una solución aproximada en las iteraciones , donde es el número de elementos y es el óptimo cubierta de conjunto fraccional (trivialmente ). (Un algoritmo similar aparece en el documento que mencionó Chandra . Vertex Cover es, por supuesto, un caso especial).$(1+O(\varepsilon))$$O(|x^*|\log(n)/\varepsilon^2)$$n$$x^*$$|x^*|\le n$

( Observación: tenga en cuenta que el límite de iteración no depende de la cantidad de conjuntos, solo de la cantidad de elementos. Por lo tanto, el algoritmo se puede usar con un sistema de conjuntos definido implícitamente, siempre que, dados los pesos de los elementos, se pueda eficientemente encuentre un conjunto de peso total máximo (o casi máximo). Este tipo de oráculo es el mismo que el oráculo de separación requerido para aplicar el algoritmo elipsoide al problema dual . Para problemas de empaquetamiento como el empaquetado de conjuntos, necesita un oráculo que, los pesos dados en los elementos, devuelve un conjunto que minimiza el peso total. Para problemas tales como el flujo de múltiples productos, es posible que, por ejemplo, necesite encontrar una ruta que minimice la suma de algunos pesos de borde dados).

Aquí hay un boceto de la prueba de la garantía de rendimiento. En cada iteración, la derivada parcial wrt la elegida es al menos, donde es la cobertura óptima del conjunto fraccionario.$s$$1/|x^*|$$x^*$

(Para ver por qué, recuerde que el gradiente de Lmin con respecto a es . Si tuviéramos que elegir un conjunto al azar de la distribución , el valor esperado de la derivada parcial con respecto a sería . Dado que , esto es al menos . Dado que , esto es al menos . Por lo tanto, debe existir alguna dé una derivada parcial al menos . Dado que el algoritmo elige$(Ax)$$x$$(g(Ax))^T A$$s'$$x^*/|x^*|$$x_{s'}$$(g(Ax))^T \,A x^*/|x^*|$$Ax^* \ge 1$$|g(Ax)|/|x^*|$$|g(Ax)|=1$$1/|x^*|$$s$$1/|x^*|$$x_s$ 1 / | x ∗en cada iteración para maximizar la derivada parcial, logra una derivada parcial de al menos.)$1/|x^*|$

Luego, el tamaño del paso se elige lo suficientemente pequeño como para que ninguna coordenada de aumente en más de . Por lo tanto, debido a la suavidad de Lmin, aumentar a aumenta al menos en .$\varepsilon$$A x$$\varepsilon$$x_s$$x_s+\varepsilon$$\mbox{Lmin}(Ax)$$(1-O(\varepsilon))\varepsilon/|x^*|$

De esta forma, el algoritmo mantiene el invariante (Tenga en cuenta que Lmin es igual a .)

$$\mbox{Lmin}(Ax) \ge (1-O(\varepsilon)) |x|/|x^*| - \ln n.$$ $(\overline 0)$$\ln n$

Al finalizar, en el invariante, el término es multiplicado por el lado izquierdo, por lo que mediante el cálculo se obtiene. Después de la normalización en la última línea del algoritmo, esto implica.$\ln n$$O(\varepsilon)$$\min_e A_e x \ge (1-O(\varepsilon)) |x|/|x^*|$$|x| \le (1+O(\varepsilon))|x^*|$

FWIW, las desigualdades involucradas en probar la invariante son esencialmente las mismas que las involucradas en probar el límite de Chernoff. (De hecho, este algoritmo puede derivarse aplicando el método de probabilidades condicionales a un esquema de redondeo aleatorio que muestrea repetidamente conjuntos de la distribución (con reemplazo), aumentando para cada conjunto muestreado Esta desrandomización de eso da el algoritmo: la invariante subyacente es solo que el estimador pesimista se mantiene por debajo de 1. Las penalizaciones exponenciales en el estimador pesimista provienen del uso del límite de Chernoff en el análisis del esquema de redondeo. Esta idea básica se explica más adelante. en el periódico que mencionó Chandra ).$x^*/|x^*|$$x_s$$s$

Cubierta de conjunto ponderada fraccional (y cubierta fraccional general)

Para manejar problemas como la cobertura de conjunto ponderado de manera eficiente , modificamos el algoritmo para usar incrementos no uniformes (una idea debido a Garg y Konemann ).

El LP es , donde extiende sobre los elementos, extiende sobre los conjuntos y todas las variables son no -negativo. Para presentar el algoritmo, primero reescriba el problema como un problema de cobertura general. Deje para y de otro modo. Entonces (con un cambio de variables, escalando cada por ), el LP es , que podemos ver como un LP de cobertura general. Aquí está el algoritmo:$\min\{ c\cdot x : (\forall e) \sum_{s\ni e} x_s \ge 1\}$$e$$s$$A_{es} = 1/c_s$$e\in s$$A_{es} = 0$$x_s$$c_s$$\min\{ |x| : A x \ge 1; x \ge 0\}$

---

1. Inicialice todos . Deje .$x_s = 0$$N=\log(n)/\varepsilon$

2. Repita hasta que se hayan eliminado todas las restricciones de cobertura:

   2.1. Elija maximizando la derivada parcial de Lmin wrt . (Explícitamente, elija maximizing .)$s$$(Ax)$$x_s$
   $s$$\sum_{e\in s} \exp({-\sum_{s'\ni e} x_{s'}})/c_s$

   2.2. Aumente en , donde se elige al máximo de tal manera que, por cada restricción de cobertura restante , el aumento en sea ​​como máximo .$x_s$$\delta$$\delta$$e$$A_e \cdot x$$\varepsilon$

   2.3 Eliminar todas las restricciones que cubren tal que .$e$$A_e\cdot x \ge N$

3. Devuelve .$x/\min_e A_e\cdot x$

---

El algoritmo devuelve una solución aproximada iteraciones , donde es el número de restricciones de cobertura. (Cada iteración aumenta algunos restantes en ; esto puede suceder solo veces a una restricción antes de que se elimine). La prueba de corrección es esencialmente la misma invariante que para Set Cover.$(1+O(\varepsilon))$$O(n\log(n)/\varepsilon^2)$$n$$A_e x$$\varepsilon$$N/\varepsilon$

La cubierta Vertex ponderada es un caso especial.

Coincidencia bipartita fraccional máxima

Dado un gráfico , el LP natural para el problema es .$G=(U,W,E)$$\max\{|x| : \forall v.\, \sum_{e\ni v} x_e \le 1\}$

En la representación matricial, este es un empaque LP con coeficientes 0-1 ( si ). Dichos problemas no requieren incrementos no uniformes, por lo que un algoritmo simple análogo al algoritmo Set Cover no ponderado (pero para empacar) hará:$\max\{|x| : Ax \le 1; x \ge 0\}$$A_{ve} = 1$$v\in e$

---

1. Inicialice todo . Deje .$x_e = 0$$N=\log(n)/\varepsilon$

2. Mientras :$A x < N$

   2.1. Elija minimizando la derivada parcial de Lmax wrt . (Explícitamente, elija para minimizar .)$e$$(Ax)$$x_e$
   $e$$\sum_{v\in e} \exp(\sum_{e'\ni v} x_{e'})$

   2.2. Aumente en . $x_e$$\varepsilon$

3. Devuelve .$x/\max_{v} A_v x$

---

El algoritmo devuelve una solución aproximada iteraciones . (Esto se debe a que cada iteración aumenta en y, finalmente, antes de la normalización, .)$(1-O(\varepsilon))$$O(n\log(n)/\varepsilon^2)$$|x|$$\varepsilon$$|x| = O(N n)$

Solo por diversión, aquí hay un algoritmo alternativo curioso para Perfect Bipartite Matching. Recuerde que . Sea.$G=(U,W,E)$$n=|U|=|W|$

---

1. Inicialice todo . Deje . $x_e = 0$$N=4\ln(n)/\varepsilon$

2. Repita veces:$n\,N$

   2.1. Elija uniformemente al azar de . 2.2. Elija tal que minimizando . 2.3. Aumente en . $u$$U$
   $w$$(u,w)\in E$$\sum_{e\ni w} x_e$
   $x_{uw}$$\varepsilon$

3. Volver .$x/N$

---

Si tiene una coincidencia perfecta, el algoritmo devuelve una tal que , y, con alta probabilidad, para todos los vértices , , y para todos los vértices , . Si está interesado en los detalles de la prueba, pregunte ...$G$$x$$|x|=n$$u\in U$$1-O(\varepsilon) \le \sum_{e\ni u} x_e \le 1+O(\varepsilon)$$w\in W$$\sum_{e\ni w} x_e \le 1+O(\varepsilon)$

Embalaje y revestimiento mixto

Es posible que haya preguntado sobre la coincidencia bipartita esperando un ejemplo de un problema de empaquetamiento y cobertura mixtos , es decir, uno de la forma Aquí hay un algoritmo para tales problemas. Primero, normalice de modo que y .

$$\exists x?~ Px \le p; Cx \ge c; x \ge 0.$$ $p=\overline 1$$c=\overline 1$

Sea el número de restricciones (filas en más filas en ).$m$$P$$C$

---

1. Inicialice todos . Deje .$x_j = 0$$N=2\ln(m)/\varepsilon$

2. Mientras :$P x < N$

   2.1. Elija para que la derivada parcial de Lmax con respecto a sea ​​como máximo la derivada parcial de Lmin con respecto a . (Explícitamente, elija tal que$j$$(Px)$$x_j$$(Cx)$$x_j$$j$

   $$\frac{\sum_i P_{ij} \exp(P_i x)}{\sum_{i}\exp(P_i x)} \le \frac{\sum_i C_{ij} \exp(-C_i x)}{\sum_{i}\exp(-C_i x)}.)$$

   2.2. Aumente en , donde se elige al máximo de tal manera que ninguna restricción o la restricción restante aumente en más de .$x_j$$\delta$$\delta$$P_i x$$C_i x$$\varepsilon$

   2.3. Eliminar todas las restricciones que cubren tal que .$i$$C_i x \ge N$

3. Devuelve .$x/\max_i P_i x$

---

Suponiendo que el problema dado es factible, el algoritmo devuelve una tal que y . El número de iteraciones es , porque cada iteración aumenta alguna restricción de , y esto puede suceder para cada restricción en la mayoría de las veces.$x$$Px\le 1$$Cx\ge 1-O(\varepsilon)$$O(m\ln(m)/\varepsilon^2)$$\varepsilon$$N$

La prueba de corrección es a través de la invariante La invariante implica Al finalizar, el lado izquierdo es , lo que demuestra la garantía de rendimiento.

$$\mbox{Lmax}(Px) \le 2\ln(m) + (1+O(\varepsilon)) \mbox{Lmin}(Cx).$$ $$\max Px \le 2\ln(m) + (1+O(\varepsilon)) \min Cx.$$ $\Omega(\log(m)/\varepsilon)$

En el Paso 2.1, el deseado debe existir siempre que el problema original sea factible. (Esto se debe a que, para cualquier factible , y cualquier , si tuviéramos que elegir una aleatoria de la distribución , el valor esperado de la derivada parcial de Lmax con respecto a sería a lo sumo (vea el boceto de prueba anterior para Set Cover). Asimismo, el valor esperado de la derivada parcial de Lmin con respecto a sería al menos . Por lo tanto, hay una$j$ $x^*$$x$$j'$$x^*/|x^*|$$(Px)$$x_{j'}$$1/|x^*|$$(Cx)$$x_{j'}$$1/|x^*|$$j$tal que la derivada parcial de Lmax con respecto a es como máximo la derivada parcial de Lmin .)$(Px)$$x_{j'}$$(Cx)$

Luego, la invariante se mantiene en cada iteración porque, mediante la elección de y , y la suavidad de Lmin y Lmax, al aumentar a aumenta Lmax como máximo veces el aumento en Lmin .$x_j$$\delta$$x_j$$x_j+\delta$$(Px)$$1+O(\varepsilon)$$(Cx)$

Aprendizaje (seguimiento de expertos / impulso)

Una referencia para comprender esta conexión es el juego adaptativo que usa pesos multiplicativos , de Freund y Schapire. Aquí hay un resumen rápido para dar la idea técnica.

Considere el siguiente juego repetido. En cada ronda : $t$

1. Eliges una distribución de probabilidad en (los llamados expertos ). $p^t$$[n]$$n$
2. Conociendo , el adversario elige un vector de pago . $p^t$$a^t\in [0,1]^{n}$
3. Usted recibe el pago por la ronda. $p^t\cdot a^t$

El juego se detiene después de algunas rondas. Su objetivo es minimizar su arrepentimiento en comparación con cualquier experto individual (es decir, estrategia pura) . Es decir, su objetivo es minimizar .$i$$(\max_i \sum_t a^t_i) - \sum_t p^t\cdot a^t$

Arregle cualquier . Deje que el vector denote , es decir, multiplicado por la suma del vector de los vectores de pago hasta el tiempo . Recuerde que es el gradiente de Lmax .$\varepsilon>0$$y^t$$\varepsilon \sum_{s \le t} a^s$$\varepsilon$$t$$G(y)$$(y)$

Aquí está la estrategia básica que analizaremos: en la ronda , elija para que sea .$t$$p^t$$G(y^{t-1})$

Por inspección, esto le da recompensa en la ronda .$a^t \cdot G(y^{t-1})$$t$

Debido a la propiedad de suavidad de , Es decir, en cada ronda, no puede aumentar más de veces su pago. Dado que , esto mantiene la invariante de que es como máximo sus tiempos de pago totales , más . Por otro lado, su arrepentimiento en comparación con el mejor experto es , es decir,$F$

$$\mbox{Lmax}(y^t) \le \mbox{Lmax}(y^{t-1}) + (1+O(\varepsilon)) \varepsilon a^t \cdot G(y^{t-1}).$$ $\mbox{Lmax}(y^t)$$\varepsilon(1+O(\varepsilon))$$\mbox{Lmax}(\overline 0) = \ln n$$\mbox{Lmax}(y^t)$$\varepsilon(1+O(\varepsilon)$$\ln(n)$$i$$\max_i \sum_t a^t_i$$\varepsilon^{-1} \max_i y^t_i$, que a su vez es como máximo .$\varepsilon^{-1} \mbox{Lmax}(y^t)$

Por lo tanto, su arrepentimiento es como máximo , más multiplicado por su pago total.$\varepsilon^{-1} \ln(n)$$O(\varepsilon)$

Observación: Creo que, como señalan Freund y Schapire, un algoritmo de "impulso" (en teoría del aprendizaje) también está implícito en este análisis. Vea su artículo para más detalles.

Minimizando el pago total

Puede derivar una estrategia similar para la configuración en la que el objetivo es minimizar , en lugar de maximizar, la recompensa total. Su arrepentimiento, que aún desea minimizar, es . En ese caso, la estrategia correspondiente es elegir para que sea el gradiente de . Con esta estrategia, su arrepentimiento es nuevamente como máximo más multiplicado por su pago total.$\sum_t p^t\cdot a^t - \min_i a^t_i$$p^t$$\mbox{Lmin}(y^t)$$\varepsilon^{-1} \ln n$$O(\varepsilon)$

Conexión a algoritmos de relajación lagrangiana

Para ver la conexión con los algoritmos de relajación lagrangiana, arregle una instancia de Set-Cover. Considere el último tipo de juego (con el objetivo de minimizar la recompensa), donde los expertos corresponden a los elementos de su sistema establecido. En cada ronda, elija la distribución de probabilidad para que sea el gradiente de Lmin como se indicó anteriormente, y haga que el adversario elija el vector de pago en función de siguiente manera: elija el conjunto maximizando , luego deje si , y caso contrario.$e$$p^t$$(y^t)$$a^t$$p^t$$s^t$$\sum_{e\in s} p^t_e$$a^t_e = 1$$e\in s^t$$a^t_e = 0$

Dada la condición de detención correcta (discutida a continuación), este proceso le proporciona exactamente el algoritmo Set-Cover discutido al inicio.

La garantía de rendimiento del algoritmo se deriva del arrepentimiento vinculado de la siguiente manera. Deje que sea ​​la cantidad de veces que el adversario eligió el set durante la jugada. Deje ser la cubierta óptima del conjunto fraccional. Dejeser el número de rondas jugadas. El límite de arrepentimiento implica $X_s$$s$$x^*$$T=|X_s|$

$$\textstyle \sum_t a^t\cdot p^t \le \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$

Usando la definición de , el pago th (el término en la suma de la izquierda) es igual a . El adversario eligió para minimizar esta recompensa. Si el adversario hubiera elegido al azar de la distribución, la expectativa de la recompensa habría sido (Arriba usamos ese para todo , y ) Dado que cada pago es al menos$a^t$$t$$t$$\sum_{e\in s^t} p^t_e$$s^t$$s^t$$x^*/|x^*|$

$$\sum_s \frac{x^*_s}{|x^*|} \sum_{e\in s} p^t_e ~=~ \frac{1}{|x^*|} \sum_e p^t_e \sum_{s\ni e} x^*_s ~\ge~ \frac{1}{|x^*|} \sum_e p^t_e ~=~ \frac{1}{|x^*|}.$$ $\sum_{s\ni e} x^*_s \ge 1$$e$$|p^t| = 1$$1/|x^*|$, el límite de arrepentimiento implica Por la definición de , tenemos (cada ronda elige un conjunto) y , dando Hacemos que el proceso se detenga cuando , entonces (reorganizando los términos) Es decir, la normalización de da una cobertura de tamaño fraccional como máximo tiempos óptimos $$\frac{T}{|x^*|} \le \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$ $X$$|X| = T$$\sum_t a_e^t = \sum_e [e\in s^t] = \sum_{s\ni e} X_s$ $$\frac{|X|}{|x^*|} \le \varepsilon^{-1}\ln(m) +\min_e \sum_{s\ni e} X_s.$$ $\min_e \sum_{s\ni e} X_s = \Omega(\varepsilon^{-2}\ln m)$ $$\frac{|X|}{\min_e \sum_{s\ni e} X_s}~ \le~ (1+O(\varepsilon)|x^*|.$$ $X$$(1+O(\varepsilon))$

Observación: En cierto sentido, esta interpretación de la teoría del aprendizaje generaliza la interpretación algorítmica. Sin embargo, algunas de las técnicas algorítmicas necesarias para la eficiencia (como los incrementos no uniformes y la eliminación de restricciones de cobertura satisfechas) no parecen trasladarse al entorno de la teoría del aprendizaje de forma natural. Del mismo modo, los algoritmos para empaquetado y cobertura de LPs mixtos (por ejemplo, estos ) no parecen tener análogos naturales en el contexto de la teoría del aprendizaje.