🤖 machine learning

Constrained Learning with Universally Learnable Concept Classes

Este artigo estabelece a aprendibilidade universal de soluções para problemas de aprendizagem estatística restritos sobre classes de hipóteses não convexas e de dimensão infinita ao reconciliar generalização e dualidade lagrangiana através de um arcabouço universal de RKHS, enquanto introduz o hiato de fechamento-realização para caracterizar a viabilidade exata ou quase-PACC de algoritmos duais.

Autores originais: Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

Publicado 2026-08-11

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Grande Equilíbrio: Quando a IA Precisa Seguir Regras

Imagine que você está ensinando um robô a jogar um videogame. Seu objetivo é simples: obter a maior pontuação possível. Mas há um porém. O jogo tem regras estritas: o robô não pode bater nas paredes, não pode ficar sem combustível e deve permanecer dentro de um limite de tempo específico. No mundo do aprendizado de máquina, isso é chamado de aprendizado com restrições (constrained learning). A "pontuação" é a precisão da previsão, e as "regras" são requisitos de segurança, justiça ou privacidade.

Por muito tempo, os cientistas pensaram que a melhor maneira de ensinar essas regras a um robô era tornar o jogo simples e previsível (matematicamente "convexo"). Em um jogo simples, você pode facilmente encontrar o caminho perfeito que obtém a maior pontuação enquanto obedece a cada regra. Mas a IA moderna, como as redes neurais profundas que alimentam carros autônomos ou diagnósticos médicos, joga em um jogo que é incrivelmente complexo e cheio de curvas e reviravoltas (matematicamente "não convexo"). É como navegar em um labirinto onde as paredes se movem e o chão é feito de gelatina.

Quando você tenta aplicar as regras antigas e simples a esse labirinto complexo, as coisas quebram. O computador pode encontrar um caminho que parece ótimo no papel, mas que na verdade faz o carro bater, ou pode encontrar um caminho que segue as regras, mas pontua zero. A grande questão que os cientistas têm feito é: Podemos ensinar esses sistemas de IA superinteligentes e complexos a serem tanto brilhantes em seu trabalho quanto perfeitamente obedientes às regras, sem ter que simplificar o mundo em que vivem?

A Grande Ideia do Artigo: O Truque da "Biblioteca Infinita"

Este artigo, intitulado "Constrained Learning with Universally Learnable Concept Classes", aborda exatamente esse problema. Os autores, Herlock Rahimi, Spyridon Pougkakiotis e Dionysis Kalogerias, propõem uma nova maneira inteligente de treinar IA que funciona mesmo quando as regras são complicadas e a IA é incrivelmente complexa.

Aqui está a história de sua descoberta, contada através de uma analogia simples.

O Problema: O Dilema do "Muito Grande" vs. "Muito Pequeno"

Imagine que você está tentando encontrar um tesouro escondido em uma biblioteca gigante e infinita.

A Biblioteca "Muito Grande": Se você procurar em toda a biblioteca infinita (que contém todos os livros possíveis, incluindo os de nonsense), você tem a garantia de encontrar o mapa do tesouro perfeito. No entanto, a biblioteca é tão grande que você poderia passar a vida inteira procurando e nunca realmente encontrar o livro de que precisa. Você tem o potencial de encontrar a resposta, mas não consegue provar que a encontrou em um tempo razoável.
A Biblioteca "Muito Pequena": Se você procurar em uma seção minúscula e gerenciável da biblioteca (como apenas o corredor de "Culinária"), você pode encontrar um livro rapidamente. Mas o mapa do tesouro perfeito pode não estar no corredor de "Culinária". Você pode encontrar uma receita de sopa, quando na verdade precisava de um mapa para o ouro.

Tentativas anteriores de resolver isso forçavam a IA a escolher uma biblioteca e manter-se nela. Se escolhessem a pequena, perdiam a melhor solução. Se escolhessem a grande, não conseguiam provar que encontraram a resposta certa.

A Solução: A Estratégia da "Prateleira Crescente"

Os autores criaram uma estratégia brilhante: Comece pequeno, mas continue crescendo.

Imagine que você tem uma prateleira mágica que começa com apenas um livro. Você o pesquisa. Se não encontrar o tesouro, você magicamente adiciona mais alguns livros à prateleira. Você pesquisa novamente. Então, você adiciona mais. Você continua fazendo isso, expandindo lentamente sua área de busca.

