Federated Online and Bandit Convex Optimization

• URL: http://arxiv.org/abs/2311.17586v1
• Date: Wed, 29 Nov 2023 12:29:54 GMT
• Title: Federated Online and Bandit Convex Optimization
• Abstract summary: We study the problems of distributed online and bandit convex optimization against an adaptive adversary. We show that collaboration is not beneficial when the machines have access to the first-order gradient information at the queried points. Our work is the first attempt towards a systematic understanding of federated online optimization with limited feedback.
• Score: 27.565740560571292
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problems of distributed online and bandit convex optimization against an adaptive adversary. We aim to minimize the average regret on $M$ machines working in parallel over $T$ rounds with $R$ intermittent communications. Assuming the underlying cost functions are convex and can be generated adaptively, our results show that collaboration is not beneficial when the machines have access to the first-order gradient information at the queried points. This is in contrast to the case for stochastic functions, where each machine samples the cost functions from a fixed distribution. Furthermore, we delve into the more challenging setting of federated online optimization with bandit (zeroth-order) feedback, where the machines can only access values of the cost functions at the queried points. The key finding here is identifying the high-dimensional regime where collaboration is beneficial and may even lead to a linear speedup in the number of machines. We further illustrate our findings through federated adversarial linear bandits by developing novel distributed single and two-point feedback algorithms. Our work is the first attempt towards a systematic understanding of federated online optimization with limited feedback, and it attains tight regret bounds in the intermittent communication setting for both first and zeroth-order feedback. Our results thus bridge the gap between stochastic and adaptive settings in federated online optimization.

Related papers

• Online Algorithms via Minimax and Posterior Matching [5.995574493969049]
  We develop a more unifying methodology via the minimax viewpoint.<n>We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems.
  arXiv  Detail & Related papers  (2026-08-03T02:46:17Z)
• MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes [57.24311218570012]
  We extend the non-smooth convex theory of EF21-P (Anonymous 2024) and MARINA-P (arXiv:2402.06412) in the non-size convex setting. We provide theoretical guarantees under constant, decreasing, and adaptive (aktypetype) steps.
  arXiv  Detail & Related papers  (2024-12-22T16:18:34Z)
• Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization [8.670873561640903]
  We investigate the finite-time analysis of finding ($delta,,ilon$)-stationary points for nonsmooth nonsmooth objectives in decentralized settings. $O is the first finite-time guarantee for decentralized nonsmooth optimization.
  arXiv  Detail & Related papers  (2024-06-03T16:09:34Z)
• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  We develop a robust decentralized saddle-point algorithm against random link failures with heterogeneous probabilities. We extend our algorithm and analysis to the two-point bandit feedback scenario.
  arXiv  Detail & Related papers  (2024-01-04T00:57:33Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  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.
  arXiv  Detail & Related papers  (2023-12-19T01:52:13Z)
• Communication-Efficient Federated Non-Linear Bandit Optimization [26.23638987873429]
  We propose a new algorithm, named Fed-GO-UCB, for federated bandit optimization with generic non-linear objective function. Under some mild conditions, we rigorously prove that Fed-GO-UCB is able to achieve sub-linear rate for both cumulative regret and communication cost.
  arXiv  Detail & Related papers  (2023-11-03T03:50:31Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  We study the smoothed online optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t in response to a quadratic hitting cost and an additional squared $ell$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management. We present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal performance.
  arXiv  Detail & Related papers  (2023-10-31T22:59:23Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  We resolve the min-max complexity of distributed convex optimization (up to a log factor) in the intermittent communication setting. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.
  arXiv  Detail & Related papers  (2021-02-02T16:18:29Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• $P^2$ Net: Augmented Parallel-Pyramid Net for Attention Guided Pose Estimation [69.25492391672064]
  We propose an augmented Parallel-Pyramid Net with feature refinement by dilated bottleneck and attention module. A parallel-pyramid structure is followed to compensate the information loss introduced by the network. Our method achieves the best performance on the challenging MSCOCO and MPII datasets.
  arXiv  Detail & Related papers  (2020-10-26T02:10:12Z)

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.