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/

Zendy Plus

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

Zendy Tools

Zendy Open

Given a separation oracle for a convex set $K \subset \mathbb{R}^n$ that iscontained in a box of radius $R$, the goal is to either compute a point in $K$or prove that $K$ does not contain a ball of radius $\epsilon$. We propose anew cutting plane algorithm that uses an optimal $O(n \log (\kappa))$evaluations of the oracle and an additional $O(n^2)$ time per evaluation, where$\kappa = nR/\epsilon$.  $\bullet$ This improves upon Vaidya's $O( \text{SO} \cdot n \log (\kappa) +n^{\omega+1} \log (\kappa))$ time algorithm [Vaidya, FOCS 1989a] in terms ofpolynomial dependence on $n$, where $\omega < 2.373$ is the exponent of matrixmultiplication and $\text{SO}$ is the time for oracle evaluation.  $\bullet$ This improves upon Lee-Sidford-Wong's $O( \text{SO} \cdot n \log(\kappa) + n^3 \log^{O(1)} (\kappa))$ time algorithm [Lee, Sidford and Wong,FOCS 2015] in terms of dependence on $\kappa$.  For many important applications in economics, $\kappa = \Omega(\exp(n))$ andthis leads to a significant difference between $\log(\kappa)$ and$\mathrm{poly}(\log (\kappa))$. We also provide evidence that the $n^2$ timeper evaluation cannot be improved and thus our running time is optimal.  A bottleneck of previous cutting plane methods is to compute leverage scores,a measure of the relative importance of past constraints. Our result isachieved by a novel multi-layered data structure for leverage scoremaintenance, which is a sophisticated combination of diverse techniques such asrandom projection, batched low-rank update, inverse maintenance, polynomialinterpolation, and fast rectangular matrix multiplication. Interestingly, ourmethod requires a combination of different fast rectangular matrixmultiplication algorithms.

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications