Introduction
Discrete optimization often involves selecting a subset of items to maximize a specific objective, such as placing sensors in a water network or identifying influential users in a social network. Traditionally, these problems are modeled using set functions, where an item is either selected or not. However, many real-world applications are more accurately represented on an integer lattice, where items can be selected at multiple "levels" or intensities—for example, choosing different power levels for a sensor or varying discount amounts for a marketing target.
While submodular functions (those exhibiting "diminishing returns") allow for efficient greedy optimization, many modern applications, such as influence boosting, are non-submodular. In these cases, the marginal gain of adding an item may actually increase as more items are added. Standard greedy approaches for these problems require a prohibitive number of function queries—typically $\Omega(nk)$, where $n$ is the number of items and $k$ is the budget—making them unusable for large-scale datasets. This paper introduces the first polynomial-time approximation algorithms designed to bridge this gap in the non-submodular lattice setting.
Algorithmic Innovations
The authors propose two primary algorithms that significantly reduce query complexity while maintaining theoretical guarantees: ThresholdGreedy and FastGreedy.
1. ThresholdGreedy and the Pivot Strategy
In a submodular environment, we know that if adding one unit of an item is beneficial, adding a second unit will be less so. In a non-submodular world, this trend is unpredictable. To address this, the authors developed the BinarySearchPivot routine. Instead of searching every possible level for every item at every step, ThresholdGreedy identifies items that exceed a specific "marginal gain" threshold. The BinarySearchPivot then efficiently finds a "good enough" number of copies (a pivot) to add, ensuring the algorithm maintains a theoretical bound without exhaustive searching.
2. FastGreedy
FastGreedy further optimizes this process by using an adaptive threshold. This threshold is updated based on the maximum marginal gain discovered during the search and an upper bound on the "diminishing-return (DR) ratio." This variant drastically reduces the number of function queries in practice, often outperforming ThresholdGreedy in speed with negligible impact on the quality of the solution.
Theoretical Framework
To provide rigorous guarantees, the authors generalized three key metrics to the integer lattice setting:
- DR ratio ($\gamma_d$): Quantifies the extent to which the function violates the diminishing returns property.
- Submodularity ratio ($\gamma_s$): Measures how close the function is to being submodular.
- Generalized curvature ($\alpha$): Captures the degree of non-submodularity.
By utilizing these metrics, the authors proved that ThresholdGreedy achieves an approximation ratio of $(1 - e^{-\gamma_d \gamma_s} - \eta)$, providing a mathematical foundation for its performance even in complex, non-submodular landscapes.
Experimental Evaluation: Generalized Influence Maximization
The algorithms were tested using a new framework called Generalized Influence Maximization (GIM). GIM unifies traditional influence maximization with "boosting" (increasing a user's susceptibility to influence through partial incentives). Experiments were conducted on real-world social networks from the SNAP dataset:
- ca-GrQc: A collaboration network (~15k nodes).
- facebook: A social circle network (~4k nodes, 176k edges).
- Synthetic BA Network: A Barabasi-Albert graph used to compute exact non-submodularity parameters.
Key Results
- Efficiency: The speedups were substantial. On the Facebook dataset, the Standard Greedy approach required approximately 20 million queries. In contrast, the new algorithms required only a few hundred thousand queries—a speedup of several orders of magnitude.
- Solution Quality: Despite the massive reduction in computation, the solution quality remained high.
FastGreedyoccasionally saw a minor decrease in quality (up to 3%), but the results were virtually identical to the much slower Standard Greedy approach in most scenarios.
Conclusion and Future Work
This research demonstrates that submodularity is not a prerequisite for achieving logarithmic query complexity in terms of the budget $k$. By employing thresholding and binary search pivots, optimization on the integer lattice becomes feasible for large-scale, non-submodular problems.
Future work may address the sensitivity of these algorithms to the non-submodularity ratios ($\gamma_d, \gamma_s$), as theoretical guarantees weaken when these ratios are near zero. Additionally, exploring "proxy" functions or sketching techniques could further reduce the cost of the "oracle" queries (often expensive Monte Carlo simulations) used to evaluate function values during optimization.
Summary updated