A unified analysis of convex and non‑convex ‑ball projection problems

Area of Science:

• Statistics
• Machine Learning
• Optimization

Background:

• Projection onto p-norm balls is fundamental in statistics and machine learning.
• Existing algorithms are limited, primarily to L2 and L-infinity norm balls.
• Scalable methods for general p-norm projections are needed.

Purpose of the Study:

• Introduce novel, scalable projection algorithms for general p-norm balls.
• Address limitations in current projection methodologies.
• Provide practical solutions for machine learning applications.

Main Methods:

• For L1-norm balls, a dual Newton method is used to solve the univariate Lagrangian dual.
• For Lp-norm balls (p>2), a bisection approach is developed, demonstrating a small duality gap even in non-convex cases.
• Algorithms are designed for scalability and computational efficiency.

Main Results:

• Novel algorithms for projecting onto general p-norm balls are presented.
• Theoretical and empirical evidence supports the efficiency and accuracy of the proposed methods.
• The methods achieve zero or small duality gaps in non-convex scenarios.

Conclusions:

• The developed methods offer scalable and efficient solutions for projections onto general p-norm balls.
• These algorithms are applicable to large-scale problems such as regularized multi-task learning and compressed sensing.
• Publicly available code facilitates the adoption and further research in this area.