nips nips2008 nips2008-22 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthew Streeter, Daniel Golovin
Abstract: We present an algorithm for solving a broad class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities, according to some schedule. We assume that the fraction of jobs completed by a schedule is a monotone, submodular function of a set of pairs (v, τ ), where τ is the time invested in activity v. Under this assumption, our online algorithm performs near-optimally according to two natural metrics: (i) the fraction of jobs completed within time T , for some fixed deadline T > 0, and (ii) the average time required to complete each job. We evaluate our algorithm experimentally by using it to learn, online, a schedule for allocating CPU time among solvers entered in the 2007 SAT solver competition. 1
Reference: text
sentIndex sentText sentNum sentScore
1 com Abstract We present an algorithm for solving a broad class of online resource allocation problems. [sent-5, score-0.25]
2 Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities, according to some schedule. [sent-6, score-0.725]
3 We assume that the fraction of jobs completed by a schedule is a monotone, submodular function of a set of pairs (v, τ ), where τ is the time invested in activity v. [sent-7, score-1.041]
4 Under this assumption, our online algorithm performs near-optimally according to two natural metrics: (i) the fraction of jobs completed within time T , for some fixed deadline T > 0, and (ii) the average time required to complete each job. [sent-8, score-0.532]
5 We evaluate our algorithm experimentally by using it to learn, online, a schedule for allocating CPU time among solvers entered in the 2007 SAT solver competition. [sent-9, score-0.807]
6 1 Introduction This paper presents an algorithm for solving the following class of online resource allocation problems. [sent-10, score-0.25]
7 A job is a function f : S → [0, 1], where for any schedule S ∈ S, f (S) represents the proportion of some task that is accomplished by performing the sequence of actions S. [sent-15, score-0.89]
8 (submodularity) for any schedules S1 , S2 ∈ S and any action a ∈ V × R>0 , fa (S1 ⊕ S2 ) ≤ fa (S1 ), where we define fa (S) ≡ f (S ⊕ a ) − f (S). [sent-18, score-0.57]
9 The second objective is to minimize the cost of a schedule, which we define as ∞ 1−f S c (f, S) = t dt t=0 where S t is the schedule that results from truncating schedule S at time t. [sent-22, score-1.22]
10 Thus c (f, S) is the expected time we must wait before the desired event occurs if we execute actions according to the schedule S. [sent-33, score-0.73]
11 Let each activity v represent a randomized algorithm for solving some decision problem, and let the action (v, τ ) represent running the algorithm (with a fresh random seed) for time τ . [sent-36, score-0.328]
12 Fix some particular instance of the decision problem, and for any schedule S, let f (S) be the probability that one (or more) of the runs in the sequence S yields a solution to that instance. [sent-37, score-0.667]
13 So f (S T ) is (by definition) the probability that performing the runs in schedule S yields a solution to the problem instance in time ≤ T , while c (f, S) is the expected time that elapses before a solution is obtained. [sent-38, score-0.711]
14 The fact that f is submodular can be seen as follows. [sent-40, score-0.2]
15 For any schedule S and action a, fa (S) equals the probability that action a succeeds after every action in S has failed, which can also be written as (1 − f (S)) · f ( a ). [sent-41, score-1.05]
16 This, together with the monotonicity of f , implies that for any schedules S1 , S2 and any action a, we have fa (S1 ⊕ S2 ) = (1 − f (S1 ⊕ S2 )) · f ( a ) ≤ (1 − f (S1 )) · f ( a ) = fa (S1 ). [sent-42, score-0.454]
17 In the online setting, an arbitrary sequence f (1) , f (2) , . [sent-43, score-0.256]
18 , f (n) of jobs arrive one at a time, and we must finish each job (via some schedule) before moving on to the next job. [sent-46, score-0.363]
19 When selecting a schedule S (i) to use to finish job f (i) , we have knowledge of the previous jobs f (1) , f (2) , . [sent-47, score-0.934]
20 In this setting we aim to minimize regret, which measures the difference between the average cost (or average benefit) of the schedules produced by our online algorithm and that of the best single schedule (in hindsight) for the given sequence of jobs. [sent-51, score-0.96]
21 1 Problems that fit into this framework A number of previously-studied problems can be cast as the task of computing a schedule S that n 1 minimizes c (f, S), where f is of the form f (S) = n i=1 1 − (v,τ )∈S (1 − pi (v, τ )) . [sent-53, score-0.626]
22 This expression can be interpreted as follows: the job f consists of n subtasks, and pi (v, τ ) is the probability that investing time τ in activity v completes the ith subtask. [sent-54, score-0.322]
23 Assuming pi (v, τ ) is a non-decreasing function of τ for all i and v, it can be shown that any function f of this form is monotone and submodular. [sent-56, score-0.199]
24 The problem of maximizing f (S T ) is a slight generalization of the problem of maximizing a monotone submodular set function subject to a knapsack constraint [14, 20] (which in turn generalizes B UDGETED M AXIMUM C OVERAGE [12], which generalizes M AX k-C OVERAGE [16]). [sent-60, score-0.625]
25 The only difference between the two problems is that, in the latter problem, f (S) may only depend on the set of actions in the sequence S, and not on the order in which the actions appear. [sent-61, score-0.274]
26 An algorithm portfolio [9] is a schedule for interleaving the execution of multiple (randomized) algorithms and periodically restarting them with a fresh random seed. [sent-66, score-0.745]
27 In database query processing, one must extract all the records in a database that satisfy every predicate in a list of one or more predicates (the conjunction of predicates comprises the query). [sent-72, score-0.267]
28 To process the query, each record is evaluated against the predicates one at a time until the record either fails to satisfy some predicate (in which case it does not match the query) or all predicates have been examined. [sent-73, score-0.271]
29 Our work addresses the online version of this problem, which arises naturally in practice. [sent-78, score-0.218]
30 Many sensor placement problems can be optimally solved by maximizing a monotone submodular set function subject to a knapsack constraint [13], a special case of our benefit-maximization problem (see §1. [sent-84, score-0.514]
31 Our online algorithms could be used to select sensor placements when the same set of sensors is repeatedly deployed in an unknown or adversarial environment. [sent-86, score-0.293]
32 In the online setting we provide an online algorithm whose worst-case performance guarantees approach those of the offline greedy approximation algorithm asymptotically (as the number of jobs approaches infinity). [sent-91, score-0.839]
33 We then show how to modify our online algorithm for use in several different “bandit” feedback settings. [sent-92, score-0.34]
34 Several of these problems have been considered in the online setting. [sent-97, score-0.218]
35 [15] gave an online algorithm for P IPELINED S ET C OVER that is asymptotically O (log |V|)-competitive. [sent-99, score-0.323]
36 Our offline benefit-maximization problem generalizes the problem of maximizing a monotone submodular set function subject to a knapsack constraint. [sent-103, score-0.523]
37 To our knowledge, none of these problems have previously been studied in an online setting. [sent-105, score-0.218]
38 Note that our problem is quite different from online set covering problems (e. [sent-106, score-0.218]
39 In this paper we convert a specific greedy approximation algorithm into an online algorithm. [sent-109, score-0.35]
40 [10] gave a generic procedure for converting an α-approximation algorithm into an online algorithm that is asymptotically α-competitive. [sent-111, score-0.355]
41 [17] developed a no-regret algorithm for the online version of M AX k-C OVERAGE, and applied it to online ranking. [sent-114, score-0.468]
42 Our goal is to compute a schedule S that achieves one of two objectives, either minimizing the cost c (f S) or maximizing f (S) subject to the constraint (S) T . [sent-118, score-0.626]
43 We now consider an arbitrary schedule G, whose j th action is gj = (vj f(v j ). [sent-124, score-0.779]
44 , greedily appending actions to the schedule so as to maximize the resulting increase in f per unit time). [sent-129, score-0.75]
45 For any schedule S, any positive integer j, and any t > 0, f (S t ) f (Gj )+t (sj + j ). [sent-132, score-0.571]
46 For any schedule L + j=1 Ej j , where Ej 4 c (f S ). [sent-138, score-0.571]
47 Given a set of jobs f (1) f (2) f (n) , we can optimize the average schedule cost (or benefit) simply P 1 by applying our offline algorithm to the job f = n n f (i) (since any convex combination of jobs is a job). [sent-140, score-1.166]
48 i=1 2 4 4 Online Greedy Algorithm In the online setting we are fed, one at a time, a sequence f (1) , f (2) , . [sent-141, score-0.256]
49 Prior to receiving job f (i) , we must specify a schedule S (i) . [sent-145, score-0.734]
50 T Here for any schedule S and job f , we define cT (S, f ) = t=0 1 − f S t dt to be the value of c (S, f ) when the integral is truncated at time T . [sent-149, score-0.775]
51 Some form of truncation is necessary because c S (i) , f (i) could be infinite, and without bounding it we could not prove any finite bound on regret (our regret bounds will be stated as a function of T ). [sent-150, score-0.257]
52 Here we require e that for each i, E S (i) = T , where the expectation is over the online algorithm’s random bits. [sent-152, score-0.218]
53 That is, we allow the online algorithm to treat T as a budget in expectation, rather than a hard budget. [sent-153, score-0.25]
54 For simplicity, we consider the oblivious adversary model, in which the sequence of jobs is fixed in advance and does not change in response to the decisions made by our online algorithm. [sent-155, score-0.456]
55 We confine our attention to schedules that consist of actions that come from some finite set A, and assume that the actions in A have integer durations (i. [sent-156, score-0.337]
56 1 Unit-cost actions In the special case in which each action takes unit time (i. [sent-160, score-0.28]
57 , A ⊆ V × {1}), our online algorithm OGunit is very simple. [sent-162, score-0.25]
58 , ET , where T is the number of time steps for which our schedule is defined. [sent-166, score-0.612]
59 The intent is that each action-selection algorithm is a no-regret algorithm such as randomized weighted majority (WMR) [4], which selects actions so as to maximize payoffs associated with the actions. [sent-167, score-0.243]
60 Just before job f (i) arrives, each action-selection algorithm Et selects an action ai . [sent-168, score-0.354]
61 The schedule used by OGunit on job f (i) is t (i) (i) (i) i i i S = a1 , a2 , . [sent-169, score-0.734]
62 The payoff that Et associates with action a is fa S t−1 . [sent-173, score-0.295]
63 Algorithm OGunit has E [Rbenefit ] O T T n = O T n ln |A| and E [Rcost ] = ln |A| in the worst case, when WMR [4] is the subroutine action-selection algorithm. [sent-175, score-0.245]
64 We will view OGunit as producing an approximate version of the offline greedy schedule for n 1 the job f = n i=1 f (i) . [sent-177, score-0.834]
65 First, view the sequence of actions selected by Et as a single meta-action at , and extend the domain of each f (i) to include the meta-actions by defining f (i) (S ⊕ at ) = ˜ ˜ f (i) (S ⊕ ai ) for all S ∈ S (note each f (i) remains monotone and submodular). [sent-178, score-0.338]
66 Thus, the online t ˜ algorithm produces a single schedule S = a1 , a2 , . [sent-179, score-0.821]
67 By construction, rt = maxa∈A fa S t−1 − fa S t−1 . [sent-184, score-0.288]
68 ˜ t Thus OGunit behaves exactly like the greedy schedule G for the function f , with t = rt . [sent-185, score-0.727]
69 WMR has worst-case expected regret 1 O n Gmax ln |A| , where Gmax is the maximum sum of payoffs payoff for any single action. [sent-189, score-0.289]
70 3 Because each payoff is at most 1 and there are n rounds, Gmax ≤ n, so a trivial bound is E [R] = O T 1 n ln |A| . [sent-190, score-0.194]
71 2 From unit-cost actions to arbitrary actions In this section we generalize the online greedy algorithm presented in the previous section to accommodate actions with arbitrary durations. [sent-194, score-0.704]
72 On each round i, OG constructs a schedule S (i) as follows: for t = 1, 2, . [sent-199, score-0.571]
73 , L, it uses Et to choose an action (i) 1 ai = (v, τ ) ∈ A, and appends this action to S (i) with probability τ . [sent-202, score-0.28]
74 Let St denote the schedule t (i) that results from the first t steps of this process (so St contains between 0 and t actions). [sent-203, score-0.571]
75 The (i) 1 payoff that Et associates with an action a = (v, τ ) equals τ fa (St−1 ) (i. [sent-204, score-0.295]
76 Thus, the online ˜ t t ˜ algorithm produces a single schedule S = a1 , a2 , . [sent-209, score-0.821]
77 For the purposes of analysis, we will imagine that each meta-action at always takes unit time ˜ (whereas in fact, at takes unit time per job in expectation). [sent-214, score-0.245]
78 Thus S can be viewed as a version of the ˜ ˜ ˜ 1 ˜ ˜ − fat (St−1 ) , where we greedy schedule from §3, with t = max(v,τ )∈A τ f(v,τ ) (St−1 ) ˜ are using the assumption that at takes unit time. [sent-220, score-0.671]
79 Because each f (i) is monotone and submodular, f is monotone and submodular as well, so the greedy schedule’s approximation guarantees apply to f . [sent-226, score-0.588]
80 One additional complication is that S (i) is now a random variable, whereas in the definition of Rcost the cost of a schedule is always calculated up to time T . [sent-239, score-0.612]
81 Algorithm OG, run with input L = T ln n, has E [Rcost ] = O(T ln n · E [R] + 3 In particular, E [Rcost ] = O (ln n) 2 T selection algorithm. [sent-244, score-0.202]
82 3 Dealing with limited feedback Thus far we have assumed that, after specifying a schedule S (i) , the online algorithm receives complete access to the job f (i) . [sent-247, score-1.074]
83 The priced and partially transparent feedback models arise naturally in the case where action (v, τ ) represents running a deterministic algorithm v for τ time units, and f (S) = 1 if some action in S yields a solution to some particular problem instance, and f (S) = 0 otherwise. [sent-252, score-0.54]
84 If we execute a schedule S and halt as soon as some action yields a solution, we obtain exactly the information that is revealed in the partially transparent model. [sent-253, score-0.742]
85 Alternatively, running each algorithm v until it returns a solution would completely reveal the function f (i) , but incurs a computational cost, as reflected in the priced feedback model. [sent-254, score-0.207]
86 This technique has been used in a number of online algorithms (e. [sent-257, score-0.218]
87 Our proofs have the same high-level structure as that of the lower bound given in [4], in that we define a distribution over jobs that allows any online algorithm’s expected performance to be easily bounded, and then prove a bound on the expected performance of the best schedule in hindsight. [sent-262, score-1.059]
88 Then any online algorithm has worst-case expected regret Ω (X) n T (resp. [sent-266, score-0.346]
89 The competition consists of running each submitted solver on a number of benchmark instances, with a per-instance time limit. [sent-272, score-0.226]
90 We evaluated the online algorithm OG by using it to combine solvers from the 2007 SAT solver competition. [sent-274, score-0.379]
91 To do so, we used data available on the competition web site to construct a matrix X, where Xi,j is the time that the j th solver required on the ith benchmark instance. [sent-275, score-0.199]
92 We used this data to determine whether or not a given schedule would solve an instance within the time limit T (schedule S solves instance i if and only if, for some j, S T contains an action (hj , τ ) with τ ≥ Xi,j ). [sent-276, score-0.789]
93 As illustrated in Example 1, the task of maximizing the number of instances solved within the time limit, in an online setting in which a sequence of instances must be solved one at a time, is an instance of our online problem (under the benefit-maximization objective). [sent-277, score-0.68]
94 Within each instance category, we compared OG to the offline greedy schedule, to the individual solver that solved the most instances within the time limit, and to a schedule that ran each solver in parallel at equal strength. [sent-278, score-0.933]
95 For these experiments, we ran OG in the full-information feedback model, after finding that the number of benchmark instances was too small for OG to be effective in the limited feedback models. [sent-279, score-0.25]
96 In each category, the offline greedy schedule and the online greedy algorithm outperform all solvers entered in the competition as well as the na¨ve parallel schedule. [sent-281, score-1.161]
97 Category Industrial Random Hand-crafted Offline greedy 147 350 114 Online greedy 149 347 107 Parallel schedule 132 302 95 Top solver 139 257 98 References [1] Noga Alon, Baruch Awerbuch, and Yossi Azar. [sent-283, score-0.847]
98 A note on the budgeted maximization of submodular functions. [sent-330, score-0.234]
99 An analysis of approximations for maximizing submodular set functions. [sent-345, score-0.255]
100 A note on maximizing a submodular set function subject to a knapsack constraint. [sent-358, score-0.332]
wordName wordTfidf (topN-words)
[('schedule', 0.571), ('online', 0.218), ('rbene', 0.211), ('jobs', 0.2), ('submodular', 0.2), ('og', 0.192), ('rcost', 0.173), ('job', 0.163), ('ogunit', 0.154), ('monotone', 0.144), ('action', 0.121), ('ine', 0.119), ('actions', 0.118), ('fa', 0.116), ('predicates', 0.115), ('overage', 0.101), ('schedules', 0.101), ('ln', 0.101), ('greedy', 0.1), ('wmr', 0.096), ('regret', 0.096), ('gmax', 0.092), ('feedback', 0.09), ('gj', 0.087), ('ipelined', 0.077), ('knapsack', 0.077), ('solver', 0.076), ('munagala', 0.067), ('et', 0.062), ('portfolio', 0.062), ('babu', 0.058), ('priced', 0.058), ('streeter', 0.058), ('payoff', 0.058), ('rt', 0.056), ('pi', 0.055), ('maximizing', 0.055), ('sat', 0.054), ('solvers', 0.053), ('competition', 0.053), ('transparent', 0.05), ('ax', 0.048), ('generalizes', 0.047), ('fresh', 0.046), ('um', 0.046), ('bene', 0.045), ('subroutine', 0.043), ('instances', 0.041), ('time', 0.041), ('st', 0.04), ('asymptotically', 0.039), ('aximum', 0.038), ('carlos', 0.038), ('golovin', 0.038), ('haim', 0.038), ('kamesh', 0.038), ('kaplan', 0.038), ('rajeev', 0.038), ('shivnath', 0.038), ('udgeted', 0.038), ('uriel', 0.038), ('sensor', 0.038), ('ai', 0.038), ('sequence', 0.038), ('ct', 0.037), ('sensors', 0.037), ('query', 0.037), ('objective', 0.037), ('theorem', 0.036), ('daniel', 0.036), ('bound', 0.035), ('gave', 0.034), ('pipelined', 0.034), ('matthew', 0.034), ('entered', 0.034), ('appending', 0.034), ('budgeted', 0.034), ('investing', 0.034), ('krause', 0.034), ('mins', 0.034), ('motwani', 0.034), ('payoffs', 0.034), ('restarting', 0.034), ('stoc', 0.034), ('submodularity', 0.034), ('algorithm', 0.032), ('nish', 0.031), ('seed', 0.031), ('yoav', 0.031), ('runs', 0.03), ('bounds', 0.03), ('activity', 0.029), ('benchmark', 0.029), ('nicol', 0.029), ('subtasks', 0.029), ('instance', 0.028), ('running', 0.027), ('sj', 0.027), ('maximize', 0.027), ('industrial', 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999976 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions
Author: Matthew Streeter, Daniel Golovin
Abstract: We present an algorithm for solving a broad class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities, according to some schedule. We assume that the fraction of jobs completed by a schedule is a monotone, submodular function of a set of pairs (v, τ ), where τ is the time invested in activity v. Under this assumption, our online algorithm performs near-optimally according to two natural metrics: (i) the fraction of jobs completed within time T , for some fixed deadline T > 0, and (ii) the average time required to complete each job. We evaluate our algorithm experimentally by using it to learn, online, a schedule for allocating CPU time among solvers entered in the 2007 SAT solver competition. 1
2 0.11334088 164 nips-2008-On the Generalization Ability of Online Strongly Convex Programming Algorithms
Author: Sham M. Kakade, Ambuj Tewari
Abstract: This paper examines the generalization properties of online convex programming algorithms when the loss function is Lipschitz and strongly convex. Our main result is a sharp bound, that holds with high probability, on the excess risk of the output of an online algorithm in terms of the average regret. This allows one to use recent algorithms with logarithmic cumulative regret guarantees to achieve fast convergence rates for the excess risk with high probability. As a corollary, we characterize the convergence rate of P EGASOS (with high probability), a recently proposed method for solving the SVM optimization problem. 1
3 0.10739115 88 nips-2008-From Online to Batch Learning with Cutoff-Averaging
Author: Ofer Dekel
Abstract: We present cutoff averaging, a technique for converting any conservative online learning algorithm into a batch learning algorithm. Most online-to-batch conversion techniques work well with certain types of online learning algorithms and not with others, whereas cutoff averaging explicitly tries to adapt to the characteristics of the online algorithm being converted. An attractive property of our technique is that it preserves the efficiency of the original online algorithm, making it appropriate for large-scale learning problems. We provide a statistical analysis of our technique and back our theoretical claims with experimental results. 1
4 0.099834003 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions
Author: Giovanni Cavallanti, Nicolò Cesa-bianchi, Claudio Gentile
Abstract: We provide a new analysis of an efficient margin-based algorithm for selective sampling in classification problems. Using the so-called Tsybakov low noise condition to parametrize the instance distribution, we show bounds on the convergence rate to the Bayes risk of both the fully supervised and the selective sampling versions of the basic algorithm. Our analysis reveals that, excluding logarithmic factors, the average risk of the selective sampler converges to the Bayes risk at rate N −(1+α)(2+α)/2(3+α) where N denotes the number of √ queried labels, and α > 0 is the exponent in the low noise condition. For all α > 3 − 1 ≈ 0.73 this convergence rate is asymptotically faster than the rate N −(1+α)/(2+α) achieved by the fully supervised version of the same classifier, which queries all labels, and for α → ∞ the two rates exhibit an exponential gap. Experiments on textual data reveal that simple variants of the proposed selective sampler perform much better than popular and similarly efficient competitors. 1
5 0.090496756 214 nips-2008-Sparse Online Learning via Truncated Gradient
Author: John Langford, Lihong Li, Tong Zhang
Abstract: We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss. This method has several essential properties. First, the degree of sparsity is continuous—a parameter controls the rate of sparsification from no sparsification to total sparsification. Second, the approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1 -regularization method in the batch setting. We prove small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. Finally, the approach works well empirically. We apply it to several datasets and find for datasets with large numbers of features, substantial sparsity is discoverable. 1
6 0.086412169 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization
7 0.083982036 170 nips-2008-Online Optimization in X-Armed Bandits
8 0.07804177 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning
9 0.076976165 168 nips-2008-Online Metric Learning and Fast Similarity Search
10 0.068606973 140 nips-2008-Mortal Multi-Armed Bandits
11 0.061982226 73 nips-2008-Estimating Robust Query Models with Convex Optimization
12 0.060844917 161 nips-2008-On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization
13 0.060528301 182 nips-2008-Posterior Consistency of the Silverman g-prior in Bayesian Model Choice
14 0.058169395 87 nips-2008-Fitted Q-iteration by Advantage Weighted Regression
15 0.055487398 131 nips-2008-MDPs with Non-Deterministic Policies
16 0.052693781 1 nips-2008-A Convergent $O(n)$ Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation
17 0.052452996 17 nips-2008-Algorithms for Infinitely Many-Armed Bandits
18 0.051482767 171 nips-2008-Online Prediction on Large Diameter Graphs
19 0.050717756 128 nips-2008-Look Ma, No Hands: Analyzing the Monotonic Feature Abstraction for Text Classification
20 0.046889476 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning
topicId topicWeight
[(0, -0.146), (1, 0.099), (2, -0.108), (3, -0.038), (4, -0.108), (5, -0.006), (6, -0.027), (7, -0.003), (8, 0.01), (9, -0.019), (10, -0.03), (11, 0.062), (12, 0.007), (13, 0.056), (14, 0.113), (15, -0.097), (16, -0.041), (17, 0.014), (18, -0.001), (19, 0.004), (20, -0.02), (21, 0.007), (22, 0.052), (23, 0.012), (24, -0.08), (25, -0.073), (26, 0.069), (27, -0.002), (28, 0.056), (29, 0.041), (30, -0.037), (31, 0.038), (32, 0.058), (33, -0.048), (34, -0.06), (35, 0.008), (36, 0.043), (37, 0.076), (38, 0.103), (39, 0.038), (40, -0.017), (41, 0.016), (42, -0.023), (43, 0.136), (44, -0.081), (45, -0.06), (46, -0.145), (47, 0.043), (48, 0.035), (49, 0.045)]
simIndex simValue paperId paperTitle
same-paper 1 0.95074034 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions
Author: Matthew Streeter, Daniel Golovin
Abstract: We present an algorithm for solving a broad class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities, according to some schedule. We assume that the fraction of jobs completed by a schedule is a monotone, submodular function of a set of pairs (v, τ ), where τ is the time invested in activity v. Under this assumption, our online algorithm performs near-optimally according to two natural metrics: (i) the fraction of jobs completed within time T , for some fixed deadline T > 0, and (ii) the average time required to complete each job. We evaluate our algorithm experimentally by using it to learn, online, a schedule for allocating CPU time among solvers entered in the 2007 SAT solver competition. 1
2 0.64608055 88 nips-2008-From Online to Batch Learning with Cutoff-Averaging
Author: Ofer Dekel
Abstract: We present cutoff averaging, a technique for converting any conservative online learning algorithm into a batch learning algorithm. Most online-to-batch conversion techniques work well with certain types of online learning algorithms and not with others, whereas cutoff averaging explicitly tries to adapt to the characteristics of the online algorithm being converted. An attractive property of our technique is that it preserves the efficiency of the original online algorithm, making it appropriate for large-scale learning problems. We provide a statistical analysis of our technique and back our theoretical claims with experimental results. 1
3 0.57740432 164 nips-2008-On the Generalization Ability of Online Strongly Convex Programming Algorithms
Author: Sham M. Kakade, Ambuj Tewari
Abstract: This paper examines the generalization properties of online convex programming algorithms when the loss function is Lipschitz and strongly convex. Our main result is a sharp bound, that holds with high probability, on the excess risk of the output of an online algorithm in terms of the average regret. This allows one to use recent algorithms with logarithmic cumulative regret guarantees to achieve fast convergence rates for the excess risk with high probability. As a corollary, we characterize the convergence rate of P EGASOS (with high probability), a recently proposed method for solving the SVM optimization problem. 1
4 0.57641155 168 nips-2008-Online Metric Learning and Fast Similarity Search
Author: Prateek Jain, Brian Kulis, Inderjit S. Dhillon, Kristen Grauman
Abstract: Metric learning algorithms can provide useful distance functions for a variety of domains, and recent work has shown good accuracy for problems where the learner can access all distance constraints at once. However, in many real applications, constraints are only available incrementally, thus necessitating methods that can perform online updates to the learned metric. Existing online algorithms offer bounds on worst-case performance, but typically do not perform well in practice as compared to their offline counterparts. We present a new online metric learning algorithm that updates a learned Mahalanobis metric based on LogDet regularization and gradient descent. We prove theoretical worst-case performance bounds, and empirically compare the proposed method against existing online metric learning algorithms. To further boost the practicality of our approach, we develop an online locality-sensitive hashing scheme which leads to efficient updates to data structures used for fast approximate similarity search. We demonstrate our algorithm on multiple datasets and show that it outperforms relevant baselines.
5 0.54084575 214 nips-2008-Sparse Online Learning via Truncated Gradient
Author: John Langford, Lihong Li, Tong Zhang
Abstract: We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss. This method has several essential properties. First, the degree of sparsity is continuous—a parameter controls the rate of sparsification from no sparsification to total sparsification. Second, the approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1 -regularization method in the batch setting. We prove small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. Finally, the approach works well empirically. We apply it to several datasets and find for datasets with large numbers of features, substantial sparsity is discoverable. 1
6 0.53056335 169 nips-2008-Online Models for Content Optimization
7 0.50933623 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions
8 0.49892452 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization
9 0.47884002 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning
10 0.45758858 170 nips-2008-Online Optimization in X-Armed Bandits
11 0.45306107 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning
12 0.45273787 182 nips-2008-Posterior Consistency of the Silverman g-prior in Bayesian Model Choice
13 0.34966493 144 nips-2008-Multi-resolution Exploration in Continuous Spaces
14 0.34338996 73 nips-2008-Estimating Robust Query Models with Convex Optimization
15 0.340969 29 nips-2008-Automatic online tuning for fast Gaussian summation
16 0.33126348 211 nips-2008-Simple Local Models for Complex Dynamical Systems
17 0.33121973 1 nips-2008-A Convergent $O(n)$ Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation
18 0.32938278 39 nips-2008-Bounding Performance Loss in Approximate MDP Homomorphisms
19 0.3285982 110 nips-2008-Kernel-ARMA for Hand Tracking and Brain-Machine interfacing During 3D Motor Control
20 0.32585442 171 nips-2008-Online Prediction on Large Diameter Graphs
topicId topicWeight
[(4, 0.026), (6, 0.105), (7, 0.041), (12, 0.043), (28, 0.15), (36, 0.342), (57, 0.052), (59, 0.011), (63, 0.037), (71, 0.025), (77, 0.037), (83, 0.028), (92, 0.011)]
simIndex simValue paperId paperTitle
same-paper 1 0.74152792 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions
Author: Matthew Streeter, Daniel Golovin
Abstract: We present an algorithm for solving a broad class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities, according to some schedule. We assume that the fraction of jobs completed by a schedule is a monotone, submodular function of a set of pairs (v, τ ), where τ is the time invested in activity v. Under this assumption, our online algorithm performs near-optimally according to two natural metrics: (i) the fraction of jobs completed within time T , for some fixed deadline T > 0, and (ii) the average time required to complete each job. We evaluate our algorithm experimentally by using it to learn, online, a schedule for allocating CPU time among solvers entered in the 2007 SAT solver competition. 1
2 0.5089376 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization
Author: Shai Shalev-shwartz, Sham M. Kakade
Abstract: We describe a primal-dual framework for the design and analysis of online strongly convex optimization algorithms. Our framework yields the tightest known logarithmic regret bounds for Follow-The-Leader and for the gradient descent algorithm proposed in Hazan et al. [2006]. We then show that one can interpolate between these two extreme cases. In particular, we derive a new algorithm that shares the computational simplicity of gradient descent but achieves lower regret in many practical situations. Finally, we further extend our framework for generalized strongly convex functions. 1
3 0.50420362 164 nips-2008-On the Generalization Ability of Online Strongly Convex Programming Algorithms
Author: Sham M. Kakade, Ambuj Tewari
Abstract: This paper examines the generalization properties of online convex programming algorithms when the loss function is Lipschitz and strongly convex. Our main result is a sharp bound, that holds with high probability, on the excess risk of the output of an online algorithm in terms of the average regret. This allows one to use recent algorithms with logarithmic cumulative regret guarantees to achieve fast convergence rates for the excess risk with high probability. As a corollary, we characterize the convergence rate of P EGASOS (with high probability), a recently proposed method for solving the SVM optimization problem. 1
4 0.50228965 62 nips-2008-Differentiable Sparse Coding
Author: J. A. Bagnell, David M. Bradley
Abstract: Prior work has shown that features which appear to be biologically plausible as well as empirically useful can be found by sparse coding with a prior such as a laplacian (L1 ) that promotes sparsity. We show how smoother priors can preserve the benefits of these sparse priors while adding stability to the Maximum A-Posteriori (MAP) estimate that makes it more useful for prediction problems. Additionally, we show how to calculate the derivative of the MAP estimate efficiently with implicit differentiation. One prior that can be differentiated this way is KL-regularization. We demonstrate its effectiveness on a wide variety of applications, and find that online optimization of the parameters of the KL-regularized model can significantly improve prediction performance. 1
5 0.50134593 202 nips-2008-Robust Regression and Lasso
Author: Huan Xu, Constantine Caramanis, Shie Mannor
Abstract: We consider robust least-squares regression with feature-wise disturbance. We show that this formulation leads to tractable convex optimization problems, and we exhibit a particular uncertainty set for which the robust problem is equivalent to 1 regularized regression (Lasso). This provides an interpretation of Lasso from a robust optimization perspective. We generalize this robust formulation to consider more general uncertainty sets, which all lead to tractable convex optimization problems. Therefore, we provide a new methodology for designing regression algorithms, which generalize known formulations. The advantage is that robustness to disturbance is a physical property that can be exploited: in addition to obtaining new formulations, we use it directly to show sparsity properties of Lasso, as well as to prove a general consistency result for robust regression problems, including Lasso, from a unified robustness perspective. 1
6 0.50091207 96 nips-2008-Hebbian Learning of Bayes Optimal Decisions
7 0.50070131 162 nips-2008-On the Design of Loss Functions for Classification: theory, robustness to outliers, and SavageBoost
8 0.50015098 75 nips-2008-Estimating vector fields using sparse basis field expansions
9 0.49998283 85 nips-2008-Fast Rates for Regularized Objectives
10 0.4979457 88 nips-2008-From Online to Batch Learning with Cutoff-Averaging
11 0.49509156 210 nips-2008-Signal-to-Noise Ratio Analysis of Policy Gradient Algorithms
12 0.49167761 245 nips-2008-Unlabeled data: Now it helps, now it doesn't
13 0.49118799 149 nips-2008-Near-minimax recursive density estimation on the binary hypercube
14 0.49113333 189 nips-2008-Rademacher Complexity Bounds for Non-I.I.D. Processes
15 0.49093065 199 nips-2008-Risk Bounds for Randomized Sample Compressed Classifiers
16 0.49084818 195 nips-2008-Regularized Policy Iteration
17 0.48963696 14 nips-2008-Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models
18 0.48943684 79 nips-2008-Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
19 0.48922339 178 nips-2008-Performance analysis for L\ 2 kernel classification
20 0.48913637 196 nips-2008-Relative Margin Machines