arXiv Machine Learning

Covariance-Aware Transformers for Quadratic Programming and Decision Making

arXiv Machine Learning
1d ago

Simultaneous Learning and Optimization via Misspecified Saddle Point Problems

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 Machine Learning
Sep 29

To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

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 Machine Learning
Oct 16

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets

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
arXiv Machine Learning
Sep 10

High-dimensional Linear Bandits with Knapsacks

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
arXiv AI
Oct 31

Convex-SKM-Net: Low-Latency Block Halfspace Corrections for Neural Convex Constraint Satisfaction

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 Machine Learning
Nov 6

Provably Efficient Representation Learning for Low-Rank CMDPs

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
arXiv Machine Learning
Oct 15

Learning to Design Convex Relaxations for Nonconvex Optimization

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
arXiv Machine Learning
Oct 19

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets

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 Machine Learning
Jul 16

Power Homotopy for Zeroth-Order Non-Convex Optimizations

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