Recall that we say that a function f is convex if the domain of f is a convex set and

f(x + (1 )y) f(x) + (1 )f(y), for all x,y in the domain of f, 0 1.

And strictly convex if

f(x + (1 )y) < f(x) + (1 )f(y), for all x =6 y in the domain of f, 0 < < 1.

Prove the following assertions.

1. The affine function f(x) = ax + b is convex, where a,b and x are scalars.
2. If multiple functions f_n(x) are convex over a fixed domain, then their sum g(x) = ^P_n f_n(x) is convex over the same domain.
3. Take f,g : R R to be convex functions and g to be increasing. Then g f is also convex.

Note: A function g is increasing if a b g(a) g(b). An example of a convex and increasing function is exp(x),x R.

4. If f : R R is convex, then g : R^D R, where g(x) := f(w^>x + b), is also convex. Here, w is a constant vector in R^D, b is a constant in R and x R^D.
5. Let f : R^D R be strictly convex. Let x^? R^D be a global minimizer of f. Show that this global minimizer is unique. Hint: Do a proof by contradiction.

1 Extension of Logistic Regression to Multi-Class Classification

Suppose we have a classification dataset with N data example pairs {x_n,y_n}, n [1,N], and y_n is a categorical variable over K categories, y_n {1,2,,K}. We wish to fit a linear model in a similar spirit to logistic regression, and we will use the softmax function to link the linear inputs to the categorical output, instead of the logistic function.

We will have K sets of parameters w_k, and define and compute the probability distribution of the output as follows,

.

Note that we indeed have a probability distribution, as. To make the model identifiable, we will fix w_K to 0, which means we have K1 sets of parameters to learn. As in logistic regression, we will assume that each y_n is i.i.d., i.e.,

.

1. Derive the log-likelihood for this model.
2. Derive the gradient with respect to each w_k.
3. Show that the negative of the log-likelihood is convex with respect to w_k.

2 Mixture of Linear Regression

In Project-I, you worked on a regression dataset with two or more distinct clusters. For such datasets, a mixture of linear regression models is preferred over just one linear regression model.

Consider a regression dataset with N pairs {y_n,x_n}. Similar to Gaussian mixture model (GMM), let r_n {1,2,,K} index the mixture component. Distribution of the output y_n under the k^th linear model is defined as follows:

Here, w_k is the regression parameter vector for the k^th model with w being a vector containing all w_k. Also, x.

1. Define r_n to be a binary vector of length K such that all the entries are 0 except a k^th entry, i.e., r_nk = 1, implying that x_n is assigned to the k^th Rewrite the likelihood p(y_n|x_n,w,r_n) in terms of r_nk.
2. Write the expression for the joint distribution p(y|X,w,r) where r is the set of all r₁,r₂,,r_N.
3. Assume that r_n follows a multinomial distribution p(r_n = k|) = _k, with = [₁,₂,,_K]. Derive the marginal distribution p(y_n|x_n,w,) obtained after marginalizing r_n
4. Write the expression for the maximum likelihood estimator L(w,) := logp(y|X,w,) in terms of data y and X, and parameters w and .
5. Is L jointly-convex with respect to w and ? Is the model identifiable? Prove your answers.

2