Por que funciona: Porque você começa pequeno, você pode provar que sua busca é eficiente e confiável (você não está perdendo tempo com bobagens).
Por que é poderoso: Porque você continua crescendo, eventualmente cobrirá toda a biblioteca infinita. Você tem a garantia de que encontrará o mapa do tesouro perfeito eventualmente, sem nunca se perder no caos de toda a biblioteca de uma só vez.

Na linguagem do artigo, eles usam um "Espaço de Hilbert de Núcleos Reproduzíveis Universal" (um nome chique para uma biblioteca matemática muito expressiva) e pesquisam dentro de "bolas de norma" (as prateleiras) que ficam maiores à medida que o computador vê mais dados.

O "Gap" nas Regras

Há um detalhe complicado. Mesmo com essa prateleira crescente, os autores descobriram que, às vezes, a solução "perfeita" que obedece às regras pode não existir como um único livro limpo. Às vezes, as regras são tão complexas que a solução "perfeita" é uma mistura de muitos livros diferentes, e nenhum livro único na biblioteca pode representar essa mistura perfeitamente.

Eles chamam isso de "Gap de Fechamento–Realização" (Closure–Realization Gap).

Se o gap for zero: A IA encontra um livro único e perfeito que obedece às regras e obtém a melhor pontuação. Isso acontece quando as regras são "suaves" e bem comportadas (especificamente, quando a geometria dual é benigna, como quando a função dual é diferenciável). Neste caso, a solução é exatamente viável.
Se o gap não for zero: A IA encontra um livro que é quase perfeito. Ele pode quebrar uma regra por uma quantidade pequena e fixa que não pode ser removida, não importa quanta quantidade de dados você dê à IA. Os autores provaram que esse pequeno erro não é uma falha da IA ou da matemática; é uma propriedade fundamental e imutável do próprio problema. É como tentar desenhar um círculo perfeito com um lápis quadrado; o lápis não é ruim, a forma apenas não se encaixa perfeitamente, e o erro é exatamente o tamanho do canto do lápis.

O Que Eles Provaram

O artigo não apenas sugere que isso pode funcionar; eles provaram matematicamente.

Valor Exato: Eles mostraram que a IA pode aprender a exata melhor pontuação possível, mesmo neste mundo complexo e não convexo.
Viabilidade: Eles mostraram que a IA pode encontrar uma solução que obedeça às regras. Crucialmente, se a geometria do problema for "benigna" (o gap é zero), a solução é perfeitamente viável. Se a geometria for "não benigna" (o gap não é zero), a solução terá uma margem de erro específica e não nula que é intrínseca ao problema, não uma limitação do algoritmo.
Sem Atalhos: Eles provaram que você não pode simplesmente assumir que as regras são simples (convexas) para facilitar a matemática. A complexidade é real, e o método deles é a única maneira de lidar com isso sem perder a garantia de encontrar a resposta.

Por Que Isso Importa

Isso é um grande avanço porque nos dá uma maneira de construir IAs que sejam tanto poderosas quanto seguras. Quer seja uma IA decidindo quem recebe um empréstimo (justiça), um robô dirigindo um carro (segurança) ou uma IA médica diagnosticando pacientes (precisão), precisamos que elas sigam regras estritas. Este artigo mostra que não temos que escolher entre "inteligente" e "seguro". Podemos ter ambos, desde que usemos a estratégia correta da "prateleira crescente" para ensiná-los.

Os autores são cuidadosos ao dizer que, embora a matemática seja sólida, transformar isso em uma ferramenta de software real que rode no seu telefone é o próximo passo. Mas a base teórica já foi estabelecida: Sim, podemos ensinar IAs complexas a seguir as regras perfeitamente (se o problema permitir), ou, se as regras forem inerentemente complicadas, a segui-las tão perfeitamente quanto as regras matematicamente permitem, com um limite fixo e conhecido de erro.

Resumo Técnico: Aprendizado com Restrições com Classes de Conceitos Universalmente Aprendíveis

1. Configuração do Problema

O artigo aborda o aprendizado estatístico com restrições sobre classes de hipóteses de dimensão infinita em um cenário totalmente não convexo. O objetivo é minimizar um risco de predição primário $R_0(\phi)$ sujeito a $m$ restrições $R_i(\phi) \leq 0$ (para $i=1,\dots,m$ ), onde os riscos são expectativas de funcionais de perda potencialmente não convexos sob distintas distribuições de dados $D_i$ .

