2025-11-25T08:04:18.158681

Adaptivity Gaps for Stochastic Probing with Subadditive Functions

Li, Liu, Zhang
In this paper, we study the stochastic probing problem under a general monotone norm objective. Given a ground set $U = [n]$, each element $i \in U$ has an independent nonnegative random variable $X_i$ with known distribution. Probing an element reveals its value, and the sequence of probed elements must satisfy a prefix-closed feasibility constraint $\mathcal{F}$. A monotone norm $f: \mathbb{R}_{\geq 0}^n \to \mathbb{R}_{\geq 0}$ determines the reward $f(X_P)$, where $P$ is the set of probed elements and $X_P$ is the vector with $X_i$ for $i \in P$ and 0 otherwise. The goal is to design a probing strategy maximizing the expected reward $\mathbb{E}[f(X_P)]$. We focus on the adaptivity gap: the ratio between the expected rewards of optimal adaptive and optimal non-adaptive strategies. We resolve an open question posed in [GNS17, KMS24], showing that for general monotone norms, the adaptivity gap is $O(\log^2 n)$. A refined analysis yields an improved bound of $O(\log r \log n / \log\log n)$, where $r$ is the maximum size of a feasible probing sequence. As a by-product, we derive an asymptotically tight adaptivity gap $Θ( \log n/\log\log n)$ for Bernoulli probing with binary-XOS objectives, matching the known lower bound. Additionally, we show an $O(\log^3 n)$ upper bound for Bernoulli probing with general subadditive objectives. For monotone symmetric norms, we prove the adaptivity gap is $O(1)$, improving the previous $O(\log n)$ bound from [PRS23].
academic

Écarts d'Adaptativité pour le Sondage Stochastique avec Fonctions Sous-Additives

Informations Fondamentales

  • ID de l'article : 2504.15547
  • Titre : Adaptivity Gaps for Stochastic Probing with Subadditive Functions
  • Auteurs : Jian Li, Yinchen Liu, Yiran Zhang (Institut de Recherche Interdisciplinaire, Université Tsinghua)
  • Classification : cs.DS (Structures de Données et Algorithmes)
  • Date de Publication : Avril 2024 (version arXiv, dernière mise à jour octobre 2025)
  • Lien de l'article : https://arxiv.org/abs/2504.15547v2

Résumé

Cet article étudie le problème du sondage stochastique sous des objectifs de normes monotones générales. Étant donné un ensemble de base U=[n]U = [n], chaque élément i∈Ui \in U est associé à une variable aléatoire non-négative indépendante XiX_i suivant une distribution connue. Le sondage d'un élément révèle sa valeur, et la séquence de sondage doit satisfaire une contrainte de faisabilité préfixe-fermée F\mathcal{F}. Une norme monotone f:R≥0n→R≥0f: \mathbb{R}_{\geq 0}^n \to \mathbb{R}_{\geq 0} détermine la récompense f(XP)f(X_P), où PP est l'ensemble des éléments sondés. L'objectif est de concevoir une stratégie de sondage maximisant la récompense espérée. Cet article se concentre sur l'étude de l'écart d'adaptativité : le rapport entre la récompense espérée de la stratégie adaptative optimale et celle de la stratégie non-adaptative optimale.

Contexte de Recherche et Motivation

Importance du Problème

Le problème du sondage stochastique constitue un cadre fondamental en optimisation sous incertitude, avec des applications larges dans :

  • La conception de mécanismes bayésiens
  • L'apprentissage en ligne
  • La maximisation d'influence
  • La planification de trajectoires robotiques
  • La gestion de bases de données

Signification de l'Écart d'Adaptativité

  1. Signification théorique : Quantifier la valeur de l'adaptativité et comprendre quand les stratégies non-adaptatives simples sont suffisamment bonnes
  2. Valeur pratique : Les stratégies non-adaptatives sont plus faciles à représenter, analyser et implémenter, évitant les frais de calcul liés à la maintenance de grands arbres de décision
  3. Orientation de la Conception Algorithmique : Un petit écart d'adaptativité justifie la concentration sur les stratégies non-adaptatives

