Shinsaku Sakaue
  • Bio
  • Experience
  • Papers
  • Recent & Upcoming Talks
    • Example Talk
  • All Papers
    • Online Inverse Linear Optimization: Improved Regret Bound, Robustness to Suboptimality, and Toward Tight Regret Analysis
    • Inverse Optimization with Prediction Market: A Characterization of Scoring Rules for Elciting System States
    • Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel–Young Loss Perspective and Gap-Dependent Regret Analysis
    • Generalization bound and learning methods for data-driven projections in linear programming
    • No-regret $\mathrm{M}^\natural$-concave function maximization: Stochastic bandit algorithms and NP-hardness of adversarial full-information setting
    • Online structured prediction with Fenchel–Young losses and improved surrogate regret for online multiclass classification with logistic loss
    • Faster discrete convex function minimization with predictions: The $\mathrm{M}$-convex case
    • Rate constant matrix contraction method for stiff master equations with detailed balance
    • Rethinking warm-starts with predictions: Learning predictions close to sets of optimal solutions for faster $\mathrm{L}$-/$\mathrm{L}^\natural$-convex function minimization
    • Nearly tight spectral sparsification of directed hypergraphs
    • Making individually fair predictions with causal pathways
    • Improved generalization bound and learning of sparsity patterns for data-driven low-rank approximation
    • Exact and scalable network reliability evaluation for probabilistic correlated failures
    • Discrete-convex-analysis-based framework for warm-starting algorithms with predictions
    • Lazy and fast greedy MAP inference for determinantal point process
    • Sample complexity of learning heuristic functions for greedy-best-first and A* search
    • Sparse regularized optimal transport with deformed $q$-entropy
    • Algorithmic Bayesian persuasion with combinatorial actions
    • Selecting molecules with diverse structures and properties by maximizing submodular functions of descriptors learned with graph neural networks
    • Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games
    • Differentiable greedy algorithm for monotone submodular maximization: Guarantees, gradient estimators, and applications
    • Learning individually fair classifier with path-specific causal-effect constraint
    • Guarantees of stochastic greedy algorithms for non-monotone submodular maximization with cardinality constraints
    • On maximization of weakly modular functions: Guarantees of multi-stage algorithms, tractability, and hardness
    • Practical Frank–Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games
    • Best-first search algorithm for non-convex sparse minimization
    • Beyond adaptive submodularity: Approximation guarantees of greedy policy with adaptive submodularity ratio
    • Greedy and IHT algorithms for non-convex optimization with monotone costs of non-zeros
    • Provable fast greedy compressive summarization with any monotone submodular function
    • Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams
    • Accelerated best-first search with upper-bound computation for submodular function maximization
    • Submodular function maximization over graphs via zero-suppressed binary decision diagrams
    • Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems
    • On maximizing a monotone $k$-submodular function subject to a matroid constraint
    • Using multiparameter eigenvalues for solving quadratic programming with quadratic equality constraints
    • Solving generalized CDT problems via two-parameter eigenvalues
  • Projects
  • Blog
    • 🎉 Easily create your own simple yet highly customizable blog
    • 🧠 Sharpen your thinking with a second brain
    • 📈 Communicate your results effectively with the best data visualizations
    • 👩🏼‍🏫 Teach academic courses
    • ✅ Manage your projects
  • Blog
    • 🎉 Easily create your own simple yet highly customizable blog
  • Projects
    • Pandas
    • PyTorch
    • scikit-learn
  • Experience
  • Teaching
    • Learn JavaScript
    • Learn Python
  • Publications
    • An example preprint / working paper
    • An example journal article
    • An example conference paper

Beyond adaptive submodularity: Approximation guarantees of greedy policy with adaptive submodularity ratio

Jul 1, 2019·
Kaito Fujii
,
Shinsaku Sakaue
· 0 min read
PDF
Type
Conference paper
Publication
International Conference on Machine Learning (ICML)
Last updated on Jul 1, 2019
← Best-first search algorithm for non-convex sparse minimization Oct 1, 2019
Greedy and IHT algorithms for non-convex optimization with monotone costs of non-zeros Apr 16, 2019 →

© 2025 Me. This work is licensed under CC BY NC ND 4.0

Published with Hugo Blox Builder — the free, open source website builder that empowers creators.