Timezone: »
Poster
Minimizing Quadratic Functions in Constant Time
Kohei Hayashi · Yuichi Yoshida
A sampling-based optimization method for quadratic functions is proposed. Our method approximately solves the following $n$-dimensional quadratic minimization problem in constant time, which is independent of $n$: $z^*=\min_{\bv \in \bbR^n}\bracket{\bv}{A \bv} + n\bracket{\bv}{\diag(\bd)\bv} + n\bracket{\bb}{\bv}$, where $A \in \bbR^{n \times n}$ is a matrix and $\bd,\bb \in \bbR^n$ are vectors. Our theoretical analysis specifies the number of samples $k(\delta, \epsilon)$ such that the approximated solution $z$ satisfies $|z - z^*| = O(\epsilon n^2)$ with probability $1-\delta$. The empirical performance (accuracy and runtime) is positively confirmed by numerical experiments.
Author Information
Kohei Hayashi (AIST)
Yuichi Yoshida (NII)
More from the Same Authors
-
2023 Poster: A Batch-to-Online Transformation under Random-Order Model »
Jing Dong · Yuichi Yoshida -
2022 Poster: Average Sensitivity of Euclidean k-Clustering »
Yuichi Yoshida · Shinji Ito -
2020 Poster: Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits »
Shinji Ito · Shuichi Hirahara · Tasuku Soma · Yuichi Yoshida -
2020 Spotlight: Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits »
Shinji Ito · Shuichi Hirahara · Tasuku Soma · Yuichi Yoshida -
2019 Poster: Einconv: Exploring Unexplored Tensor Network Decompositions for Convolutional Neural Networks »
Kohei Hayashi · Taiki Yamaguchi · Yohei Sugawara · Shin-ichi Maeda -
2017 Poster: Fitting Low-Rank Tensors in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2017 Spotlight: Fitting Low-Rank Tensors in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2017 Poster: On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm »
Masaaki Imaizumi · Takanori Maehara · Kohei Hayashi -
2015 Poster: A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice »
Tasuku Soma · Yuichi Yoshida -
2015 Poster: Monotone k-Submodular Function Maximization with Size Constraints »
Naoto Ohsaka · Yuichi Yoshida -
2013 Poster: Factorized Asymptotic Bayesian Inference for Latent Feature Models »
Kohei Hayashi · Ryohei Fujimaki -
2012 Poster: Weighted Likelihood Policy Search with Model Selection »
Tsuyoshi Ueno · Yoshinobu Kawahara · Kohei Hayashi · Takashi Washio -
2011 Poster: Statistical Performance of Convex Tensor Decomposition »
Ryota Tomioka · Taiji Suzuki · Kohei Hayashi · Hisashi Kashima