Limitations des Travaux Existants

  • Gupta et al. GNS17 ont conjecturé que l'écart d'adaptativité pour les fonctions sous-additives est polylogarithmique
  • Patton et al. PRS23 ont prouvé une borne supérieure de O(log⁡n)O(\log n) pour les normes symétriques, mais conjecturent que l'écart réel pourrait être constant
  • Kesselheim et al. KMS24 ont étendu la conjecture aux normes monotones générales

Contributions Principales

  1. Résolution du Problème Ouvert Central : Preuve que l'écart d'adaptativité pour les normes monotones générales est O(log⁡2n)O(\log^2 n), raffiné en O(log⁡rlog⁡n/log⁡log⁡n)O(\log r \log n / \log\log n)
  2. Obtention de Bornes Serrées : Pour les objectifs XOS binaires avec sondage de Bernoulli, preuve que l'écart d'adaptativité est Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n), correspondant aux bornes inférieures connues
  3. Amélioration des Bornes pour Fonctions Sous-Additives : Preuve que l'écart d'adaptativité pour les objectifs sous-additifs généraux avec sondage de Bernoulli est O(log⁡3n)O(\log^3 n)
  4. Résultats de Bornes Constantes : Pour les normes symétriques monotones, amélioration de l'écart d'adaptativité de O(log⁡n)O(\log n) à O(1)O(1)

Détail des Méthodes

Définition de la Tâche

Problème du Sondage Stochastique :

  • Entrée : Ensemble de base U=[n]U = [n], chaque élément ii associé à une variable aléatoire XiX_i, fonction objectif ff, contraintes de faisabilité F\mathcal{F}
  • Processus : Sondage adaptatif des éléments, observation des valeurs réalisées, jusqu'à atteindre un nœud feuille
  • Sortie : Ensemble des éléments sondés PP, récompense obtenue f(XP)f(X_P)
  • Objectif : Maximiser la récompense espérée E[f(XP)]\mathbb{E}[f(X_P)]

Écart d'Adaptativité : Reˊcompense espeˊreˊe de la strateˊgie adaptative optimaleReˊcompense espeˊreˊe de la strateˊgie non-adaptative optimale\frac{\text{Récompense espérée de la stratégie adaptative optimale}}{\text{Récompense espérée de la stratégie non-adaptative optimale}}

Cadre Technique Principal

1. Stratégie de Réduction en Trois Étapes

L'article adopte une approche de réduction systématique :

Première Étape : Variables Aléatoires Générales → Paramètre de Bernoulli

  • Utilisation de la technique de décomposition λ\lambda-grande
  • Discrétisation des distributions continues en puissances négatives de 2
  • Conversion des arbres de décision en arbres binaires

