An algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$ is designed, improving over the previous best-known bound of $\widetilde{\mathcal{O}}(T^{3/4})$ and showing that the curse of dimensionality can be at least partially lifted for this class of objectives.
Abstract
We study regret minimization for learning CDF-related objectives of the form \[ g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x), \] over $[0,1]^2$, where $g$ is a known Lipschitz function and $\mathcal{D}$ is an unknown distribution. At each round $t$, the learner selects a point $x_t$ and observes the binary feedback $\mathbb{I}(X_t\le x_t)$, where $X_t\sim\mathcal{D}$. We design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$, improving over the previous best-known bound of $\widetilde{\mathcal{O}}(T^{3/4})$ and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the $\Omega(T^{2/3})$ lower bound. As an application, our techniques yield the same $\widetilde{\mathcal{O}}(T^{7/10})$ regret bound for profit maximization in repeated bilateral trade with fixed prices.
We prove two lower bounds for the first order oracle complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory. We first show that any such (possibly randomized) algorithm must make $\tilde{\Omega}(\frac{d^2}{\sqrt{m}})$ oracle queries. For deterministic optimization algorithms, we show that $\tilde{\Omega}(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})$ queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of $\tilde{\Omega}(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})$ and $\tilde{\Omega}(\frac{d^{5/3}}{m^{1/3}})$ for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around $m\approx d^2$, where a polylogarithmic change in memory leads to a $\mathsf{poly}(d)$ change in the number of required oracle calls. Further, when the suboptimality is polynomially small in $d$, our lower bound randomized algorithms is the first to show that $\tilde{\Omega}(d^2)$ memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in $d$.
Michael Menart, Aleksandar Nikolov, Ohad Shamir· arXiv.org· 0 citations
This paper settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Gyorfi, and Lugosi.
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy· 0 citations
The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022).
A nonuniform version in which the failure probability depends on the individual parameters, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$, are proved.
This work proposes LoRA-NSGDM, which finds an $\epsilon$-stationary point with $\mathcal{O}(\epsilon^{-8})$ stochastic oracle complexity, and LoRA-STORM, which improves the stochastic oracle complexity to $\mathcal{O}(\epsilon^{-6})$.
Ru Wang, Chengchang Liu, John C. S. Lui· arXiv.org· 1 citation
We determine the exact worst-case value, at every horizon $N\geq7$, of the smallest queried gradient norm generated by Nesterov's fast gradient method on smooth convex functions. Let $t_0=1$ and $t_{k+1}=(1+\sqrt{1+4t_k^2})/2$, and let $x_0,\ldots,x_N$ denote the points at which the method evaluates gradients. For every such $N$ and every dimension $d\geq N-4$, we prove \[ \sup_{\substack{f\in\F_{0,L}(\R^d),\ x_\star\in\arg\min f \norm{x_0-x_\star}\leq R}} \min_{0\leq k\leq N}\norm{\nabla f(x_k)}^2 =\frac{L^2R^2}{\sum_{k=0}^N t_k^2}. \] The relaxed-PEP upper bound is due to Kim and Fessler, who also reported tight numerical solutions of the exact-interpolation PEP at selected horizons. What remained missing was an analytic matching family valid uniformly over the horizon. For every $N\geq7$, we construct such a family using an FGM-specific spherical polytope $K_N$ and the standard projection-envelope function \[ f_N(x)=\max_{g\in K_N}\left\{\ip{x}{g}-\frac12\norm{g}^2\right\}, \qquad \nabla f_N(x)=\Proj_{K_N}(x). \] Every queried gradient has the same norm, and the vertices of $K_N$ are generated from a three-dimensional seed by a one-dimensional spherical cone lift. The lift preserves all projection inequalities and raises the adversary dimension by one at each horizon. The projection/Moreau-envelope template itself is classical; the new ingredients are the FGM-specific algebraic seed, the proof that it attains the relaxed bound, and the common-latitude lift that propagates this exactness to every $N\geq7$. We state precise hypotheses for that propagation and do not claim that every rank-one relaxed PEP admits such a seed.
Yixing Du· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
