5 papers
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
Zongqi Wan, Zhijie Zhang
We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank- matroid on elements, we give a randomized oracle-polynomial…
Approximating the Trace Distance Between Product Quantum States
Kun He, Dimitrios Myrisiotis, Junhong Nie +1
We study the trace distance \[D_{\mathrm{tr}}(Ï,Ï) =\frac12\|Ï-Ï\|_1, Ï=\bigotimes_{i=1}^nÏ_i,\quad Ï=\bigotimes_{i=1}^nÏ_i, \] when the two exponentially large states are…
Boosting Gradient Ascent for Continuous DR-submodular Maximization
Qixin Zhang, Zongqi Wan, Zengde Deng +4
Projected Gradient Ascent (PGA) is the most commonly used optimization scheme in machine learning and operations research areas. Nevertheless, numerous studies and examples have sh…
Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
Zongqi Wan, Jialin Zhang, Xiaoming Sun +1
Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the…
Competitive Auctions with Imperfect Predictions
Pinyan Lu, Zongqi Wan, Jialin Zhang
The competitive auction was first proposed by Goldberg, Hartline, and Wright. In their paper, they introduce the competitive analysis framework of online algorithm designing into t…