(SEM VII) THEORY EXAMINATION 2023-24 OPTIMIZATION IN MACHINE LEARNING

SECTION A – Very Short Answer Type (2 × 10 = 20)

a) Role of Convexity in Optimization

Convexity ensures that any local minimum is also a global minimum. This property simplifies optimization because algorithms are guaranteed to converge to the optimal solution without getting trapped in local minima.

b) Real-World Applications of Convex Optimization

Convex optimization is widely used in:

Machine learning (regularized regression, SVMs)

Signal processing (noise removal)

Finance (portfolio optimization)

Network optimization (routing and bandwidth allocation)

c) Nesterov’s Acceleration in Convex Optimization

Nesterov’s accelerated gradient method improves convergence speed by using a momentum term, achieving a faster rate of O(1/k2)O(1/k^2)O(1/k2) compared to standard gradient descent.

d) Moreau–Yosida Regularization

Moreau–Yosida regularization smooths non-smooth functions by approximating them with a 

differentiable surrogate, making gradient-based optimization feasible.

e) Regularization Process

Regularization adds a penalty term to the objective function to prevent overfitting, control model complexity, and improve generalization.

f) Dual Decomposition

Dual decomposition breaks a large optimization problem into smaller subproblems using Lagrange multipliers, enabling parallel and distributed optimization.

g) Douglas–Rachford Splitting

This method handles complex constraints by splitting them into simpler subproblems and solving them iteratively, ensuring convergence in convex settings.

h) Navigating Saddle Points

Optimization algorithms escape saddle points using:

Momentum methods

Random noise (e.g., Langevin dynamics)

Second-order information

i) Implications for Convergence

Efficient optimization algorithms improve:

Faster convergence

Stability

Reduced computational cost

j) Impact of Optimization Landscape

The geometry of the landscape (convex, non-convex, smoothness) determines the choice of algorithm, step size, and convergence guarantees.

SECTION B – Long Answer Type (Attempt Any Three)

2(a) Linear Programming vs SOCP vs SDP

Linear Programming (LP) involves linear objectives and constraints and is computationally efficient.
Example: Resource allocation problems.

Second-Order Cone Programming (SOCP) extends LP by allowing quadratic constraints.
Example: Robust portfolio optimization.

Semidefinite Programming (SDP) involves matrix variables and positive semidefinite constraints.
Example: Control systems and graph partitioning.

Comparison Summary:
LP < SOCP < SDP in expressive power and computational complexity.

2(b) Duality in Convex Optimization

Duality provides a way to analyze optimization problems by converting the primal problem into a dual 

problem.
Strong duality holds under Slater’s condition, meaning optimal primal and dual values coincide.

Duality offers:

Lower bounds on solutions

Sensitivity analysis

Efficient distributed optimization

2(c) Mirror Descent vs Gradient Descent

Gradient descent updates parameters in Euclidean space, while mirror descent adapts updates using a geometry-aware distance function.

Advantages of Mirror Descent:

Works well in high-dimensional and constrained spaces

Effective for sparse optimization

Example: Online learning and large-scale NLP models.

2(d) Augmented Lagrangian vs ADMM

Augmented Lagrangian methods penalize constraint violations strongly, while ADMM splits variables and solves them alternately.

ADMM is preferred when:

Problems are large-scale

Distributed computation is required

2(e) Polyak–Juditsky Averaging

This technique averages SGD iterates to reduce variance and improve convergence stability.

In deep learning, it:

Smoothens noisy gradients

Enhances generalization

Accelerates convergence

SECTION C – Descriptive Answer Type

3(a) Karush–Kuhn–Tucker (KKT) Conditions

KKT conditions define optimality in constrained convex optimization.

They include:

Primal feasibility

Dual feasibility

Complementary slackness

Stationarity

Example:
In constrained regression, KKT conditions determine optimal coefficients while respecting constraints.

4(a) Frank–Wolfe Method

The Frank–Wolfe algorithm is used for constrained optimization without projection steps.

Advantages:

Low memory usage

Suitable for large-scale problems

Applications:
Matrix completion and sparse learning problems.

5(b) Proximal Gradient Methods

Proximal gradient methods extend gradient descent to handle non-smooth objectives.

They are widely used in:

LASSO regression

Sparse neural networks

6(b) Douglas–Rachford Splitting

This algorithm alternates between proximal operators and converges under convexity assumptions.

Effective in:

Signal reconstruction

Image processing

7(a) Langevin Dynamics in Bayesian Inference

Langevin dynamics adds noise to gradient updates, enabling:

Escaping saddle points

Efficient sampling

It is widely used in Bayesian deep learning and probabilistic modeling.