Faster Convergence with Multiway Preferences
- URL: http://arxiv.org/abs/2312.11788v1
- Date: Tue, 19 Dec 2023 01:52:13 GMT
- Title: Faster Convergence with Multiway Preferences
- Authors: Aadirupa Saha, Vitaly Feldman, Tomer Koren, Yishay Mansour
- Abstract summary: We consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway comparisons.
Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates.
- Score: 99.68922143784306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of convex optimization with preference feedback, where
the goal is to minimize a convex function given a weaker form of comparison
queries. Each query consists of two points and the dueling feedback returns a
(noisy) single-bit binary comparison of the function values of the two queried
points. Here we consider the sign-function-based comparison feedback model and
analyze the convergence rates with batched and multiway (argmin of a set
queried points) comparisons. Our main goal is to understand the improved
convergence rates owing to parallelization in sign-feedback-based optimization
problems. Our work is the first to study the problem of convex optimization
with multiway preferences and analyze the optimal convergence rates. Our first
contribution lies in designing efficient algorithms with a convergence rate of
$\smash{\widetilde O}(\frac{d}{\min\{m,d\} \epsilon})$ for $m$-batched
preference feedback where the learner can query $m$-pairs in parallel. We next
study a $m$-multiway comparison (`battling') feedback, where the learner can
get to see the argmin feedback of $m$-subset of queried points and show a
convergence rate of $\smash{\widetilde O}(\frac{d}{ \min\{\log m,d\}\epsilon
})$. We show further improved convergence rates with an additional assumption
of strong convexity. Finally, we also study the convergence lower bounds for
batched preferences and multiway feedback optimization showing the optimality
of our convergence rates w.r.t. $m$.
Related papers
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
We propose two variance reduced ZO estimators for complex gradient problems.
We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
arXiv Detail & Related papers (2024-10-03T15:04:01Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems.
We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
arXiv Detail & Related papers (2022-10-23T21:24:37Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
We consider a distributed multi-agent optimization problem where each agent holds a local objective function that is smooth and convex.
We extend the distributed gradient-tracking method to the bandit setting where we don't have an estimate of the gradient.
We analyze the convergence of this novel technique for smooth and convex objectives using approximation tools.
arXiv Detail & Related papers (2022-10-11T17:04:45Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
Existing methods either require two gradient calls or two projections in each iteration, which may costly in some applications.
In this paper, we first show that a variant of the Optimistic Gradient (RGOG) has a rich set of non-comonrate min-max convergence rate problems.
Our convergence rates hold for standard measures such as and the natural and the natural.
arXiv Detail & Related papers (2022-10-06T17:50:42Z) - Dueling Convex Optimization with General Preferences [85.14061196945599]
We address the problem of emph optimization with dueling feedback, where the goal is to minimize a convex function given a weaker form of emphilonling feedback.
Our main contribution is an efficient algorithm with convergence $smashwidetilde O(epsilon-4p)$ for a smooth convex objective function, and an efficient $smashwidetilde O(epsilon-2p) when the objective is smooth and convex.
arXiv Detail & Related papers (2022-09-27T11:10:41Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems.
Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
arXiv Detail & Related papers (2022-07-18T12:03:26Z) - A New One-Point Residual-Feedback Oracle For Black-Box Learning and
Control [28.679167097106813]
We propose a novel one-point feedback scheme that queries the function value once at each iteration and estimates the gradient using the residual between two consecutive points.
We show that the proposed algorithm achieves the same convergence rate as that of two-point scheme with uncontrollable data samples.
arXiv Detail & Related papers (2020-06-18T19:31:13Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope.
Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
arXiv Detail & Related papers (2020-06-11T17:43:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.