In this paper, we study a class of online continuous optimization problems. At each round, the utility function is the sum of a weakly diminishing-returns (DR) submodular function and a concave function, certain cost associated with the action will occur, and the problem has total limited budget. Combining the two methods, the penalty function and Frank-Wolfe strategies, we present an online method to solve the considered problem. Choosing appropriate stepsize and penalty parameters, the performance of the online algorithm is guaranteed, that is, it achieves sub-linear regret bound and certain mild constraint violation bound in expectation.

In this work, we study a $k$-Cardinality Constrained Regularized Submodular Maximization ( $k$-CCRSM) problem, in which the objective utility is expressed as the difference between a non-negative submodular and a modular function. No multiplicative approximation algorithm exists for the regularized model, and most works have focused on designing weak approximation algorithms for this problem. In this study, we consider the $k$-CCRSM problem in a streaming fashion, wherein the elements are assumed to be visited individually and cannot be entirely stored in memory. We propose two multipass streaming algorithms with theoretical guarantees for the above problem, wherein submodular terms are monotonic and nonmonotonic.

Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees. The submodularity was investigated to capture the diversity and representativeness of the utilities, and the monotonicity has the advantage of improving the coverage. Regularized submodular optimization models were developed in the latest studies (such as a house on fire), which aimed to sieve subsets with constraints to optimize regularized utilities. This study is motivated by the setting in which the input stream is partitioned into several disjoint parts, and each part has a limited size constraint. A first threshold-based bicriteria $\mathrm{(}\mathrm{1}\mathrm{/}\mathrm{3}\mathrm{,}\mathrm{2}\mathrm{/}\mathrm{3}\mathrm{)}$-approximation for the problem is provided.

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter $k$ subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a $\mathrm{(}\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}\mathrm{/}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation with $𝒪\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}{\epsilon }^{\mathrm{4}}\mathsf{}{\log }^{\mathrm{3}}\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}\epsilon \mathrm{)}\mathsf{}\log \mathsf{}\mathrm{(}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathsf{}k\mathrm{/}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{2}}\mathrm{)}\mathrm{)}$ memory complexity, where $\kappa$ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a $\mathrm{(}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{4}}\mathrm{/}{\mathrm{(}\mathrm{2}\mathrm{-}\mathrm{2}\mathsf{}\kappa \mathrm{+}{\kappa }^{\mathrm{2}}\mathrm{)}}^{\mathrm{2}}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation algorithm.