More Like this

1. Differentially Private Monotone Submodular Maximization Under Matroid and Knapsack Constraints

   Sadeghi, Omid; Fazel, Maryam (April 2021, Proceedings of Machine Learning Research)

   Banerjee, Arindam; Fukumizu, Kenji (Ed.)

   Numerous tasks in machine learning and artificial intelligence have been modeled as submodular maximization problems. These problems usually involve sensitive data about individuals, and in addition to maximizing the utility, privacy concerns should be considered. In this paper, we study the general framework of non-negative monotone submodular maximization subject to matroid or knapsack constraints in both offline and online settings. For the offline setting, we propose a differentially private $$(1-\frac{\kappa}{e})$$-approximation algorithm, where $$\kappa\in[0,1]$$ is the total curvature of the submodular set function, which improves upon prior works in terms of approximation guarantee and query complexity under the same privacy budget. In the online setting, we propose the first differentially private algorithm, and we specify the conditions under which the regret bound scales as $$Ø(\sqrt{T})$$, i.e., privacy could be ensured while maintaining the same regret bound as the optimal regret guarantee in the non-private setting. 

   more » « less
2. Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

   Asi, Hilal; Liu, Daogao; Tian, Kevin (June 2024, https://doi.org/10.48550/arXiv.2406.02789)

   This paper studies differentially private stochastic convex optimization (DP-SCO) in the presence of heavy-tailed gradients, where only a 𝑘 kth-moment bound on sample Lipschitz constants is assumed, instead of a uniform bound. The authors propose a reduction-based approach that achieves the first near-optimal error rates (up to logarithmic factors) in this setting. Specifically, under ( 𝜖 , 𝛿 ) (ϵ,δ)-approximate differential privacy, they achieve an error bound of 𝐺 2 𝑛 + 𝐺 𝑘 ⋅ ( 𝑑 𝑛 𝜖 ) 1 − 1 𝑘 , n ​ G 2 ​ ​ +G k ​ ⋅( nϵ d ​ ​ ) 1− k 1 ​ , up to a mild polylogarithmic factor in 1 𝛿 δ 1 ​ , where 𝐺 2 G 2 ​ and 𝐺 𝑘 G k ​ are the 2nd and 𝑘 kth moment bounds on sample Lipschitz constants. This nearly matches the lower bound established by Lowy and Razaviyayn (2023). Beyond the basic result, the authors introduce a suite of private algorithms that further improve performance under additional assumptions: an optimal algorithm under a known-Lipschitz constant, a near-linear time algorithm for smooth functions, and an optimal linear-time algorithm for smooth generalized linear models. 

   more » « less
3. Eulerian Graph Sparsification by Effective Resistance Decomposition

   Jambulapati, Arun; Sachdeva, Sushant; Sidford, Aaron; Tian, Kevin; Zhao, Yibin (August 2024, https://doi.org/10.48550/arXiv.2408.10172)

   The authors present an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an 𝑂 ~ ( 𝑛 log ⁡ 2 𝑛 ⋅ 𝜀 − 2 ) O ~ (nlog 2 n⋅ε −2 )-edge 𝜀 ε-approximate Eulerian sparsifier with high probability in 𝑂 ~ ( 𝑚 log ⁡ 3 𝑛 ) O ~ (mlog 3 n) time (where 𝑂 ~ ( ⋅ ) O ~ (⋅) hides polyloglog(n) factors). By a reduction from Peng-Song (STOC ’22), this yields an 𝑂 ~ ( 𝑚 log ⁡ 3 𝑛 + 𝑛 log ⁡ 6 𝑛 ) O ~ (mlog 3 n+nlog 6 n)-time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially bounded weights with high probability, improving on the previous state-of-the-art runtime of Ω ( 𝑚 log ⁡ 8 𝑛 + 𝑛 log ⁡ 23 𝑛 ) Ω(mlog 8 n+nlog 23 n). They also provide a polynomial-time algorithm that computes sparsifiers with 𝑂 ( min ⁡ ( 𝑛 log ⁡ 𝑛 ⋅ 𝜀 − 2 + 𝑛 log ⁡ 5 / 3 𝑛 ⋅ 𝜀 − 4 / 3 , 𝑛 log ⁡ 3 / 2 𝑛 ⋅ 𝜀 − 2 ) ) O(min(nlogn⋅ε −2 +nlog 5/3 n⋅ε −4/3 ,nlog 3/2 n⋅ε −2 )) edges, improving the previous best bounds. Furthermore, they extend their techniques to yield the first 𝑂 ( 𝑚 ⋅ polylog ( 𝑛 ) ) O(m⋅polylog(n))-time algorithm for computing 𝑂 ( 𝑛 𝜀 − 1 ⋅ polylog ( 𝑛 ) ) O(nε −1 ⋅polylog(n))-edge graphical spectral sketches, along with a natural Eulerian generalization. Unlike prior approaches using short cycle or expander decompositions, their algorithms leverage a new effective resistance decomposition scheme, combined with natural sampling and electrical routing for degree balance. The analysis applies asymmetric variance bounds specialized to Eulerian Laplacians and tools from discrepancy theory. 

   more » « less
4. Combinatorial Stochastic-Greedy Bandit

   https://doi.org/10.1609/aaai.v38i11.29093  

   Fourati, Fares; Quinn, Christopher John; Alouini, Mohamed-Slim; Aggarwal, Vaneet (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We propose a novel combinatorial stochastic-greedy bandit (SGB) algorithm for combinatorial multi-armed bandit problems when no extra information other than the joint reward of the selected set of n arms at each time step t in [T] is observed. SGB adopts an optimized stochastic-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms. Unlike existing methods that explore the entire set of unselected base arms during each selection step, our SGB algorithm samples only an optimized proportion of unselected arms and selects actions from this subset. We prove that our algorithm achieves a (1-1/e)-regret bound of O(n^(1/3) k^(2/3) T^(2/3) log(T)^(2/3)) for monotone stochastic submodular rewards, which outperforms the state-of-the-art in terms of the cardinality constraint k. Furthermore, we empirically evaluate the performance of our algorithm in the context of online constrained social influence maximization. Our results demonstrate that our proposed approach consistently outperforms the other algorithms, increasing the performance gap as k grows. 

   more » « less
5. Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints

   Sadeghi, Omid; Fazel, Maryam (August 2020, Proceedings of Machine Learning Research)

   In this paper, we study a class of online optimization problems with long-term budget constraints where the objective functions are not necessarily concave (nor convex), but they instead satisfy the Diminishing Returns (DR) property. In this online setting, a sequence of monotone DR-submodular objective functions and linear budget functions arrive over time and assuming a limited total budget, the goal is to take actions at each time, before observing the utility and budget function arriving at that round, to achieve sub-linear regret bound while the total budget violation is sub-linear as well. Prior work has shown that achieving sub-linear regret and total budget violation simultaneously is impossible if the utility and budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against the best fixed decision in hindsight which satisfies the budget constraint proportionally over any window of length W. We propose the Online Saddle Point Hybrid Gradient (OSPHG) algorithm to solve this class of online problems. For W = T, we recover the aforementioned impossibility result. However, if W is sublinear in T, we show that it is possible to obtain sub-linear bounds for both the regret and the total budget violation. 

   more » « less