Algorithm selection is typically based on models of algorithm performance, learned during a separate offline training sequence, which can be prohibitively expensive. In recent work, we adopted an online approach, in which a performance model is iteratively updated and used to guide selection on a sequence of problem instances. The resulting exploration-exploitation trade-off was represented as a bandit problem with expert advice, using an existing solver for this game, but this required the setting of an arbitrary bound on algorithm runtimes, thus invalidating the optimal regret of the solver. In this paper, we propose a simpler framework for representing algorithm selection as a bandit problem, with partial information, and an unknown bound on losses. We adapt an existing solver to this game, proving a bound on its expected regret, which holds also for the resulting algorithm selection technique. We present preliminary experiments with a set of SAT solvers on a mixed SAT-UNSAT benchmark.
Low-knowledge'' oblivious approaches can be found in @cite_12 @cite_33 , in which various simple indicators of current solution improvement are used for algorithm selection, in order to achieve the best solution quality within a given time contract. In @cite_33 , the selection process is dynamic: machine time shares are based on a recency-weighted average of performance improvements. We adopted a similar approach in @cite_8 , where we considered algorithms with a scalar state, that had to reach a target value. The time to solution was estimated based on a shifting-window linear extrapolation of the learning curves.
@cite_33 @cite_12 @cite_8
1485083952 2068852191 1988351624 2042997796
We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance. When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(logn loglogn) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee. We consider the makespan-minimization problem on unrelated machines in the context of algorithmic mechanism design. No truthful mechanisms with non-trivial approximation guarantees are known for this multidimensional domain. We study a well-motivated special case (also a multidimensional domain), where the processing time of a job on each machine is either "low" or "high." We give a general technique to convert any c-approximation algorithm (in a black-box fashion) to a 3c-approximation truthful-in-expectation mechanism. Our construction uses fractional truthful mechanisms as a building block, and builds upon a technique of Lavi and Swamy [Lavi, R., Swamy, C., 2005. Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th FOCS, pp. 595-604]. When all jobs have identical low and high values, we devise a deterministic 2-approximation truthful mechanism. The chief novelty of our results is that we do not utilize explicit price definitions to prove truthfulness. Instead we design algorithms that satisfy cycle monotonicity [Rochet, J., 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. J. Math. Econ. 16, 191-200], a necessary and sufficient condition for truthfulness in multidimensional settings; this is the first work that leverages this characterization. We discuss a new robust convergence analysis of the well-known subspace iteration algorithm for computing the dominant singular vectors of a matrix, also known as simultaneous iteration or power method. The result characterizes the convergence behavior of the algorithm when a large amount noise is introduced after each matrix-vector multiplication. While interesting in its own right, the main motivation comes from the problem of privacy-preserving spectral analysis where noise is added in order to achieve the privacy guarantee known as differential privacy. This result leads to nearly tight worst-case bounds for the problem of computing a differentially private low-rank approximation in the spectral norm. Our results extend to privacy-preserving principal component analysis. We obtain improvements for several variants of differential privacy that have been considered. The running time of our algorithm is nearly linear in the input sparsity leading to strong improvements in running time over previous work. Complementing our worst-case bounds, we show that the error dependence of our algorithm on the matrix dimension can be replaced by a tight dependence on the coherence of the matrix. This parameter is always bounded by the matrix dimension but often much smaller. Indeed, the assumption of low coherence is essential in several machine learning and signal processing applications. We study the completion time of broadcast operations on static ad hoc wireless networks in presence of unpredictable and dynamical faults.Concerning oblivious fault-tolerant distributed protocols, we provide an Ω(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D min n, Δ log n ) completion time on any network of maximum in-degree Δ.Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an Ω(Dn) lower bound when D = Θ(√n). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time.