[
    {
        "id": "osp-16802",
        "type": "article-journal",
        "title": "Optimal and Efficient Online Inverse Optimization",
        "author": [
            {
                "family": "Gupta",
                "given": "Anupam"
            },
            {
                "family": "Guruganesh",
                "given": "Guru"
            },
            {
                "family": "Lin",
                "given": "Honghao"
            },
            {
                "family": "Mirrokni",
                "given": "Vahab"
            },
            {
                "family": "Leme",
                "given": "Renato Paes"
            },
            {
                "family": "Woodruff",
                "given": "David P."
            }
        ],
        "URL": "https://omanscience.com/ar/articles/optimal-and-efficient-online-inverse-optimization",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "abstract": "In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\\mathbb{R}^{d}$; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret $O(\\sqrt d)$ with a randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$. It is a variant of the variable-metric algorithms of Sakaue et al.\\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made."
    }
]