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