Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere

Abstract: 

Unit sphere-constrained quadratic optimization has been studied extensively over the past decades. While state-of-art algorithms for solving this problem often rely on relaxation or approximation techniques, there has been little research into scalable first-order methods that tackle the problem in its original form. These first-order methods are often more well-suited for the big data setting. In this paper, we provide a novel analysis of the simple projected gradient descent method for minimizing a quadratic over a sphere. When the gradient step size is sufficiently small, we show that convergence is locally linear and provide a closed-form expression for the rate. Moreover, a careful selection of the step size can stimulate convergence to the global solution while preventing convergence to local minima.

up
0 users have voted:

Paper Details

Authors:
Trung Vu, Raviv Raich, Xiao Fu
Submitted On:
26 October 2019 - 2:40pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Trung Vu
Paper Code:
MLSP-L6.2
Document Year:
2019
Cite

Document Files

MLSP2019.pdf

(100)

Subscribe

[1] Trung Vu, Raviv Raich, Xiao Fu, "On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere", IEEE SigPort, 2019. [Online]. Available: http://sigport.org/4897. Accessed: Sep. 27, 2020.
@article{4897-19,
url = {http://sigport.org/4897},
author = {Trung Vu; Raviv Raich; Xiao Fu },
publisher = {IEEE SigPort},
title = {On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere},
year = {2019} }
TY - EJOUR
T1 - On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere
AU - Trung Vu; Raviv Raich; Xiao Fu
PY - 2019
PB - IEEE SigPort
UR - http://sigport.org/4897
ER -
Trung Vu, Raviv Raich, Xiao Fu. (2019). On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere. IEEE SigPort. http://sigport.org/4897
Trung Vu, Raviv Raich, Xiao Fu, 2019. On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere. Available at: http://sigport.org/4897.
Trung Vu, Raviv Raich, Xiao Fu. (2019). "On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere." Web.
1. Trung Vu, Raviv Raich, Xiao Fu. On Convergence of Projected Gradient Descent for Minimizing a Large Scale Quadratic over the Unit Sphere [Internet]. IEEE SigPort; 2019. Available from : http://sigport.org/4897