English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider a new and general online resource allocation problem, where thegoal is to maximize a function of a positive semidefinite (PSD) matrix with ascalar budget constraint. The problem data arrives online, and the algorithmneeds to make an irrevocable decision at each step. Of particular interest areclassic experiment design problems in the online setting, with the algorithmdeciding whether to allocate budget to each experiment as new experimentsbecome available sequentially.  We analyze two greedy primal-dual algorithms and provide bounds on theircompetitive ratios. Our analysis relies on a smooth surrogate of the objectivefunction that needs to satisfy a new diminishing returns (PSD-DR) property(that its gradient is order-reversing with respect to the PSD cone). Using therepresentation for monotone maps on the PSD cone given by L\"owner's theorem,we obtain a convex parametrization of the family of functions satisfyingPSD-DR. We then formulate a convex optimization problem to directly optimizeour competitive ratio bound over this set. This design problem can be solvedoffline before the data start arriving. The online algorithm that uses thedesigned smoothing is tailored to the given cost function, and enjoys acompetitive ratio at least as good as our optimized bound. We provide examplesof computing the smooth surrogate for D-optimal and A-optimal experimentdesign, and demonstrate the performance of the custom-designed algorithm.

Competitive Online Algorithms for Resource Allocation over the Positive Semidefinite Cone