Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

This paper establishes the convergence of Dual Space Preconditioned Gradient Descent to an interpolating solution for overparameterized linear models using novel Bregman divergence techniques, while characterizing its implicit bias to show that isotropic preconditioners recover standard gradient descent solutions and general preconditioners yield solutions within a constant factor of the standard solution.

Reza Ghane, Danil Akhtiamov, Babak HassibiThu, 12 Ma📊 stat

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

This paper proposes a trust-region interior-point stochastic sequential quadratic programming (TR-IP-SSQP) method that utilizes adaptive stochastic oracles to solve optimization problems with stochastic objectives and deterministic nonlinear constraints, proving its global almost-sure convergence to first-order stationary points and demonstrating practical performance on benchmark and logistic regression problems.

Yuchen Fang, Jihun Kim, Sen Na, James Demmel, Javad LavaeiThu, 12 Ma🔢 math

On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

This paper addresses the fixed-budget best-arm identification problem in non-stationary linear bandits by establishing a tighter, arm-set-dependent lower bound on error probability and proposing the Adjacent-BAI\textsf{Adjacent-BAI} algorithm, which utilizes an Adjacent-optimal design to achieve minimax-optimal performance that fully leverages the geometric structure of the arm set.

Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam FazelThu, 12 Ma📊 stat

Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent

This paper establishes a general stability criterion for stochastic mirror descent algorithms to enable valid statistical inference in adaptive bandit settings, introducing regularized-EXP3 variants that simultaneously achieve minimax-optimal regret, nominal confidence interval coverage, and robustness to adversarial corruptions.

Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury, Koulik KhamaruThu, 12 Ma📊 stat

SDSR: A Spectral Divide-and-Conquer Approach for Species Tree Reconstruction

The paper introduces SDSR, a scalable spectral divide-and-conquer algorithm for species tree reconstruction that achieves up to 10-fold faster runtimes compared to standard methods while maintaining comparable accuracy under the multispecies coalescent model.

Ortal Reshef (Hebrew University of Jerusalem), Ofer Glassman (Weizmann Institute of Science), Or Zuk (Hebrew University of Jerusalem), Yariv Aizenbud (Tel Aviv University), Boaz Nadler (Weizmann Institute of Science), Ariel Jaffe (Hebrew University of Jerusalem)Thu, 12 Ma🧬 q-bio