Arrow Research search

Author name cluster

Wesley Pegden

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
1 author row

Possible papers

5

UAI Conference 2020 Conference Paper

Semi-bandit Optimization in the Dispersed Setting

  • Travis Dick
  • Wesley Pegden
  • Maria-Florina Balcan

The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good performance on example instances from the application domain. In the online setting, we must choose algorithm parameters for each instance as they arrive, and our goal is to be competitive with the best fixed algorithm in hindsight.There are two major challenges in online data-driven algorithm design. First, it can be computationally expensive to evaluate the loss functions that map algorithm parameters to performance, which often require the learner to run a combinatorial algorithm to measure its performance. Second, the losses can be extremely volatile and have sharp discontinuities. However, we show that in many applications, evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms, essentially for free. We develop online optimization algorithms capable of using this kind of extra information by working in the semi-bandit feedback setting. Our algorithms achieve regret bounds that are essentially as good as algorithms under full-information feedback and are significantly more computationally efficient. We apply our semi-bandit results to obtain the first provable guarantees for data-driven algorithm design for linkage-based clustering and we improve the best regret bounds for designing greedy knapsack algorithms.

Details

SODA Conference 2019 Conference Paper

On the rank of a random binary matrix

  • Colin Cooper
  • Alan M. Frieze
  • Wesley Pegden

We study the rank of a random n × m matrix A n, m; k with entries from GF (2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all ( n k ) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix A n, m; k forms the vertex-edge incidence matrix of a k -uniform random hypergraph H. The rank of A n, m; k can be expressed as follows. Let | C 2 | be the number of vertices of the 2-core of H, and | E ( C 2 )| the number of edges. Let m* be the value of m for which | C 2 | = | E ( C 2 )|. Then w. h. p. for m < m * the rank of A n, m; k is asymptotic to m, and for m ≥ m * the rank is asymptotic to m – | E ( C 2 )| + | C 2 |. In addition, assign i. i. d. U [0, 1] weights X i, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X ( S ) = ∑ j ∊ S X j. Define a basis as a set of n – 1 ( k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1. 202.

Details