题目: Combinatorial Pure Exploration for Dueling Bandits
摘要: In this paper, we study combinatorial pure exploration for dueling bandits (CPE-DB): we have multiple candidates for multiple positions as modeled by a bipartite graph, and in each round we sample a duel of two candidates on one position and observe who wins in the duel, with the goal of finding the best candidate-position matching with high probability after multiple rounds of samples. CPE-DB is an adaptation of the original combinatorial pure exploration for multi-armed bandit (CPE-MAB) problem to the dueling bandit setting. We consider both the Borda winner and the Condorcet winner cases. For Borda winner, we establish a reduction of the problem to the original CPE-MAB setting and design PAC and exact algorithms that achieve both the sample complexity similar to the CPE-MAB setting (which is nearly optimal for a subclass of problems) and polynomial running time per round. For Condorcet winner, we first design a fully polynomial time approximation scheme (FPTAS) for the offline problem of finding the Condorcet winner with known winning probabilities, and then use the FPTAS as an oracle to design a novel pure exploration algorithm CAR-Cond with sample complexity analysis. CAR-Cond is the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.

题目: Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
摘要: Mehta and Panigrahi (FOCS 2012) introduce the problem of online matching with stochastic rewards, where edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. It is one of the few online matching problems that have defied the randomized online primal dual framework by Devanur, Jain, and Kleinberg (SODA 2013) thus far. In this talk, I will present my recent work in STOC 2020, which unlocks the power of randomized online primal dual in online matching with stochastic rewards by employing the configuration linear program rather than the standard matching linear program used in previous works. Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam (SODA 2015) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi (FOCS 2012) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis.

题目: Tight Approximation Ratio of Anonymous Pricing
摘要: We study revenue maximization in two canonical Bayesian mechanism design settings. In the single-item setting, we prove that Anonymous Pricing approximates Myerson Auction by a factor of $\mathcal{C}^* \approx 2.62$. This improves the upper bound of $e \approx 2.72$ by Alaei et al. (GEB 2019) and matches with the lower bound by Jin et al. (SICOMP 2020). En route, new characterizations of Myerson Auction and distributions are discovered.
In the unit-demand single-buyer setting, we show that Uniform Pricing approximates the optimal deterministic mechanism by a factor of $\mathcal{C}^*$ and then give a matching lower-bound instance. This is by extending the {\em single-dimensional representative method} of Chawla et al. (EC 2007) and settles an open question asked first by Cai and Daskalakis (GEB 2015).

题目: Almost Tight Approximation Hardness for K-EC-DST
摘要: The k-EC-DST problem is an important variant of the classical directed Steiner tree problem. The instance is a directed graph G with a root vertex r, a set of vertices T called terminals and nonnegative edge costs. A feasible solution F is a subset of edges that for each terminal t in T, there are at least k edge-disjoint paths of F from r to t. The cost of F is the sum of the cost of edges in F. The problem is to find a feasible solution of minimum cost. For k > lTl, we obtained approximation hardness of lTl ^ (1-o(1)), which almost matches the straightforward approximation ratio lTl. For directed acyclic graphs with diameter L and k >= lTl, we obtained approximation hardness of k ^ L , which is close the state-of-the-art approximation ratio O(L k^{L-1} \log n). This is a joint work with Qingyun Chen, Bundit Laekhanukit and Yuhao Zhang.

题目: Optimization from Structured Samples for Coverage and Influence Functions
摘要: We revisit the optimization from samples (OPS) model, which studies the problem of optimizing objective functions directly from the sample data. Previous results showed that we cannot obtain a constant approximation ratio for the maximum coverage problem using polynomial independent samples of the form (BRS, STOC17), even if coverage functions are -PMAC learnable using these samples (BDF+, SODA12). In this work, to circumvent the impossibility result of OPS, we propose a stronger model called optimization from structured samples (OPSS), where the data samples encode the structural information of the functions. We show that under OPSS model, the maximum coverage problem enjoys constant approximation under mild assumptions on the sample distribution. We further generalize the result and show that influence maximization also enjoys constant approximation under this model.