A dificuldade central surge de uma tensão estrutural entre dois requisitos para uma teoria de aprendizado viável:

Dualidade Forte (Nível da População): Para garantir que o problema dual lagrangiano caracteriza fielmente o problema primal restrito (lacuna de dualidade zero), a classe de hipóteses deve ser decomponível (fechada sob junção mensurável). Esta propriedade, ligada à convexidade de Lyapunov para medidas vetoriais, garante que o conjunto de vetores de risco atingíveis seja convexo, mesmo que os funcionais individuais não sejam. No entanto, espaços decomponíveis (ex: espaços $L_p$ ) são grandes demais para admitir garantias de generalização estatística (complexidade de Rademacher evanescente) a partir de dados finitos.
Generalização Estatística (Nível Empírico): Para garantir a aprendibilidade a partir de amostras finitas, a classe de hipóteses deve ter uma complexidade estatística controlada (ex: complexidade de Rademacher decrescente). Escolhas padrão como bolas de norma de Espaços de Hilbert de Núcleo Reproduzível (RKHS) satisfazem isso, mas não são decomponíveis, levando a erros de aproximação irredutíveis (resultados near-PACC) onde as violações de restrição não podem ser levadas a zero, independentemente do tamanho da amostra.

Abordagens existentes frequentemente cedem a esse compromisso utilizando uma única classe de complexidade finita, resultando em garantias "near-PACC" com resíduos que não desaparecem com mais dados. Este artigo busca resolver essa tensão para alcançar aprendibilidade exata ou quase-exata sem tais resíduos irredutíveis.

2. Metodologia

Os autores propõem um framework de complexidade variável utilizando classes RKHS densas e Minimização de Risco Empírico Dual (DERM).

Problema Populacional sobre um RKHS Universal: O problema restrito populacional é formulado sobre um RKHS universal $\mathcal{H}_K$ que é denso em um espaço envelope decomponível $\mathcal{G}$ (ex: um espaço $L_p$ ). Embora o $\mathcal{H}_K$ não seja decomponível por si só, sua densidade em $\mathcal{G}$ permite a transferência das propriedades de dualidade forte de $\mathcal{G}$ para $\mathcal{H}_K$ via argumentos de continuidade.
Problema Empírico com Bolas de Norma Crescentes: O aprendiz opera sobre uma sequência de bolas de norma fechadas $B_{Q_n} = \{f \in \mathcal{H}_K : \|f\|_{\mathcal{H}_K} \leq Q_n\}$ $B_{Q_{n}} = {f \in H_{K} : ∥ f ∥_{H_{K}} \leq Q_{n}}$ , onde o raio $Q_n$ $Q_{n}$ cresce com o tamanho da amostra $n$ $n$ de tal forma que $Q_n \to \infty$ $Q_{n} \to \infty$ , mas $Q_n/\sqrt{n} \to 0$ $Q_{n} / n \to 0$ .
- Isso garante que o espaço de busca eventualmente esgote o RKHS (capturando a solução populacional).
- Simultaneamente, a complexidade estatística (complexidade de Rademacher) da bola $B_{Q_n}$ desaparece como $O(Q_n/\sqrt{n})$ , garantindo convergência uniforme.
Algoritmo DERM: O aprendiz maximiza a função dual empírica sobre multiplicadores não negativos e, em seguida, minimiza o Lagrangiano empírico sobre a bola atual $B_{Q_n}$ .
Análise de Viabilidade: Como a não convexidade impede que o Lagrangiano atinja seu ínfimo ou garanta que um único preditor realize o subgradiente dual, os autores introduzem a lacuna de fechamento–realização $\varepsilon^\star_\infty$ . Esta constante geométrica mede a distância entre o superdiferencial da função dual e o conjunto de vetores de risco realizáveis por preditores dentro do RKHS.

3. Principais Contribuições

1. Aprendibilidade Universal (Quase-)PACC:
O artigo estabelece a aprendibilidade agnóstica Universal Probably Approximately Correct with Constraints (PACC). Diferente do aprendizado PAC livre de distribuição, a complexidade de amostra aqui é permitida depender das distribuições subjacentes (especificamente via margem de Slater e complexidade de Tikhonov), o que os autores argumentam ser necessário devido à alta expressividade dos RKHSs.

