A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization

C. Josz; Y. Ouyang; R. Y. Zhang; J. Lavaei; S. Sojoudi

A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization

C. Josz, Y. Ouyang, R. Y. Zhang, J. Lavaei, S. Sojoudi

Research output: Contribution to journal › Conference article

Abstract

We study the set of continuous functions that admit no spurious local optima (i.e. local minima that are not global minima) which we term global functions. They satisfy various powerful properties for analyzing nonconvex and nonsmooth optimization problems. For instance, they satisfy a theorem akin to the fundamental uniform limit theorem in the analysis regarding continuous functions. Global functions are also endowed with useful properties regarding the composition of functions and change of variables. Using these new results, we show that a class of nonconvex and nonsmooth optimization problems arising in tensor decomposition applications are global functions. This is the first result concerning nonconvex methods for nonsmooth objective functions. Our result provides a theoretical guarantee for the widely-used `₁ norm to avoid outliers in nonconvex optimization.

Original language	English (US)
Pages (from-to)	2441-2449
Number of pages	9
Journal	Advances in Neural Information Processing Systems
Volume	2018-December
State	Published - Jan 1 2018
Externally published	Yes
Event	32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada Duration: Dec 2 2018 → Dec 8 2018

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Access to Document

Fingerprint Dive into the research topics of 'A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization'. Together they form a unique fingerprint.

Cite this

Josz, C., Ouyang, Y., Zhang, R. Y., Lavaei, J., & Sojoudi, S. (2018). A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization. Advances in Neural Information Processing Systems, 2018-December, 2441-2449.

@article{207efac498b14725af7f9b4134c2ed95,

title = "A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization",

abstract = "We study the set of continuous functions that admit no spurious local optima (i.e. local minima that are not global minima) which we term global functions. They satisfy various powerful properties for analyzing nonconvex and nonsmooth optimization problems. For instance, they satisfy a theorem akin to the fundamental uniform limit theorem in the analysis regarding continuous functions. Global functions are also endowed with useful properties regarding the composition of functions and change of variables. Using these new results, we show that a class of nonconvex and nonsmooth optimization problems arising in tensor decomposition applications are global functions. This is the first result concerning nonconvex methods for nonsmooth objective functions. Our result provides a theoretical guarantee for the widely-used `1 norm to avoid outliers in nonconvex optimization.",

author = "C. Josz and Y. Ouyang and Zhang, {R. Y.} and J. Lavaei and S. Sojoudi",

year = "2018",

month = jan,

day = "1",

language = "English (US)",

volume = "2018-December",

pages = "2441--2449",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

note = "32nd Conference on Neural Information Processing Systems, NeurIPS 2018 ; Conference date: 02-12-2018 Through 08-12-2018",

}

TY - JOUR

T1 - A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization

AU - Josz, C.

AU - Ouyang, Y.

AU - Zhang, R. Y.

AU - Lavaei, J.

AU - Sojoudi, S.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We study the set of continuous functions that admit no spurious local optima (i.e. local minima that are not global minima) which we term global functions. They satisfy various powerful properties for analyzing nonconvex and nonsmooth optimization problems. For instance, they satisfy a theorem akin to the fundamental uniform limit theorem in the analysis regarding continuous functions. Global functions are also endowed with useful properties regarding the composition of functions and change of variables. Using these new results, we show that a class of nonconvex and nonsmooth optimization problems arising in tensor decomposition applications are global functions. This is the first result concerning nonconvex methods for nonsmooth objective functions. Our result provides a theoretical guarantee for the widely-used `1 norm to avoid outliers in nonconvex optimization.

AB - We study the set of continuous functions that admit no spurious local optima (i.e. local minima that are not global minima) which we term global functions. They satisfy various powerful properties for analyzing nonconvex and nonsmooth optimization problems. For instance, they satisfy a theorem akin to the fundamental uniform limit theorem in the analysis regarding continuous functions. Global functions are also endowed with useful properties regarding the composition of functions and change of variables. Using these new results, we show that a class of nonconvex and nonsmooth optimization problems arising in tensor decomposition applications are global functions. This is the first result concerning nonconvex methods for nonsmooth objective functions. Our result provides a theoretical guarantee for the widely-used `1 norm to avoid outliers in nonconvex optimization.

UR - http://www.scopus.com/inward/record.url?scp=85064821954&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064821954&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85064821954

VL - 2018-December

SP - 2441

EP - 2449

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

SN - 1049-5258

T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018

Y2 - 2 December 2018 through 8 December 2018

ER -