Deuxième Étape : XOS Général → Normes XOS Spéciales

  • Arrondi des poids à des puissances négatives de 2
  • Construction de formes spéciales : fxos(S)=max⁡ℓ{∣elt(Aℓ′)∩S∣}f_{xos}(S) = \max_\ell \{|\text{elt}(A'_\ell) \cap S|\}
  • Perte d'un facteur O(log⁡r)O(\log r) uniquement

Troisième Étape : Analyse d'Algorithme Glouton

  • Conception d'un système d'étiquetage complexe contrôlant les informations de profondeur
  • Preuve de bornes de probabilité de queue
  • Application de techniques d'inégalités

2. Conception d'Algorithme Clé

Algorithme d'Étiquetage Glouton :

Entrée: (ℓ, R)
Sortie: Étiquette B = (m; s; d₁,...,dₘ; e₁,...,eₘ; y₁,...,y⌊s/K⌋)

1. Initialisation: s ← |A'_ℓ|, d₁ ← depth(ℓ)
2. Paramètres de contrôle de profondeur: yᵢ
3. Parcours ascendant de chaque nœud u le long du chemin Pₓ:
   - Vérification de u ∈ R et existence d'une feuille appropriée ℓ'
   - Si conditions satisfaites, mise à jour de l'étiquette B
4. Retour de l'étiquette finale B

3. Points d'Innovation Technique

Mécanisme de Contrôle de Profondeur :

  • Introduction du paramètre K=O(log⁡n)K = O(\log n) contrôlant la profondeur des éléments dans Aℓ′A'_\ell
  • Pour chaque jj, yjy_j représente la profondeur du jj-ième élément de Aℓ′A'_\ell
  • Assurance de similarité de la structure Aℓ′A'_\ell entre différentes feuilles

Identification de Nœuds Impossibles :

  • Définition de Imp(ℓ,B0)\text{Imp}(\ell, B_0) : ensemble de nœuds ne pouvant pas être activés sous une étiquette donnée
  • Preuve que chaque ℓ∈S(B0)\ell \in S(B_0) contient au moins s−mKs - mK nœuds impossibles
  • Utilisation de ces contraintes pour obtenir des bornes de probabilité exponentiellement petites

Fonction Technique g(h,p)g(h,p) :

  • Définition g(h,p)=p⋅exp⁡(−0.1hp1/h)g(h,p) = p \cdot \exp(-0.1h p^{1/h})
  • Preuve d'inégalités clés traitant les cas où le nœud racine est ou n'est pas dans l'ensemble de contrainte
  • Plus serrée que la borne de Chernoff standard pour p=n−O(m)p = n^{-O(m)}

Traitement Spécial des Normes Symétriques

Pour les normes symétriques, une stratégie d'analyse différente est adoptée :

  1. Partitionnement de Catégories : Division des nœuds par poids 4−k4^{-k} en catégories QkQ_k
  2. Classification Feuilles Bonnes/Mauvaises : Définition des feuilles kk-mauvaises, preuve de leur proportion exponentiellement petite
  3. Analyse Directe : Évitement du système d'étiquetage complexe, analyse directe de la récompense espérée

Configuration Expérimentale

Cet article est un travail purement théorique, validé principalement par preuve mathématique. L'article fournit :

Vérification Théorique

  1. Correspondance de Bornes Inférieures : Pour les objectifs XOS binaires, la borne supérieure O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) correspond à la borne inférieure Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n) de GNS17
  2. Dépendance aux Paramètres : Analyse de la dépendance des bornes à rr (longueur maximale de séquence de sondage)
  3. Analyse de Constantes : Borne de constante explicite 2050 pour les normes symétriques

Vérification Technique

  1. Correction de Réduction : Analyse du ratio d'approximation de chaque étape de réduction
  2. Complexité d'Algorithme : Bien que l'algorithme soit utilisé uniquement pour l'analyse, sa complexité est raisonnable
  3. Sélection de Paramètres : Optimalité de K=O(log⁡n/log⁡log⁡n)K = O(\log n/\log\log n)

Résultats Expérimentaux

Résultats Théoriques Principaux

Théorème 1.2 (Normes Monotones Générales) : Borne supérieure de l'écart d'adaptativité : O(log⁡r⋅log⁡nlog⁡log⁡n)O\left(\log r \cdot \frac{\log n}{\log\log n}\right)

Théorème 1.3 (Objectifs XOS Binaires) : Écart d'adaptativité : Θ(log⁡nlog⁡log⁡n)\Theta\left(\frac{\log n}{\log\log n}\right) (serré)

Théorème 1.4 (Normes Symétriques) : Écart d'adaptativité : O(1)O(1)

Analyse des Contributions Techniques

Ampleur des Améliorations :

  • Normes symétriques : amélioration de O(log⁡n)O(\log n) PRS23 à O(1)O(1)
  • Normes générales : première borne polylogarithmique, résolution du problème ouvert
  • XOS binaire : obtention de borne asymptotiquement serrée

Innovation Méthodologique :

  • Système d'étiquetage avec contrôle de profondeur
  • Techniques d'analyse probabiliste améliorées
  • Cadre de réduction unifié

Travaux Connexes

Développement Historique

  1. Travaux Précoces : Gupta-Nagarajan GN13 introduisent le sondage de Bernoulli
  2. Fonctions Sous-Modulaires : GNS16, GNS17 prouvent l'écart d'adaptativité constant
  3. Fonctions XOS : GNS17 prouvent la borne O(log⁡W)O(\log W), où WW est la largeur XOS
  4. Objectifs de Normes : PRS23, KMS24 étudient les normes symétriques et surmodulaires

Positionnement de cet Article

  • Résolution de la conjecture centrale proposée par GNS17, KMS24
  • Amélioration des résultats de PRS23 pour les normes symétriques
  • Fourniture d'un cadre technique unifié pour différentes fonctions objectif

Conclusion et Discussion

