Technische Samenvatting: Differentieel Privaat Submodulair Maximaliseren met een Knapzakbeperking

1. Probleemdefinitie

Het artikel behandelt het probleem van Submodulair Maximaliseren onder een Knapzakbeperking (SMK) binnen het kader van Differentiële Privacy (DP).

• SMK-context: Gegeven een grondverzameling $N$ van $n$ elementen, een submodulaire objectievectieffunctie $f: 2^N \to \mathbb{R}$, een kostenfunctie $c: N \to \mathbb{R}_{>0}$, en een budget $B$, is het doel om een deelverzameling $S \subseteq N$ te vinden waarvoor geldt dat $\sum_{v \in S} c(v) \leq B$ en $f(S)$ wordt gemaximaliseerd. Dit probleem is NP-hard en veelvoorkomend in machine learning-toepassingen zoals feature selectie, datasamenvatting en invloedmaximalisatie.
• Privacy-instelling: De objectievectieffunctie $f_D$ hangt af van een gevoelige dataset $D$. Het algoritme moet een oplossing $S$ produceren die voldoet aan $(\epsilon, \delta)$-differentiële privacy, wat garandeert dat de distributie van de output verwaarloosbaar verandert wanneer de gegevens van één individu in $D$ wordt gewijzigd.
• Reikwijdte: Het werk beschouwt zowel monotone als niet-monotone objectievectieffuncties.

2. Methodologie en Technische Uitdagingen

De auteurs identificeren dat standaardtechnieken voor DP-submodulair maximaliseren (vaak ontworpen voor kardinaliteitsbeperkingen) suboptimaal zijn voor knapzakbeperkingen vanwege twee primaire uitdagingen:

1. Variërende Sensitiviteit van Dichtheidsscores: In knapzaksettings selecteren algoritmen doorgaans elementen op basis van "dichtheid" (marginale winst gedeeld door kosten). In tegenstelling tot kardinaliteitsbeperkingen, waarbij de sensitiviteit uniform is, hangt de sensitiviteit van een dichtheidsscore $f(u|S)/c(u)$ omgekeerd evenredig samen met de kosten $c(u)$ van het element. Een naïeve toepassing van standaard selectiemechanismen (zoals het Exponential Mechanism) zou een additieve fout veroorzaken die proportioneel is aan $\Delta f \cdot (B/c_{\min})$, wat leidt tot een suboptimale afhankelijkheid van de maximale omvang van de haalbare oplossing $k$.

   • Oplossing: De auteurs maken gebruik van het Generalized Report Noisy Max (GRNM) mechanisme (Raskhodnikova & Smith, 2016). Dit mechanisme past zich aan de individuele sensitiviteiten van kandidaten aan, waardoor de additieve fout schaalt met de specifieke sensitiviteit van de geselecteerde kandidaat in plaats van de worst-case bovengrens.

2. Compositie-bottleneck: State-of-the-art niet-private algoritmen voor monotone SMK (bijv. Two-Guess-Greedy) vereisen $O(n^2)$ iteraties om optimale elementen te raden. Standaard geavanceerde compositiestellingen zouden resulteren in een foutenterm die polynomiaal schaalt met $n$, wat de voordelen van privacy tenietdoet.

   • Oplossing: De auteurs maken gebruik van het Generalized Private Selection framework (Cohen et al., 2023). Door te randomiseren hoe vaak elke enumeratiestap wordt aangeroepen, ontkoppelen zij het privacyverlies van het totaal aantal subroutines, waardoor een additieve fout wordt bereikt met een polylogaritmische afhankelijkheid van $n$.

3. Belangrijkste Bijdragen en Algoritmen

A. Monotone Objectievectieffuncties

Het artikel stelt twee algoritmen voor voor de monotone casus:

1. DP-2GG (Algoritme 2): Een differentieel privaat adaptatie van het "Two-Guess-Greedy" algoritme (Feldman et al., 2023).

   • Mechanisme: Het iterereert over alle deelverzamelingen $Y \subseteq N$ van grootte maximaal 2. Voor elke $Y$ voert het een geprivatiseerde dichtheids-greedy subroutine uit (Algoritme 1) op de residuele instantie. De uiteindelijke oplossing wordt geselecteerd uit de ruisige outputs van deze subroutines met behulp van het Generalized Selection framework.
   • Garanties: Bereikt een optimale $(1 - 1/e)$-benadering.
   • Complexiteit: $O(\beta^{-1} n^3 k)$ oracle queries.
   • Fout: De additieve fout schaalt als $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$, wat de eerdere resultaten verbetert door de polynomiale afhankelijkheid van $n$ en $1/c_{\min}$ te verwijderen.

