What has changed in Machine Learning in the past 25 years? You may not care about this question. You may even not realize that Machine Learning as a technical and scientific field is older than 25 years. But I do care about this question. I care because I got a PhD in Machine Learning in 1990.

In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving such non-smooth optimization problems is $O(1/\epsilon)$ without any assumption on the strong convexity. In this work, we will show that the proposed HOPS achieved a lower iteration complexity of $\widetilde O(1/\epsilon^{1-\theta})$\footnote{$\widetilde O()$ suppresses a logarithmic factor.} with $\theta\in(0,1]$ capturing the local sharpness of the objective function around the optimal solutions. To the best of our knowledge, this is the lowest iteration complexity achieved so far for the considered non-smooth optimization problems without strong convexity assumption. The HOPS algorithm employs Nesterov's smoothing technique and Nesterov's accelerated gradient method and runs in stages, which gradually decreases the smoothing parameter in a stage-wise manner until it yields a sufficiently good approximation of the original function. We show that HOPS enjoys a linear convergence for many well-known non-smooth problems (e.g., empirical risk minimization with a piece-wise linear loss function and $\ell_1$ norm regularizer, finding a point in a polyhedron, cone programming, etc). Experimental results verify the effectiveness of HOPS in comparison with Nesterov's smoothing algorithm and the primal-dual style of first-order methods.

Determining the optimal size and orientation of small-scale residential based PV arrays will become increasingly complex in the future smart grid environment with the introduction of smart meters and dynamic tariffs. However consumers can leverage the availability of smart meter data to conduct a more detailed exploration of PV investment options for their particular circumstances. In this paper, an optimization method for PV orientation and sizing is proposed whereby maximizing the PV investment value is set as the defining objective. Solar insolation and PV array models are described to form the basis of the PV array optimization strategy. A constrained particle swarm optimization algorithm is selected due to its strong performance in non-linear applications. The optimization algorithm is applied to real-world metered data to quantify the possible investment value of a PV installation under different energy retailers and tariff structures. The arrangement with the highest value is determined to enable prospective small-scale PV investors to select the most cost-effective system.

Many machine learning algorithms require precise estimates of covariance matrices. The sample covariance matrix performs poorly in high-dimensional settings, which has stimulated the development of alternative methods, the majority based on factor models and shrinkage. Recent work of Ledoit and Wolf has extended the shrinkage framework to Nonlinear Shrinkage (NLS), a more powerful covariance estimator based on Random Matrix Theory. Our contribution shows that, contrary to claims in the literature, cross-validation based covariance matrix estimation (CVC) yields comparable performance at strongly reduced complexity and runtime. On two real world data sets, we show that the CVC estimator yields superior results than competing shrinkage and factor based methods.

Sparse coding, which represents a data point as a sparse reconstruction code with regard to a dictionary, has been a popular data representation method. Meanwhile, in database retrieval problems, learning the ranking scores from data points plays an important role. Up to now, these two problems have always been considered separately, assuming that data coding and ranking are two independent and irrelevant problems. However, is there any internal relationship between sparse coding and ranking score learning? If yes, how to explore and make use of this internal relationship? In this paper, we try to answer these questions by developing the first joint sparse coding and ranking score learning algorithm. To explore the local distribution in the sparse code space, and also to bridge coding and ranking problems, we assume that in the neighborhood of each data point, the ranking scores can be approximated from the corresponding sparse codes by a local linear function. By considering the local approximation error of ranking scores, the reconstruction error and sparsity of sparse coding, and the query information provided by the user, we construct a unified objective function for learning of sparse codes, the dictionary and ranking scores. We further develop an iterative algorithm to solve this optimization problem.

What has changed in Machine Learning in the past 25 years? You may not care about this question. You may even not realize that Machine Learning as a technical and scientific field is older than 25 years. But I do care about this question. I care because I got a PhD in Machine Learning in 1990.

In this paper we study a broad class of structured nonlinear programming (SNLP) problems. In particular, we first establish the first-order optimality conditions for them. Then we propose sequential convex programming (SCP) methods for solving them in which each iteration is obtained by solving a convex programming problem exactly or inexactly. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the methods is a KKT point of the SNLP problems. In addition, we propose a variant of the exact SCP method for SNLP in which nonmonotone scheme and "local" Lipschitz constants of the associated functions are used. And a similar convergence result as mentioned above is established.

A novel approach termed \emph{stochastic truncated amplitude flow} (STAF) is developed to reconstruct an unknown $n$-dimensional real-/complex-valued signal $\bm{x}$ from $m$ `phaseless' quadratic equations of the form $\psi_i=|\langle\bm{a}_i,\bm{x}\rangle|$. This problem, also known as phase retrieval from magnitude-only information, is \emph{NP-hard} in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) A series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that is useful when $n$ is large. When $\{\bm{a}_i\}_{i=1}^m$ are independent Gaussian, STAF provably recovers exactly any $\bm{x}\in\mathbb{R}^n$ exponentially fast based on order of $n$ quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian $\{\bm{a}_i\}$ vectors demonstrate that STAF empirically reconstructs any $\bm{x}\in\mathbb{R}^n$ exactly from about $2.3n$ magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations $m=2n-1$. Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

Supervised dimensionality reduction has emerged as an important theme in the last decade. Despite the plethora of models and formulations, there is a lack of a simple model which aims to project the set of patterns into a space defined by the classes (or categories). To this end, we set up a model in which each class is represented as a 1D subspace of the vector space formed by the features. Assuming the set of classes does not exceed the cardinality of the features, the model results in multi-class supervised learning in which the features of each class are projected into the class subspace. Class discrimination is automatically guaranteed via the imposition of orthogonality of the 1D class sub-spaces. The resulting optimization problem - formulated as the minimization of a sum of quadratic functions on a Stiefel manifold - while being non-convex (due to the constraints), nevertheless has a structure for which we can identify when we have reached a global minimum. After formulating a version with standard inner products, we extend the formulation to reproducing kernel Hilbert spaces in a straightforward manner. The optimization approach also extends in a similar fashion to the kernel version. Results and comparisons with the multi-class Fisher linear (and kernel) discriminants and principal component analysis (linear and kernel) showcase the relative merits of this approach to dimensionality reduction.

We provide tight upper and lower bounds on the complexity of minimizing the average of $m$ convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.