Optimización en problemas no convexos

1st Alexander González Cardenas 2nd David Gaona Medina 3rd Kevin Guevara Devia
Escuela Ciencias de la computación Escuela Ciencias de la computación Escuela Ciencias de la computación
Universidad del Valle Universidad del Valle Universidad del Valle
Cali, Colombia Cali, Colombia Cali, Colombia
gonzalez.alexander@correounivalle.edu.co david.gaona@correounivalle.edu.co kevin.guevara@correounivalle.edu.co

Abstract—In the present article a revision of the literature of puntos extremos, infinita o no tenerla.
non-convex problems is made, these such problems are explored Definición 2. Sea f una función definida en R sobre K ⊆ V,
from a mathematical point of view, as they are of great impor- se dice que f es convexa si
tance in the computer sciences. For this reason the most popular
algorithms used to solve non-convex optimization problems will f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) (1)
be seen in detail. Among others they are: Stochastic Gradient
Descent (SGD) and Adaptive Gradient Algorithm (ADAGRAD). para cada x, y ∈ D(f ) y λ ∈ (0, 1). Sı́ la función f cumple
Keywords—Non convex problems, ADAGRAD, SGD
Resumen—En el presente articulo se hace una revisión de la
la desigualdad de forma estricta que para cada valor de x e
literatura de los problemas no convexos, los cuales se desarrollan y sobre el dominio de la función, entonces se dice que f es
en el área de las Matemáticas y que son de suma importancia estrictamente convexa.
en las ciencias de la computación. Por lo cual se ve a detalle Definición 3. La función indicador Λ para un conjunto Ω
los algoritmos mas utilizados en la actualidad para resolver convexo se define
problemas de optimización de problemas no convexos como lo (
son SGD y ADAGRAD. 0 x∈Ω
Palabras clave—Problemas No Convexos, ADAGRAD, SGD ΛΩ (x) = (2)
∞ otro caso
I. I NTRODUCCI ÓN Definición 4. El conjunto de todos subgradientes de una
Los problemas no convexos surgen en Matemáticas cuando función f no suave y no convexa se define como: Para todo
se requiere minimizar cierta función objetivo (campo escalar) y en Rn , v en Rn y x ∈ D(f )
pero en ella existen muchos mı́nimos locales, también cuando
∂f (x) = {v : f (y) − f (x) > hv, (x − y)i + o(ky − xk)} (3)
se encuentra con puntos silla o regiones muy planas. Por esta
razón muchos de los problemas no-convexos se catalogan, al Definición 5. Dado un x ∈ Ω con Ω convexo, se dice que
menos, NP-Hard. Un ejemplo clásico es: ”Dado un conjunto x es un punto estacionario de primer orden sı́ 0 ∈ ∂(f +
de enteros, ¿Existe un subconjunto no vació donde la suma ΛΩ )(x); Generalizando se dice que un punto x es de orden
de sus elementos sea cero?”. Muchos de estos problemas  estacionario sı́ k∂(f + ΛΩ )(x), 0k ≤  , se especifica la
no tiene una solución eficiente para todos los casos, por anterior norma euclidiana k. , .k como la distancia entre un
lo que es importante el estudio de estos problemas y la punto y un conjunto.
posible construcción teórica de mejores algoritmos que logren Definición 6. Una proyección del punto x ∈ Rn , bajo el
optimizar la convergencia de los mismos; Cabe resaltar que el conjunto convexo cerrado Ω se define
presente documento hace una revisión, principalmente, de los
algoritmos utilizados en el ámbito del M ACHINE L EARNING, ProyecΩ (x) = arg minu∈Ω ku − xk (4)
los cuales se sustentan en mayor medida en las bases teóricas
Definición 7. (Envoltura de Moreau) Para toda función f
que se exponen sobre optimización de problemas no-convexos.
definida en Ω y λ > 0, se dice define la envoltura de Moreau
II. P RELIMINAR M ATEM ÁTICO para f como sigue

Se presenta la definición de conjunto convexo y luego se 1

fλ (x) = minu∈Ω f (u) + ku − xk2 (5)
ven las consideraciones para un conjunto no convexo (que en 2λ
este caso en particular sera un espacio vectorial de funciones). Definición 8. (Operador proximal)
[1], [2]
1
Definición 1. Sea V un espacio vectorial sobre el campo R. proxλf (x) = arg minu∈Ω f (u) + ku − xk2 (6)
2λ
Sea K un subespacio de V, se dice que K es convexo sı́
{∀ x, y ∈ K ∧ λ ∈ (0, 1) : λx + (1 − λ)y ∈ K} una Definición 9. (Continuidad M-Lipschitz) Sea f : Rd −→ R,
interpretación geométrica se puede ver como dados dos puntos se dice que esta es L-Lipschitz continua, si existe un L > 0
si se unen por un segmento, este segmento debe residir en K tal que
Sı́ K es convexo cerrado puede tener una cantidad finita de kf (x) − f (y)k ≤ M kx − yk (7)
Definición 10. (Continuidad L-Lipschitz) Sea f : Rd −→ R, IV. D IFICULTADES DE LOS PROBLEMAS NO CONVEXOS
se dice que esta es gradiente L-Lipschitz continua, si existe un
L > 0 tal que Los problemas no-convexos presentan varias dificultades
y problemas, entre ellas la existencia de múltiples mı́nimos
k∇f (x) − ∇f (y)k ≤ Lkx − yk (8) locales, por lo que garantizar que se convergio a un mı́nimo
local óptimo es complicado y en algunos casos imposible.
Definición 11. (Debilmente convexa) Una función f se dice Es más el solo hecho de saber si siquiera se convergió a un
µ-debil convexa, si f (x)+ µ2 kxk es convexa. De esto se puede mı́nimo local es, en algunos casos, muy complicado también,
deducir que si f es µ-debil convexa y γ < µ−1 entonces su especialmente cuando se está tratando problemas de muchas
envoltura (2) es continua y suave con gradiente variables, donde las dimensiones son muchas. Esto se debe
a la existencia de los puntos de silla, ya que dependiendo
∇fγ (x) = γ −1 (x − proxγf (x)) (9) del método que se utilice, pueden hacer creer al método que
ha llegado a un mı́nimo haciendo que este converja a uno
Definición 12. (Proyección del gradiente) de estos o que haga mucho más lento el avance del mismo,
entre mayor sean las dimensiones del problema, mayor será
1 el número de puntos de silla de forma exponencial y mayor
Gγ (x) = (x − proxγδΩ (x − γ∇f (x))) (10)
γ podrá ser la complejidad de estos mismos, tanto ası́ que el solo
hecho de saber si es un punto de silla se vuelve un problema
III. C RITERIOS DE CONVERGENCIA np-hard. Otra gran dificultad de este tipo de problemas son la
presencia de regiones muy planas, las cuales pueden engañar
III-A. Envoltura de Moreau como criterio de convergencia
a los métodos a creer que están próximos a llegar a un mı́nimo
para problemas con funciones no suaves y no convexas
local, haciendo que los estos se demoren mucho en salir de
La meta detrás de la optimización de los problemas con estas regiones, o se pierdan. [3]
funciones objetivo no convexas y no suaves es la de que se
encuentre un punto estacionario. Sin embargo saber a priori
el progreso de un algoritmo para este tipo de funciones no es
totalmente claro, por lo que una herramienta es la envoltura de
Moreau [2] la cual permite saber si se esta aproximando a un
punto estacionario mediante el valor de la norma de ∇fγ (x),
en general para cada x ∈ Rd , el punto próximo (estacionario)
x̂ = proxγf (x) satisface

kx̂ − xk = γk∇fγ (x)k

f (x̂) ≤ f (x) (11)

k∂f (x̂), 0k ≤ k∇fγ (x)k


Esto quiere decir entonces que x es un punto que satisface

k∇fγ (x)k ≤  y se acerca al punto con O() de distancia el
cual es -estacionario.

III-B. Proyección no convexa Figura 1. Región no convexa

En el análisis de convergencia de los métodos utilizados

para resolver problemas no convexos y suaves es el de la
proyección no convexa, en particular la de gradiente de f , V. S OLUCIONES
por lo que por (9) y (7) se obtiene el siguiente criterio que se V-A. Gradiente Descendiente Estocástico
le conoce como ”comparación del tamaño del paso”
El Stochastic Gradient descent (SGD) [4] aplica una ac-
(1 − Lγ )kGγ (x)k ≤ k∇fγ (x)k ≤ (1 + Lγ )kGγ (x)k (12) tualización, siguiendo la estrategia del gradiente descen-
diente, con la diferencia que el ”paso” se hace de forma
Este importante resultado dice que si ∇fγ (x) se acerca a un aleatoria por lo que si el paso es lo suficientemente
punto estacionario implica que también lo hace Gγ (x). La bueno se puede llegar a un punto -estacionario en tiempo
2
∗
importancia de este resultado radica que para la envoltura de O(( L + Lσ 2 ) × (f (x0 ) − f (x )), otros algoritmos como el
Moreau puede que la función para un numero k de iteraciones Batch gradient descent hace recomputos redundan-
se acerque al punto estacionario mas la distancia k∂f (x), 0k tes en cojuntos grandes de datos, por lo que el SGD al hacer
no converge, esto para funciones no suaves. una actualización por iteración resulta mucho mas rápido,
sumado a que la variación del salto es mas alta. Formalmente entre otras. Uno de los algoritmos revisados en este artı́culo fue
se presenta la ecuación que rige el SGD el gradiente descendente estocástico, en este se basan varios
de los algoritmos más usados en las redes neuronales para
xt+1 = xt + ηt g(xt , ξt ) (13)
minimizar la función que permite a estas “aprender”, uno
Se asumen las siguientes condiciones para f donde f es la de estos también fue revisado, el algoritmo ADAGRAD es
función objetivo a minimizar: una mejora del algoritmo previamente mencionado y es del
A1 f es continua M-Lipschitz (7) tipo de algoritmos donde la tasa de aprendizaje es adaptativa.
A2 f es continua L-Lipschitz (8) Pero el gran problema de la optimización convexa radica
A3 Eξ [g(x, ξ)] = ∇f (x) donde Eξ [.] es la función de en que garantizar la convergencia a un mı́nimo local es un
expectación sobre un espacio probabilı́stico. problema np-hard, debido a la imposibilidad de los algoritmos
A4 El ruido (noise) esta acotado por kg(x, ξ) − ∇f (x)k ≤ de diferenciar entre un punto de silla y un mı́nimo en funciones
S, ∀x de muchas dimensiones, ser capaces de escapar regiones
planas y no diverger en regiones de alta curvatura sin perder
Con las anteriores condiciones se puede establecer el siguiente
velocidad de convergencia.
teorema
Teorema 1: Para ηt con  ∈ (0, 21 ], entonces los gradientes R EFERENCIAS
del SGD convergen a cero, donde [1] P. Jain and P. Kar. (2017, Dec) Non-convex Optimization for Machine
1 Learning.
lı́m inf k∇f (xt )k2 t 2 − [2] Z. Chen, Z. Yuan, J. Yi, B. Zhou, E. Chen, and T. Yang, “Universal
t→∞
Stagewise Learning for Non-Convex Problems with Convergence on
En la literatura se escogen diferentes estrategias para calcular Averaged Solutions,” arXiv e-prints, p. arXiv:1808.06296, Aug 2018.
ηt puesto que SGD es demasiado sensible a este parámetro. [3] Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio,
“Identifying and attacking the saddle point problem in high-dimensional
non-convex optimization,” arXiv e-prints, p. arXiv:1406.2572, Jun 2014.
[4] X. Li and F. Orabona, “On the Convergence of Stochastic Gradient
V-B. Método del gradiente adaptativo Descent with Adaptive Stepsizes,” arXiv e-prints, p. arXiv:1805.08114,
May 2018.
El Adaptive Gradient Algorithm (ADAGRAD) [4], [5] es un [5] S. Ruder, “An overview of gradient descent optimization algorithms,”
algoritmo que esta basado en al idea del gradiente descendiente arXiv e-prints, p. arXiv:1609.04747, Sep 2016.
estocástico con la diferencia de que es capaz de adaptar
su ”paso” a través de la información suministrada en cada
iteración por los subgradientes (3) de la función objetivo.
Bajo las mismas condiciones presentadas para el algoritmo
SGD y con las condiciones de que se tiene disponible el
operador proximal de f (6), se enuncia el siguiente lema.
Lema 1: Sea f (x) una función convexa, H0 = GI con
G ≥ maxt kgnt kı́nf , y un numero de iteración To que satisface
T ≥ M max G+maxi2kg1:T,ik , i=1 kg1 : T, ik , el algoritmo
Pd

retorna la solución promedio x̂ tal que

E[f (xˆT ) − f (x∗ )] ≤ 
donde x∗ = arg minx∈Ω f (x), g1:T (g(x1 ), ..., g(xT )) con
g1:T,i siendo los subgradientes acumulados del gradiente es-
tocástico en la coordenada i en la iteración T .
Finalmente cabe resaltar que este algoritmo tiene múltiples
variantes para los problemas no convexos, dado que este fue
diseñado para funciones fuertemente convexas, sin embargo
con las condiciones anteriormente enunciadas y haciendo uso
del lema, se pueden construir teoremas donde se proponen
distintas estrategias para calcular T o refinar la matriz g de
los subgradientes.
VI. C ONCLUSIONES
En este artı́culo hemos hablado de algunos de los algoritmos
usados para la optimización no convexa y de las enormes
dificultades que este tipo de problemas proporcionan, tanto
es ası́ que la un gran número de estos son problemas abiertos
que siguen en investigación por diversas ramas, como lo es
la matemática, la estadı́stica y las ciencias de la computación