Cotas de riesgo en optimización convexa estocástica mediante estimación del desempeño computacional de peor caso
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Se considera el problema de optimización convexa estocástica, que permite una representación general de una diversa gama de aplicaciones en aprendizaje automático, estadística e investigación de operaciones, entre otros. En el estudio de tal problema, se analiza la complejidad de generalizar el conocimiento obtenido a través de una muestra de datos con comportamiento desconocido, minimizando un problema convexo definido por la muestra. Debido a no realizar supuestos sobre tales datos, los resultados comunes entregan cotas asintóticas que garantizan órdenes de convergencia de los errores inducidos por aproximaciones al optimo a través de métodos de primer orden, descartando una cuantificación exacta del peor caso alcanzable en la práctica. En este trabajo, se plantea la hipótesis que es posible recuperar cotas de generalización ayudándose de un problema computacional que calcula el rendimiento de peor caso de tanto el error de optimización como la estabilidad algorítmica de un método de primer orden. Se proponen problemas semi definidos que permiten la representación exacta de ambas métricas, para distintos tipos de métodos. Luego, basándose en una implementación de los modelos desarrollados, se procura inferir expresiones simbólicas de los resultados obtenidos a través de un proceso heurístico, recuperando información que puede traducirse en demostraciones de garantías de generalización. Se encontró una representación matricial de dos tipos de métodos de primer orden, aprovechando la estructura de las actualizaciones. También se realizó el proceso heurístico para el método de punto proximal, encontrando casos donde es posible su correcta utilización y otros donde aparecen limitaciones prácticas que imposibilitan producir una demostración rigurosa.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2021