FenixEdu™

Dissertação

{en_GB=COCO Denoiser – Using Co-coercivity for Variance Reduction in Stochastic Convex Optimization} {} EVALUATED

Detalhes: {pt=Os algoritmos de primeira-ordem para optimização estocástica têm ganho inegável relevância, em particular pelo papel preponderante que desempenham em Aprendizagem Automática. Estes algoritmos aceitam cegamente gradientes ruidosos facultados por um oráculo, que podem ser inconsistentes com propriedades estruturais da função de custo em questão. Nós exploramos a co-coercividade do gradiente de funções convexas L-suaves para obter estimativas mais precisas desses gradientes. O método apresentado nesta tese é então designado por filtro de Co-coercividade (COCO). O nosso filtro é um estimador conjunto de máxima verosimilhança (MV) para os gradientes, restringidos dois a dois por condições de co-coercividade. Embora a MV nos leve a um Problema Quadrático Quadraticamente Restringido, propomos um algoritmo de primeira-ordem eficiente para o COCO, baseado no método Fast Dual Proximal Gradient. Para o Filtro que considera um único par de gradientes, derivamos a sua solução em forma fechada, resultado que demonstramos ser relevante na prática. Realizamos uma análise teórica que fornece intuição acerca do ajuste de parâmetros e dos resultados dados pelo estimador, demonstrando, em particular, como o COCO necessariamente leva a melhorias em relação ao oráculo com ruído. A nossa análise experimental corrobora estes resultados e mostra que o COCO, apesar de ser um estimador enviesado, leva à diminuição do erro quadrático médio dos gradientes da função de custo. Para ilustrar o seu impacto em optimização estocástica, testamo-lo usando quer dados sintéticos, quer uma tarefa real de aprendizagem online. Estes testes demonstram que o COCO leva a melhorias na redução de variância em relação a algoritmos correntes., en=First-order methods for stochastic optimization gained undeniable relevance, in particular due to their pivotal role in machine learning. These methods blindly accept noisy gradients provided by an oracle, which may be inconsistent with structural properties of the underlying objective function. We exploit gradient co-coercivity of L-smooth convex objective functions to obtain more accurate gradient estimates. The method introduced in this thesis is then coined as the co-coercivity (COCO) denoiser. Our denoiser is a joint Maximum Likelihood (ML) estimator for the gradients, constrained by pairwise co-coercivity conditions. Although ML leads to a Quadratically Constrained Quadratic Problem, we introduce an efficient first-order algorithm for COCO, which is based on the Fast Dual Proximal Gradient method. For the denoiser that deals with a single pair of gradients, we derive the closed-form solution for the ML problem, which is relevant in practice, since our experiments have shown that even this simple scenario leads to variance reduction gains in stochastic optimization. We carry out a theoretical analysis that provides insight into parameter tuning and estimator results, showing in particular why COCO necessarily improves with respect to the noisy oracle. The experimental analysis corroborates these results and shows that the COCO estimator, although not unbiased, leads to a reduction of the mean squared error of the function gradients. To illustrate the impact in stochastic optimization, we use both synthetic data and a real online learning task. Our experiments show that COCO leads to improvements in variance reduction with respect to baseline algorithms. }
Keywords: {pt=Optimização Estocástica, Algoritmos de Primeira Ordem, Optimização Convexa, Co-coercividade, Filtro COCO, Redução de Variância, en=Stochastic Optimization, First-Order Algorithms, Convex Optimization, Co-coercivity, COCO Denoiser, Variance Reduction}

Discussão: janeiro 25, 2021, 10:0