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
- Data Classification With Multiprocessing [6.513930657238705]
Python multiprocessing is used to test this hypothesis with different classification algorithms.
We conclude that ensembling improves accuracy and multiprocessing reduces execution time for selected algorithms.
arXiv Detail & Related papers (2023-12-23T03:42:13Z) - 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) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations.
This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation.
We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
arXiv Detail & Related papers (2021-05-10T13:07:44Z) - 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.