arXiv:2604. 27742v2 Announce Type: replace Abstract: A fundamental dichotomy in the theory of classification sets smoothness against statistical efficiency: smooth surrogate losses such as the logistic loss enable fast $O(1/T)$ optimization but yield slow square-root $H$-consistency bounds, while piecewise-linear losses like the Hinge loss achieve optimal linear $H$-consistency rates but are non-differentiable.
By Mehryar Mohri, Yutao Zhong
arXiv:2505.20817v3 Announce Type: replace-cross
Abstract: Gradient clipping is widely used in language-model training to control heavy-tailed gradient noise and can improve convergence guarantees ove...
By Taha El Bakkali El Kadi, Savelii Chezhegov, Aleksandr Beznosikov, Samuel Horv\'ath, Eduard Gorbunov
arXiv:2607. 02681v1 Announce Type: cross Abstract: Integrating information across related tasks can improve estimation and prediction in transfer, multi-task, and federated learning, but contamination and heterogeneity make robust borrowing challenging.
By Ye Tian, Mengchu Li, Marco Avella Medina
arXiv:2608. 12009v1 Announce Type: cross Abstract: Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness.
By Chenhan Jin, Shengze Xu, Binghui Xie, Kaiwen Zhou, Fan Jia, James Cheng, Tieyong Zeng
arXiv:2607. 10618v1 Announce Type: cross Abstract: We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition: $y_i=g(\inner{\ba_i}{\bPhi\bw^\ast+\bPsi\bz^\ast})+e_i$, $i=1,\dots,m$, with $m\ll n$, incoherent orthonormal bases $\bPhi,\bPsi$, a scalar link $g$, and noise $e_i$ that may be heavy-tailed or contaminated.
By Raziyeh Takbiri
arXiv:2602.08372v2 Announce Type: replace
Abstract: We study dynamic regret minimization in non-stationary online learning, with a primary focus on follow-the-regularized-leader (FTRL) methods. FTRL...
By Yan-Feng Xie, Yu-Jie Zhang, Peng Zhao, Zhi-Hua Zhou
arXiv:2604. 13130v2 Announce Type: replace Abstract: We study learning to learn through the lens of hyperparameter tuning.
By Saumya Goyal, Rohith Rongali, Ritabrata Ray, Barnab\'as P\'oczos
arXiv:2602. 12471v2 Announce Type: replace Abstract: We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data.
By Michael Crawshaw, Mingrui Liu
arXiv:2604. 03146v2 Announce Type: replace-cross Abstract: We study high-dimensional convex empirical risk minimization (ERM) under general non-Gaussian data designs.
By Chiheb Yaakoubi, Cosme Louart, Malik Tiomoko, Zhenyu Liao
arXiv:2506. 11336v2 Announce Type: replace Abstract: We study the sample complexity of stochastic convex optimization when problem parameters such as the distance to optimality and the Lipschitz constant are unknown.
By Jared Lawrence, Ari Kalinsky, Hannah Bradfield, Yair Carmon, Oliver Hinder
The paper investigates stochastic contextual bandits in an agnostic setting, aiming to compete with the best policy in a given class without assuming realizability or specific loss/reward models. It introduces an algorithm that updates the policy each round by minimizing a pessimistic objective— a clipped inverse‑propensity estimate of the policy value plus a variance penalty— and proves the first fast regret rates relative to the best‑in‑class policy. By exploiting entropy assumptions on the policy class and a H"olderian error‑bound condition, the authors achieve fast best‑in‑class regret rates, including polylogarithmic rates in the parametric case, using a sequential self‑normalized maximal inequality for bounded martingale empirical processes to derive uniform variance‑adaptive confidence bounds and ensure pessimism under adaptive data collection.
By Samuel Girard, Aurelien Bibaut, Arthur Gretton, Nathan Kallus, Houssam Zenati
arXiv:2607. 14731v1 Announce Type: new Abstract: Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm.
By Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich, Aurelien Lucchi, Eduard Gorbunov, Lingxiao Wang