Conclusions Principales

  1. Complétude Théorique : Résolution essentiellement complète du problème d'écart d'adaptativité pour les normes monotones
  2. Contributions Techniques : Développement de nouveaux outils techniques pour traiter les fonctions objectif générales
  3. Orientation Pratique : Preuve que dans de nombreux cas, les stratégies non-adaptatives sont approximativement optimales

Limitations

  1. Facteurs Constants : La constante 2050 pour les normes symétriques est importante, possiblement non serrée
  2. Écart log⁡r\log r : Écart de O(log⁡r)O(\log r) subsiste avec les bornes inférieures connues
  3. Complexité Technique : Les techniques de preuve sont complexes, possiblement difficiles à étendre à d'autres problèmes

Directions Futures

  1. Resserrement des Bornes : Réduction de l'écart avec les bornes inférieures
  2. Amélioration des Constantes : Obtention de constantes serrées pour les normes symétriques
  3. Applications Algorithmiques : Application des intuitions à l'optimisation combinatoire stochastique plus large
  4. Complexité Computationnelle : Étude de la complexité du calcul des stratégies optimales

Évaluation Approfondie

Points Forts

Innovation Technique :

  1. Mécanisme de Contrôle de Profondeur : Utilisation innovante des informations de profondeur pour contrôler la structure d'étiquetage
  2. Cadre Unifié : Fourniture d'une approche systématique pour traiter différentes fonctions objectif
  3. Analyse Fine : Techniques probabilistes améliorées obtenant des bornes plus serrées

Contributions Théoriques :

  1. Résolution de Problème Ouvert : Réponse à la conjecture centrale du domaine
  2. Résultats Serrés : Obtention de bornes optimales pour XOS binaire
  3. Amélioration Inattendue : Borne constante pour les normes symétriques est un résultat étonnamment fort

Qualité Technique :

  1. Rigueur de Preuve : Raisonnement mathématique clair et complet
  2. Structure Claire : Organisation d'article excellente, facile à comprendre
  3. Profondeur Technique : Utilisation de multiples techniques probabilistes et combinatoires avancées

Insuffisances

Limitations Techniques :

  1. Complexité : Les techniques de preuve sont très complexes, possiblement limitant le développement ultérieur
  2. Problème de Constantes : Certaines constantes peuvent ne pas être serrées
  3. Dépendance aux Paramètres : L'analyse de la dépendance à rr pourrait être plus approfondie

Limitations d'Application :

  1. Purement Théorique : Absence de vérification d'application pratique
  2. Efficacité Algorithmique : Complexité computationnelle élevée de l'algorithme d'analyse
  3. Valeur Pratique : La valeur d'application dans les problèmes réels nécessite vérification ultérieure

Influence

Impact Académique :

  1. Résolution de Problème Important : Réponse à des problèmes ouverts depuis plusieurs années
  2. Avancement Technique : Fourniture de nouveaux outils d'analyse pour l'optimisation stochastique
  3. Effet Inspirant : Possibilité d'inspirer la recherche sur des problèmes connexes

Valeur Pratique :

  1. Orientation de Conception Algorithmique : Support théorique pour la conception d'algorithmes pratiques
  2. Garanties d'Approximation : Preuve de l'efficacité des stratégies simples
  3. Domaines d'Application : Applications potentielles en apprentissage automatique, recherche opérationnelle, etc.

Scénarios d'Application

  1. Recherche Théorique : Optimisation combinatoire stochastique, théorie des algorithmes en ligne
  2. Conception Algorithmique : Scénarios nécessitant l'équilibre entre adaptativité et simplicité
  3. Applications Pratiques : Allocation de ressources, conception d'expériences, systèmes de recommandation, etc.

Références

  • GNS17 Gupta, Nagarajan, Singla. "Adaptivity gaps for stochastic probing: submodular and XOS functions"
  • KMS24 Kesselheim, Molinaro, Singla. "Supermodular approximation of norms and applications"
  • PRS23 Patton, Russo, Singla. "Submodular Norms with Applications To Online Facility Location and Stochastic Probing"

Cet article apporte des contributions théoriques importantes au domaine de l'optimisation combinatoire stochastique, non seulement en résolvant plusieurs problèmes ouverts, mais aussi en développant un nouveau cadre technique pour traiter les fonctions objectif générales. Bien que les techniques de preuve soient complexes, leur valeur théorique et leur contribution à l'avancement du domaine sont significatifs.