Stochastic learning via optimizing the variational inequalities.

Area of Science:

• Machine Learning
• Convex Optimization
• Computational Science

Background:

• Learning problems are often framed using convex optimization, with algorithms offering theoretical convergence rates.
• A practical gap exists between theoretical convergence and actual learning speed in these algorithms.
• Existing online learning analyses may be too loose for stochastic settings.

Purpose of the Study:

• To develop a more accurate measure of learning speed in stochastic optimization.
• To propose a novel algorithm for solving variational inequalities (VI) in learning problems.
• To analyze the convergence rate of stochastic algorithms for non-smooth convex optimization.

Main Methods:

• Formulating regularized learning problems as variational inequalities (VI).
• Developing a stochastic version of the alternating direction method of multipliers (ADMM) to solve VIs.
• Defining a new VI-criterion to measure the convergence of stochastic algorithms.

Main Results:

• The proposed stochastic ADMM (SADMM) achieves an O(1/t) VI-convergence rate for l1-regularized hinge loss problems.
• This rate holds even without strong convexity and smoothness assumptions.
• SADMM demonstrates experimental performance comparable to state-of-the-art methods.

Conclusions:

• SADMM offers a tighter characterization of learning speed compared to standard online analysis.
• The O(1/t) VI-convergence rate provides a more realistic measure of practical learning efficiency.
• This work bridges the gap between theoretical convergence and practical learning speed in convex optimization.