A near-optimal algorithm for approximating the John Ellipsoid

被引：0

作者：

Cohen, Michael B. ^{[1
]}

Cousins, Ben ^{[2
]}

Lee, Yin Tat ^{[3
]}

Yang, Xin ^{[3
]}

机构：

[1] MIT, Cambridge, MA 02139 USA

[2] Columbia Univ, New York, NY 10027 USA

[3] Univ Washington, Seattle, WA 98195 USA

来源：

CONFERENCE ON LEARNING THEORY, VOL 99 | 2019年 / 99卷

关键词：

John Ellipsoid; fixed point method; optimal design; HIT-AND-RUN; VOLUME; COMPUTATION; COMPLEXITY; MODEL;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. Experimental results suggest that our algorithm significantly outperforms existing algorithms. We also provide the MATLAB code for further research.

引用

页数：25

共 50 条

[21] A heuristic algorithm for designing near-optimal mobile agent itineraries
Gavalas, D
JOURNAL OF COMMUNICATIONS AND NETWORKS, 2006, 8 (01) : 123 - 131
[22] On a near-optimal and efficient algorithm for the sparse pooled data problem
Hahn-klimroth, Max
van der Hofstad, Remco
Mueller, Noela
Riddlesden, Connor
BERNOULLI, 2025, 31 (02) : 1579 - 1605
[23] Near-optimal Solar Sail trajectories generated by a genetic algorithm
Rauwolf, GA
Friedlander, A
ASTRODYNAMICS 1999, PTS 1-3, 2000, 103 : 489 - 505
[24] MULTIITEM GROUPING ALGORITHM YIELDING NEAR-OPTIMAL LOGISTICS COST
BUFFA, FP
MUNN, JR
DECISION SCIENCES, 1990, 21 (01) : 14 - 34
[25] Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
Kleinberg, Robert
Leyton-Brown, Kevin
Lucier, Brendan
Graham, Devon
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), 2019, 32
[26] Use of a genetic algorithm in the search for a near-optimal shielding design
Kim, Byeong Soo
Moon, Joo Hyun
ANNALS OF NUCLEAR ENERGY, 2010, 37 (02) : 120 - 129
[27] Near-optimal approximation algorithm for simultaneous MAX-CUT
Bhangale, Amey
Khot, Subhash
Kopparty, Swastik
Sachdeva, Sushant
Thiruvenkatachari, Devanathan
SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 1407 - 1425
[28] A near-optimal routing and dimensioning algorithm for dynamic WDM rings
Vallejos, Reinaldo
Beghelli, Alejandra
OPTICAL FIBER TECHNOLOGY, 2009, 15 (5-6) : 420 - 424
[29] Near-Optimal MIMO Detection Algorithm with Low and Fixed Complexity
Kim, Hyunsub
Kim, Jaeseok
2015 IEEE INTERNATIONAL SYMPOSIUM ON CONSUMER ELECTRONICS (ISCE), 2015,
[30] A near-optimal algorithm for differentially-private principal components
Chaudhuri, Kamalika
Sarwate, Anand D.
Sinha, Kaushik
Journal of Machine Learning Research, 2013, 14 : 2905 - 2943

← 1 2 3 4 5 →