2. DP-DG+ (Algoritme 7): Een sneller, single-pass algoritme gebaseerd op Density-Greedy+.

   • Mechanisme: Voert één keer een geprivatiseerde density-greedy pass uit en selecteert de beste oplossing onder de partiële oplossingen en hun haalbare single-element extensies met behulp van Report Noisy Max (RNM).
   • Garanties: Bereikt een $1/2$-benadering.
   • Complexiteit: $O(nk)$ oracle queries.
   • Fout: Verbeterde additieve fout vergelijkbaar met de monotone casus.

B. Niet-monotone Objectievectieffuncties

Het artikel introduceert het eerste differentieel private algoritme met bewijsbare garanties voor niet-monotone SMK.

• Algoritme: DP-SDG (Algoritme 3), een geprivatiseerde adaptatie van het niet-private SmkRan algoritme (Han et al., 2021).
• Mechanisme: Het voert dichtheid-gebaseerde selecties uit met GRNM. Geselecteerde elementen worden met een waarschijnlijkheid van $1/2$ aan de oplossing toegevoegd (randomized discarding) om niet-monotoniciteit te behandelen. Cruciaal is dat het blijft itereren zelfs als de marginale winsten negatief worden (door ruis) en gebruikt RNM om de beste geobserveerde oplossing te selecteren uit alle partiële oplossingen en hun extensies.
• Privacy-analyse: Om de onzekerheid in het aantal selectiestappen te behandelen, leiden de auteurs een concentratiebegrenzing af die aantoont dat het totaal aantal iteraties stochastisch wordt gedomineerd door een som van geometrische random variabelen, die concentreert rond $O(k)$.
• Garanties: Bereikt een $1/4$-benadering in verwachting.
• Complexiteit: $O(nk)$ oracle queries.
• Fout: De additieve fout is vergelijkbaar met de monotone casus.

4. Resultaten en Empirische Evaluatie

Theoretische Resultaten

De auteurs vergelijken hun resultaten met eerder werk (specifiek Sadeghi & Fazel, 2021) in Tabel 1. Belangrijkste verbeteringen zijn:

• Benaderingsratio's: Overeenkomst met de best bekende niet-private ratio's ($(1-1/e)$ voor monotoon, $1/4$ voor niet-monotoon).
• Additieve Fout: Aanzienlijk verbeterde afhankelijkheid van de grootte van de grondverzameling $n$ (polylogaritmisch versus polynomiaal) en de maximale haalbare oplossing $k$ (schalend met $k^{1.5}$ versus $k$ of erger in eerder werk).
• Query Complexiteit: Polynomiaal in $n$ en $k$, terwijl eerder werk voor monotone SMK vertrouwde op de exacte evaluatie van de multilineaire extensie die $O(2^n)$ queries vereist.

Empirische Resultaten

De algoritmen werden geëvalueerd op een optimalisatietaak voor ridesharing met een dataset van 100.000 Uber pickup locaties in Manhattan.

• Utiliteit: Voor $\epsilon \geq 0.1$ bereiken de DP-algoritmen (DP-2GG, DP-DG+, DP-SDG) een utiliteit die vergelijkbaar is met hun niet-private tegenhangers (2GG, DG+, SmkRan), waarbij ze de random baseline aanzienlijk overtreffen. Bij $\epsilon=0.2$ zit DP-2GG binnen 2% van de niet-private 2GG.
• Schaalbaarheid: DP-DG+ en DP-SDG vertonen een lineaire groei in oracle queries met betrekking tot de grootte van de grondverzameling $n$, wat hun praktische efficiëntie bevestigt vergeleken met de meer query-intensieve DP-2GG.

5. Betekenis en Claims

Het artikel beweert kritische hiaten in de literatuur met betrekking tot differentiële private combinatorische optimalisatie te overbruggen:

1. Eerste Bewijsbare Niet-monotone SMK: Het vestigt de eerste bewijsbare garanties voor niet-monotone SMK onder differentiele privacy.
2. Verbeterde Monotone Grenzen: Het verbetert zowel de utiliteit (additieve fout) als de query complexiteit van monotone SMK-algoritmen, waarbij het afstand neemt van de exponentiële query complexiteit van eerdere benaderingen.
3. Omgaan met Knapzakbeperkingen: Het demonstreert dat de specifieke uitdagingen van knapzakbeperkingen (variërende sensitiviteiten en compositie-bottlenecks) kunnen worden overwonnen met behulp van gegeneraliseerde selectiemechanismen en concentratiebegrenzingen, waarmee resultaten worden behaald die de efficiëntie van kardinaliteitsbeperkte settings evenaren.

De auteurs merken op dat hoewel hun additieve fout-afhankelijkheid van $k$ overeenkomt met de best bekende voor polynomiale tijd-algoritmen in kardinaliteitsbeperkte settings, de vraag of een betere afhankelijkheid van $k$ haalbaar is onder gebonden sensitiviteit openstaat. Ze suggereren ook om deze technieken uit te breiden naar gecombineerde knapzak- en matroidbeperkingen als een richting voor toekomstig werk.