Aprendibilidade Exata: Quando a lacuna de fechamento–realização $\varepsilon^\star_\infty = 0$ (ex: sob diferenciabilidade dual), o aprendiz alcança viabilidade e otimalidade exatas.
Aprendibilidade Near-PACC: Quando $\varepsilon^\star_\infty > 0$ , o aprendiz alcança otimalidade e viabilidade dentro de um resíduo exatamente igual a $\varepsilon^\star_\infty$ . Crucialmente, este resíduo é uma propriedade intrínseca da geometria do problema, não um artefato de uma escolha de modelagem fixa, e desaparece sob condições benignas.

2. Certificados de Viabilidade sem Atendimento Primal:
No regime totalmente não convexo, o problema primal restrito pode não possuir uma solução atingida. O artigo prova que os outputs do DERM são assintoticamente viáveis e quase-ótimos até a lacuna $\varepsilon^\star_\infty$ , mesmo sem assumir a existência de um minimizador primal. Isso é alcançado através de um argumento variacional no lado dual, utilizando a representação de Levin–Valadier de superdiferenciais.

3. Taxas Estatísticas Explícitas:
Os autores derivam um limiar de amostra polinomial explícito para aprender o valor ótimo. Eles introduzem a complexidade de Tikhonov $T^\varepsilon_n$ , definida como a norma mínima do RKHS necessária para atingir um conjunto de nível de Lagrangiano $\varepsilon$ -ótimo. Sob uma condição de fonte padrão no caminho de regularização, eles mostram que $T^\varepsilon_n$ é finito e derivam uma complexidade de amostra de $O(\varepsilon^{-\max\{4, 2(1-\beta)/\beta\}})$ , onde $\beta$ caracteriza a condição de fonte.

4. Necessidade do Framework Universal:
O artigo prova que, na especialização não restrita de seu cenário, não existe um limiar de amostra livre de distribuição devido à capacidade ilimitada dos RKHS universais. Assim, o framework de aprendizado universal (onde as taxas dependem da distribuição) não é apenas conveniente, mas canônico para algoritmos duais sobre grandes classes de hipóteses.

4. Principais Resultados

Teorema 1: Estabelece que o DERM sobre RKHSs densos com bolas de norma crescentes é universalmente aprendível PACC.
- Parte (i): Aprendibilidade exata do valor ótimo com um limiar explícito.
- Partes (ii)–(v): Garantias de viabilidade e quase-otimalidade controladas pela lacuna de fechamento–realização $\varepsilon^\star_\infty$ .
- Parte (vi): Aprendibilidade PACC exata quando $\varepsilon^\star_\infty = 0$ .
Corolário 1: Fornece um limite explícito de complexidade de amostra polinomial sob uma condição de fonte.
Lema 1: Caracteriza a lacuna de fechamento–realização, mostrando que ela desaparece se a função dual for diferenciável no ótimo.

5. Significância e Alegações

O artigo afirma resolver a tensão estrutural fundamental entre a dualidade forte ao nível da população (que exige decomponibilidade) e a generalização de amostra finita (que exige baixa complexidade). Ao alavancar a densidade de RKHSs universais em envelopes decomponíveis, os autores demonstram que é possível herdar as propriedades de dualidade exata de espaços grandes enquanto mantém o controle estatístico através de restrições de bola de norma.

A significância reside em ir além dos resultados "near-PACC" com resíduos irredutíveis. O artigo argumenta que os resíduos anteriores eram artefatos de aproximações paramétricas fixas, enquanto o resíduo deles ( $\varepsilon^\star_\infty$ ) é uma constante geométrica do próprio problema, que comprovadamente desaparece em geometrias benignas. Isso fornece uma base teórica para o aprendizado com restrições em cenários não convexos (ex: aprendizado profundo com restrições de justiça ou segurança) sem depender de substitutos convexos que podem falhar em preservar a viabilidade da restrição sob distribuições heterogêneas.

Limitações reconhecidas pelos autores:

A condição de recuperação (Assunção 5) necessária para a viabilidade é verificada apenas por um critério geral no regime exato ( $\varepsilon^\star_\infty=0$ ).
A alegação agnóstica para viabilidade depende desta assunção, enquanto o aprendizado do valor é livre de atendimento (attainment-free).
O procedimento DERM é uma especificação de um algoritmo idealizado; a implementação computacional e a convergência de esquemas primal-dual práticos são deixadas para trabalhos futuros.
As taxas explícitas dependem de uma condição de fonte; sem ela, o limiar é finito, porém não explícito.