题目: On exploring practical potentials of variational quantum algorithms with advantages
摘要: Quantum computers, as a new paradigm for computing, have experienced rapid advances in both hardware and software. A concrete milestone is Google’s quantum supremacy experiment on a 53-qubit superconducting quantum processor. With this regard, huge efforts have been made to apply noisy intermediate-scale quantum (NISQ) machines to accomplish practical tasks with computational advantages. Variational quantum algorithms (VQAs), which include quantum neural networks (QNNs) and variational quantum eigensolvers (VQEs), are promising candidates to achieve this goal. In this talk, we will first discuss the capabilities and limitations of VQAs in the view of optimization theory and learning theory. We will next exhibit a quantum architecture search scheme to automatically seek an optimal ansatz, which well balances the tradeoff between expressivity and trainability encountered in VQAs. Then, we will present an efficient measure to explicitly quantify the expressivity of VQAs, supported by a notion developed in statistical learning theory. Last, we will elaborate on the possibilities to use quantum kernels instead of QNNs to pursue computational merits in the NISQ era.

题目: Gradient Descent on Homogeneous Neural Networks:Maximization and Simplicity Bias
摘要:The generalization mystery of overparametrized deep nets has motivated efforts to understand how gradient descent (GD) converges to low-loss solutions that generalize well. In this talk, we draw a connection between GD on homogeneous neural networks (including VGG-like CNNs without bias) and margin maximization. Our work suggests that GD may converge to the “max-margin” solution attaining the global optimum of the loss, which presumably generalizes well. We further look into gradient flow on finite two-layer Leaky ReLU nets trained on linearly separable and symmetric data and prove such convergence with global optimality of margin. The analysis also gives some theoretical justification for recent empirical findings on the so-called simplicity bias of GD towards linear or other “simple” classes of solutions. On the pessimistic side, we demonstrate via simple examples that in general global optimality of margin might not be easy to achieve due to non-convexity, but local optimality still makes sense.
Joint work with Jian Li, Zhiyuan Li, Runzhe Wang, Sanjeev Arora.

题目: 基于人类感知的无监督视频异常事件检测框架
摘要: 视频异常检测旨在自动的检测视频中各类违反常规、值得注意的异常事件。现有的视频异常检测方法通常需要正常视频构建一个正常模型/分布。并且，虽然视频异常检测是一种源于人类主观感知的任务，现有方法并没有考虑到这种生物动机。为此，提出一种基于人类感知的无监督视频异常检测框架，其基于两个核心观察：1）人类的感知通常是局部的，即在感知异常时聚焦于局部前景及其周围环境。为此，我们借助通用知识提出一种精准全面的前景定位算法。同时，设计了一种高效的区域定位策略以充分利用局部环境信息。2）频繁发生的事件将会塑造人类对正常的定义，这启发我们设计一种理论支持的代理训练机制，其利用未标注的视频数据训练一个深度网络完成某种代理任务，频繁发生的事件将在深度网络的“塑造”中起主导作用。通过这种方式，正常和异常之间的训练误差间隙将会凸显罕见的事件为异常。此外，在框架中我们探索了各种代理任务和网络模型，验证了框架的广泛适用性和惊异的性能：其不仅远超无监督方法，同时能比肩或优于半监督方法。

题目: 结合强化学习和Lin-Kernighan-Helsgaun算法求解旅行商问题
摘要: 我们提出将强化学习与著名的启发式算法Lin–Kernighan–Helsgaun (LKH) 相结合以解决经典的旅行商问题(TSP)。所提出的算法显著改进了LKH算法的性能，为组合优化与强化学习的结合提供了新的思路。这一工作被AAAI 2021收录。
现有的应用强化学习解决TSP问题的方法或是应用强化学习改进启发式算法，或是应用深度强化学习直接解决TSP问题。但前者未能将强化学习与启发式算法的核心过程相结合，因此并无实质上的改进；后者因神经网络的复杂性限制，无法扩展到大规模TSP实例，且在小规模问题上结果也远不如优秀的启发式算法。对此，我们提出将强化学习与LKH算法的核心搜索过程相结合，以优化LKH算法的性能。
具体而言，我们通过强化学习算法使LKH的核心搜索邻域能够自适应地变化，从而加强算法对最优解的探索能力。我们尝试了蒙特卡洛(MC)，Q–learning和Sarsa三种强化学习算法，并发现它们都能明显改进LKH算法，并且三者在解决不同TSP实例时具有互补性。因此，我们提出一种变策略强化学习算法(VSR–LKH)，进一步优化了算法。
总之，所提出的VSR–LKH算法将三种强化学习算法(MC，Q–learning，Sarsa)与LKH的核心搜索过程相结合。我们在著名的数据集TSPLIB中的所有111个标准TSP实例上测试了VSR–LKH的性能，其中TSP城市数量最多可达在85900个。结果表明，所提出的算法显著增强了LKH算法。此外，这项工作验证了应用强化学习改进启发式算法的可行性，我们所提出的将强化学习与启发式核心搜索过程相结合的方法也可应用于优化其他的启发式算法