Online inverse linear optimization: Efficient logarithmic-regret algorithm, robustness to suboptimality, and lower bound
This post describes how to achieve the current best regret bound for online inverse linear optimization using the online Newton step (ONS), one of the main results in our recent paper. The method and analysis are very simple.
Sep 19, 2025
Bandit and delayed feedback in online structured prediction
Sep 19, 2025
Any-stepsize gradient descent for separable data under Fenchel–Young losses
Sep 19, 2025
Learning to generate projections for reducing dimensionality of heterogeneous linear programming problems
May 20, 2025
Revisiting online learning approach to inverse linear optimization: A Fenchel–Young loss perspective and gap-dependent regret analysis
May 1, 2025
Inverse optimization with prediction market: A characterization of scoring rules for elciting system states
May 1, 2025
No-regret $\mathrm{M}^\natural$-concave function maximization: Stochastic bandit algorithms and NP-hardness of adversarial full-information setting
Dec 1, 2024
Generalization bound and learning methods for data-driven projections in linear programming
Dec 1, 2024
Online structured prediction with Fenchel–Young losses and improved surrogate regret for online multiclass classification with logistic loss
Jul 1, 2024
Faster discrete convex function minimization with predictions: The $\mathrm{M}$-convex case
Dec 1, 2023
Rethinking warm-starts with predictions: Learning predictions close to sets of optimal solutions for faster $\mathrm{L}$-/$\mathrm{L}^\natural$-convex function minimization
Aug 1, 2023
Nearly tight spectral sparsification of directed hypergraphs
Jul 10, 2023
Improved generalization bound and learning of sparsity patterns for data-driven low-rank approximation
May 1, 2023
Exact and scalable network reliability evaluation for probabilistic correlated failures
Dec 4, 2022
Sample complexity of learning heuristic functions for greedy-best-first and A* search
Dec 1, 2022
Lazy and fast greedy MAP inference for determinantal point process
Dec 1, 2022
Discrete-convex-analysis-based framework for warm-starting algorithms with predictions
Dec 1, 2022
Algorithmic Bayesian persuasion with combinatorial actions
Jun 1, 2022
Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games
Dec 1, 2021
Learning individually fair classifier with path-specific causal-effect constraint
May 1, 2021
Differentiable greedy algorithm for monotone submodular maximization: Guarantees, gradient estimators, and applications
May 1, 2021
On maximization of weakly modular functions: Guarantees of multi-stage algorithms, tractability, and hardness
Aug 26, 2020
Guarantees of stochastic greedy algorithms for non-monotone submodular maximization with cardinality constraints
Aug 26, 2020
Practical Frank–Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games
Apr 1, 2020
Beyond adaptive submodularity: Approximation guarantees of greedy policy with adaptive submodularity ratio
Jul 1, 2019
Greedy and IHT algorithms for non-convex optimization with monotone costs of non-zeros
Apr 16, 2019
Provable fast greedy compressive summarization with any monotone submodular function
Jun 1, 2018
Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams
Apr 9, 2018
Submodular function maximization over graphs via zero-suppressed binary decision diagrams
Jan 1, 2018
Accelerated best-first search with upper-bound computation for submodular function maximization
Jan 1, 2018
An example conference paper
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Duis posuere tellus ac convallis placerat. Proin tincidunt magna sed ex sollicitudin condimentum.
Jul 1, 2013