# Sparse Text Classification with Proximal SGD

> Оптимизируем разреженный линейный классификатор для новостей:
> минимизируем cross-entropy с L1-регуляризацией.

**Команда**: Иванов А., Петрова К. (2 чел.)
**Дедлайн D1**: 21 марта 2026, 23:59 MSK

---

## Задача оптимизации

min_{W ∈ ℝ^{d×c}}  (1/n) Σᵢ CrossEntropy(W·xᵢ, yᵢ)  +  λ‖W‖₁

где:
- f(W) = (1/n) Σᵢ CrossEntropy(W·xᵢ, yᵢ)  — L-гладкая (L≈1 в batch режиме)
- g(W) = λ‖W‖₁                              — negладкая, prox-friendly
- W ∈ ℝ^{d×c} — веса классификатора (d=10000 признаков, c=4 класса)

**Метод**: Stochastic Proximal Gradient (SGD + мягкий порог)

**Baseline**: Adam без регуляризации (Kingma & Ba, 2015, arXiv:1412.6980)

## Данные / среда

- **Датасет**: AG News (120k train / 7.6k test, 4 класса)
- **Признаки**: TF-IDF, d=10000
- **Среда**: PyTorch, CPU
- **Воспроизводимость**: `pip install -r requirements.txt && python train.py`

## D1. Формализация задачи

### 1.1 Задача оптимизации

Рассматривается задача разреженной многоклассовой классификации:

min_{W ∈ ℝ^{d×c}}  F(W) = f(W) + g(W)

где:

| Символ | Определение |
|--------|-------------|
| W ∈ ℝ^{d×c} | матрица весов классификатора |
| xᵢ ∈ ℝ^d   | TF-IDF вектор i-го документа |
| yᵢ ∈ {0..3} | метка класса |
| n           | размер датасета (120 000) |
| λ = 1e-4    | коэффициент регуляризации |

**Гладкая часть**:
f(W) = (1/n) Σᵢ CrossEntropy(softmax(W·xᵢ), yᵢ)

Предположения: f является L-гладкой (L ≤ ‖X‖²/n) и выпуклой по W.

**Негладкая часть**:
g(W) = λ‖W‖₁ = λ Σⱼₖ |Wⱼₖ|

Оператор близости: prox_{αg}(W)ⱼₖ = sign(Wⱼₖ) · max(|Wⱼₖ| - αλ, 0)

### 1.2 Метод оптимизации

Stochastic Proximal Gradient (SGD шаг + prox):

W_{k+1} = prox_{αg}( W_k - α · ∇̂f(W_k) )

где ∇̂f(W_k) = мини-батч стохастический градиент (batch size = 256).

Шаг α = 0.01 (постоянный). При L-гладкости и выпуклости f:

E[F(W_K) - F*] ≤ O(1/√K)  — стохастический проксимальный GD

Базовый SGD Adam (baseline): W_{k+1} = W_k - α_t · m̂_t / (√v̂_t + ε)
(адаптивный шаг, но без регуляризации → плотные веса)

### 1.3 Данные

- **Датасет**: AG News (Zhang et al., 2015)
- **Задача**: 4-классовая классификация новостных статей
- **Метрика**: Accuracy (тест)
- **Ожидаемый результат**: Proximal SGD ≈ Adam по accuracy,
  но W имеет ~70% нулей (разреженность) → лучше интерпретируемость

min_{U∈ℝ^{m×k}, V∈ℝ^{n×k}}  Σ_{(i,j)∈Ω} (Aᵢⱼ - Uᵢ·Vⱼᵀ)²

f(U,V) = Σ_{(i,j)∈Ω} (Aᵢⱼ - Uᵢ·Vⱼᵀ)²  — негладкая (не выпуклая совместно!)
g(U,V) = 0  → обычный GD или ALS

Метод: ALS (Alternating Least Squares) или SGD по парам (Koren et al., 2009)
Baseline: SVD (numpy.linalg.svd на плотной матрице)
Датасет: MovieLens-100K (943 пользователя, 1682 фильма)

min_{θ ∈ ℝ^p}  (1/n) Σᵢ L(fθ(xᵢ), yᵢ)  +  (λ/2)‖θ‖²

f(θ) = (1/n) Σᵢ L(fθ(xᵢ), yᵢ)  — L-гладкая (при Lipschitz-гр.)
g(θ) = (λ/2)‖θ‖²              — гладкая, prox = (1/(1+αλ))·θ

Метод: SGD с momentum (Polyak heavy ball):
  v_{k+1} = β·vₖ - α·∇̂f(θₖ)
  θ_{k+1} = θₖ + vₖ₊₁