Majority-of-Three is Optimal

Resumo Técnico: A Maioria de Três é Ótima

Enunciado do Problema
O artigo aborda o problema central de determinar a complexidade de amostra ótima para o aprendizado PAC no cenário realizável. Embora a existência de aprendizes ótimos tenha sido estabelecida por Hanneke [Han16] (baseando-se em Simon [Sim15]), os algoritmos resultantes e suas análises probabilísticas são complexos. Um candidato específico e elementar para um aprendiz ótimo é a regra da "maioria de três": dividir uma amostra de treinamento em três blocos independentes, treinar um classificador consistente em cada bloco e produzir o voto da maioria. Trabalhos anteriores [AAHLZ24] provaram que esta regra atinge um limite ótimo em expectativa e um limite PAC quase ótimo (até um fator duplo logarítmico, $\log \log(\min\{n/d, 1/\delta\})$). Os autores de [AAHLZ24] conjecturaram que a regra da maioria de três atinge o limite PAC ótimo sem esses fatores extras. Este artigo fornece uma prova dessa conjectura.

Metodologia
A prova estabelece um limite superior de alta probabilidade para o erro do classificador de maioria de três, $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$, onde cada $\hat{f}_i$ é um classificador consistente treinado em um bloco independente $S_i$ de tamanho $m = n/3$.

1. Redução aos Momentos de Sobreposição:
   O erro do voto da maioria ocorre apenas quando pelo menos dois dos três classificadores classificam incorretamente um ponto $x$. Definindo $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ como o conjunto de erro do $i$-ésimo classificador, o erro total é limitado pela soma das interseções pareadas:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   A prova foca em limitar os momentos $L_q$ dessas probabilidades de interseção, especificamente $\|P(E_1 \cap E_2)\|_{L_q}$.

2. Ferramenta Técnica Principal: Proposição 2.2:
   O núcleo do argumento é a Proposição 2.2, que fornece um limite de momento para a sobreposição de conjuntos de erro de duas amostras independentes $S$ e $T$ de tamanho $m$. Para uma classe VC $\mathcal{C}$ com dimensão $d$ e um seletor consistente determinístico $A$ (onde $A(S) \cap S = \emptyset$), a proposição afirma:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   Este resultado é análogo à estimativa de sobreposição de Simon [Sim15], mas aplica-se a amostras independentes em vez de aninhadas. A independência é crucial para evitar os fatores duplo logarítmicos presentes em análises anteriores de estruturas aninhadas.

3. Decomposição Recursiva e Probabilidades Condicionais:
   Para provar a Proposição 2.2, os autores analisam o $q$-ésimo momento da sobreposição introduzindo $q$ pontos de teste independentes $X = (X_1, \dots, X_q)$. O momento é reescrito como $\mathbb{E}_X [p_q(X)^2]$, onde $p_q(X) = P(X \subseteq A(S))$.
   Usando uma decomposição de regra da cadeia, $p_q(X)$ é expressa como um produto de probabilidades de inclusão condicionais:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{onde } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   A prova baseia-se no Lema 3.1, um limite de cauda para essas probabilidades condicionais. Ele mostra que, para um evento de condicionamento $E_z$ com probabilidade $p_z$, a probabilidade de a probabilidade de inclusão condicional $\alpha_z(X)$ exceder um limiar $a$ é limitada por:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   Este limite controla a "raridade" do evento de condicionamento sem inflar o termo da dimensão VC.

4. Argumento Recursivo:
   Os autores definem um funcional ponderado $M_k$ envolvendo as probabilidades condicionais ao quadrado e um termo logarítmico. Eles estabelecem uma recursão $M_k \leq \frac{960}{m} M_{k-1}$. Iterar esta recursão de $k=1$ até $q$ produz o limite desejado para o $q$-ésimo momento, que é então convertido para um limite de alta probabilidade usando a desigualdade de Markov com $q = \lceil \log(1/\delta) \rceil$.

Principais Contribuições e Resultados

• Prova de Otimalidade: O artigo prova que o aprendiz de maioria de três atinge a complexidade de amostra ótima no cenário PAC realizável. Especificamente, para qualquer distribuição $P$, alvo $f^\star$ e confiança $\delta$:
  $$P\left( \text{err}_P(Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)) \leq 107 \frac{d + \log(1/\delta)}{n} \right) \geq 1 - \delta.$$
  Isso corresponde ao limite inferior clássico [EHKV89] até uma constante universal.
• Simplificação da Análise: A prova simplifica a estrutura algorítmica e a análise probabilística de aprendizes ótimos anteriores (como o de Hanneke [Han16] e a análise de bagging de Larsen [Lar23]). Ela remove a necessidade de estruturas de amostras aninhadas complexas e os fatores duplo logarítmicos resultantes.
• Independência sobre Aninhamento: O trabalho demonstra que o uso de blocos independentes (em vez de amostras aninhadas) permite uma análise mais limpa que evita os fatores $\log \log$ anteriormente considerados necessários para esquemas de votação simples.

Significância e Alegações
Os autores afirmam que este resultado resolve a conjectura de [AAHLZ24] em relação à otimalidade da regra da maioria de três. O artigo posiciona isso como uma simplificação significativa na teoria do aprendizado PAC, fornecendo o "esquema de votação mais simples" que é comprovadamente ótimo. A prova é descrita como curta e autossuficiente, baseando-se em uma nova decomposição recursiva de probabilidades de inclusão condicionais em vez das construções mais intrincadas de aprendizes ótimos anteriores.

O artigo também inclui um apêndice detalhando o uso de Modelos de Linguagem de Grande Escala (LLMs) para simplificar a prova. Os autores observam que a prova inicial era mais longa e derivada pelo primeiro autor, mas a assistência de LLM foi usada para explorar argumentos alternativos, levando à forma recursiva mais curta apresentada no manuscrito final. As alegações matemáticas foram verificadas e escritas pelos autores.