arXiv:2609. 20687v1 Announce Type: cross Abstract: We study first-order black-box convex optimization over an $\ell_p$-ball for objectives Lipschitz in the $\ell_q$-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set ($p < q$) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors.
By David Mart\'inez-Rubio, Brian Bullins, Crist\'obal Guzm\'an, Mathieu Molina
arXiv:2607. 27807v1 Announce Type: new Abstract: This paper studies learning-augmented and randomized online aggregation with delays on a line metric.
By Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
arXiv:2505. 21460v2 Announce Type: replace Abstract: We study online calibration of multi-dimensional forecasts over an arbitrary convex set $P \subset \mathbb{R}^d$ relative to an arbitrary norm $|\cdot|$.
By Maxwell Fishelson, Noah Golowich, Mehryar Mohri, Jon Schneider
arXiv:2409. 10908v3 Announce Type: replace-cross Abstract: Recovering the underlying $k$-clustering of a set $U$ of $n$ points by asking pair-wise same-cluster queries has garnered significant interest in the past few years.
By Hadley Black, Euiwoong Lee, Arya Mazumdar, Barna Saha
arXiv:2602. 06257v2 Announce Type: replace Abstract: Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions.
By Chase Hutton, Adam Melrod, Han Shao
We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b).
arXiv:2609.06394v1 Announce Type: cross
Abstract: Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computat...
By Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar, Hoang-Son Tran
arXiv:2609. 20701v1 Announce Type: cross Abstract: We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$.
By David Mart\'inez-Rubio, Crist\'obal Guzm\'an
arXiv:2608. 01616v1 Announce Type: new Abstract: Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific.
By Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla
arXiv:2602. 08542v3 Announce Type: replace-cross Abstract: Given a weighted undirected graph, a number of clusters $k$, and an exponent $z$, the goal in the $(k, z)$-clustering problem on graphs is to select $k$ vertices as centers that minimize the sum of the distances raised to the power $z$ of each vertex to its closest center.
By Emilio Cruciani, Sebastian Forster, Antonis Skarlatos
The paper addresses bias introduced by aggregating local signs in distributed sign-based variance reduction methods, which hampers optimal convergence rates. By proposing an unbiased compression of recursive gradient increments to track the global gradient at the server, the authors achieve optimal convergence rates for both nonconvex stochastic and finite-sum optimization. They provide specific rate bounds for α-norms and demonstrate matching sample complexities to centralized settings for finite-sum problems.
By Wei Jiang, Zechao Li, Lijun Zhang
arXiv:2608. 05327v1 Announce Type: cross Abstract: Our results show that the existence of a short high-utility protocol already suffices for efficient communication.
By Mark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart Russell