Distributed Online Non-convex Optimization with Composite Regret
- URL: http://arxiv.org/abs/2209.10105v1
- Date: Wed, 21 Sep 2022 04:16:33 GMT
- Title: Distributed Online Non-convex Optimization with Composite Regret
- Authors: Zhanhong Jiang, Aditya Balu, Xian Yeow Lee, Young M. Lee, Chinmay
Hegde, Soumik Sarkar
- Abstract summary: We propose a novel composite regret with a new network regret for distributed online general bounds losses.
To our knowledge, is the first regret bound for distributed online nonlinear learning.
- Score: 31.53784277195043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Regret has been widely adopted as the metric of choice for evaluating the
performance of online optimization algorithms for distributed, multi-agent
systems. However, data/model variations associated with agents can
significantly impact decisions and requires consensus among agents. Moreover,
most existing works have focused on developing approaches for (either strongly
or non-strongly) convex losses, and very few results have been obtained
regarding regret bounds in distributed online optimization for general
non-convex losses. To address these two issues, we propose a novel composite
regret with a new network regret-based metric to evaluate distributed online
optimization algorithms. We concretely define static and dynamic forms of the
composite regret. By leveraging the dynamic form of our composite regret, we
develop a consensus-based online normalized gradient (CONGD) approach for
pseudo-convex losses, and it provably shows a sublinear behavior relating to a
regularity term for the path variation of the optimizer. For general non-convex
losses, we first shed light on the regret for the setting of distributed online
non-convex learning based on recent advances such that no deterministic
algorithm can achieve the sublinear regret. We then develop the distributed
online non-convex optimization with composite regret (DINOCO) without access to
the gradients, depending on an offline optimization oracle. DINOCO is shown to
achieve sublinear regret; to our knowledge, this is the first regret bound for
general distributed online non-convex learning.
Related papers
- LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner.
We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
arXiv Detail & Related papers (2024-08-12T17:08:31Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
We study unconstrained Online Linear Optimization with Lipschitz losses.
Motivated by the pursuit of instance optimality, we propose a new algorithm.
Central to these results is a continuous time approach to online learning.
arXiv Detail & Related papers (2023-09-27T21:54:52Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$.
Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
arXiv Detail & Related papers (2023-09-16T07:30:12Z) - Optimal Regularized Online Allocation by Adaptive Re-Solving [16.873430173722994]
This paper introduces a dual-based algorithm framework for solving the regularized online resource allocation problems.
Under a strategy of adaptively updating the resource constraints, the proposed framework only requests approximate solutions to the empirical dual problems up to a certain accuracy.
Surprisingly, a delicate analysis of the dual objective function enables us to eliminate the notorious log-log factor in regret bound.
arXiv Detail & Related papers (2022-09-01T12:23:26Z) - Provably Efficient Reinforcement Learning for Online Adaptive Influence
Maximization [53.11458949694947]
We consider an adaptive version of content-dependent online influence problem where seed nodes are sequentially activated based on realtime feedback.
Our algorithm maintains a network model estimate and selects seed adaptively, exploring the social network while improving the optimal policy optimistically.
arXiv Detail & Related papers (2022-06-29T18:17:28Z) - 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) - Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems [1.6709415233613623]
This paper proposes a novel approach to construct data-driven online solutions to optimization problems (P) subject to a class of distributionally uncertain dynamical systems.
The introduced framework allows for the simultaneous learning of distributional system uncertainty via a parameterized, control-dependent ambiguity set.
We also introduce an online version of Nesterov's accelerated-gradient algorithm, and analyze its performance to solve this class of problems via dissipativity theory.
arXiv Detail & Related papers (2021-02-18T01:49:06Z) - Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
In online learning an algorithm plays against an environment with losses possibly picked by an adversary at each round.
We introduce optimism and adaptive stepsizes to Lagrangian hedging, a class of online algorithms that includes regret-matching, and hedge.
arXiv Detail & Related papers (2021-01-23T23:32:40Z) - Regret minimization in stochastic non-convex learning via a
proximal-gradient approach [80.59047515124198]
Motivated by applications in machine learning and operations, we regret with first-order oracle feedback minimization online constrained problems.
We develop a new prox-grad with guarantees proximal complexity reduction techniques.
arXiv Detail & Related papers (2020-10-13T09:22:21Z) - Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
We propose novel online algorithms that are able to minimize the dynamic regret and adaptive regret simultaneously.
Our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.
arXiv Detail & Related papers (2020-02-06T03:32:37Z)
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.