Sintesi Tecnica: Massimizzazione Submodulare con Vincolo di Knapsack in Presenza di Privacy Differenziale

1. Definizione del Problema

Il documento affronta il problema della Massimizzazione Submodulare con un Vincolo di Knapsack (SMK) nell'ambito del framework della Privacy Differenziale (DP).

• Contesto SMK: Dato un insieme fondamentale $N$ di $n$ elementi, una funzione obiettivo submodulare $f: 2^N \to \mathbb{R}$, una funzione di costo $c: N \to \mathbb{R}_{>0}$ e un budget $B$, l'obiettivo è trovare un sottoinsieme $S \subseteq N$ tale che $\sum_{v \in S} c(v) \leq B$ e $f(S)$ sia massimizzato. Questo problema è NP-difficile ed è onnipresente in applicazioni di machine learning come la selezione delle caratteristiche, la sintesi dei dati e la massimizzazione dell'influenza.
• Impostazione della Privacy: La funzione obiettivo $f_D$ dipende da un dataset sensibile $D$. L'algoritmo deve produrre una soluzione $S$ garantendo la $(\epsilon, \delta)$-privacy differenziale, assicurando che la distribuzione dell'output cambi in modo trascurabile quando i dati di un singolo individuo in $D$ vengono modificati.
• Ambito: Il lavoro considera sia funzioni obiettivo monotone che non monotone.

2. Metodologia e Sfide Tecniche

Gli autori identificano che le tecniche standard per la massimizzazione submodulare DP (spesso progettate per vincoli di cardinalità) sono subottimali per i vincoli di knapsack a causa di due sfide primarie:

1. Sensibilità Variabile dei Punteggi di Densità: Negli scenari knapsack, gli algoritmi tipicamente selezionano elementi basandosi sulla "densità" (guadagno marginale diviso per il costo). A differenza dei vincoli di cardinalità dove la sensibilità è uniforme, la sensibilità di un punteggio di densità $f(u|S)/c(u)$ dipende inversamente dal costo dell'elemento $c(u)$. Un'applicazione ingenua dei meccanismi di selezione standard (come l'Exponential Mechanism) comporterebbe un errore additivo proporzionale a $\Delta f \cdot (B/c_{\min})$, portando a una dipendenza subottimale dalla dimensione massima della soluzione ammissibile $k$.

   • Risoluzione: Gli autori impiegano il meccanismo Generalized Report Noisy Max (GRNM) (Raskhodieva & Smith, 2016). Questo meccanismo si adatta alle sensibilità individuali dei candidati, assicurando che l'errore additivo sia scalato con la specifica sensibilità del candidato selezionato piuttosto che con il limite del caso peggiore.

2. Collo di Bottiglia della Composizione: Gli algoritmi allo stato dell'arte per la massimizzazione SMK monotona non privata (ad esempio, Two-Guess-Greedy) richiedono $O(n^2)$ iterazioni per indovinare gli elementi ottimali. I normali teoremi di composizione avanzata risulterebbero in un termine di errore che scala polinomialmente con $n$, annullando i benefici della privacy.

   • Risoluzione: Gli autori sfruttano il framework della Selezione Privata Generalizzata (Cohen et al., 2023). Randomizzando il numero di volte in cui ogni fase di enumerazione viene invocata, essi scindono la perdita di privacy dal numero totale di subroutine, ottenendo un errore additivo con dipendenza polilogaritmica da $n$.

3. Contributi Chiave e Algoritmi

A. Funzioni Obiettivo Monotone

Il documento propone due algoritmi per il caso monotono:

1. DP-2GG (Algoritmo 2): Un adattamento differenzialmente privato dell'algoritmo "Two-Guess-Greedy" (Feldman et al., 2023).

   • Meccanismo: Itera su tutti i sottoinsiemi $Y \subseteq N$ di dimensione al massimo 2. Per ogni $Y$, esegue una subroutine density-greedy privatizzata (Algoritmo 1) sull'istanza residua. La soluzione finale è selezionata dagli output rumorosi di queste subroutine utilizzando il framework di Selezione Generalizzata.
   • Garanzie: Ottiene un'approssimazione $(1 - 1/e)$.
   • Complessità: $O(\beta^{-1} n^3 k)$ query di oracle.
   • Errore: L'errore additivo scala come $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$, migliorando il lavoro precedente eliminando la dipendenza polinomiale da $n$ e $1/c_{\min}$.

2. DP-DG+ (Algoritmo 7): Un algoritmo più veloce a passaggio singolo basato su Density-Greedy+.

   • Meccanismo: Esegue un singolo passaggio density-greedy privatizzato e seleziona la migliore soluzione tra le soluzioni parziali e le loro estensioni a singolo elemento ammissibili usando Report Noisy Max (RNM).
   • Garanzie: Ottiene un'approssimazione di $1/2$.
   • Complessità: $O(nk)$ query di oracle.
   • Errore: Errore additivo migliorato comparabile al caso monotono.

B. Funzioni Obiettivo Non-Monotone

Il documento introduce il primo algoritmo differenzialmente privato con garanzie dimostrabili per la SMK non-monotona.

• Algoritmo: DP-SDG (Algoritmo 3), un adattamento privatizzato dell'algoritmo non privato SmkRan (Han et al., 2021).
• Meccanismo: Esegue selezioni basate sulla densità usando GRNM. Gli elementi selezionati vengono aggiunti alla soluzione con probabilità $1/2$ (scarto randomizzato) per gestire la non-monotonicità. Fondamentalmente, continua l'iterazione anche se i guadagni marginali diventano negativi (a causa del rumore) e usa RNM per selezionare la migliore soluzione osservata tra tutte le soluzioni parziali e le loro estensioni.
• Analisi della Privacy: Per gestire l'incertezza nel numero di passi di selezione, gli autori derivano un limite di concentrazione mostrando che il numero totale di iterazioni è stocasticamente dominato da una somma di variabili casuali geometriche, che si concentra attorno a $O(k)$.
• Garanzie: Ottiene un'approssimazione di $1/4$ in valore atteso.
• Complessità: $O(nk)$ query di oracle.
• Errore: L'errore additivo è comparabile al caso monotono.

4. Risultati e Valutazione Empirica

Risultati Teorici

Gli autori confrontano i loro risultati con il lavoro precedente (specificamente Sadeghi & Fazel, 2021) nella Tabella 1. I miglioramenti chiave includono:

• Rapporti di Approssimazione: Pareggiando i migliori rapporti non privati noti ($(1-1/e)$ per il caso monotono, $1/4$ per il caso non-monotono).
• Errore Additivo: Dipendenza significativamente migliorata dalla dimensione dell'insieme fondamentale $n$ (polilogaritmica vs polinomiale) e dalla dimensione massima della soluzione ammissibile $k$ (scala con $k^{1.5}$ rispetto a $k$ o peggio nei lavori precedenti).
• Complessità di Query: Polinomiale in $n$ e $k$, mentre il lavoro precedente per la SMK monotona si affidava alla valutazione esatta dell'estensione multilineare richiedendo $O(2^n)$ query.

Risultati Empirici

Gli algoritmi sono stati valutati su un compito di ottimizzazione di ride-sharing utilizzando un dataset di 100.000 posizioni di pickup di Uber a Manhattan.

• Utilità: Per $\epsilon \geq 0.1$, gli algoritmi DP (DP-2GG, DP-DG+, DP-SDG) raggiungono un'utilità comparabile ai loro controparti non privati (2GG, DG+, SmkRan), superando sostanzialmente un baseline casuale. A $\epsilon=0.2$, DP-2GG è entro il 2% del 2GG non privato.
• Scalabilità: DP-DG+ e DP-SDG mostrano una crescita lineare nelle query di oracle rispetto alla dimensione dell'insieme fondamentale $n$, confermando la loro efficienza pratica rispetto al più intensivo DP-2GG.

5. Significato e Rivendicazioni

Il documento sostiene di colmare lacune critiche nella letteratura riguardante l'ottimizzazione combinatoria con privacy differenziale:

1. Prima SMK Non-Monotona Provabile: Stabilisce le prime garanzie dimostrabili per la SMK non-monotona sotto privacy differenziale.
2. Migliori Limiti per il Caso Monotono: Migliora sia l'utilità (errore additivo) che la complessità di query della SMK monotona, allontanandosi dalle precedenti approcci a complessità di query esponenziale.
3. Gestione dei Vincoli di Knapsack: Dimostra che le sfide specifiche dei vincoli di knapsack (sensibilità variabile e colli di bottiglia della composizione) possono essere superate utilizzando meccanismi di selezione generalizzati e limiti di concentrazione, raggiungendo risultati che eguagliano l'efficienza degli scenari con vincolo di cardinalità.

Gli autori notano che, sebbene la loro dipendenza dell'errore additivo da $k$ corrisponda ai migliori casi noti per algoritmi a tempo polinomiale negli scenari con vincolo di cardinalità, la questione se sia possibile una migliore dipendenza da $k$ sotto sensibilità limitata rimanga aperta. Suggeriscono inoltre di estendere queste tecniche ai vincoli combinati di knapsack e matroid come direzione per il lavoro futuro.