Vahab S. Mirrokni

The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization

  • Benjamin Grimmer
  • Haihao Lu
  • Vahab S. Mirrokni
  • Pratik Worah
    • Categories Robust Optimization, Unconstrained Optimization Tags , , , , , ,

    Minimax optimization has become a central tool for modern machine learning with applications in generative adversarial networks, robust optimization, reinforcement learning, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties posed by nonconvex-nonconcave structures. In this paper, we study the classic proximal point method … Read more

    Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

  • Viswanath Nagarajan
  • Vahab S. Mirrokni
  • Maxim Sviridenko
  • Jon Lee
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more