The paper introduces a framework for misspecified saddle point problems where the objective depends on an unknown parameter that must be learned simultaneously from data. Two accelerated primal-dual algorithms are proposed: a naive extension that substitutes evolving parameter estimates, and a learning‑aware variant that adjusts momentum updates to account for parameter dynamics. Both achieve an ≥O(log K/K) convergence rate, with the learning‑aware method offering a tighter constant and adaptive step‑size, and an extended version handles multiple optimal solutions with an O(1/√K) rate, demonstrated on a portfolio optimization task.
By Mohammad Mahdi Ahmadi, Erfan Yazdandoost Hamedani
arXiv:2602. 14154v3 Announce Type: replace Abstract: Differentiating through the solution of a quadratic program (QP) is a central problem in differentiable optimization.
By Yuxuan Linghu, Zhiyuan Liu, Qi Deng
arXiv:2609. 30501v1 Announce Type: new Abstract: Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.
By Zhiyao Zhang, Menglu Yu, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu
arXiv:2606. 08797v1 Announce Type: cross Abstract: Decision-focused learning has shown great promise for addressing predict-then-optimize problems, particularly in the presence of under-specified models.
By St\'ephane Eilles-Chan Way, Hugo Percot, Quentin Cappart, Tias Guns, Louis-Martin Rousseau
The paper presents the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general convex action sets. It achieves a regret of ≥O(d^{5/4}√T) using only linear optimization oracles, and a near‑optimal ≥O(d√T) regret when an optimal‑design exploration distribution is available. The work improves on previous FTPL algorithms and generalizes earlier results for special action sets, offering a simpler and more computationally efficient approach that relies on adaptive perturbation distributions and a new analysis framework based on Fisher information.
By Chen-Yu Wei
The paper studies high‑dimensional linear contextual bandits with knapsack constraints (CBwK), aiming to exploit sparsity for tighter regret bounds. It introduces an online hard‑thresholding estimator integrated into a primal‑dual framework, achieving sub‑linear regret that grows only logarithmically with the feature dimension. Under either a diverse‑covariate or margin condition, the regret improves to τ‑dependent rates, and when both hold simultaneously, a dual resolving scheme yields an even tighter bound. The approach also recovers optimal rates for high‑dimensional contextual bandits without knapsacks, and experiments demonstrate its practical effectiveness.
By Wanteng Ma, Dong Xia, Jiashuo Jiang
Convex‑SKM‑Net is a neural layer that enforces convex constraints by constructing linearization halfspaces from residual and gradient oracles, avoiding constraint‑specific projections. It uses fixed‑depth dual projected‑gradient descent on GPU‑friendly matrix operations to solve minimum‑displacement block problems, jointly learning a predictor and a positive‑definite mobility matrix to shape corrections. The method converges theoretically, achieves sub‑$10^{-3}$ feasibility on SOC‑MPC and power‑system relaxations, and outperforms state‑of‑the‑art constraint‑satisfaction techniques with up to 144× speedups and near‑optimal objective gaps.
By Haoyu Zhu, Xiaochen Zhang, Qingchun Hou
arXiv:2606. 01081v1 Announce Type: new Abstract: Decision-focused learning (DFL) trains predictive models by optimizing downstream decision quality rather than standalone prediction accuracy.
By Wyame Benslimane, Tinghan Ye, Pascal Van Hentenryck, Paul Grigas
The paper introduces “MFRLC”, a model‑free algorithm for representation learning in low‑rank Constrained Markov Decision Processes (CMDPs). It combines Least‑Squares Value Iteration with Upper Confidence Bound and a primal‑dual scheme to balance reward maximization and constraint compliance, learning value functions directly from representations without estimating transition kernels. The authors prove that “MFRLC” achieves sublinear “O(K^{3/4})” reward regret and cumulative constraint violation over K rounds, independent of the state‑space size.
By Kaixuan Liu, Guojun Xiong, Shengpu Tang, Wanyun Si, Jian Li
The paper introduces AutoConvexRelax, a learning-based framework that automates the design of convex relaxations for nonconvex optimization problems. By representing a problem as a tripartite graph of variables, symbolic terms, and objective/constraint positions, the method learns a policy to compose symbolic rewrites that generate valid relaxation trajectories. Experiments on quadratic and fractional problems show that the learned policy improves McCormick lower bounds by 13.52% and achieves near‑semidefinite bounds while using smaller formulations.
By Jinrun Liu, Bai Yan, Tengfei Liu, Qunfeng Liu, Jian Yang, Shi Cheng, Yuhui Shi, Qi Zhao
The paper presents the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general action sets. It attains a ≥O(d^{5/4}√T) regret using only linear optimization oracles, and a near‑optimal ≥O(d√T) regret when an optimal‑design exploration distribution is available. The authors introduce adaptive perturbation distributions—including Gaussian, random‑weighting, and elliptical perturbations—and develop a systematic analysis of the FTPL stability term via Fisher information, extending the FTPL framework beyond previous approaches.
By Chen-Yu Wei
arXiv:2511. 13592v2 Announce Type: replace-cross Abstract: The existing method of GS-PowerOpt solves the non-convex optimization problem of the form $\max_{\boldsymbol{x} \in \mathbb{R}^d} f(\boldsymbol{x})$ through maximizing a Gaussian-smoothed surrogate $F_{N,\sigma}(\boldsymbol{\mu}) = \mathbb{E}_{\boldsymbol{x}\sim\mathcal{N}(\boldsymbol{\mu},\sigma^2 I_d)}[e^{N f(\boldsymbol{x})}]$.
By Chen Xu