Fast Learning for Renewal Optimization in Online Task Scheduling
- URL: http://arxiv.org/abs/2007.09532v2
- Date: Sat, 29 May 2021 03:05:25 GMT
- Title: Fast Learning for Renewal Optimization in Online Task Scheduling
- Authors: Michael J. Neely
- Abstract summary: This paper considers online optimization of a renewal-reward system.
The probability distribution for the task type vector is unknown.
The proposed algorithm uses an auxiliary variable that is updated according to a classic Robbins-Monro iteration.
- Score: 18.935043109084543
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers online optimization of a renewal-reward system. A
controller performs a sequence of tasks back-to-back. Each task has a random
vector of parameters, called the task type vector, that affects the task
processing options and also affects the resulting reward and time duration of
the task. The probability distribution for the task type vector is unknown and
the controller must learn to make efficient decisions so that time average
reward converges to optimality. Prior work on such renewal optimization
problems leaves open the question of optimal convergence time. This paper
develops an algorithm with an optimality gap that decays like $O(1/\sqrt{k})$,
where $k$ is the number of tasks processed. The same algorithm is shown to have
faster $O(\log(k)/k)$ performance when the system satisfies a strong concavity
property. The proposed algorithm uses an auxiliary variable that is updated
according to a classic Robbins-Monro iteration. It makes online scheduling
decisions at the start of each renewal frame based on this variable and on the
observed task type. A matching converse is obtained for the strongly concave
case by constructing an example system for which all algorithms have
performance at best $\Omega(\log(k)/k)$. A matching $\Omega(1/\sqrt{k})$
converse is also shown for the general case without strong concavity.
Related papers
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.
We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.
Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
arXiv Detail & Related papers (2025-02-07T15:57:56Z) - Algorithm Design for Continual Learning in IoT Networks [16.35495567193046]
Continual learning (CL) is a new online learning technique over sequentially generated streaming data from different tasks.
In practical IoT networks, an autonomous vehicle to sample data and learn different tasks can route and alter the order of task pattern.
arXiv Detail & Related papers (2024-12-22T02:36:09Z) - Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
We show that a bandit online learning algorithm can select parameters for a sequence of instances such that the overall cost approaches that of the best fixed $omega$ as the sequence length increases.
Our work provides the first learning-theoretic treatment of high-precision linear system solvers and the first end-to-end guarantees for data-driven scientific computing.
arXiv Detail & Related papers (2023-10-03T17:51:42Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
We introduce two oblivious mirror descent algorithms based on a complementary composite setting.
Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function.
We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
arXiv Detail & Related papers (2023-06-30T08:34:29Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport.
We propose an accelerated primal-dual mirror descent algorithm with variance reduction.
Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $widetildeO(n2/epsilon)$ for solving OT.
arXiv Detail & Related papers (2023-01-23T19:13:25Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
We investigate the sample complexity of learning the optimal arm for multi-task bandit problems.
Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor)
We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as $H(Glog(delta_G)+ Xlog(delta_H))$, with $X,G,H$ being, respectively, the number of tasks, representations and predictors.
arXiv Detail & Related papers (2022-11-28T08:40:12Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning.
Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system.
The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
arXiv Detail & Related papers (2022-06-14T08:14:14Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
We consider optimization with delayed gradients where, at each time stept$, the algorithm makes an update using a stale computation - d_t$ for arbitrary delay $d_t gradient.
Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.
arXiv Detail & Related papers (2021-06-22T15:50:45Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate.
We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
arXiv Detail & Related papers (2020-12-17T04:56:51Z)
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.