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 条

[31] Improved layered MIMO detection algorithm with near-optimal performance
Alimohammad, A.
Fard, S. F.
Cockburn, B. F.
ELECTRONICS LETTERS, 2009, 45 (13) : 675 - 677
[32] A Near-Optimal Algorithm for Debiasing Trained Machine Learning Models
Alabdulmohsin, Ibrahim
Lucic, Mario
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 34 (NEURIPS 2021), 2021, 34
[33] 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
[34] Performance bounds analyzing on a near-optimal algorithm of Qm || Cmax
Li Dong
Yang Dan
Deng Lin
Wang Shi-long
Proceedings of 2005 Chinese Control and Decision Conference, Vols 1 and 2, 2005, : 1812 - 1814
[35] A NEAR-OPTIMAL HEURISTIC ALGORITHM FOR SINGLE-ROW ROUTING
LIU, LC
DU, HC
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) : 603 - 608
[36] An Optimal Algorithm for the Stochastic Bandits While Knowing the Near-Optimal Mean Reward
Yang, Shangdong
Gao, Yang
IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, 2021, 32 (05) : 2285 - 2291
[37] Barriers to Near-Optimal Equilibria
Roughgarden, Tim
2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, : 71 - 80
[38] Universal Near-Optimal Feedbacks
S. Nobakhtian
R. J. Stern
Journal of Optimization Theory and Applications, 2000, 107 : 89 - 122
[39] A Near-Optimal Randomized Algorithm for Uplink Resource Allocation in OFDMA Systems
Yang, Yang
Nam, Changwon
Shroff, Ness B.
2014 12TH INTERNATIONAL SYMPOSIUM ON MODELING AND OPTIMIZATION IN MOBILE, AD HOC, AND WIRELESS NETWORKS (WIOPT), 2014, : 218 - 225
[40] DEVELOPMENT AND VALIDATION OF A PREDICTIVE ALGORITHM FOR NEAR-OPTIMAL CONTROL OF VENETIAN BLINDS
Karizi, Nasim
Reddy, T. Agami
Dasgupta, Partha
PROCEEDINGS OF THE ASME INTERNATIONAL MECHANICAL ENGINEERING CONGRESS AND EXPOSITION, 2016, VOL. 6B, 2017,

← 1 2 3 4 5 →