arXiv Statistics ML

Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions

arXiv:2611. 04171v2 Announce Type: replace-cross Abstract: We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm.

arXiv Machine Learning
Nov 2

Stochastic and Noisy Oracles in Smooth Continuous Optimization

The article reviews models of inexact computational oracles in smooth continuous optimization, focusing on zeroth-, first-, and second-order oracles characterized by quantitative error bounds and controllable parameters. It introduces deterministic and stochastic oracle models, illustrating them with examples such as finite-difference approximations, stochastic gradients, and randomized derivative estimators, and discusses distinctions between absolute/relative errors, bias/variance, and independent/coupled randomness. The review emphasizes analytical tools that recover and compare convergence and complexity guarantees across different oracle models, providing bounds on expected stopping times and computational complexity for both deterministic and stochastic first-order methods, and briefly covering inexact second-order information.

By Albert S. Berahas, Liyuan Cao, Katya Scheinberg
arXiv Machine Learning
Oct 5

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

arXiv:2610. 03222v1 Announce Type: cross Abstract: This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations.

By Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang
arXiv Machine Learning
Sep 2

Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

The paper establishes the optimal incremental first‑order oracle (IFO) complexity for nonconvex finite‑sum optimization under individual smoothness, proving a matching lower bound that closes a previously missing √{n} factor. It also refines the analysis of the PAGE algorithm under the global Polyak‑Lojasiewicz condition, providing tighter guarantees for different ranges of the condition number. The authors introduce a novel dense weak hiding construction that yields these lower bounds and demonstrates the limits of existing methods.

By Yuxing Peng, Zhiqing Tang, Weijia Jia
arXiv Machine Learning
Sep 18

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

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 Machine Learning
Jun 18

How fast can you find a good hypothesis?

arXiv:2509. 03734v3 Announce Type: replace-cross Abstract: In the hypothesis selection problem, we are given sample and query access to finite set of candidate distributions (hypotheses), $\mathcal{H} = \{H_1, \ldots, H_n\}$, and samples from an unknown distribution $P$, both over a domain $\mathcal{X}$.

By Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Sandeep Silwal