High-probability zeroth-order online convex optimisation beyond Euclidean geometry

Resumo Técnico: Otimização Convexa Online de Ordem Zero de Alta Probabilidade Além da Geometria Euclidiana

Configuração do Problema
Este trabalho aborda o problema da otimização convexa online (OCO) em um cenário de ordem zero, onde o aprendiz tem acesso apenas a avaliações da função, não a gradientes. A configuração específica envolve uma sequência de perdas aleatórias Lipschitzianas $f_t$ retiradas de uma distribuição $\mu$. Embora as realizações $f_t$ não precisem ser convexas, assume-se que sua função média $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ é convexa. O aprendiz opera sobre um conjunto compacto e convexo $\Theta \subset \mathbb{R}^d$ e visa minimizar o pseudo-arrependimento:
$$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$$
O modelo de feedback permite que o aprendiz consulte a função em dois pontos por rodada, $x_t \pm h_t \zeta_t$, onde a direção $\zeta_t$ é amostrada a partir da fronteira de uma bola $\ell_r$ de acordo com a medida cônica. Assume-se que as perdas são $L$-Lipschitzianas em relação a uma norma $\ell_q$, e o algoritmo emprega um regularizador fortemente convexo $\ell_p$ dentro de uma estrutura Follow-The-Regularised-Leader (FTRL).

Metodologia
O artigo propõe um algoritmo adaptativo e "anytime" (SOLO FTRL) que utiliza estimadores de gradiente por diferenças finitas aleatorizados de dois pontos. As inovações metodológicas centrais residem na generalização geométrica e na análise probabilística:

1. Estimação de Gradiente Generalizada: O estimador de gradiente é construído usando direções amostradas a partir da medida cônica na fronteira de uma bola $\ell_r$ ($\zeta \sim \partial B_d^r$). O estimador é definido como:
   $$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$$
   onde $n_r(\zeta)$ é o normal unitário à esfera $\ell_r$ em $\zeta$. Isso generaliza estimadores esféricos clássicos ($r=2$) e permite geometrias de amostragem $\ell_1$ ou $\ell_\infty$.

2. Análise de Momentos e Concentração: Diferentemente de trabalhos anteriores que dependem de limites em expectativa (tipicamente usando momentos de segunda ordem), esta análise estabelece limites de todos os momentos para o estimador de gradiente na norma dual $\ell_{p^*}$. Ao provar que a sequência de erros quadráticos da norma dual satisfaz uma condição de momento de Bernstein sequencial (SBM), os autores derivam desigualdades de concentração de alta probabilidade uniformes no tempo. Isso envolve controlar o comportamento de cauda do estimador de gradiente usando resultados de concentração de medida para funções Lipschitzianas em esferas $\ell_r$.

3. Algoritmo Adaptativo: O algoritmo é totalmente orientado por dados e não requer conhecimento do horizonte temporal $n$ ou de constantes do pior caso derivadas da análise de momentos. Requer apenas a especificação dos parâmetros geométricos ($p, r$), do regularizador e de um limite superior para o tamanho do domínio.

Principais Contribuições

1. Limites Unificados de Alta Probabilidade: O artigo fornece os primeiros limites unificados de alta probabilidade para arrependimento em OCO de ordem zero para todas as combinações de geometria $p, q, r \in [1, \infty]$. Esses limites valem para perdas Lipschitzianas aleatórias com média convexa, fortalecendo garantias anteriores em expectativa para declarações de alta probabilidade uniformes no tempo.
2. Limites de Momentos do Estimador de Gradiente: Os autores provam limites de momentos novos para estimadores de gradiente aleatorizados de dois pontos em norma $\ell_r$ na norma dual $\ell_{p^*}$. Esses resultados rastreiam a dependência da geometria de amostragem ($r$) e da norma Lipschitziana ($q$), estabelecendo que as normas duais quadradas cumulativas comportam-se como um processo subgama.
3. Limites Inferiores Independentes do Algoritmo: O artigo estabelece limites inferiores de probabilidade constante para a mesma classe de problemas. Esses limites melhoram resultados anteriores em expectativa (especificamente para $p=q=1$, removendo um fator $\sqrt{\log d}$) e cobrem a faixa completa de $p, q \in [1, \infty]$ com uma única construção.
4. Identificação de uma Lacuna para $q > 2$: A análise revela uma discrepância entre os limites superior e inferior quando $q > 2$. Os autores argumentam que isso não é um artefato da prova, mas indica uma subotimalidade intrínseca dos estimadores de gradiente aleatorizados de dois pontos padrão neste regime, pois falham em explorar a esparsidade inerente a funções Lipschitzianas de alta-$q$.

Principais Resultados
O resultado teórico primário (Teorema 2.3) afirma que, com probabilidade de pelo menos $1-\delta$, o arrependimento satisfaz:
$$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$$
onde $\nu_r$ é uma variância proxy dependendo de $L, d, p, q, r$, e $\gamma_r = (1/p - 1/r)_+$. O termo $\sqrt{\log \log n}$ surge da natureza "anytime" do limite.

O limite inferior (Teorema 2.4) mostra que, para qualquer algoritmo de dois pontos, existe uma instância de problema onde o arrependimento é, no mínimo, da ordem $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ com probabilidade constante.

Significado e Alegações
O artigo alega fornecer o primeiro tratamento unificado da otimização convexa online de ordem zero além do cenário euclidiano ($p=q=r=2$). Ao migrar da análise em expectativa para a análise de alta probabilidade, os resultados oferecem garantias mais fortes e uniformes no tempo, adequadas para configurações adaptativas e "anytime".

O trabalho destaca uma limitação específica na metodologia atual: para $q > 2$, os estimadores de gradiente aleatorizados padrão parecem ser subótimos em comparação com o limite inferior teórico. Os autores sugerem que a lacuna surge porque esses estimadores carecem de um mecanismo para explorar a esparsidade das instâncias "difíceis" no regime $q > 2$, uma propriedade que a construção do limite inferior utiliza explicitamente. Essa descoberta sugere que melhorias futuras neste regime podem exigir estruturas de estimador fundamentalmente diferentes, em vez de apenas análises refinadas de métodos de diferenças finitas existentes.